最小化总的估计解耗散

4.1.2 A*搜索：最小化总的估计解耗散

最佳优先搜索的最广为人知的形式称为A*搜索（发音为“A星搜索”）。它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：

f(n) = g(n)+h(n)

因为g(n)给出了从起始节点到节点n的路径耗散，而h(n)是从节点n到目标节点的最低耗散路径的估计耗散值，因此

f(n) = 经过节点n的最低耗散解的估计耗散

这样，如果我们想要找到最低耗散解，首先尝试找到g(n)+h(n)值最小的节点是合理的。可以发现这个策略不只是合理的：倘若启发函数h(n)满足一定的条件，A*搜索既是完备的也是最优的。

如果把 A*搜索用于 TREE-SEARCH，它的最优性是能够直接分析的。在这种情况下，如果 h(n)是一个可采纳启发式——也就是说，倘若h(n)从不会过高估计到达目标的耗散——那么A*算法是最优的。可采纳启发式天生是最优的，因为它们认为求解问题的耗散是低于实际耗散的。因为g(n)是到达节点n的确切耗散，我们得到一个直接的结论：f(n)永远不会高估经过节点n的解的实际耗散。

一个可采纳启发式的明显例子就是我们用来寻找到达Bucharest的路径的直线距离hSLD。直线距离是可采纳启发式，因为任何两点之间的最短路径是这两点之间的直线距离，所以用直线距离不会高估。在图4.3中，我们显示了A*树搜索到达Bucharest的过程。g值从图3.2的单步耗散计算得到，hSLD值在图4.1中给出。特别应该注意的是，Bucharest首先在步骤(e)的边缘节点集里出现，但是在这一步扩展中并没有选它，因为它的f耗散（450）比Pitesti的f耗散（417）高。换一种说法就是可能有一个经过Pitesti的解的耗散低至417，所以算法将不会满足于耗散值为450的解。从这个例子，我们可以抽取出一个广义的证明，即如果h(n)是可采纳的，那么使用TREE-SEARCH的A*算法是最优的。假设一个非最优的目标节点G2出现在边缘中，并且令最优解的耗散为C*。那么，由于G2不是最优的，而且h(G2) = 0（对于任何目标节点都为真），我们知道

f(G2) = g(G2)+h(G2) = g(G2)＞C*

图4.3 使用A*搜索，寻找前往Bucharest的最短路径的几个阶段。节点都用f=g+h标明。h值是来自图4.1的到Bucharest的直线距离

现在考虑一个处于最优解路径上的边缘节点 n ——例如，在前面图中例子里 Pitesti。（如果解存在的话，总是存在这样一个节点的。）如果h(n)没有高估完成解路径的耗散，那么我们知道

f(n) = g(n)+h(n)≤C*

现在我们已经证明了f(n)≤C*＜f(G2)，因此G2将不会被扩展，A*算法必然返回最优解。

如果我们用图3.19中的GRAPH-SEARCH算法替代TREE-SEARCH，那么这个证明就不成立了。因为如果最优路径不是第一个生成的，则有可能因为有重复状态而被丢弃，而被返回的是非最优解。（参见习题4.4。）有两条途径可以解决这个问题。第一个解决方案是扩展GRAPH-SEARCH算法使它丢弃到达同一节点的两条路径中耗散大的那条。（参见第3.5节中的讨论。）虽然额外的记录比较杂乱，但是确实能保证得到最优解。第二个解决方案是保证到达任何重复状态的最优路径总是第一条被追随的——如同代价一致搜索的情况。如果我们对h(n)强加上一个额外要求，即一致性（也称为单调性），就会保持这个性质。我们称启发式h(n)是一致的，如果对于每个节点n和通过任何行动a生成的n的每个后继节点n '，从节点n到达目标的估计耗散值不大于从n到n ' 的单步耗散与从n ' 到达目标的估计耗散值之和：

h(n)≤c(n, a, n ')+h(n ')

这是一般的三角不等式的一种形式，它保证了三角形中任何一条边的长度不大于另两条边之和。这里，三角形是由n，n ' 和离n最近的目标节点构成的。很容易证明（习题4.7）每个一致的启发式都是可采纳的。一致性最重要的结果是：如果h(n)是一致的，那么使用GRAPH-SEARCH的A*算法是最优的。

虽然一致性是比可采纳性更严格的要求，要编制满足可采纳性的但可能不一致的启发式仍然需要艰苦的工作。所有本章中我们讨论的可采纳启发式都是一致的。例如，考虑 hSLD。我们知道当每边都用直线距离来度量时是满足一般的三角形不等式的，而且n和n ' 之间的直线距离不超过c(n, a, n ')。因此，hSLD是一个一致的启发式。

