5．最佳图搜索算法A�~（Optimal Search）

最佳图搜索算法A*又可以简称为A*算法。
在前面介绍A算法时，我们只是说启发函数h(n)是h*(n)的一种近似估计，但对h(n)本身没有任何具体的限制。因此也就无法具体讨论A算法的一些性质。如果我们给h(n)加上如下的限制条件，h(n)≤h*(n)，则A算法转换为A*算法。而A*算法，具有一些很好的性质，比如可采纳性等。

当在算法A的评价函数中，使用的启发函数h(n)是处在h�~（n）的下界范围，即满足h(n) ≤h*(n)时，则我们把这个算法称为算法A�~。A�~算法实际上是分支界限和动态规划原理及使用下界范围的h相结合的算法。当问题有解时，A�~一定能找到一条到达目标节点的最佳路径。例如在极端情况下，若h(n)≡0（肯定满足下界范围条件），因而一定能找到最佳路径。此时若g≡d，则算法等同于宽度优先算法。前面已提到过，宽度优先算法能保证找到一条到达目标节点最小长度的路径，因而这个特例从直观上就验证了A�~的一般结论。
一般地说对任意一个图，当s到目标节点有一条路径存在时，如果搜索算法总是在找到一条从s到目标节点的最佳路径上结束，则称该搜索算法是可采纳的（Admissibility）。A�~就具有可采纳性。

对于以下的定理、引理和推论，我们只要求掌握其结论和含义，不要求掌握其具体的证明过程。但是证明过程有助于你对算法的理解。
以下定理的证明，正文部分是严格的，而解释部分，则不是严格的证明，只是从直观上，或者从思路上进行说明。
在以下的定理证明过程中，要明确这样几个关系：
f*(s)=f*(t)=h*(s)，其中s是初始节点，t是目标节点（有时也用g表示）。当n是从初始节点到目标节点t的最优路径上的节点时，f*(n)= f*(s)=f*(t)=h*(s)。

下面来证明A�~的可采纳性及若干重要性质。

定理1的结论是显然的。由于问题的状态是有限的，那么A算法至少可以在有限的步数内搜索完所有的可以从初始节点到达的节点，只要问题是有解的，则一定可以找到问题的解。
定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。
证明：设A搜索失败，则算法在第2步结束，OPEN表变空，而CLOSED表中的节点是在结束之前被扩展过的节点。由于图有解，令（n0=s，n1，n2，…，nk=t）表示某一解路径，我们从nk开始逆向逐个检查该序列的节点，找到出现在CLOSED表中的节点ni，即ni CLOSED，ni+1 CLOSED（ni一定能找到，因为n0 DLOSED，nk CLOSED）。由于ni在CLOSES中，必定在第6步被扩展，且ni+1被加到OPEN中，因此在OPEN表空之前，ni+1已被处理过。若ni+1是目标节点，则搜索成功，否则它被加入到CLOSED中，这两种情况都与搜索失败的假设矛盾，因此对有限图不失败则成功。[证毕]

因为A�~是A的特例，因此它具有A的所有性质。这样对有限图如果有解，则A�~一定能在找到到达目标的路径结束，下面要证明即使是无限图，A�~也能找到最佳解结束。我们先证两个引理：
引理2.1：对无限图，若有从初始节点s到目标点t的一条路径，则A�~不结束时，在OPEN中即使最小的一个f值也将增到任意大，或有f(n)>f�~(s)。

在如下的证明中，隐含了两个假设：（1）任何两个节点之间的耗散值都大于某个给定的大于零的常量；（2）h(n)对于任何n来说，都大于等于零。
引理2.1的证明也比较好理解。由于当问题有解存在时，从初始节点到目标节点的路径的耗散值总是一个有限的常量。那么在该解路径上的任何一个节点n，由于f(n)=g(n)+h(n)，而g(n)是有限的，h(n)≤h*(n)也是有限的（因为h*(n)有限），所以f(n)也是有限的。而对于一个无限图来说，那些不在解路径上的无限路径，随着搜索的进行，其耗散值总会趋于无穷大，因此那些在解路径上的节点的f值总会变得最小，总会有机会被排在OPEN表的第一个位置，从而被A*扩展。而目标节点也是解路径上的一个节点，这样它同样会有机会被排在OPEN表的第一个位置，从而使得算法成功结束，找到问题的解路径。

证明：设d�~(n)是A�~生成的搜索树中，从s到任一节点n最短路径长度的值（设每个弧的长度均为1），搜索图上每个弧的耗散值为C(ni，ni+1)（C取正）。令e=min C(ni，ni+1)，则g�~(n)≥d�~(n)e。而g(n)≥g�~(n)≥d�~(n)e，故有：
f(n)=g(n)+h(n)≥g(n)≥d�~(n)e（设h(n)≥0）
若A�~不结束，d�~(n)y ，f值将增到任意大。
设 ，M是一个定数，所以搜索进行到一定程度会有d�~(n)>M，或 ，则
。
[证毕]

