hoduao

与或图的启发式搜索算法AO*

算法类似于普通图搜索中的算法。在算法中，对当前搜索图的"前沿"（即在OPEN

表中的节点）节点进行评价，选取f值最小的节点进行扩展。回想一下，f是如何定义的？

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

其中g(n)表示的是已经求得的从初始节点到当前节点n的路径耗散值，h(n)表示的是从n到目

标节点的最优路径耗散值的估计值。所以对节点n的评价，实际上是对"初始节点--节点n--目标节

点"这一条路径的评价。

在与或图搜索中，由于"与"节点的存在，单纯对一个节点的评价已经不能反映解图的全面情况。

与或图中的解图相当于普通图中的解路径。从上边所分析的，"对节点n的评价，实际上是对'初始

节点--节点n--目标节点'这一条路径的评价"这一思路出发，我们可以很容易的想到，能否通过对局

部解图进行评价，来达到类似于普通图中A*搜索的目的。AO*算法，正是这样的一种适用于与或

图的搜索算法。

启发式的与或图搜索过程和普通图类似，也是通过评价函数f（n）来引导搜索过程。

对于与或图来说，由于局部图中有多个叶节点，不能像普通图搜索那样，通过对某一个节

点的评价来实现对整个局部图的评价。在普通图搜索中，f(n)=g(n)+h(n)，表面上是对n的评价，实

际上是对通过n的这条路径的评价。因此对于与或图搜索来说，就是通过对局部图的评价来选择待

扩展的节点。

下面首先讨论算法本身，然后再通过示例说明搜索过程以及与算法的某些差别。

1．算法

算法可以划分为两个阶段。

第一阶段：图生成过程，即扩展节点。

对于每一个已经扩展了的节点，算法都有一个指针，指向该节点的后继节点中，耗散值小的那

个连接符。图生成过程，就是从初始节点出发，按照该指针向下搜索，一直到找到一个未扩展的节

点为止。然后扩展该节点。从下面的讨论可以知道，这实际上扩展的是一个耗散值最小的局部图。

第二阶段：耗散值计算过程。

这是一个逆向的计算过程。设n为最新被扩展的节点，该节点有m个外向连接符连接n的所有后

继节点。则根据耗散值的计算公式，可以计算出节点n相对于每一个外向连接符的耗散值。从中选

择一个最小值作为n的耗散值。并标记一个指针指向产生最小耗散值的外向连接符。对于n的父节

点，进行同样的计算。重复这一过程，直到初始节点s为止。这时，从s出发，选择那些指针所指

向的连接符得到的局部图，为当前耗散值最小的局部图。

当连接符全部为1－连接符时，局部图就是一个路径，选择一个耗散值最小的局部图扩展，与第二

章中从OPEN表中选择一个f值最小的节点扩展是一致的。

过程：

1、建立一个搜索图G，G:＝s，计算q（s）＝h（s），IFGOAL（s）THENM（s，SOLVED）；

开始时图G只包括s，耗散值估计为h（s），若s是终节点，则标记上能解。

2、Untils已标记上SOLVED，do：

3、begin

4、G′:＝FIND（G）；根据连接符标记（指针）找出一个待扩展的局部解图G′。

5、n:＝G′中的任一非终节点；选一个非终节点作为当前节点。

6、EXPAND（n），生成子节点集{nj}，计算q（nj）＝h（nj），其中njG，G:＝ADD（{nj}，G），

IFGOAL（nj）THENM（nj，SOLVED）；对G中未出现的子节点计算耗散值，若有终节点则

加能解标记，然后把n的子节点添加到G中。

7、S:＝{n}；建立含n的单一节点集合S。

8、UntilS为空，do：

9、begin

10、REMOVE（m，S），；这个m的子节点mc应不在S中。

11、·修改m的耗散值q（m）：

对m指向节点集{n1i，n2i，…，nki}的每一个连接符i分别计算qi：

qi（m）＝Ci+q（n1i）+…+q（nki），

q（m）:＝minqi（m）；对m的i个连接符，取计算结果最小的那个耗散值为q（m）。

·加指针到minqi（m）的连接符上，或把指针修改到minqi（m）的连接符上，即原来指针与新确

定的不一致时应删去。

·IFM（nji，SOLVED）THENM（m，SOLVED）；若该连接符的所有子节点都是能解的，则

m也标上能解。

12、IFM（m，SOLVED）∨（q（m）≠q0（m））

THENADD（ma，S）；m能解或修正的耗散值与原先估算q0不同，则把m的所有先辈节点ma

