第3章图搜索算法

搜索算法的搜索路径是用称为图的数据结构保存的。图由节点和边构成，节点代表搜索过程中的某一个状态，边是从一个节点过渡到另一个节点的算子。前面讨论了用搜索求解问题的方法是在一个图(一般是隐式图)中进行搜索，而搜索的策略是在图中寻找最佳解路径。下面首先讨论图在搜索过程中是以怎样的形式存储的。
抽象地来看，搜索图可以有两种结构。
(1) 树结构，允许搜索图中有相同状态多次出现，每出现一次就用一个新的节点表示，这样的图没有回路出现，即没有圈。
(2)  图结构，不允许搜索图中有相同状态多次出现，即相同的状态只能用一个节点表示。这样，如果有两条路径都生成了某个状态，这个状态只能用一个节点表示，这就在图中形成了圈。
本章讨论用图来存储问题的搜索空间，而保存解路径则用树结构。根据图对应的实际问题背景可分为“或图”和“与/或图”两种。或图对应的背景为搜索扩展时，可在若干分支中选择一个(这就是“或”的意思)； 与/或图则是在搜索扩展时，有可能同时搜索若干分支(这就是“与”的含义)，也有可能在若干分支选择其中之一(这就是“或”的含义)。这两种图都可能存在回路，以下讨论的算法中，都通过一定的手段避开在回路中循环搜索。
3．1或图搜索
或图对应的背景为搜索扩展时，可在若干分支中选择一个。例如编写一个下棋程序，其搜索过程的每一步就是在若干下棋的走步中选择一个，这就是典型的或图中的搜索。
下面首先讨论一般或图上的搜索算法，然后讨论建立在这个一般算法之上的若干更高效的搜索算法。
3．1．1或图搜索算法
图搜索算法只记录状态空间那些被搜索过的状态，它们组成一个搜索图G。G由两张存放节点的表(List)，再加上一个反向树组成。
（1） Open表。用于存放已经生成，且已用启发式函数作过估计或评价，但尚未产生它们的后继节点的那些节点，也称未考察节点。
（2） Closed表。用于存放已经生成，且已考察过的节点。
（3） 反向边组成的Tree。用来存放当前已生成的搜索树，该树也是一个表，该表的元素是搜索过程中的反向边(反向指针)。



 
例3．1在如图3．1所示的搜索图中，假如由节点A搜索到节点B，再搜索到节点E，而且已扩展了它的两个后继节点。此时用上述方法表示的隐式图G为： 

Open=(D，H，I)//还未考察节点

Closed=(A，B，E)//已考察过的节点

Tree=((E，B)，(B，A)) //反向边组成的表



图3.1一个简单的搜索图



