《人工智能：计算Agent基础》——3.7　更复杂的搜索方

本节书摘来自华章计算机《人工智能：计算Agent基础》一书中的第3章，第3.7节,作者：（加）David L.Poole,Alan K.Mackworth 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.7　更复杂的搜索方法

之前的策略可以进行很多优化。首先，我们给出两种适用于图中有环的方法：一种是对环路的明确检查，而另一种是对到某一节点的多路径检查。然后，我们给出迭代深度算法和深度分支界限搜索法，92这两种方法是能保证找到解路径（甚至是最优解）的一般方法，就像宽度优先搜索算法或者A搜索算法，但是利用了深度优先搜索的空间优点。我们将搜索问题分解为很多小的搜索问题来简化搜索方法，这样每一个都更容易解决。最后，我们说明利用动态规划法如何寻找路径和构建启发函数。
3.7.1　环检查
用来代表搜索空间的图可能包含环。例如，图3-6中的机器人域中的机器人会在节点o103和o109之间来回移动。前面所述的搜索方法中有些会陷入环，不断循环，甚至在有限图中也找不到搜索结果。其他的方法也可能循环，但最终会找到解。
当能保证在有限图中找到解后，修剪搜索树的最简单的方法是，不考虑那些已经在从起始节点开始的路径上的点。“环检查”（cycle check）和“回路检查”(loop check)就是用来检查最后一个节点是否在从初始节点到这个点的路径上出现过。有了循环检查，只有路径〈s,…,sk,s〉，其中，s{s0,…,sk}，加入了图3-4中第16行。另外，也可以在选择了节点之后再进行检查，删除有环的路径。
环检查的计算复杂性决定于所使用的搜索方法。对于深度优先搜索方法，其图是显式存储的，管理费用跟常数因子一样低。图中每个节点增加1位，当节点扩张的时候该位应当为1，回溯的时候为0。搜索算法可以通过不扩展该位是1的节点来避免循环。因为深度优先算法保持单一当前路径，所以这个方法有效，路径上的边界有可替代的分支。即使图是动态生成的，只要当前路径上的点有一个有效的索引结构，那么很容易完成环检查。
对于多路径的搜索策略（也就是说，图3-9中所有有指数空间的那些），环检查的时间与搜索的路径长度保持线性增长。在检查以保证不会添加已经在路径中出现过的节点上，这些算法不能比搜索局部路径做得更好。
3.7.2　多路径剪枝
通常有多条路径通向一个节点。如果只需要一条路径，对于已经找到一条路径的节点，搜索算法就需要从边界中剪枝掉其他任何通往该节点的路径。93
多路径剪枝（multiple-path pruning）是通过由已扩展节点组成的closed表来实现的。如图3-4中的13行，选择了一个路径，如果它的最后一个节点在closed表中，那么这条途径就该删除。否则，将最后的节点加到closed表中，算法会继续进行。
这个方法不一定保证最短的路径不被丢弃。可能要更复杂的方法才能保证找到最优解。为了保证搜索算法可以找到至目标节点最低花费的路径，应当遵守以下几条之一：

• 保证到达任何节点的第一条路径都是到那个点的最低花费路径，然后像前面讨论过的那样，剪枝掉所有随后找到的到那个点的路径。
• 如果搜索算法找到比已经找到的路径花费更低的路径了，那么它就可以将所有较高花费的路径删除（因为这些都不可能是最优解）。也就是说，如果边界有一条路径p在路径〈s,…,n,…,m〉中，当发现到n的路径p′比p中相应部分更近，那么p就可以从边界中删除了。
• 无论何时，如果搜索中找到比之前找到的路径花费更低的至某点的路径，那么就把这条新路径吸收到已扩展路径的初始路径中。因此，如果有路径p=〈s,…,n,…,m〉，一个到n的更短的路径p′就可以代替到n的路径p的初始部分。

这些方案中的第一条，允许在找到最优解的保证下使用closed表。其他则需要更复杂的算法。
在最低花费优先算法中，第一次找到的到某一个节点（如，从边界中选择的一个节点）的路径，是到该节点的最低花费路径。删除随后的到该节点的路径不会移除最低花费的那条到该节点的路径，所以，剪掉随后的路径仍然可以保证找到最优解。
像之前描述的一样，A算法不能保证到某点第一次选择的路径就是到该点的最低花费路径。注意到，可采纳性定理保证的是对于到目标节点的每一条路径，而不是每一条路径。看看何时删除到一个节点的随后路径会删除最优解，假设算法选择了到节点n的路径p来扩展，但是存在一个到节点n的更低花费的路径，而这条路径还没有找到。那么，边界中就应该有路径p′，它是较低花费路径的初始部分。猜想路径p′在节点n′结束。则一定有f(p)≤f(p′)，因为p是在p′之前选择的。这就是说：

