第八章图搜索技术

1、1李伟生李伟生信科大厦信科大厦19楼楼Tel：2内容提要内容提要: : 8.1 8.1 状态图搜索策略状态图搜索策略 8.2 8.2 启发式搜索启发式搜索 8.3 8.3 与或图搜索与或图搜索 8.4 8.4 博弈树搜索博弈树搜索3l迷宫问题：把迷宫每一个位置以及入口和出口都作为节点，把通道作为边，则迷宫可由一个有向图表示。走迷宫实际就是从该有向图的初始节点（入口）出发，寻找目标节点（出口）的问题，或者是寻找通向目标节点（出口）的路径的问题。l8数码问题：在一个3*3的方格棋盘上放置着1，2，3，4，5，6，7，8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与

2、空格相邻的数码才可以移入空格。问题：对于指定的初始棋局和目标棋局，给出数码的移动序列。 如果把一个棋局作为一个节点，相邻的节点就可以通过移动数码，一个一个地产生出来。这样，所有节点就可由它们相邻的关系连成一个有向图，图中的一条边就对应一次数码移动，反之，一次数码移动就对应着图中的一条边，边也就代表着一个移动规则或者移动规则的一次执行。该问题也就是要在该有向图中寻找目标节点，或找一条从初始节点到目标节点的路径问题。4l上述两个问题虽然内容不同，但抽象地看，它们都是在某个有向图中寻找目标或路径的问题。我们把这种描述问题的有向图称为状态空间图，简称状态图。58.1.1 图搜索策略的定义 8.1.2

3、图搜索算法中的几个重要名词术语 8.1.3 图搜索(GRAPH SEARCH)的一般过程 8.1.4 图搜索方法分析 6l图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。l研究图搜索的一般策略，能够给出图搜索过程的一般步骤。 7l（1）OPEN表与CLOSED表l（2）搜索(状态)图与搜索树 登记当前登记当前待考查的待考查的节点节点记录考查记录考查过的节点过的节点父节点编号节点编号父节点编号节点OPENCLOSED8(1) 建立一个只含有起始节点S的搜索图G，把S

4、放到一个叫做OPEN的未扩展节点表中。(2) 建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3) LOOP：若OPEN表是空表，则失败退出。(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5) 若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。(6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。9(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员

5、加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8) 按某一或按某个探试值，重排OPEN表。(9) GO LOOP。 10开始开始把S放入OPEN表把S放入OPEN表把第一个节点(n)从OPEN移至CLOSE表把第一个节点(n)从OPEN移至CLOSE表OPEN为空表OPEN为空表n为目标节点n为目标节点把n的后继节点放入OPEN表的末端，把n的后继节点放入OPEN表的末端，提供返回节点的指针提供返回节点的指针修改指针方向修改指针方向重排OPEN表重排

6、OPEN表失败失败成功成功11 图搜索过程的第8步（按某一方式重排OPEN表）对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。 1.

7、 宽度优先搜索2. 深度优先搜索121)定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。 (breadth-first search) 2)特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。 13 (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。(5) 把n的所有后继节点放到OPEN表的末

8、端，并提供从这些后继节点回到n的指针。(6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。 14(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。 15

9、 宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。 宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止)。 16把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：2 8 32 8 31 1 4 47 6 57 6 51 2 31 2 38 8 4 47 6 57 6 5172 8 3417 6 51 2 38 47 6

10、52 8 3 1 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 6 4 7 52 8 31 6 47 52 81 4 37 6 52 8 31 4 57 68 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 8 7 6 52 8 3 6 41 7 52 8 31 67 5 42 81 4 37 6 52 8 31 4 57 68 32 1 47 6 58 1 3427 6 52 8 37

11、 46 1 52 8 37 1 46 51 2 37 8 4 6 5181)定义在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。2)特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。 193)深度界限为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度棗深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。4)含有深度界限的深度优

12、先搜索算法请课后自学。201.为什么需要启发式搜索 盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。2.定义 进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。 213.启发式搜索策略有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。

13、224.估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 。f(n)表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 231、定义、定义用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)

14、或最佳优先搜索 best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。被选为扩展的节点，是估价函数最小的节点。 24l选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。 25 (1) 把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。 (2) 如果OPEN是个空表，则失败退出，无解。 (3) 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选

15、择此目标节点，否则就选择其中任一个节点作为节点i. (4) 把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。 (5) 如果i是个目标节点，则成功退出，求得一个解。 (6) 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： 26(6) 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： (a)计算f(j)。 (b)如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。 (c)如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节