添加到S中。

13、end

14、end

这个算法可划分成两个操作阶段：第一阶段是4-6步，完成自顶向下的图生成操作，先通过有标记

的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终节点进行扩展，并对其后继节

点赋估计耗散值和加能解标记。第二阶段是7-12步，完成自下向上的耗散值修正计算、连接符（即

指针）的标记以及节点的能解标记。

耗散值的修正从刚被扩展的节点n开始，其修正耗散值q（n）取估计h（n）的所有值中最小的一

个，然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值，只有下层节点耗散值修正后，

才可能影响上一层节点的耗散值，因此必须自底向上一直修正到初始节点。这由算法中的内循环过

程完成，下面就用图3.1的例子来说明算法的应用过程。

2．算法应用举例

设某个问题的状态空间如图3.1所示，并定义了某个启发函数h（n），我们来看一看解图的搜

索过程。

为了使用方便，将h（n）函数对图3.1中各节点的假想估值先列写如下（实际应用中是节点生

成出来之后才根据h（n）定义式计算）：

h（n0）＝3，h（n1）＝2，h（n2）＝4，h（n3）＝4，h（n4）＝1，h（n5）＝1，h（n6）＝2，h

（n7）＝h（n8）＝0（目标节点）。

此外我们假设k-连接符的耗散值为k。

图3.3给出了使用算法对图3.1所示与或图的搜索过程。

开始时，只有一个初始节点n0，n0被扩展，生成出节点n1、n4和n5，一个1－连接符指向

n1，一个2－连接符指向n4和n5。这两个连接符之间是"或"的关系。由已知条件知：h(n1)=2，h(n4)=1，

h(n5)=1，并且已经假设k－连接符的耗散值为k。所以由n0的1－连接符，可以计算出n0的耗散

值（即算法中的q值，为了与算法一直，以下用q值表示）为（n0的1－连接符的耗散值）＋（n1

的q值）＝1＋2＝3。对于目前得到的局部图来说，n1是一个叶节点，所以其q值用h值（＝2）

代替。由n0的2－连接符，可以计算出n0的q值为（n0的2－连接符的耗散值）＋（n4的q值）

＋（n5的q值）＝2＋1＋1＝4。在两个不同渠道计算得到的耗散值中取最小值作为n0的q值，并

设置一个指针指向提供该耗散值的连接符。在这里3<4，所以n0的q值为3，指针所指向的连接

符为n0的1－连接符。至此算法的第一个循环结束。搜索图如图3.3（a）所示。

在第二个循环中，首先从n0开始，沿指针所指向的连接符，寻找一个未扩展的非终节点。这

时找到的是n1节点。扩展n1节点，生成出节点n2和n3，两个节点分别通过1－连接符与n1连接。

由于h(n2)=h(n3)=4，所以通过这两个连接符计算的耗散值也一样，均为5。取其最小者还是5，从

而更新n1的q值为5。由于耗散值相等，所以指向连接符的指针可以指向两个连接符中的任何一

个，假定指向了n3这一边。由于n1的q值由2更新为5，所以需要从新计算n0的q值。对于n0

来说，此时从1－连接符这边算得的耗散值为6，大于从2－连接符这边得到的耗散值4，所以n0

的q值更新为4，并将指向连接符的指针由指向1－连接符改为指向2－连接符。注意，这时由n1

出发的指向连接符的指针并没有被改变或删除。至此第二循环结束，搜索图如图3.3（b）所示。

在第三个循环中，同样从n0开始，沿指针所指向的连接符，寻找未扩展的非终节点。这时n4

和n5都是满足这一条件的节点，可以从它们中任选择一个扩展。假定选择的是n5。n5生成出n6、

n7和n8三个节点。一个1－连接符指向n6，一个2－连接符指向n7和n8。计算的结果，得到n5

的q值为2，指针指向2－连接符。由于n5的q值改变了，因此需要重新计算n0的q值，计算的

结果为5。该结果还是比通过n0的1－连接符计算得到的耗散值小，因此只需更新n0的q值即可，

不需要改变指向连接符的指针。

在本次循环中，由于n7和n8都是目标节点，是能解节点，而n5通过一个2－连接符连接n7

和n8，所以n5也被标记为能解节点。虽然n5是能解节点，但由于n0是通过一个2－连接符连接

n5和n4，而此时n4还不是能解的，所以n0还不是能解的。搜索将继续进行。至此第三循环结束，

搜索图如图3.3（c）所示。