cost(p)+h(n)≤cost(p′)+h(n′)

如果经过p′比经过p的到n的路径有更低花费，则

cost(p′)+d(n′,n)<cost(p)94

其中，d(n′,n)为从节点n′到节点n的最短路径的实际花费。从上面两个等式，我们可以得出：

d(n′,n)<cost(p)-cost(p′)≤h(p′)-h(p) = h(n′)-h(n)

（h(p′)-h(p) = h(n′)-h(n)可通过以上假设得出。）因此，对于任意两个节点n和n′，如果h(n′)-h(n) ≤ d(n′,n)，那么就能保证找到的第一条路径就是最低花费路径。对于任意两个节点n和n′，对h的单调限制（monotone restriction）是h(n′)-h(n)≤d(n′,n)。也就是说，两个节点的启发函数值的差必须小于或等于两点最低花费路径的实际花费。例如，当花费函数是关于距离的函数时，它适用于两点之间的欧几里得距离（在n维欧几里得空间的直线距离）的启发函数。它也适用于启发函数是有更短解的简化问题的解。
因为单调的限制，在边界，f值是单调非递减函数。也就是说，随着边界的扩展，f值不会变小。因此，因为单调的限制，A算法中随后的到任何节点的路径都可以删除。
多路径剪枝包含环检查，因为环是到某个节点的另外一条路径，因此要被删除掉。如果图是显式存储的，通过在每个节点上设置一个比特位标明已被找到的路径，多路径剪枝可以在一个常数时间内完成。如果图是动态生成的，通过存储由已扩展过的所有节点组成的closed列表，它能在对数时间（只要进行适当索引，可与已扩展的节点数量成对数级）完成。多路径剪枝优先于宽度优先的环检查，因为宽度优先搜索中所有节点被认为必须存储。然而，对于深度优先搜索，算法并不是存储所有的已经扩展节点。存储它们会使这个方法的空间呈指数增长。因此，对于深度优先搜索，环检查优先于多路径剪枝。
3.7.3　迭代深化
到目前为止，我们所讨论过的方法中，没有一种方法是理想的。仅有的能保证找到路径方法需要指数空间（见图3-9）。结合深度优先搜索算法的空间效率和宽度优先搜索算法的最优性的一种方法是迭代深化（iterative deepening）。这种方法的思想是重新计算边界中的点而不是储存它们。每一次重新计算的过程都是深度优先搜素，因此用更少的空间。
我们考虑将宽度优先搜索融合到迭代深化搜索。由仅进行有限深度搜索的搜索器来进行。首先，通过用深度为1的方式进行深度优先搜索，找到深度为1的深度优先方式的路径。然后找深度为2的路径，然后是深度为3的路劲，依次进行。每一次重新计算都可以删掉之前的计算并再次启动。最后如果解存在就可以找到解了，95因为它是按顺序列举路径，所以第一个找到的路径就是弧线最少的。
当使用迭代深化搜索时，应当注意区分：

• 因为达到深度界限的失败。
• 还未到达深度界限的失败。

对于第一种情况，搜索必须进行更深界限的搜索。对于第二种情况，重新进行一次更深界限搜索是浪费时间，因为不管多深，路径都不存在。我们称这种到达了深度界限的失败叫做非自然失败（failing unnaturally），未到达深度界限的失败叫做自然失败(failing naturally)。

1：procedure IdSearch(G,s,goal)
2：　Inputs
3：　　G：具有N个节点和A条边的图
4：　　s：开始节点的集合
5：　　goal：关于状态的布尔函数
6：　Output
7：　　从s到goal函数值为真的节点的路径
8：　　或者如果没有这样的路径则⊥
9：　Local
10：　　natural_failure:布尔型
11：　　bound:整型
12：　　procedure dbsearch(〈n0,…,nk〉,b)
13：　　　Inputs
14：　　　　〈n0,…,nk〉:path
15：　　　　b:integer,b≥0
16：　　　Output
17：　　　　到目标节点的长度为k+b的路径
18：　　　if b＞0 then
19：　　　　for each arc〈nk,n〉∈A do
20：　　　　　dbsearch(〈n0,…,nk,n〉,b-1)
21：　　　else if goal(nk) then
22：　　　　return〈n0,…,nk〉
23：　　　else if nk 有任意邻居 then
24：　　　　natural_failure∶= false
25：　bound ∶= 0
26：　repeat
27：　　natural_failure∶= true
28：　　dbsearch({〈s〉∶s∈S},bound)
29：　　bound∶= bound+1
30：　until natural_failure
31：　return⊥

