启发式函数对性能的影响
一种描述启发式函数质量的方法是有效分支因子$b^*$。如果针对一个特定问题，$A^*$搜索所生成的总节点数是$n$，而解的深度是$d$，那么$b^*$就是深度为$d$的均衡树要包含$n + 1$个节点所必需的分支因子。因此有:
$$
n+1=1+b^*+\left( b^* \right) ^2+\cdot \cdot \cdot +\left( b^* \right) ^d
$$
在不同的问题实例中，有效分支因子可能会发生变化，但通常对于特定特定问题的所有复杂的问题实例，它都
是相当恒定的。因此，对一小部分问题的$b^*$进行实验测量可以为启发式函数的总体有用性提供良好的指导。设计良好的启发式函数的$b^*$接近 1，算法便能以合理的计算代价求解相当大的问题。
对于一个使用给定启发式函数$h$的$A^*$剪枝，刻画其效果的一个更好方式是：有效深度，相比于真实深度的减少量$k_h$（一个常数）。这意味着相较于无信息搜索的代价$O(b^d)$，上述方法的总搜索代价为$O(b^{d-k_h})$。在魔方和$n$数码问题上的实验结果表明，这一公式可以准确地预测各种解长度范围内（至少对于大于$k_h$的解长度）的抽样问题实例的总搜索代价。
启发式函数构造
减少了对动作的限制条件的问题称为松弛问题，松弛问题的状态空间图是原始状态空间的一个超图，因为删除限制条件会导致原图中边的增加。因为松弛问题向状态空间图中添加了一些边，根据定义，原问题的任一最优解也是松弛问题的一个解；但是，如果增加的边提供了捷径，松弛问题可能有更好的解。
因此，松弛问题中最优解的代价可以作为原问题的一个可容许的启发式函数。此外，因为得到的启发式函数是松弛问题的准确代价，所以它一定满足三角不等式，因此它是一致的。
如果一个可容许的启发式函数集合$h_1,…,h_m$可以求解同一个问题，但没有一个函数明显优于其他函数，那么应该选择哪个函数？事实证明，可以通过如下定义，得到最优的启发式函数：
$$
h\left( n \right) =max\left\{ h_1\left( n \right) ,…,h_k\left( n \right) \right\}
$$
这种复合启发式函数将选择对于所讨论节点最准确的函数。因为$h_i$都是可容许的，所以$h$也是可容许的（如果$h_i$都是一致的，则$h$也是一致的）。此外，$h$优于所有组成它的启发式函数。唯一的缺点是$h(n)$的计算时间更长。
另一种选择是在每次评价时随机选择一个启发式函数，或者使用机器学习算法来预测哪个启发式函数是最优的。这样做可能会导致启发式函数失去一致性（即使每个$h_i$都是一致的），但在实践中，它通常能更快地求解问题。
模式数据库的思想是为每个可能的子问题存储准确的解代价。然后，通过在数据库中查找相应的子问题，为搜索过程中遇到的每个状态计算一个可容许的启发式函数。数据库本身是从目标状态反向搜索并记录所遇到的每个新模式的代价来构建的；这一搜索的开销将分摊到后续的问题实例中，因此如果需要求解很多问题，那么这种方法是有意义的。
对一些最优路径代价进行预计算，虽然预计算可能相当耗时，但只需完成一次预计算，就可以摊销数十亿用户的搜索请求。更好的方法是从顶点中选择一些（也许 10 个或 20 个）地标点。然后，对于图中每个地标$L$和每个其他顶点$v$，计算并存储$C^*(v, L)$，即从$v$到$L$的最优路径的准确代价。可以很容易地创建出一个高效的（尽管是不可容许的）启发式函数：在所有地标中，从当前节点到地标然后到目标节点代价的最小值为:
$$
h_L\left( n \right) =\underset{L\in Landmarks}{\min}C^*\left( n,L \right) +C^*\left( n,goal \right)
$$
如果最优路径刚好经过一个地标，这个启发式函数将是准确的；否则，这个启发式函数就是不可容许的——它高估了到目标的代价。在$A^*$搜索中，如果启发式函数是准确的，那么一旦到达一个位于最优路径上的节点，此后所扩展的每个节点都将位于最优路径上。
$h_L(n)$是高效的，但不是可容许的。只要稍加注意，就可以提出一种既高效又可容许的启发式函数：
$$
h_{DH}\left( n \right) =\underset{L\in Landmarks}{\max}\left| C^*\left( n,L \right) -C^*\left( n,goal \right) \right|
$$
这被称为差分启发式函数，可以把它理解为在比目标还要远的某个位置设置一个地标点。如果目标恰好在从$n$到该地标点的最优路径上，那么考虑从$n$到$L$的完整路径，然后减去这条路径的最后一部分，即从$goal$到$L$，即可得到从$n$到$goal$的这段路径的准确代价。如果目标稍微偏离到地标的最优路径，启发式函数将是不准确的，但仍然是可容许的。
地标在寻径问题上尤其有效，这是由世界上道路的布局方式导致的：许多交通运输实际上都是在地标之间穿行，所以土木工程师在这些路线上修建最宽、最快的道路；地标式搜索可以更轻松地复原这些路线。
可学习的启发式函数
学习算法可以从经验中学习，以避免探索毫无希望的子树。学习的目标是对计算开销和路径代价进行权衡，以最小化求解问题的总代价。大多数学习到的都是启发式函数的一个不完美的近似，因此存在启发式函数不可容许的风险。这必然导致算法需要在学习时间、搜索运行时间和解的代价之间进行权衡。
如果除了原始状态描述外，还提供与预测启发式函数值相关的状态特征（$feature$），那么一些机器学习技术将表现得更好。