第四次循环，同样的道理，从n0开始沿指针所指向的连接符，寻找未扩展的非终节点，这次

找到的是n4。扩展n4，生成节点n5和n8，并分别以1－连接符连接。对n4来说，从n5这边计算

得耗散值为3（n5已经被扩展过，其q值已经被更新为2，因此在计算n4的耗散值时，应使用更

新后的q值，而不是n5的h值），从n8这边计算得耗散值为1。取小者，得n4的q值为1，并且

将指向连接符的指针指向n8这边的连接符。因为扩展n4并没有改变它的q值，因此n0的q值也

不需重新计算了。由于n8是目标节点，是能解节点，而n4通过一个1－连接符连接n8，因此n4

也被标记为能解节点。在第三循环中，n5已经被标记为能解节点。这样n4、n5都是能解节点了，

从而n0也被标记为能解节点。而n0是初始节点，至此搜索全部结束。从n0开始，沿指向连接符

的指针找到的解图即为搜索的结果。下图为得到的解图。

搜索得到的解图

应用算法求解，经过4个大循环后就找到解图，图3.3给出这4个循环之后的搜索结果。

第四个循环后算法结束，这时带指针的连接符就给出了所得到的解图，n0给出的修正耗散值q（n0）

＝5就是解图的实际耗散值。该例中显然找到了具有最小耗散值的解图。

3．算法应用的若干问题

（1）在第6步扩展节点n时，若不存在后继节点（即陷入死胡同），则可在第11步中对m

（即n）赋一个高的q值，这个高的q值会依次传递到s，使得含有节点n的子图具有高的q（s），

从而排除了被当作候选局部解图的可能性。

算法的第五步，从G′中选择一个非终节点扩展。一般情况下会有若干个非终节点供选择，算

法并没有规定选择节点的方式。如果最终求解出来的解图是从该G′产生的，则优先选择哪个节点

先扩展并不重要，因为这几个节点最终都要被扩展的，扩展次序的先后，并不会影响到搜索的效率。

我们考虑最终的解图不是从该G′产生的情况。则在这种情况下，如果问题有解的话，最佳解图应

从其他的局部图产生。所以此时应该尽快从G′中跳出来，转到别的局部图去搜索。而跳出G′的唯

一条件是使得G′的耗散值不是最小。假设G′有两个非终节点，一个h值小，一个h值大。显然先

扩展h值大的节点会有力于尽快从G′中跳出。因此，当有几个非终节点供选择时，选择h值较大

的节点首先扩展，有利于提高搜索的效率。

（2）第5步中怎样选出G′中的一个非终节点来扩展呢？一般可以选一个最可能导致该局部解

图耗散值发生较大变化的那个节点先扩展，因为选这个节点先扩展，会促使及时修改局部解图的标

记。

与A*算法不同的是，只有当h满足单调限制条件时，AO*才能够在问题有解的情况，一定保

证找到最佳解图。

（3）同A算法类似，若s→N集存在解图，当h（n）≤h*（n）且h（n）满足单调限制条件时，

则AO*一定能找到最佳解图，即AO*具有可采纳性。当h（n）≡0时，AO*也蜕化为宽度优先算法。

这里单调限制条件是指：对隐含图中，从节点n→{n1，…，nk}的每一个连接符都施加限制，即假

定h（n）≤C+h（n1）+…+h（nk）其中C是连接符的耗散值。

如果h（n）满足单调限制，且h（ti）＝0（ti∈N），那么单调限制意味着h是h*的下界范围，即

对所有节点n有h（n）≤h*（n）。

图3.3AO*算法4个循环的搜索图

（a）一次循环之后（b）两次循环之后

（c）三次循环之后（d）四次循环之后

综上所述，看出与A有类似之处，但也有若干区别。首先是AO*算法不能像A算法

那样，单纯靠评价某一个节点来评价局部图。其次是由于k-连接符连接的有关子节点，对父节点

能解与否以及耗散值都有影响，因而显然不能象A算法那样优先扩展其中具有最小耗散值的节点。

再一点是算法仅适用于无环图的假设，否则耗散值递归计算不能收敛，因而在算法中还必须检

查新生成的节点已在图中时，是否是正被扩展节点的先辈节点。最后还必须注意A算法没有OPEN

和CLOSED表，而AO*算法只用一个结构G，它代表到目前为止已明显生成的部分搜索图，图中

每一个节点的h（n）值是估计最佳解图，而不是估计解路径。

有关AO*算法的具体应用及一些提高搜索效率的修正算法，可进一步参阅人工智能有关文献。