图3-10中提出一种迭代深化搜索的实现IdSearch。局部程序dbsearch实现了一个深度有界的深度优先搜索（使用递归来保持堆栈），可以限制正在搜索的路径长度。它使用深度优先搜索来找到所有长度为k+b的路径，其中，k是给定的从起点开始的路径长度，b是一个非负整数。迭代深化搜索器调用这个程序来增加深度界限。这个程序发现的到目标节点的路径的顺序和宽度优先算法相同。作为一种通用的图搜索算法，为找到更多路径，在22行的return之后，搜索能从23行继续。
只要宽度优先搜索失败，迭代深化搜索就会失败。当需要更多解时，即使在后续的迭代中可能被再次发现，每一个成功路径也只返回一次。通过跟踪何时增加界限可以帮助找到解能使搜索终止：

• 如果深度搜索中因为到达了深度界限而截断了，那么深度界限可以增加。在这种情况下，搜索就非自然失败了。如果因为深度界限的限制而没有删除任何路径，那么搜索就自然失败了。这种情况下，程序终止，报告0路径。
• 搜索只报告在之前的迭代中没有报告过的一条路径，因此，它只返回那些长度等于深度界限的路径。

迭代深化搜索的最明显的问题是每一步的计算浪费。然而，这可能不像某些人想的那样糟糕，尤其是当分支系数很高的时候。考虑下面算法的运行时间。假定一个常数分支系数b>1，考虑界限是k的搜索。对于深度k，有bk个节点，每一个节点被生成1次。深度为k-1的节点被生成2次，那些深度为k-2的节点被生成3次，如此类推，然后深度为1的节点被产生k次。因此，节点的生成总数是：

在深度n生成节点有一个固定的开销(b/(b-1))2，当b=2时，就有一个开销系数4，当b=3时，有开销系数2.25保证边界。该算法是O(bk)，并且找不到一个更好的渐进的无信息搜索策略。注意到，如果分支系数接近1，这种分析就没有用（因为分母趋近于0），见习题3.9。
迭代深化也可以用于A搜索中。迭代深化A（IDA）算法通过重复的有深度界限的深度优先搜索来进行。它是一个有界的f(n)的值，而不是路径中弧的数量有界。它的阈值起始于是f(s)，其中s是有最小h值的初始节点。然后IDA进行深度优先的深度有界搜索，但从不扩展一个比当前的界限更高的f值的节点。如果深度有界的搜索非自然地失败了，那么下一个界限就是超过之前界限的最小的f值。IDA就如A一样检查相同的节点，但用深度优先搜索重新计算它们，而不是存储它们。
3.7.4　分支界限法
深度优先分支界限(branch and bound)搜索是一种结合了深度优先搜索算法的空间节约和启发信息搜索的方法。它特别适用于存在很多条通往目标节点的路径，我们需要的是最优的路径。像在A搜索中，我们假设h(n)小于或等于从n到目标节点的最低花费路径的花费。
深度优先分支界限搜索的思想是保持到目标最低花费的路径和它的花费，假定这个花费是有界的。如果搜索碰到路径p满足cost(p)+h(p)≥ bound，那么p就该删除掉。如果找到没被删除的路径，那么这条路径一定优于之前最好的路径。这个新解被记住，而且界限就设置成这个新解的花费，然后寻找更好的解。
分支界限搜索生成持续优化解的序列。一旦找到一个解，就一直优化它。
分支界限搜索典型地用于深度优先搜索，这样可以保持深度优先的节省空间的优点。它和深度有界搜索的实现方法相似，但是这里的界限是路径的花费，然后减少花费发现更短的路径。算法会记住所发现的花费最低的路径，当搜索完成时返回这条路径。
算法见图3-11。对于花费有界搜索，内部程序cbsearch使用全局变量来给主程序提供信息。
最初，界限可以设定为无穷大，但是也可以设置一个高估的值，bound0，作为最优路径的花费，这很有用。如果存在比初始花费界限bound0更低的路径，这个算法会返回最优解（从初始节点到目标节点的最低花费路径）。