16、点在表中的f值。如果新的f值较小，则 (i) 以此新值取代旧值。 (ii) 从j指向i，而不是指向它的父辈节点。 (iii) 如果节点j在CLOSED表中，则把它移回OPEN表(7) 转向(2)，即GO TO(2)。 27宽度优先搜索和深度优先搜索统统是有序搜索技术的特例。 有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。 28采用了简单的估价函数 f(n)=d(n)+W(n)其中：d(n)是搜索树中节点

17、n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此，起始节点棋局2 8 31 6 47 5的f值等于0+4=4。 1 2 31 2 38 8 4 47 6 57 6 5292 8 31 6 47 51 2 38 47 6 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 51 2 37 8 4 6 51 2 3 8 47 6 530lA*算法是一种有序搜索算法

18、，其特点在于对估价函数的定义上。 31令k(ni，nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。 于是，从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n,ti)给出。 令h*(n)表示整个目标节点集合ti上所有k(n,ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n，函数h*没有定义)。 32定义g*为 g*(n)=k(S,n)定义函数f*，使得在任一节点n上其函数值f*(n

19、)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和，即f*(n)=g*(n)+h*(n) 33希望估价函数f是f*的一个估计，此估计可由下式给出：f(n)=g(n)+h(n)其中：g是g*的估计；h是h*的估计。对于g(n)来说，一个明显的选择就是搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)g*(n)。h*(n)的估计h(n)依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信

20、息相似。把h叫做启发函数。 34定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据 f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。 35树式搜索树式搜索穷举式穷举式盲目搜索盲目搜索启发式搜索启发式搜索宽度优先宽度优先深度优先深度优先A算法A算法A*算法A*算法线式搜索线式搜索36 为了便于分析，我们仅考虑二阶梵塔(即只有两个金盘)问题。 设

21、有三根宝石杆，在1号杆上穿有A、B两个金盘，A小于B，A位于B的上面. 要求把这两个金盘全部移到另一根杆上，而且规定每次只能移动一个盘子，任何时刻都不能使B位于A的上面。37 设用二元组(SA，SB)表示问题的状态， SA表示金盘A所在的杆号， SB表示金盘B所在的杆号。这样，全部可能的状态有9种，可表示如下：这里的状态转换规则就是金盘的搬动规则，分别用A(i，J)及B(i，J)表示：A(i，J)表示把A从第i号杆移到第J号杆上；共有l 2个操作，它们分别是: A(1，2)，A(1，3)，A(2，1)，A(2，3)，A(3，1)，4(3，2)，B(1，2)，B(1，3)，B(2，1)，B(2，

22、3)，B(3，1)，B3，2)3839在现实世界中，经常会遇到这样的问题：一个问题可以有几种求解方法，只要其中一种方法可以求解问题，则该问题被求解。也就是说，对求解该问题来说，方法之间是“或”的关系。但在用每一种方法求解时，又可能需要求解几个子问题，这些子问题必须全部求解，才可能用该方法求解原始问题。也就是说，这些子问题之间是“与”的关系。此类问题可以用与或图来表示。 40它表示，如果要求解n0，可以求解n1，或者求解n4、n5，也就是说，对于n0来说，n4和n5是与的关系，而n1和n4、n5的与之间是或的关系。其他节点之间也具有类似的关系。一个节点与它的k个与子节点间用下图的形式连接，称为k

23、连接符。 41从图可以看出，节点n0有两个连接符：1-连接符指向节点n1；2-连接符指向节点集n4，n5。该2-连接符还用一小段圆弧括起来（对k1的k-连接符都应有小圆弧标记），以表示子节点间与的关系。可以看出这种标记法在节点间具有明确的关系。显然若用原先的术语，则对父节点n0来说，n4、n5是两个与节点，而n1可称为或节点；而n8既是n5的一个与节点，又是n4的一个或节点，混淆难于避免。另外也把图中没有任何父节点的节点叫根节点，没有任何后继节点的节点叫端节点或叶节点。42在普通图中，目标用一个节点表达，而在与或图中，目标则表现为一个节点的集合，该集合中由一些子目标节点组成。值得指出的是，解图

24、不一定要求到达目标集中的每一个子目标节点，而只要求解图的端节点是目标集中的节点即可。也就是说，解图中的端节点是目标集的子集即可。 43与或图中某一个节点n到节点集N的一个解图类似于普通图中的一条解路径。解图的求法是：从节点n开始，正确选择一个外向连接符，再从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。44在与或图是无环（即不存在这样的节点-其后继节后同时又是它的祖先）的假定下，解图可递归定义如下：定义：一个与或图G中，从节点n到节点集N的解图记为G， G是G的子图。若n是N的一个元素，则G由单一节点组成；若n有一个