图3.1中，假如I是目标节点，搜索到I节点后，搜索成功，(I，E)加入到了Tree。这时，根据这个Tree，做反向查找，很快就可以找到解路径是(A，B)(B，E)(E，I)。
下面讨论或图通用搜索算法，通用的含义是，只要搜索问题能表示成这样一个或图，这个算法就可以用于求解这个问题，即算法具有通用性。
1．  或图通用搜索算法
设S0为初始状态，Sg为目标状态。
（1） 产生仅由S0组成的Open表，即Open＝(S0)。
（2） 产生一个空的Closed表。
（3） 如果Open为空，则失败退出。
（4） 在Open表上按某一原则选出一个节点，称为n，将n放到Closed表中，并从Open表中去掉n。
（5） 若n∈Sg，则成功退出，此时，解为在Tree中沿指针从n到S0的路径，或n本身。(例如八皇后问题给出到达的目标状态n即可，八数码问题要给出到达目标状态的路径)。
（6） 产生n的一切后继，将后继中不是n的先辈点的一切点构成集合M，装入G作为n的后继。(这就剔除了既是n的先辈又是n的后继的结点，从而避免了回路。)
（7） 对M中的元素P，分别作两类处理： 
① 若PG，即P不在Open表中也不在Closed表中，则P根据一定原则加入Open表，同时对P进行评价，把指向P的边反向后，加入Tree中。
② 若P∈G，则决定是否更改Tree中P到n的指针。
（8） 转3。
2．  算法说明
以上算法中有两点需要说明。
说明一： 在算法的第（4）步，每次取出Open表的第一个节点，然后在第（7）步的①中，若生成的后继节点放于： 
(1) Open表的尾部，算法相当于广度优先(Breadthfirstsearch)。
(2) Open表的首部，算法相当于深度优先(Depthfirstsearch)。
(3) 根据启发式函数f的估计值确定最佳者，放于Open表的首部，算法相当于最佳优先(Bestfirstsearch)。
例3．2我们不妨对上述第(1)种情况进行算法步骤的跟踪，还是假定目标是图3．1中的节点G。
（1） 产生仅由S0组成的Open表，即Open＝(A)。
（2） 产生一个空的Closed表。
（3） Open＝(A)，不为空。
（4） 从Open表中取出第一个节点A，称为n，将n放到Closed表中，并从Open表中去掉A，此时Open＝( )，Closed＝(A)。
（5） n=A，不是目标。
（6） 产生A的后继B和C，此时M=(B，C)。
（7） 考察M中的元素B、C，它们不在Open表中也不在Closed表中，加入Open表，Open＝(B，C)， 再将反向边(B，A)、(C，A)加入Tree中。
（8） 转（3）。
（9） Open＝(B，C)，不为空。
（10） 从Open表中取出第一个结点B，放到Closed表中，并从Open表中去掉B，此时Open＝(C)，Closed＝(A，B)。
（11）  n=B，不是目标。
（12）  产生B的后继D、E，此时M=(D，E)。
（13）  考察M中的元素D、E，它们不在Open表中也不在Closed表中，加入Open表，Open＝(C，D，E)， 反向边(D，B)、(E，B)加入Tree中。
（14）  转（3）。
（15） Open＝(C，D，E)，不为空。
（16）  从Open表中取出第一个节点C，放到Closed表中，并从Open表中去掉C，此时Open＝(D，E)，Closed＝(A，B，C)。
（17）  n=C，不是目标。
（18）  产生C的后继F、G，此时M=(F，G)。
（19）  考察M中的元素F、G，它们不在Open表中也不在Closed表中，加入Open表，Open＝(D，E，F，G)， 反向边(F，C)、(G，C)加入Tree中。
（20）  转（3）。
继续跟踪下去，不难看出，按照这种策略，访问的次序是A、B、C、D、E、F、G。这正是广度优先搜索的次序。
若生成的后继节点放于Open表的首部，读者用上述同样的步骤进行跟踪，不难看出，访问的次序是A、B、D、E、H、I、C、F、G。这正是深度优先搜索的次序。
若将启发式函数f的估计值的最佳者放于Open表的首部，再对或图通用的搜索算法进行跟踪。对于图3．1，若将达到某个节点的边的权值作为这个节点启发式函数f的值，即f(B)=3，f(C)=1，f(D)=4，f(E)=5，f(F)=3，f(G)=7，f(H)=3，f(I)=2，在这个假定下，搜索算法访问的次序分别是A、C、B、E、H、I、D、F、G。读者不妨跟踪算法，记录一下Open表中节点的编号变化的情况。
说明二： 在算法的第②步中，若p∈G，则决定是否更改Tree中p到n的指针。这是因为p已经在G中，说明以前访问过p节点，那么原来的访问路径与当前的访问路径就要进行比较，看哪一条路径更好。
例如，如图3．2所示，p∈M且在Open表中，这说明p在作为n的后继之前已是某一节点m的后继，但本身尚未被考察(未生成p的后继)。


图3．2p在n之前已是某一节点m的后继


这说明S0→p至少有两条路径，这时有两种情况： 
 若Path1的代价<Path2的代价时，当前路径较好，要修改p的指针，使其指向n，即标出搜索之后的最好路径； 
 若Path1的代价≥Path2的代价时，原路径较好，不改变p的指针。
或图通用搜索算法第②步中是否需要更改Tree中p到n的指针，还有更复杂的情况，在这里不再详细讨论。
3．1．2A算法与A*算法
1． A算法与A*算法定义

在或图通用搜索算法第④步“在Open表上按某一原则选出一个节点”定义为： 按启发式函数f的值从小到大排列，然后取出第一个节点，并将启发式函数的形式定义为： f(n)=g(n)+h(n)。具有这样的启发式函数的或图通用搜索算法就称为A算法。
A算法的启发式函数中，g(n)表示从S0到n点的搜索费用的估计，因为n为当前节点，搜索已达到n点，所以可计算出g(n)。h(n)表示从n到Sg接近程度的估计，因为尚未找到解路径，所以h(n)仅仅是估计值。
在A算法中，若令h(n)≡0，则A算法相当于广度优先，因为上一层节点的搜索费用一般比下一层的小，所以优先搜索本层节点（向广度发展）。
g(n)≡h(n)≡0，则相当于随机算法。
g(n)≡0，则相当于最佳优先算法。
在A算法中若进一步规定h(n)≥0，并且定义： 

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