如果初始界限略高于最低花费路径的花费，那么这个算法不需扩展比A算法更多的弧就可以找到最优的路径。上述情况发生的条件是，算法将那些花费比最低花费高的任何路径都剪枝；一旦它发现一个通往目标节点的路径，它就只探索那些f值低于已扩展路径的路径。而这些正好就是A找到一个解后所探索的路径。

99当bound0=∞时，如果返回⊥，则不存在解。当bound0是有界值时，返回⊥，表示比bound0花费少的解不存在。在找到解或者已知解不存在之前，这个算法可以结合迭代深化算法来增加界限，见习题3.13。
【例3-17】　看图3-12中的树形图。目标节点被涂上阴影。假设每一段弧线的长度为1，没有启发信息（即每个节点的h(n)=0）。在算法中，假设depth0=∞，深度优先搜索总是先选择最左边的后继节点。该图说明了检验确定节点是否是目标节点的顺序。没有标出序号的节点是未检验的节点。
在节点5下面的子树形图中，没有目标节点，被完全探索完（或者根据深度的有限值depth0进行扩展）。被检验的第9个节点是目标节点。它有一条路径，其花费是5，所以界限值设为5。从此以后，只有长度小于5的路径才能作为可能的解被检验。第15个被检验的节点也是目标节点。它的路径花费是3，所以界限减少到3。再没有找到其他的目标节点，所以到标号15的那条路径返回，这个是最优路径。有另外一条最优路径被剪枝。算法就不再检验标号为18的节点的后继节点。
如果有启发信息，就可以用来剪枝部分的搜索空间，就像A算法。
3.7.5　搜索方向
在有限无信息图上的通用搜索算法的搜索空间大小是bk，这里b是分支系数，k是路径长度。任何可以减少b和k的方法都可能会节省很多资源。
问题求解的图搜索方法的抽象定义在以下意义上是对称的，100即这个算法可以从初始节点开始，向前搜索目标节点；或者逆向从目标节点开始，向后搜索初始节点。注意，目标节点的许多应用是由布尔函数隐式地确定，即当发现目标节点时返回true，而不是显式地返回节点集，所以说逆向的向后搜索也许是不可能的。
对于那些目标节点是显式的情况，在一个方向上搜索可能比另一个方向更有效。搜索空间的大小与分支系数成指数增长。通常情况下，向前和向后搜索有不同的分支系数。向前或者向后搜索的一般原则是哪个方向有较小的分支系数。
下面讨论的几种方法对于搜索空间来说可以提高效率。
1.双向搜索
这个搜索方法的思想是同时从起始节点向后以及从目标节点向前搜索来减少搜索时间。当两个搜索的边界相交，这个算法就重构出一个路径，它从起始节点到相交的边界再到目标节点。
在双向搜索中产生一个新问题，即要保证两个搜索的边界真正相交。举例来说，在两个方向上的深度优先搜索不一定能够很好地起作用，因为它可能会因为其较小的搜索边界而相互错过相交。在两个方向上的宽度优先搜索可以保证相交。
一个方向深度优先搜索结合另一个方向宽度优先搜索可以保证所需要的搜索边界的相交，但是在哪个方向上选择用哪种方法很困难。这取决于宽度优先节省的花费以及搜索检查深度优先搜索何时与其元素相交的花费。
在有些情况下，双向搜索可以节省很多。例如，如果前向分支系数和后向分支系数都是b，目标节点的深度是k，那么宽度优先搜索花费的时间与bk成比例，然而一个对称双向搜索花费的时间与2bk/2成比例。即使时间复杂度仍然是指数级，它以指数函数形式节省时间。注意，这种复杂性分析需要假设找到相交点是无需代价的，在很多应用中这种假设可能不成立（见习题3.10）。
2.岛驱动搜索
一种使搜索更有效的方式是找到有限的向前和向后搜索可以相交的地方，例如，找到不同楼层的两间房间之间的通路，101合适的搜索限制可能是先去其中一个楼层的电梯，然后到目标楼层的那个电梯。直觉上，这些指定的位置在搜索图上就像一些岛（island），它们被限定在从起始节点到目标节点的解路径上。
当岛确定了，Agent可以将一个搜索问题分解为几个子问题，例如，一个从初始房间到电梯，一个从某一层的电梯到另外一层的电梯，一个从电梯到目标房间。通过三个更简单的问题求解就缩小了搜索空间。这些更小问题减少了大搜索的组合爆炸，这也是个很好的例子，说明了问题的额外信息如何提高搜索的效率。
为使用岛来找到s和g之间的一条路径，需要：
1) 确定一系列的岛i0,…,ik；
2) 找到从s到i0，从ij-1到ij（j为1～k），从ik到g的路径。
每一个搜索问题应该比总的问题更简单，因此更容易解决。
岛的识别可能是我们从图中无法获得的额外信息。使用不适当的岛可能使问题更复杂（甚至不可解决）。通过选择不同岛集，我们可以将问题分解为另外一组子问题，并通过可能的岛空间进行搜索。在实际使用中是否适用取决于问题的细节。
3.抽象层次搜索
岛的概念可以用来定义在细节上的多个层次或者抽象的多个层次上所使用的问题求解策略。
抽象层次上的搜索的思想首先涉及问题的抽象，尽可能去掉细节。我们可能找到问题的部分解：它的解需要进一步的细节。例如，从一个房间到另一个房间的问题，需要使用多次转身，但是Agent喜欢从一个抽象层次推理问题，其中实际转向的细节被省略了。我们期望适当的抽象解决能从广义角度解决问题，只剩下一些小问题还需要解决。像传递机器人的路径规划问题，不省略细节的搜索求解很困难，除非必须考虑它们。
这种方法的实现可以通过岛驱动搜索找到可能的岛。一旦在岛层次上找到一个解，子问题就可以同样的方式通过递归解决了。在低层次发现的信息可以通知高层次，其中的某些可能解不如期望的那么好。高层次可以使用这些信息重新规划，这个过程通常不能保证最优解，因为它只考虑一些高层次的分解。
在抽象层次的搜索很大程度上取决去怎样分解和抽象要解决的问题。一旦问题被抽象和分解出来，任何搜索方法都能用来解决它们。然而，识别有用的抽象和问题分解并不容易。
3.7.6　动态规划法
动态规划法是最优化的一般方法，它可以存储问题的部分解，所以对于已经发现的解可以检索而不必重新计算。动态规划算法的使用贯穿人工智能。
动态规划算法可以用来在图中找到路径。直觉上，图搜索中的动态规划（dynamic programming）可以被看做用来构造完美的启发函数使得A可以保证找到解，即使它只有边界的一个元素。cost_to_goal函数表示每个节点到目标节点的最低花费路径的准确花费。
政策（policy）用来指定从每个节点引出哪条弧。cost_to_goal函数可以离线计算，用来建立最优的政策。Agent可以利用这个政策在线决定在这个节点做什么。
令cost_to_goal(n)是从n到目标节点的最低花费路径的实际花费。cost_to_goal(n)函数可以定义为：