25、指向节点n1，nk的外向连接符K，使得从每一个ni到N有一个解图（i=1，k），则G由节点n，连接符K，及n1，nk中的每一个节点到N的解图所组成；否则n到N不存在解图。 45递归定义局部图：定义：单一节点是一个局部图；对于一个局部图的任意叶节点n，选择一个n的外向连接符K，则该局部图、外向连接符K，以及K所连接的n的后继节点一起组成的图，仍然组成一个局部图。 46与或图一般表示问题的变换过程（而不是状态变换）。具体讲，它是从原问题出发，通过运用某些规则不断进行问题分解（得到与分支）和变换（得到或分支），而得到一个与或图。换句话说，与或图的节点一般代表问题。那么，整个图就表示问题空间。与或图中

26、的父节点与其子节点服从逻辑上的与、或运算关系。所以，与或图表示的问题是否有解，要进行逻辑判断，与或图的搜索也受逻辑的制约。47与或图也是一个三元组(Q0,F,Qn)Q0,表示初始问题，F表示问题变换规则集， Qn表示本原问题集。例如：积分公式，就是一些典型的问题分解和变换问题。所以，一般求不定积分就可用与或图来描述。48123三阶 Hanoi塔可分解为下面三个子问题：1） 把A、B盘从1号杆移到2号杆。2） 把C盘从1号杆移到3号杆。3） 把A、B盘从2号杆移到3号杆。其中，子问题1）、3）又可分解为三个子问题。49(i,j,k) i: C盘所在杆号， j: B盘所在杆号， k: A盘所在杆号

27、。(1,1,1)(3,3,3)(1,1,1)(1,2,2)(1,2,2)(3,2,2)(3,2,2)(3,3,3)(1,1,1)(1,1,3)(1,1,3)(1,2,3)(1,2,3)(1,2,2)(3,2,2)(3,2,1)(3,2,1)(3,3,1)(3,3,1)(3,3,3)50这里所讲的博弈，指的是类似于象棋这样的游戏问题。这类问题有以下一些特点：（1）双人对弈，对垒的双方轮流走步。（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。（3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或

28、者双方和棋。51博弈问题为什么可以用与或图表示呢？可以这样来看待这个问题：当轮到我方走棋时，只需从若干个可以走的棋中，选择一个棋走就可以了。从这个意义上说，若干个可以走的棋是“或”的关系。而对于轮到对方走棋时，对于我方来说，必须能够应付对手的每一种走棋。这就相当于这些棋是“与”的关系。因此，博弈问题可以看成是一个与或图，但是与一般的与或图并不一样，是一种特殊的与或图。52博弈一向被认为是富有智能行为的游戏，因而很早就受到人工智能界的重视，早在60年代就已经出现若干博弈程序，并达到一定水平。博弈问题的研究还不断提出一些新的研究课题，从而也推动了人工智能研究的发展。对于单人博弈的一些问题，可用一般

29、的搜索技术进行求解，本节着重讨论双人完备信息这一类博弈问题的搜索策略。由于双人博弈可用与或树（或图）来描述，因而搜索就是寻找最佳解树（图）的问题。53所谓双人完备信息，就是两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。对弈的结果是一方赢（另一方则输），或者双方和局。这类博弈的实例有：一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。对于带机遇性的任何博弈，因不具有完备信息，不属这里讨论范围，但有些论述可推广到某些机遇博弈中应用。54博弈问题可以用产生式系统的形式来描述，例如中国象棋，综合数据库可规定为棋盘上棋子各种位置布局的一种描述，

30、产生式规则是各类棋子合法走步的描述，目标则可规定为将（帅）被吃掉，规则作用于数据库的结果便生成出博弈图或博弈树。55极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的-剪枝搜索方法，就是从这一方法发展而来的。首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大

31、的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。56想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应.这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。极小极大搜索方法，模拟的就是人的这样一种思维过程当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶

32、节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。57在博弈问题中，每一个棋局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。据统计，西洋跳棋完整的博弈树约有1040个节点。试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树，然后进行极小极大分析，找出当前最好的行动方案。在此之后，再在已选定的分支上扩展一定深度，再选最好的行动方案。如此进行下去，直到取得胜败的结果为止。至于每次生成博弈树的深度，当然是越大越好，但由于受到存储空间的限制，只好根据实际情况而定。58在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果