其中，f*(n)表示S0经点n到Sg最优路径的搜索费用，也有人将f*(n)定义为实际最小搜索费用； g*(n)为S0到n的实际最小费用； h*(n)为n到Sg的实际最小费用的估计。
特别是要求h(n) ≤h*(n)，就称这种A算法为A*算法。
例3．3在图3．3中寻找城市A到城市B的最短路径，实线表示从S0到某节点ni所经过的路径，虚线表示ni与Sg的可选择路径，双虚线表示ni与Sg的直线距离(可以从地图上量出)，但并不一定有实际的道路，则实线表示的路径为g(n)，双虚线和虚线表示的路径都可作为h(n)。以n3为例，g(n)＝{S0→n1→n3}，h(n)可以是{n3→n4→Sg}、{n3→n4→n5→Sg}或{n3→Sg(双虚线)}这些路径中的一个，即h(n)是n3到Sg的各种可能的路径。


图3.3在地图上寻找城市A到城市B的最短路径


在本例中，如果将双虚线表示的路径定义为h(n)，显然有h(n) ≤h*(n)，g(n)≥g*(n)。所以，本例使用这样的h(n)(双虚线)作为搜索算法的估计函数，这个算法就是A*算法。
不难看出，A*算法是从A算法约束而来，而A算法又是从或图通用搜索算法进行限制得到的，因此很容易将或图通用搜索算法改造成为如下所示的A*算法。
2. A*算法
设S0为初始状态， Sg为目标状态。

（1） Open={S0}。
（2） Closed={ }。
（3） 如果Open={}，失败退出。
（4） 从Open表中取出f(n)值最小的节点n，放到Closed表中。

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


（5） 若n∈Sg，则成功退出。
（6） 产生n的一切后继，将后继中不是n的先辈点的一切点构成集合M。
（7） 考察M中的元素P，分别作两类处理： 
① 若PG，则对P进行估计加入Open表，记入G和Tree。
② 若P∈G，则决定更改Tree中P到n的指针，并且更改P的子节点n的指针和费用。
（8） 转（3）。
3． A*算法的性质
A*算法与一般的最佳优先算法比较，有其特有的优良性质： 如果问题有解，即S0→Sg存在一条路径，A*算法一定能找到最优解。这一性质称为可采纳性。
例3．4继续讨论八数码问题的求解，如图3.4所示。


图3．4八数码问题求解


以前采用的估计函数为： 

f=放错位置的数字的个数

现在采用： 

f(n)=d(n)+ w(n)

其中，d(n)为搜索树的深度； w(n)为放错位置的数字的个数。这里g(n)=d(n)，h(n)=w(n)，并且满足w(n) ≤h*(n)，因为w(n)只估计放错位置的数字的个数，而这些数码从放错位置到正确位置要移动的步数，比这些数码的个数显然要大得多。用这样定义的f(n)所得到的搜索图如图3．5所示。


图3．5八数码问题使用A*算法的搜索图


在搜索第二层时，若f值相等，需要再规定一下如何优先选择后继：
(1) 后生成的节点优先，如图3.5中双线路径所示。
(2) 先生成的节点优先，则如图3.5中的粗线路径，但生成3个后继(C1，C2，C3)之后，下次在算法的第4步仍会在Open中找最小，即在Open表中含有图3．5的如下3层的节点： 

一层二层三层

(A1=6，A3=6)(B2=5，B3=6)(C1=6，C2=7，C3=6)

其中B2最优，则仍可找到B2继续扩展。我们通过跟踪Open表中元素可以看到这一点。
例3．5野人与传教士过河问题。有N个传教士和N个野人，要从左岸向右岸渡河，有一条船，每次最多可供k人乘渡。问为了传教士的安全起见，应如何规划摆渡方案，使得任何时刻，传教士和野人在一起时，河两岸以及船上的野人数目总是不超过传教士的数目(否则传教士有可能被野人吃掉)。
这个问题要求在求解传教士和野人从左岸全部摆渡到右岸的过程中， 任何时刻传教士和野人在一起时，满足传教士数大于等于野人数，并且两者人数之和小于或等于k的摆渡方案。该问题的求解过程如下。
设M、C为某一时刻传教士人数和野人人数，k为船能够承载的人数。过河时，要求M≥C且M+C≤k。又设L表示船在左岸，R表示船在右岸，并假设传教士和野人都为5个人，船一次可载3人时，即N=5，k=3，该问题的状态空间可表示为： 
初始状态

LR
M50
C50
B10
目标状态

LR
M05
C05
B01