cost_to_goal(n)=0如果是is_goal(n)
min〈n,m〉∈A(cost(〈n,m〉)+cost_to_goal(m))其他

一般的思想是从目标节点开始，建立一个表存放每一个节点的cost_to_goal(n)值。这可以通过多路径剪枝的最低花费优先搜索来实现，它从目标节点开始在反向图（将图中所有弧的方向反过来）中搜索。对于已发现的每个节点，动态规划算法记录其cost_to_goal值，而不是有一个需搜索的目标。使用反向图计算每个节点到目标节点的花费，而不是从目标到每个节点。实质上，动态规划从目标节点进行逆向搜索，它通过建立从图中每个节点到目标节点的最低花费路径来完成。
对于一个特定的目标，一旦每个节点的cost_to_goal值记录下来，Agent就可以根据这个值来决定最优路径的下一段弧。从节点n应该选择这样的邻居m，它有cost(〈n,m〉) + cost_to_goal(m)的最小值。遵循这个政策，Agent就能沿着最低花费路径从任意节点直到目标。假设每个节点有有限邻居，给定cost_to_goal，决定哪段弧是最优的需要常数时间，该常数与图的大小有关。动态规划法建立cost_to_goal表所需要的时间和空间与图的大小呈线性关系。
动态规划算法在下面条件下是有用的：