　　该引理可以这样来理解：如果问题从初始节点s到目标节点g的路径存在时，则一定有一个最短路径存在。在A*没有结束之前，OPEN表中的节点不会为空。由于总是从OPEN表中取出节点来扩展，所以最优路径肯定要通过OPEN表中的某个节点，设该节点为n。那么n有两个特点，一是n是从s到g的最优路径上的节点，二是到目前为止已经找到了从s到n的最优路径。第一点会比较容易接受，第二点是如何保证的呢？如果到目前为止找到的不是从s到n的最优路径，同样的理由，在OPEN表中一定有一个节点--假定为n'--在从s到n的最优路径上，当然他也一定在从s到g的最优路径上。用n'来代替n，重复下去，一直找到满足以上两个特点的n为止。当然，我们不一定明确的知道到底OPEN表中的哪个节点满足这样的特点，但从以上的叙述可以知道，这样的节点一定存在。这一点就足够了。
对于具有这样特点的n，由于以上所说的第一个特点有g(n)=g*(n)，所以有f(n)=g*(n)+h(n)，而由于算法是A*的，所以有h(n)≤h*(n)，所以f(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)。对于最后一个等式，是由于对于任何两个最优路径上的节点n1和n2，都有f*(n1)=f*(n2)，而n和s都是最优路径上的节点。引理2.2得证。

引理2.2：A*结束前，OPEN表中必存在f(n)≤f�~(s)的节点（n是在最佳路径上的节点）。
证明：设从初始节点s到目标节点t的一条最佳路径序列为：
(n0=s，n1，…，nk=t)
算法初始化时，s在OPEN中，由于A�~没有结束，在OPEN中存在最佳路径上的节点。设OPEN表中的某节点n是处在最佳路径序列中（至少有一个这样的节点，因s一开始是在OPEN上），显然n的先辈节点np已在CLOSED中，因此能找到s到np的最佳路径，而n也在最佳路径上，因而s到n的最佳路径也能找到，因此有
f(n)=g(n)+h(n)=g*(n)+h(n)
≤g*(n)+h*(n)=f*(n)
而最佳路径上任一节点均有f*（n）=f*(s)（f*(s)是最佳路径的耗散值），所以f(n)≤f*(s)。[证毕]

定理2：对无限图，若从初始节点s到目标节点t有路径存在，则A*也一定成功结束。
有了以上两个引理，定理2的证明就简单了。值得说明的是，对于无限图来说，当问题有解时，从理论上来说，只有A*算法才能保证一定能找到问题的解，而A算法则不能保证。但是在实际应用中，一般来说，A算法也总能找到解，除非你故意设计一个找不到解的f函数。

证明：假定A*不结束，由引理2.1有f(n)＞f*(s)，或OPEN表中最小的一个f值也变成无界，这与引理2.2的结论矛盾，所以A*只能成功结束。[证毕]

由于A*算法每次选择f值最小的节点优先扩展，由定理2得知，只要问题有解，则A*算法总能找到一个解，这个解的耗散值要大于等于f*(s)（f*(s)是最优路径的耗散值），所以OPEN表中满足条件f(n)＜f*(s)的任何节点n，肯定会在A*结束前被扩展。

推论2.1：OPEN表上任一具有f(n)＜f*(s)的节点n，最终都将被A*选作为扩展的节点。

定理3指出，当问题有解时，A*算法不但一定能找到解，而且一定能找到最优解，这一点称为可采纳性。

定理3：若存在初始节点s到目标节点t的路径，则A*必能找到最佳解结束。

　　其实从对引理2.2的证明注释已经清楚，在A*算法结束之前，在OPEN表中一定存在一个节点n，该节点在最优路径上，同时也找到了从s到n的最优路径。如果A*找到的不是最优路径的话，设其找到的路径的耗散值为f(g)，由于f(n)≤f*(n)<f(g)，所以，这时在OPEN表中，应该至少是n排在目标g的前面，而按照A*算法，只有当目标节点排在OPEN表的第一位时，算法才结束，所以在A*结束时，找到的只能是最优路径。从这里也可以看出，在前面反复强调过的A算法（A*算法）的结束判断条件，必须是当目标节点的f值在OPEN表中最小时才能结束，而不是目标一出现就结束是多么的重要。只有这样，才能保证A*算法的可采纳性。

证明：
（1）由定理1、2知A*一定会找到一个目标节点结束。
（2）设找到一个目标节点t结束，而syt不是一条最佳路径，即：
f(t)=g(t)>f*(s)
而根据引理2.2知结束前OPEN表上有节点n，且处在最佳路径上，并有f(n)≤f*(s)，所以
f(n)≤f*(s)<f(t)
这时算法A*应选n作为当前节点扩展，不可能选t，从而也不会去测试目标节点t，即这与假定A*选t结束矛盾，所以A*只能结束在最佳路径上。[证毕]

该推论可以直接从引理2.2推出。由引理2.2，在A*结束前，OPEN表中必有满足条件f(n)≤f*(s)的节点存在，因此，A*必然从这些节点中选择一个节点扩展，而不可能去选择f(n)>f*(s)的节点扩展，所以A*选作扩展的任一节点n，必有f(n)≤f*(s)。

推论3.1：A*选作扩展的任一节点n，有f(n)≤f*(s)。

证明：令n是由A*选作扩展的任一节点，因此n不会是目标节点，且搜索没有结束，由引理2.2而知在OPEN中有满足 的节点 。若n= ，则f(n)≤f*(s)，否则选n扩展，必有 ，所以f(n)≤f*(s)成立。[证毕]