启发函数的精确度对性能的影响

4.2.1 启发函数的精确度对性能的影响

有效分支因子b*是一个刻画启发式的质量的途径。如果对于一个特殊问题，A*算法生成的总节点数为N，解的深度为d，那么b*就是深度为d的一致搜索树为了能够包括N+1个节点所必需的分支因子。因此

N+1 = 1+b*+(b*)2+…+(b*)d。

例如，如果A*算法使用52个节点在第5层找到了解，那么有效分支因子是1.92。有效分支因子可能根据问题实例发生变化，但是通常在足够难的问题中它是相当稳定的。因此，在小规模问题集合上实验地测量出b*的值，可以对研究启发式的总体有效性提供很好的指导。一个良好设计的启发式会使b*的值接近于1，允许对相当大规模的问题求解。

为了测试启发函数h1和h2，我们随机地产生了1200个八数码游戏的问题，它们的解的长度从2到24 （每个偶数值有100个例子），分别用迭代深入搜索、使用h1与h2的A*树搜索对这些问题求解。图4.8给出了每种搜索策略扩展节点的平均数和它们的有效分支因子。结果说明h2好于h1，并且远好于使用迭代深入搜索。在长度为14的解上，用h2作为启发函数的A*算法的效率比无信息的迭代深入搜索高30 000倍。

图4.8 对ITERATIVE-DEEPENING-SEARCH、以及使用h1和h2的A*算法的搜索代价和有效分支因子的比较。图中的数据是通过八数码游戏的100个实例计算的平均值，分别对应于不同长度的解

有人可能会问，h2是否总比h1好？答案是肯定的。从两个启发式的定义很容易看出来，对于任意节点n，h2(n)≥h1(n)。因此我们说h2比h1占优势。优势可以直接转化为效率：使用h2的A*算法绝不会比使用h1的A*算法扩展更多的节点（除了可能有某些节点f(n) = C*）。论证很简单。回忆一下第4.1.2节的结论，每个f(n)＜C*的节点都必将被扩展。同样可以说，每个h(n)＜C* – g(n)的节点必将被扩展。但是因为对于所有的节点h2都至少和h1一样大，每个被使用h2的A*搜索扩展的节点必定也会被使用h1的 A*所扩展，而 h1还可能引起其它节点的扩展。因此，使用值更高的启发函数总是更好的，倘若它不会过高估计耗散值而且该启发式花费的时间不是太多的话。