其中，B=1代表在左岸，B=0代表不在左岸。
由于野人和传教士的总数是一定的，可以只考虑左岸或右岸就可以了(这就减少了状态变量)，因此可以用如下方式考虑状态空间。
1) 定义状态空间
用三元组Sk=(ML，CL，BL)来表示传教士、野人和船是否在左岸的状态，其中ML表示传教士在左岸的实际人数，CL表示野人在左岸的实际人数，BL用来指示船是否在左岸。
条件： ML≥0，CL≤5，BL∈{ 0，1}
问题即转化为： 初始状态为 (5，5，1)，目标状态为 (0，0，0)。
为了表述的简洁，按每次渡河的人数分别写出每一个规则，共有(3，0)、(0，3)、(2，1)、(1，1)、(1，0)、(0，1)、(2，0)、(0，2)8种渡河可能的组合(其中(x，y)表示x个传教士和y个野人一起上船渡河)，因此共有16个规则(从左岸到右岸、从右岸到左岸各8个)。注意，这里没有出现(1，2)，因为该组合在船上的传教士人数少于野人人数。
规则集如下： 
P01if(ML，CL，BL=1) then(ML，CL-1，BL-1) 
P02if(ML，CL，BL=1) then(ML，CL-2，BL-1) 
P03if(ML，CL，BL=1) then(ML，CL-3，BL-1) 
P10if(ML，CL，BL=1) then(ML-1，CL，BL-1) 
P11if(ML，CL，BL=1) then(ML-1，CL-1，BL-1) 
P20if(ML，CL，BL=1) then(ML-2，CL，BL-1) 
P21if(ML，CL，BL=1) then(ML-2，CL-1，BL-1) 
P30if(ML，CL，BL=1) then(ML-3，CL，BL-1) 
Q01if(ML，CL，BL=0) then(ML，CL+1，BL+1) 
Q02if(ML，CL，BL=0) then(ML，CL+2，BL+1) 
Q03if(ML，CL，BL=0) then(ML，CL+3，BL+1) 
Q10if(ML，CL，BL=0) then(ML+1，CL，BL+1) 
Q11if(ML，CL，BL=0) then(ML+1，CL+1，BL +1) 
Q20if(ML，CL，BL=0) then(ML+2，CL，BL+1) 
Q21if(ML，CL，BL=0) then(ML+2，CL+1，BL+1) 
Q30if(ML，CL，BL=0) then(ML+3，CL，BL+1) 
为了理解以上规则的含义，通过规则P21来说明： 
P21if(ML，CL，BL=1) then (ML-2，CL-1，BL-1)

表示从左岸渡了两个传教士和一个野人到右岸，因此，左岸的传教士和野人的人数减少了，分别为ML-2和CL-1，而此时BL-1=0，表示船在右岸。
Q21表示的意义正好相反，即从右岸渡了两个传教士和一个野人到左岸，因此左岸的传教士和野人的人数增加了。
2) 启发式搜索策略
这里的启发式搜索策略使用如下A算法中的启发式函数表示： 

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

其中，g(n)是从开始节点搜索到节点n时已经花费的代价； h(n)指启发式函数中的启发式部分，是从节点n到目标节点的最优路径的估计代价，搜索的启发信息主要由h(n)来体现。
(1) 启发式函数1： 

f(n)=g(n)，两岸的传教士数目≥野人数目

∞，其他

其中，g(n)表示搜索树的深度，也是船只来回的次数。f函数中启发函数为零，即h(n)=0，此时对应的搜索图如图3．6所示，图中还是针对N=5、k=3时的搜索图。


图3．6启发式函数1对应的搜索图



(2) 启发式函数2： 


f(n)=g(n)+M+C，两岸的传教士数目分别大于等于野人数目（当野人与传教士在一起时）

∞，其他

即启发函数为h(n)=M+C，此时对应的搜索图如图3．7所示。


图3．7启发式函数2对应的搜索图


搜索图中的初始节点10(5，5，1)表示f值为10f(n)=g(n)+M+C=0+5+5=10)，(5，5，1)表示有5个传教士、5个野人在左岸，船在左岸。
(3) 启发式函数3： 


f(n)=g(n)+ML+CL－2BL，两岸的传教士数目≥野人数目（当传教士与野人在一起时）

∞，其他

其中，
g(n)表示搜索树的深度，也是船只往返的次数。启发函数为h(n)=M+C－2B，此时对应的搜索图如图3．8所示。



图3．8启发式函数3对应的搜索图