• 目标节点是显式的（之前的方法只假设一个函数来识别目标节点）；
• 需要一个最低花费路径；
• 图是有限的和足够小的，能够存储每一个节点的cost_to_goal值；
• 目标不经常变化；
• 政策对于每个目标可以使用多次，产生cost_to_goal值的花费可以分摊到很多实例问题上。

动态规划搜索的主要问题是：

• 只有当图有限，而且表能小到适应于内存时，这个方法才有效。
• 对于每一个不同的目标，Agent必须重新计算政策。
• 需要的时间空间线性于图的大小，对于有限的图来说，图的大小通常是路径长度的指数形式。

【例3-18】　对于图3-2，从r123到目标节点的花费是0，因此
cost_to_goal (r123) = 0
继续从r123使用最低花费优先搜索

cost_to_goal (o123) = 4
cost_to_goal (o119) = 13
cost_to_goal (o109) = 29
cost_to_goal (b4) = 36
cost_to_goal (b2) = 39
cost_to_goal (o103) = 41
cost_to_goal (b3) = 43
cost_to_goal (b1) = 45

　　到这个阶段向后搜索停止了。这里注意两点:首先，如果一个节点没有cost_to_goal值，那么不存在从该节点到目标节点的路径；其次，Agent可以很快地确定任意一个节点到目标节点的最低花费值路径的下一段弧。例如，如果Agent在o103，决定到r123的最低花费路径，需要比较4+43（通过b3的花费）和12+29（直接到o109的花费），可以很快决定去o109。
当建立cost_to_goal函数时，搜索者会隐式地决定选择哪个邻居到达目标，它不是在运行时就确定哪个邻居在最优路径上，而是储存该信息。104
动态规划搜索可以用来为A算法和分支界限算法建构启发信息。构建启发函数的一种方式是简化问题（如去掉一些细节），直到被简化的问题有一个足够小的状态空间。动态规划算法可以用来在简化了的问题中找到最优的路径。这个信息也可以用来作为原始问题的启发信息。A算法的最优性对于一个搜索算法，如果不存在能使用更少的时间或空间或扩展更少的节点的其他算法，同时保证解的质量，那么这个算法就是最优的(optimal)。最优搜索算法每次都会选择正确的节点。然而，因为我们不能直接实现它，所以这个算法的详细说明并不有效。这样一个算法是否能实现是一个开放问题（就像是否P=NP）。然而，似乎有一个能被证明的陈述。
A的最优性(optimality of A)：在只使用弧花费和从起始节点到目标节点花费的启发式估计的搜索算法中，没有算法能比A算法扩展更少的节点并保证能找到最低花费路径。
证明概述：除非算法扩展了每一个路径p，这里f(p)低于最优路径的花费，否则只给定弧线花费以及启发信息，我们不知道p是否是一条最低花费的路径。更正式地，假设一个算法A′找到了问题P的解，这里某些路径p没有扩展，这样f(p)小于找到的解。假设有另一个问题P′，除了有一条花费为f(p)的通过p的路径，其他与问题P一样。算法A′不能分辨P′和P，因为它不扩展路径p，所以它对问题P′会返回和P一样的解，但是对于P找到的解对于P′来说不是最优解，因为这个解比经过p的路径有更高的花费。因此，算法不能保证找到最低花费的路径，除非它找到所有的f值比最优路径低的路径，这样就必须找到A所找到的所有的路径。
反例：尽管这个证明似乎合理，但是有的算法扩展更少的节点。考虑一个算法，它使用像A算法的向前搜索以及向后的动态规划搜索方法，这两种方法在某些方面是交叉进行的（例如，向前和向后交叉进行）。向后的搜索会建立一个表：cost_to_goal(n)，指的是从n到目标节点的实际花费，它有边界值b，它已经扩展了所有到目标花费低于b的路径。向前搜索使用cost(p)+c(n)上的优先级队列，这里n是路径p的最后一个节点，如果这个值已经算出c(n)是cost_to_goal(n)，否则c(n)是max(h(n),b)。直觉上，如果从路径的最后一个节点p到目标节点存在路径，或者它使用向后搜索已经扩展的路径，或者使用花费至少为b的路径。这个算法保证能找到最低花费的路径，扩展比A更少的节点（见习题3.11）。
总结：上面的反例似乎意味着A的最优性是错误的。然而，证明也有一定的吸引力，这不应被彻底忽视。A不是所有算法中最优的，但是对于所有向前搜索的方法，这个证明似乎是正确的（见习题3.12）。