一致性的另一个重要结论是：如果h(n)是一致的，那么沿着任何路径的f(n)值是非递减的。证明是直接由一致性的定义得到的。假设n ' 是节点n的后继节点；那么对于某个行动a，有g(n ') = g(n)+c(n, a, n ')，于是我们得到

f(n ') = g(n ')+h(n ') = g(n)+c(n, a, n ')+h(n ')≥g(n)+h(n) = f(n)。

它的必然结果是使用GRAPH-SEARCH的A*算法按照非递减的f(n)的顺序扩展的节点序列。因此，最先被选中扩展的目标节点就是最优解，因为所有后来的节点耗散都不小于它。

f耗散值沿着任何路径都是非递减的事实也意味着我们可以在状态空间上绘制等值线。图4.4 给出了一个例子。在标称400的等值线内，所有节点的f(n)值都小于等于400，依此类推。那么，因为A*算法扩展的是f耗散值最低的节点，我们可以看到A*搜索由起始节点散开，以同心带状增长f耗散值的方式添加节点。

图4.4 罗马尼亚地图显示的等值线f=380，f=400和f=420，以Arad为初始状态。在给定的等值线内的节点的f耗散值小于等于线上的值

使用代价一致搜索（A*搜索中令h(n) = 0），同心带是以起始状态为圆心的“圆形”。使用更精确的启发式，同心带将向目标节点方向拉伸，并且在最优路径的周围汇聚变窄。如果C*是最优解路径的耗散值，那么我们可以得到：

• A*算法扩展所有f(n)＜C*的节点。

• A*算法在扩展目标节点前可能会扩展一些正好处于“目标等值线”（f(n) = C*）上的节点。

直观地看，最先找到的解一定是最优的，因为所有随后的等值线中的目标节点f耗散值都要更高，因此g耗散值也会更高（因为目标节点的h(n) = 0）。直观地看，A*搜索显然也是完备的。在我们添加不断增长的f值的同心带时，我们最终会到达一条同心带，它对应的f值和到达目标状态的路径耗散值相等。[10]

注意A*算法不扩展f(n)＞C*的节点——例如，图4.3中Timisoara尽管是根节点的子节点，也没有被扩展。我们说在Timisoara下的子树被剪枝了；因为hSLD是可采纳的，搜索算法可以安全地忽略这棵子树，仍然能保证最优性。剪枝这个概念——不需要检验就直接把它们的可能性从考虑中排除——在AI的很多领域中都是很重要的。

最后一个观察到的事实是，在这类最优算法中——从根节点开始扩展搜索路径的算法——A*算法对于任何给定的启发函数都是效率最优的。就是说，没有其它的最优算法保证扩展的节点少于 A*算法（除了可能搜索f(n) = C*的节点）。这是因为任何不扩展所有f(n)＜C*的节点的算法都要冒漏掉最优解的风险。

A*搜索在所有此类算法中是完备的、最优的，也是效率最优的，这很令人满意。不幸的是，这不意味着A*算法是对我们全部的搜索需要的答案。困难的地方在于，对于大多数问题而言，在搜索空间中处于目标等值线内的节点数量仍然是解长度的指数级。虽然对于这个结论的证明超出了本书的范围，但是已经证明了除非启发函数与实际路径耗散的偏差的增长不超过实际路径耗散的对数，否则节点数量会出现指数级增长。用数学方式表达，非指数级增长的条件是：

|h(n) － h*(n)|≤O(log h*(n))

其中h*(n)是从节点n到目标节点的实际耗散。对于几乎所有实际使用的启发式，偏差至少都是与路径耗散成正比的，因此最终造成指数级的增长而超过计算机的承受能力。由于这个原因，坚持找到最优解的做法通常是不实用的。可以使用A*算法的变种快速地找到非最优解，或者有时候可以设计更准确但不是严格可采纳的启发式。在任何情况下，与使用无信息搜索相比，使用好的启发式还是能节省了大量的时间和空间。在第4.2节中，我们将探讨好的启发式的设计问题。

然而，计算时间还不是 A*算法的主要缺点。因为它在内存中保留了所有生成的节点（如同算法GRAPH-SEARCH那样），A*算法往往在计算完之前就耗尽了它的空间。由于这个原因，A*算法对于许多大规模问题是不实用的。最近发展的一些算法通过执行时间上的小代价来克服空间的问题，而且不牺牲最优性和完备性。这将在下面讨论。