3．2与/或图搜索
在问题求解过程中，往往需要将一个大的问题变换成若干个子问题，子问题又可分解成更小的子问题，这样一直分解到可以直接求解为止，全部子问题的解构成了整个问题的解，这样的问题求解过程称为问题的规约(Problem Reduction)。这也是一种搜索过程，不过现在在图中搜索到的解不只是一个节点或一条路径，而是一个搜索树。因为在问题分解成子问题后，对于解决原来的问题有3种可能： 
（1） 解决其中一个子问题就相当于解决原来的问题(分支之间是“或”关系)。
（2） 解决全部子问题才算解决原来的问题(分支之间是“与”关系)。
（3） 解决其中一些子问题就相当于解决原来的问题(分支之间“与”“或”关系都有)。

这样从原问题到子问题之间就存在AND(全部解决)和OR(部分解决)的关系。这就是“与/或(AND/OR)图”的来由。
3．2．1问题归约求解方法和“与/或图”
在与/或图中，要求解的大问题称为初始问题，可直接求解的问题为本原问题。一般来说，使用归约方法求解问题需要具备三大要素： 
(1) 初始问题的描述。
(2) 一组将问题变换成子问题的变换规则。
(3) 一组本原问题的描述。
例3．6符号积分问题。
(1) 初始问题描述： ∫f(x)dx。
(2) 变换规则： 积分规则。
(3) 本原问题： 可直接求原函数的积分，如∫sin(x)dx、∫exdx。
求解高等数学中的积分问题是典型的与/或图的搜索，一个积分问题可能有不同的求解方法，这些不同的解法之间就是“或”的关系； 利用某些积分规则，例如，使用和式分解规则： ∫（f(x)+g(x)）dx→∫f(x)dx+∫g(x)dx，将一个积分问题分解成两个积分问题，这两个积分问题都要求解出来，才能算得上原积分问题求解完成了，这两个积分问题之间就是“与”的关系。
从初始问题出发，分解子问题以及子问题的子问题，直至把初始问题归约成为一个本原问题的集合，这就是问题规约方法求解问题的基本途径。
3．2．2与/或图的构造方法
将问题求解归约为与/或图的搜索时，作如下规定： 
（1） 与/或图中对应于原始问题描述的节点为初始节点； 
与/或图中对应于本原问题的节点叫终叶节点。
（2） 可解节点的可递归定义为： 
① 终叶节点是可解节点； 
② 若n为一非终叶节点，且含有“或”后继节点，则只有当后继节点中至少有一个是可解节点时，n才可解； 
③ 若n为一非终叶节点，且含有“与”后继节点，则只有当后继节点全部可解时，n才可解。

（3） 不可解节点的可递归定义为： 
① 没有后继节点的非终叶节点为不可解； 
② 若n为一非终叶节点，且含有“或”后继节点，则仅当全部后继节点为不可解时，n不可解； 
③ 若n为一非终叶节点，且含有“与”后继节点，则至少有一个后继节点为不可解时，n为不可解。
（4） 与或图搜索费用的计算： 设从当前节点n到目标集Sg费用估计为h(n)。
① 若n∈Sg，则h(n)=0； 
② 若n有一组由“与”弧连接的后继节点{n1,n2,…，ni},则

h(n)=c1+c2+…+ci+h(n1)+h(n2)+…+h(ni)

其中，ck为n到nk弧的费用；
③ 若n既有“与”弧又有“或”弧连接的后继，则一个“与”弧算作一个“或” 后继，再取各“或”弧所连接的后继中费用最小者为n的费用。
3．2．3与/或图的搜索过程
对或图搜索，若搜索到某个节点时，则无论n是否生成了后继节点，n的费用都是由本身的状态决定的。但对与/或图则不同，其费用计算的规则是： 
（1） n未生成后继节点时，费用由n本身的估计值决定，这个费用是给定的一个估计值； 
（2） n已生成后继节点时，费用由n的后继节点的费用决定，即利用3．2．2中搜索费用计算的第（1）~（4）步的方法进行计算。
因为后继节点代表分解的子问题，子问题的难易程度决定原问题求解的难易程度，所以不再考虑n在之前估计的难易程度。因此当决定了某个路径时，要将后继节点的估计值往回传送。
下面举例说明这个过程。
例3．7图3．9为一个与/或图的搜索过程。
（1） A是唯一节点。
（2） 扩展A后，得到节点B、C和D，因为B、C的耗费为9，D的耗费为6，所以把到D的边标志为出自A最有希望的边。
（3） 选择对D的扩展，得到E和F的与弧，其耗费估计值为10。此时回退一步后，发现与弧BC比D更好，所以将弧BC标志为目前最优路径。
（4） 在扩展B后，再回传值发现弧BC的耗费为12(6+4+2)，所以D再次成为当前最优路径。 


图3．9一个与/或图的搜索过程


最后求得的耗费为： f(A)=min(12，4+4+2+1)=11。
以上搜索过程由两个步骤组成： 
(1)  自顶向下，沿当前最优路径产生后继节点。
(2) 自底向上，作估计值修正，再重新选择最优路径。
与/或图搜索仅对不含循环路径的图进行操作，因为循环路径表示循环推理，它不可能对问题进行规约。
例如： 





表示求解x可以归结为求y，求y又可以归结为求x，因而两者都不可能求解。
3．2．4与/或图搜索算法AO*
AO*算法用一个阈值Futility作为不可解节点的标志，用h′作为静态估计函数，用mark作为当前最优路径的标记。
AO*算法步骤为： 
（1） 令G仅由初始状态节点组成，称为Init，计算h′(Init)。
（2） 在Init标志solved之前或h′(Init)变成大于Futility之前，执行以下步骤： 
① 沿始于Init的已带标志的弧，选出当前沿标志路上未扩展的节点之一扩展(即求后继节点)，此节点称为node。
② 生成node的后继节点。
若无后继节点，则令h′(node)=Futility，说明该节点不可解。
若有后继节点，称为successor，对每个不是node祖先的后继节点(避免回路)，执行以下步骤： 
i 将successor加入G。
ii 若successor∈Sg，则标志successor为solved，且令h′(successor)=0。
iii 若successorSg，则求h′(successor)。
③ 自底向上作评价值修正，重新挑选最优路径。
令S为一节点集。
S＝｛已标志为solved的点，或h′值已改变，需回传至其先辈节点的节点｝
令S初值＝｛node｝，重复以下过程，直到S为空时停止。
i 从S中挑选一节点，该节点的后辈点均不在S中(保证挑选出的要处理的点都在其先辈节点之前作处理)，此节点称为current，并从S中删除。
ii 计算始于current的每条弧及其后继节点的费用，即每条弧本身的费用加上弧末端节点h′ 的值(注意按与或图搜索费用的计算规则，区分与弧和或弧的计算方法)，并从中选出极小费用的弧作为h′(current)的新值。
iii 将费用最小弧标志为出自current的最优路径。
iv 若current与新的带标志的弧所连接的点均标志为solved，则current标志为solved。
v 若current已标志为solved或current的费用已改变，则需要往回传，因此要将current的所有先辈节点加入S中。
例3．8 以图3．10为例，仅跟踪AO*算法的若干步骤。
2．3．1步S={A}
2．3．2步current＝A； 
由于有A→B and C的弧，
current的费用=1+1+h′(B)+h′(C)=9
由有A→D的弧，current的费用=1+5=6
(3)(4)(5)A的费用=min(9，6)=6； 标记A→D为最优路径。 
(9)

(10)由step2．2．1，node=D，扩展D得successor={E，F}，继续step2．3，D的耗费估计已经改变为10，向上回传，导致A的耗费为min(9，10)=9，所以，最优路径为
(3)(4)A→BC弧。
h′(E)=4h′(F)=4 
图3．10跟踪AO*算法耗费估计向上回传的过程
3．2．5用AO*算法求解一个智力问题
有这样一个智力问题： 有12枚硬币，凡轻于或重于真币者，即为假币(只有一枚假币)，要设计一个搜索算法来识别假币并指出它是轻于还是重于真币，且利用天平的次数不多于3次。
该问题的困难之处在于问题要求只称3次就要找到假币，否则就承认失败。如果称法不得当，使得留下的未知币太多，就不可能在3次内称出假币。 因此，每称一次，我们希望尽可能地得到关于假币的信息。
利用人工智能的求解方法解决这个问题首先必须解决下面两个问题:
（1） 问题表示方法，记录和描述问题的状态；
（2） 求解程序如何对某种称法进行评价。
下面就对使用AO*算法求解这个智力难题进行讨论。
1． 问题的表示
要把这个问题在计算机中表示出来，就要分析构成该问题状态的因素有哪些： 首先是硬币可能有哪些状态； 然后是使用天平每称一次后，有关硬币的状态会发生什么样的变化； 最后是每称一次后，必须保存所剩的使用天平的次数。
可将硬币的重量状态分为4种类型:
（1） 标准型(Standard)，标记为S；
（2） 轻标型(Light or Standard)，标记为LS；
（3） 重标型(Heavy or Standard)，标记为HS；
（4） 轻重标准型(Light or Heavy or Standard)，标记为LHS。
一个硬币为LHS状态，那是我们对它一无所知； LS和HS状态是有可能为轻的或有可能为重的，当然也可能是标准的； S状态是已知为标准的。
例如，一次称两个硬币，如果天平偏向左边，则天平左盘中的硬币属于重标型，而右盘中的硬币属于轻标型，其余不在天平上的属于标准型(因为只有一个假币)。每称一次，硬币的重量状态可能会从一种类型转变为另一种类型。问题处于初始状态时，所有的硬币均属于LHS型。
综上所述，问题的状态空间可表示成一个五元组:

(lhs，ls，hs，s，t)

其中，前4个元素表示当前这4种类型硬币的个数，t表示所剩称硬币的次数。在这样的状态空间表示下，有:
初始状态： (l2，0，0，0，3)
目标状态： sg1： (0，1，0，11，0)和sg2： (0，0，1，11，0) 

其中，sg1和sg2分别表示最后找到一个轻的或找到一个重的硬币，其余11个为标准硬币。
2． 如何利用AO*算法求解
利用AO*算法求解问题需要找出如下要素:
(1)  初始问题的描述；
(2)  一组将问题变换成子问题的变换规则；
(3)  一组本原问题描述。
该问题的初始问题前面已经表示出来了，本原问题就是两个目标状态。下面要定义一组转换规则。这里的转换规则就是每称一次，要考虑如何取硬币放到天平上，然后称完后，根据天平的状态，硬币的重量状态可能会从一种类型转变为另一种类型。 
首先考虑如何取硬币的问题。设当前的状态为(lhs，ls，hs，s，t)，用函数PICKUP(［lhs1，ls1，hs1，s1］,［ lhs2，ls2，hs2，s2］)表示本次分别从(lhs，ls，hs，s)中取出lhs1、ls1、hs1、s1个硬币放到天平的左边，取出lhs2、ls2、hs2、s2个硬币放到天平的右边。对于PICKUP应默认有如下性质成立:
（1） 0<lhs1+ls1+hs1 +s1=lhs2 +ls2 +hs2 +s2 ≤6，即天平两边的硬币数相等且小于等于6； 
（2） lhs1+lhs2 ≤lhs∧ls1+ls2≤ls ∧ hs1+hs2 ≤hs ∧ s1+s2≤s，即取出的硬币数小于等于相应类型原有的硬币数。 
然后令PICKUP()等于-1、0、1 分别表示天平左倾斜、平衡和右倾斜。在这个定义下，有如下转换规则。
（1） 左倾斜规则： 

if PICKUP(［lhs1，ls1，hs1，s1］,［ lhs2，ls2，hs2，s2］)=- 1∧ (lhs，ls，hs，s,t)

then(lhs′，ls′，hs′，s′，t-1)；

其中，s′=s+ ls-ls2 + hs-hs1 + lhs - (lhs1+lhs2) ； ls′=ls2+lhs2 ； hs′=lhs1+hs1； lhs′=0。
这4个公式的含义分别是： 若天平左倾,则在左天平的状态为LS的硬币、在右天平的状态为HS的硬币和未放到天平上的硬币都是标准的，即hs2+ls1+ (lhs-lhs1-lhs2)+(ls-ls1-ls2)+(hs-hs1-hs2) 个硬币的状态都改变为标准型； 右天平原有的ls2个轻标准型的硬币仍然为轻标准型，右天平的lhs2个轻重标准型硬币改变为轻标准型； 左天平原有的hs1个重标准型的硬币仍然为重标准型，左天平的lhs2个轻重标准型硬币改变为重标准型； 只要不平衡，就不存在LHS型的硬币，天平上的硬币可以确定为LS或HS型，天平下的硬币可以确定为S型，这时lhs′=0。 
（2） 平衡规则： 

if PICKUP(［lhs1，ls1，hs1，s1］,［ lhs2，ls2，hs2，s2］)=0 ∧ (lhs，ls，hs，s,t)

then(lhs′，ls′，hs′，s′，t-1)；

其中，s′=s+ls1+ls2+hs1+hs2 + lhs1+lhs2； ls′=ls-ls1-ls2； hs′=hs-hs1-hs2； lhs′=lhs- lhs1-lhs2。
这4个公式的含义分别是： 若天平平衡，则所有在天平上的硬币都是标准的，即有ls1+ls2 + hs1+hs2 + lhs1+lhs2个硬币的状态都改变为标准型； 左、右天平原有的轻标准型的硬币改变为标准型，所以从ls 中减去ls1和ls2； 左、右天平原有的重标准型的硬币改变为标准型，所以也要从hs 中减去hs1和hs2； 在平衡情况下，lsh型的硬币要减去左、右天平原有的轻重标准型的硬币，即lhs′=lhs- lhs1-lhs2。
（3） 右倾斜规则： 

if PICKUP(［lhs1，ls1，hs1，s1］,［ lhs2，ls2，hs2，s2］)=1∧ (lhs，ls，hs，s,t)

then(lhs′，ls′，hs′，s′，t-1)；

其中，s′=s+ ls-ls1 + hs-hs2 + lhs - (lhs1+lhs2)； ls′=ls1+lhs1 ； hs′=lhs2+hs2； lhs′=0。
这4个公式的含义与L规则的含义类似： 若天平右倾，则在左天平上状态为HS的硬币和右天平上状态为LS的硬币以及未放到天平上的硬币都是标准的，即hs1+ls2+(lhs-lhs1-lhs2)+(ls-ls1-ls2)+(hs-hs1-hs2) 个硬币的状态都改变为标准型； 左天平原有的ls1个轻标准型的硬币仍然为轻标准型，左天平的lhs1个轻重标准型硬币改变为轻标准型； 右天平原有的重标准型的hs2个硬币仍然为重标准型，右天平的lhs2个轻重标准型硬币改变为重标准型； 因为不平衡，lhs′=0。
以上3个规则中t-1表示所剩使用天平的次数减少了一次。
3． 如何在问题空间中搜索
该问题可以用AO*算法求解，主要是基于这样的背景： 用PICKUP()填入不同的参数表示一种选取方法，不同的选取方法之间是或的关系，当选定一组PICKUP的参数后，就必须考虑它的值为 -1、0、1时下层的节点都可解，则3种情况之间的关系为“与”的关系。这说明该问题的搜索图是与或图，图3．10给出了这个问题的搜索图。
用于该算法的评价函数可设置为： 

h(lhs，ls，hs，s，t)=ls+hs+ lhs-1


显然有： 

h(0，1，0，11，0)=0 和h(0，0，1，11，0)=0

即 h(sg1)=h(sg2)=0。
由于问题的本原问题对应的节点是可解节点，因此sg1、sg2为可解节点。不可解节点可定义为： 如果节点n=(lhs，ls，hs，s，t)中t=0且(lhs，ls，hs，s)不属于{(0，1，0，11)，(0，0，1，11)}，则n为不可解节点。
作好上述准备工作后，就可用AO*算法进行求解，图3．10就是用AO*算法得到的一个解图。
用AO*算法可以很快地接近目标，因为对于某种选法，它的节点层数不超过三层，且某个节点只要有一个下层的and节点为不可解节点，则马上推出该节点为不可解节点。例如，考虑PICKUP(［6，0，0，0］，［6，0，0，0］)，它的值只可能是1或-1，它的下层节点实际只有一个为(0，6，6，0，2)的节点。对于它的下两层的节点的搜索可很快导出都是不可解节点。因而导出PICKUP(［6，0，0，0］，［6，0，0，0］)不是一种正确的取法。同样的道理也可以很快导出PICKUP(［1，0，0，0］，［1，0，0，0］)、PICKUP(［2，0，0，0］，［2，0，0，0］)等都不是正确的取法。因为使用AO*算法抛去了大量的不可解的分支，所以可以很快地找出所有解。


图3．10利用AO*算法求解12硬币问题的解图


习题3
3．1对N=5、k≤3的传教士和野人问题，定义两个h函数(非零)，并给出用这两个启发函数的A算法搜索图。讨论用这两个启发函数求解该问题时是否得到最优解。
3．2什么是图搜索过程？其中，重排Open表意味着什么，重排的原则是什么？
3．3什么是A*算法？它的评价函数如何确定，它与A算法有什么区别？
3．4证明Open表上具有f(n)＜f*(s)的任何节点n，最终都将被A*选择去扩展。
3．5怎么用一架天平3次称出13个硬币中唯一的然而未知轻重的假币(已知有标准的硬币)？
3．6A*算法有哪些性质？
3．7请给出通用图搜索算法中，Open表和Closed表所表示的一般的含义。
3．8A*算法在什么条件下，执行效果最好？为什么？ 
3．9“或图”和“与或图”各对应什么样的实际背景？所对应的最优搜索算法是什么？
3．10请给出使用天平4次从39个硬币中找出唯一的未知轻重的假币的方案。
3．11在问题的分析过程中，将一个大的复杂问题分解为一组简单的问题，这组简单的问题解决了，则大的复杂问题解决了，这是什么逻辑关系？应该分解成什么样的搜索树？如果将一个较难的问题变换为容易的、等价的或等效的问题，变换后的问题解决了则原来的问题解决了，这是什么逻辑关系？应该分解成什么样的搜索树？
3．12请写出可解和不可解节点的递归定义。