第 3 章 图搜索与问题求解 3.1 状态图搜索 3.2 状态图搜索问题求解 3.3 与或图搜索 3.4 与或图搜索问题求解 3.5 博弈树搜索 习题三
3.1 状 态 图 搜 索 3.1.1 状态图 例3.1 走迷宫是人们熟悉的一种游戏, 如图3－1就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点, 把通道作为边, 则该迷宫可以由一个有向图表示(如图3-2所示)。 那么, 走迷宫其实就是从该有向图的初始节点(入口)出发, 寻找目标节点(出口)的问题, 或者是寻找通向目标节点(出口)的路径的问题。
图 3-1 迷宫图
图 3-2 迷宫的有向图表示
例 3.2 在一个3×3的方格棋盘上放置着1, 2, 3, 4, 5, 6, 7, 8八个数码, 每个数码占一格, 且有一个空格。 这些数码可在棋盘上移动, 其移动规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的初始棋局和目标棋局(如图3-3所示), 给出数码的移动序列。该问题称为八数码难题或重排九宫问题。 可以看出,图中的一条边(即相邻两个节点的连线)就对应一次数码移动,反之, 一次数码移动也就对应着图中的一条边。而数码移动是按数码的移动规则进行的。所以, 图中的一条边也就代表一个移动规则或者移动规则的一次执行。于是,这个八数码问题也就是要在该有向图中寻找目标节点, 或找一条从初始节点到目标节点的路径问题。
图 3-3 八数码问题示例
3.1.2 状态图搜索 1. 搜索方式 用计算机来实现状态图的搜索, 有两种最基本的方式： 树式搜索和线式搜索。 所谓树式搜索, 形象地讲就是以“画树”的方式进行搜索。 即从树根(初始节点)出发, 一笔一笔地描出一棵树来。准确地讲, 树式搜索就是在搜索过程中记录所经过的所有节点和边。 所以, 树式搜索所记录的轨迹始终是一棵“树”, 这棵树也就是搜索过程中所产生的搜索树。
所谓线式搜索, 形象地讲就是以“画线”的方式进行搜索。 准确地讲, 线式搜索在搜索过程中只记录那些当前认为是处在所找路径上的节点和边。所以,线式搜索所记录的轨迹始终是一条“线”(折线)。
线式搜索的基本方式又可分为不回溯的和可回溯的两种。 不回溯的线式搜索就是每到一个“叉路口”仅沿一条路继续前进, 即对每一个节点始终都仅生成一个子节点(如果有子节点的话)。 生成一个节点的子节点也称对该节点进行扩展。这样,如果扩展到某一个节点, 该节点恰好就是目标节点,则搜索成功；如果直到不能再扩展时, 还未找到目标节点,则搜索失败。可回溯的线式搜索也是对每一个节点都仅扩展一条边,但当不能再扩展时, 则退回一个节点, 然后再扩展另一条边(如果有的话)。 这样, 要么最终找到了目标节点, 搜索成功；要么一直回溯到初始节点也未找到目标节点, 则搜索失败。
由上所述可以看出, 树式搜索成功后, 还需再从搜索树中找出所求路径, 而线式搜索只要搜索成功, 则“搜索线”就是所找的路径, 即问题的解。 那么, 又怎样从搜索树中找出所求路径呢？ 这只需在扩展节点时记住节点间的父子关系即可。 这样, 当搜索成功时, 从目标节点反向沿搜索树按所作标记追溯回去一直到初始节点, 便得到一条从初始节点到目标节点的路径, 即问题的一个解。
2. 搜索策略 由于搜索具有探索性, 所以要提高搜索效率(尽快地找到目标节点), 或要找最佳路径(最佳解)就必须注意搜索策略。 对于状态图搜索, 已经提出了许多策略, 它们大体可分为盲目搜索和启发式(heuristic)搜索两大类。 通俗地讲, 盲目搜索就是无“向导”的搜索, 启发式搜索就是有“向导”的搜索。那么, 树式盲目搜索就是穷举式搜索, 即从初始节点出发, 沿连接边逐一考察各个节点(看是否为目标节点), 或者反向进行；而线式盲目搜索, 对于不回溯的就是随机碰撞式搜索, 对于回溯的则也是穷举式的搜索。
启发式搜索则是利用“启发性信息”引导的搜索。 所谓“启发性信息”就是与问题有关的有利于尽快找到问题解的信息或知识。例如：“欲速则不达”、“知已知彼, 百战不殆”、 “学如逆水行舟不进则退”等格言, 就是指导人们行为的启发性信息。常识告诉我们,如果有向导引路, 则就会少走弯路而事半功倍。 所以, 启发式搜索往往会提高搜索效率, 而且可能找到问题的最优解。根据启发性信息的内容和使用方式的不同, 启发式搜索又可分为许多不同的策略, 如全局择优、局部择优、 最佳图搜索等等。 按搜索范围的扩展顺序的不同, 搜索又可分为广度优先和深度优先两种类型。对于树式搜索, 既可深度优先进行, 也可广度优先进行。对于线式搜索则总是深度优先进行。
3. 搜索算法 由于搜索的目的是为了寻找初始节点到目标节点的路径, 所以在搜索过程中就得随时记录搜索轨迹。为此, 我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点。显然, 对于树式搜索来说, CLOSED表中存储的正是一棵不断成长的搜索树； 而对于线式搜索来说, CLOSED表中存储的是一条不断伸长的折线, 它可能本身就是所求的路径(如果能找到目标节点的话)。 另一方面, 对于树式搜索来说, 还得不断地把待考查的节点组织在一起, 并做某种排列, 以便控制搜索的方向和顺序。 为此, 我们采用一个称为OPEN表的动态数据结构,来专门登记当前待考查的节点。
图 3-4 OPEN表与CLOSED表示例
树式搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。 步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2。
步6扩展N, 生成一组子节点, 对这组子节点做如下处理： (2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”, 则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示 )。 (3)对已存在于CLOSED表的节点(如果有的话), 做与(2)同样的处理, 并且再将其移出CLOSED表, 放入OPEN表重新扩展(为了重新计算代价)。 (4)对其余子节点配上指向N的返回指针后放入OPEN表中某处, 或对OPEN表进行重新排序, 转步2。
图 3-5 修改返回指针示例
说明： (1) 这里的返回指针也就是父节点在CLOSED表中的编号。 (2) 步6中修改返回指针的原因是, 因为这些节点又被第二次生成, 所以它们返回初始节点的路径已有两条, 但这两条路径的“长度”可能不同。 那么, 当新路短时自然要走新路。 (3) 这里对路径的长短是按路径上的节点数来衡量的, 后面我们将会看到路径的长短也可以其“代价”(如距离、 费用、 时间等)衡量。若按其代价衡量, 则在需修改返回指针的同时还要修改相应的代价值, 或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。
线式搜索算法： · 不回溯的线式搜索 步1 把初始节点So放入CLOSED表中。 步2 令N＝So。 步3 若N是目标节点,则搜索成功,结束。 步4 若N不可扩展,则搜索失败,退出。 步5 扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中, 令N＝N1, 转步3。
· 可回溯的线式搜索 步1 把初始节点So放入CLOSED表中。 步2令N＝So。 步3若N是目标节点, 则搜索成功, 结束。 步4 若N不可扩展, 则移出CLOSED表的末端节点Ne,若Ne＝So,则搜索失败, 退出。否则, 以CLOSED表新的末端节点Ne作为N,即令N＝Ne, 转步4。 步5扩展N, 选取其一个未在CLOSED表用出现过的子节点N1放入CLOSED表中, 令N＝N1,转步3。
需说明的是,上述算法仅是搜索目标节点的算法, 当搜索成功后, 如果需要路径, 则还须由CLOSED表再找出路径。找路径的方法是： 对于树式搜索, 从CLOSED表中序号最大的节点起,根据返回指针追溯至初始节点So,所得的节点序列或边序列即为所找路径；对于线式搜索, CLOSED表即是所找路径。
3.1.3 穷举式搜索 1. 广度优先搜索 广度优先搜索就是始终先在同一级节点中考查, 只有当同一级节点考查完之后, 才考查下一级节点。或者说,是以初始节点为根节点, 向下逐级扩展搜索树。所以,广度优先策略的搜索树是自顶向下一层一层逐渐生成的。
例 3.3 用广度优先搜索策略解八数码难题。 由于把一个与空格相邻的数码移入空格, 等价于把空格向数码方向移动一位。所以,该题中给出的数码走步规则也可以简化为： 对空格可施行左移、移、上移和下移等四种操作。 设初始节点So和目标节点Sg分别如图3-3的初始棋局和目标棋局所示, 我们用广度优先搜索策略, 则可得到如图3-6所示的搜索树。
图 3-6 八数码问题的广度优先搜索
广度优先搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败,退出。 步3 取OPEN表中前面第一个节点N放在CLOSED表中, 并冠以顺序编号n。 步4 若目标节点Sg=N,则搜索成功, 结束。 步5 若N不可扩展, 则转步2。 步6 扩展N, 将其所有子节点配上指向N的指针依次放入OPEN表尾部, 转步2。
其中OPEN表是一个队列,CLOSED表是一个顺序表,表中各节点按顺序编号, 正被考察的节点在表中编号最大。如果问题有解, OPEN表中必出现目标节点Sg,那么,当搜索到目标节点Sg时,算法结束,然后根据返回指针在CLOSED表中往回追溯,直至初始节点,所得的路径即为问题的解。 广度优先搜索亦称为宽度优先或横向搜索。这种策略是完备的,即如果问题的解存在, 用它则一定能找到解,且找到的解还是最优解(即最短的路径)。这是广度优先搜索的优点。但它的缺点是搜索效率低。
2. 深度优先搜索 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进, 直到不能再前进(到达叶子节点或受到深度限制)时, 才从当前节点返回到上一级节点, 沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
深度优先搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败, 退出。 步3 取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。 步4 若目标节点Sg=N, 则搜索成功,结束。 步5 若N不可扩展, 则转步2。 步6扩展N, 将其所有子节点配上指向N的返回指针依次放入OPEN表的首部, 转步2。
例3.4 对于八数码问题, 应用深度优先搜索策略, 可得如图3-7所示的搜索树。 图 3-7 八数码问题的深度优先搜索
深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝, 深度优先搜索如果误入无穷分枝(即深度无限), 则不可能找到目标节点。所以, 深度优先搜索策略是不完备的。另外, 应用此策略得到的解不一定是最佳解(最短路径)。
3. 有界深度优先搜索 广度优先和深度优先是两种最基本的穷举搜索方法, 在此基础上, 根据需要再加上一定的限制条件, 便可派生出许多特殊的搜索方法。例如有界深度优先搜索。 有界深度优先搜索就是给出了搜索树深度限制, 当从初始节点出发沿某一分枝扩展到一限定深度时, 就不能再继续向下扩展, 而只能改变方向继续搜索。节点x的深度(即其位于搜索树的层数)通常用d(x)表示, 则有界深度优先搜索算法如下：
步1 把So放入OPEN表中,置So的深度d(So)=0。 步3 取OPEN表中前面第一个节点N,放入CLOSED表中, 并冠以顺序编号n。 步4 若目标节点Sg=N, 则成功, 结束。 步5 若N的深度d(N)=dm(深度限制值), 或者若N无子节点, 则转步2。 步6 扩展N, 将其所有子节点Ni配上指向N的返回指针后依次放入OPEN表中前部, 置d(Ni)=d(N)+1,转步2。
3.1.4 启发式搜索 1. 问题的提出 从理论上讲, 似乎可以解决任何状态空间的搜索问题,但实践表明,穷举搜索只能解决一些状态空间很小的简单问题, 而对于那些大状态空间问题, 穷举搜索就不能胜任了。因为大空间问题往往会导致“组合爆炸”。 例如梵塔问题, 当阶数较小(如小于6)时, 在计算机上求解并不难, 但当阶数再增加时, 其时空要求将会急剧地增加。
例如当取64时, 则其状态空间中就有364=0.94*10３０个节点,最短的路径长度(节点数)=264-1≈2×1019,这是现有的任何计算机都存放不下,也计算不了的。又如博弈问题, 计算机为了取胜, 它可以将所有算法都试一下,然后选择最佳走步。找到这样算法并不难, 但计算时的时空消耗却大得惊人。例如：就可能有的棋局数讲,一字棋是9!≈3.6×105, 西洋棋是1078,国际象棋是10120,围棋是10761。假设每步可以选择一种棋局,用极限并行速度(10-104秒/步)计算, 国际象棋的算法也得1016年,即1亿亿年才可以算完。
2. 启发性信息 启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分, 启发性信息一般可分为以下三类： (1) 用于扩展节点的选择, 即用于决定应先扩展哪一个节点, 以免盲目扩展。 (2) 用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。 (3) 用于删除节点的选择,即用于决定应删除哪些无用节点, 以免造成进一步的时空浪费。
例如, 由八数码问题的部分状态图可以看出, 从初始节点开始, 在通向目标节点的路径上, 各节点的数码格局同目标节点相比较, 其数码不同的位置个数在逐渐减少, 最后为零。 所以, 这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息, 利用这个信息就可以指导搜索。 可以看出, 这种启发性信息属于上面的第一种类型。 需指出的是,不存在能适合所有问题的万能启发性信息, 或者说, 不同的问题有不同的启发性信息。
3. 启发函数 在启发式搜索中,通常用所谓启发函数来表示启发性信息。 启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数, 通常记为h(x)。 如何定义一个启发函数呢？启发函数并无固定的模式, 需要具体问题具体分析。通常可以参考的思路有：一个节点到目标节点的某种距离或差异的度量；一个节点处在最佳路径上的概率；或者根据经验的主观打分，等等。例如,对于八数码难题,用h(x)就可表示节点x的数码格局同目标节点相比数码不同的位置个数。
4. 启发式搜索算法 1) 全局择优搜索 全局择优搜索就是利用启发函数制导的一种启发式搜索方法。该方法亦称为最好优先搜索法, 它的基本思想是：在OPEN表中保留所有已生成而未考察的节点, 并用启发函数h(x)对它们全部进行估价,从中选出最优节点进行扩展,而不管这个节点出现在搜索树的什么地方。
全局择优搜索算法如下： 步1 把初始节点So放入OPEN表中,计算h(So)。 步2 若OPEN表为空,则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以序号n。 步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2。 步6 扩展N, 计算每个子节点x的函数值h(x), 并将所有子节点配以指向N的返回指针后放入OPEN表中, 再对OPEN表中的所有子节点按其函数值大小以升序排序,转步2。
图 3-8 八数码问题的全局择优搜索
例 3.5 用全局择优搜索法解八数码难题。 初始棋局和目标棋局同例3。 解 设启发函数h(x)为节点x的格局与目标格局相比数码不同的位置个数。以这个函数制导的搜索树如图3-8所示。图中节点旁的数字就是该节点的估价值。由图可见此八数问题的解为： So, S1, S2, S3, Sg。
2) 局部择优搜索 局部择优搜索与全局择优搜索的区别是, 扩展节点N后仅对N的子节点按启发函数值大小以升序排序, 再将它们依次放入OPEN表的首部。 故算法从略。
3.1.5 加权状态图搜索 1. 加权状态图与代价树 例 3.6 图3-9(a)是一个交通图,设A城是出发地,E城是目的地, 边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。
图 3-9 交通图及其代价树
可以看出, 这个图与前面的状态图不同的地方是边上附有数值。它表示边的一种度量(此例中是交通费, 当然也可以是距离)。一般地, 称这种数值为权值, 而把边上附有数值的状态图称之为加权状态图或赋权状态图。 显然,加权状态图的搜索与权值有关, 并且要用权值来导航。 具体来讲,加权状态图的搜索算法, 要在一般状态图搜索算法基础上再增加权值的计算与传播过程, 并且要由权值来确定节点的扩展顺序。
同样, 为简单起见,我们先考虑树型的加权状态图——代价树的搜索。所谓代价,可以是两点之间的距离、交通费用或所需时间等等。通常用g(x)表示从初始节点So到节点x的代价, 用c(xi,xj)表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有 g(xj)＝g(xi)＋c(xi, xj) 而 g(So)＝0
2. 分支界限法(最小代价优先法) 其基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察, 而不管这个节点在搜索树的什么位置上。 可以看出,这种搜索法与前面的最好优先法(即全局择优法)的区别仅是选取扩展节点的标准不同,一个是代价值g(x)(最小),一个是启发函数值h(x)(最小)。这就是说, 把最好优先法算法中的h(x)换成g(x)即得分支界限法的算法。所以,从算法角度考虑, 这两种搜索法实际是一样的。但二者在计算节点的代价值与启发函数值的方法是有差别的。
g(xj)＝g(xi)＋c(xi, xj) (xj是xi的子节点) 事实上, 一个节点x的代价值g(x)是从初始节点So方向计算而来的, 其计算方法为 g(So)＝0 g(xj)＝g(xi)＋c(xi, xj) (xj是xi的子节点) 而启发函数值h(x)则是朝目标节点方向计算的；g(x)与x的父节点代价有关,与子节点代价无关, 而h(x)与x的父、子节点的启发值均无关。
3. 最近择优法(瞎子爬山法) 同上面的情形一样,这种方法实际同局部择优法类似, 区别也仅是选取扩展节点的标准不同,一个是代价值g(x)(最小), 一个是启发函数值h(x)(最小)。这就是说,把局部择优法算法中的h(x)换成g(x)就可得最近择优法的算法。 现在我们用代价树搜索求解例3.6中给出的问题。 我们用分支界限法得到的路径为 A→C→D→E 这是一条最小费用路径(费用为8)。
f(x)＝g(x)＋h(x) 3.1.6 A算法和A*算法 1. 估价函数 1. 估价函数 利用启发函数h(x)制导的启发式搜索, 实际是一种深度优先的搜索策略。虽然它是很高效的, 但也可能误入歧途。所以, 为了更稳妥一些,人们把启发函数扩充为估价函数。估价函数的一般形式为 f(x)＝g(x)＋h(x) 其中g(x)为从初始节点So到节点x已经付出的代价, h(x)是启发函数。即估价函数f(x)是从初始节点So到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值之总和。
有时估价函数还可以表示为 f(x)＝d(x)＋h(x) 其中d(x)表示节点x的深度。 可以看出,ｆ(x)中的g(x)或d(x)有利于搜索的横向发展(因为g(x)或d(x)越小,则说明节点x越靠近初始节点So), 因而可提高搜索的完备性, 但影响搜索效率；h(x)则有利于搜索的纵向发展(因为h(x)越小,则说明节点x越接近目标节点Sg),因而可提高搜索的效率, 但影响完备性。所以,f(x)恰好是二者的一个折中。但在确定f(x)时,要权衡利弊, 使g(x)(或d(x))与h(x)的比重适当。 这样,才能取得理想的效果。例如,我们只关心到达目标节点的路径, 并希望有较高的搜索效率,则g(x)可以忽略。当然, 这样会影响搜索的完备性。
2.A算法 A算法是基于估价函数f(x)的一种加权状态图启发式搜索算法。其具体步骤如下： 步1 把附有f(So)的初始节点So放入OPEN表。 步2 若OPEN表为空, 则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。 步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2。
步6 扩展N,生成一组附有f(x)的子节点,对这组子节点做如下处理： (1)考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点,若有则删除之；对于其余节点, 也删除之,但由于它们又被第二次生成, 因而需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f(x)值, 修改原则是“抄f(x)值小的路走”。 (2)对其余子节点配上指向N的返回指针后放入OPEN表中, 并对OPEN表按f(x)值以升序排序, 转步2。
算法中节点x的估价函数f(x)的计算方法是 f(xj)＝g(xj)＋h(xj) ＝g(xi)＋c(xi, xj)＋h(xj) (xj是xi的子节点) 至于h(x)的计算公式则需由具体问题而定。 可以看出,A算法其实就是对于本节开始给出的图搜索一般算法中的树式搜索算法, 再增加了估价函数f(x)的一种启发式搜索算法。
h(x)≤h*(x) 3.A*算法 如果对上述A算法再限制其估价函数中的启发函数h(x)满足： 对所有的节点x均有 其中h*(x)是从节点x到目标节点的最小代价, 即最佳路径上的实际代价(若有多个目标节点则为其中最小的一个),则它就称为A*算法。
A*算法中,限制h(x)≤h*(x)的原因是为了保证取得最优解。 理论分析证明,如果问题存在最优解, 则这样的限制就可保证能找到最优解。虽然,这个限制可能产生无用搜索。 实际上, 不难想像,当某一节点x的h(x)＞h*(x),则该节点就可能失去优先扩展的机会, 因而导致得不到最优解。 A*算法也称为最佳图搜索算法。它是著名的人工智能学者Nilsson提出的。
3.1.7 状态图搜索策略小结
3.2 状态图搜索问题求解 3.2.1 问题的状态图表示 1. 状态 1. 状态 状态就是问题在任一确定时刻的状况,它表征了问题特征和结构等。状态在状态图中表示为节点。状态一般用一组数据表示。在程序中用字符、数字、记录、数组、结构、对象等表示。
2. 状态转换规则 状态转换规则就是能使问题状态改变的某种操作、规则、 行为、变换、关系、函数、算子、过程等等。状态转换规则也称为操作,问题的状态也只能经定义在其上的这种操作而改变。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。
3. 状态图表示 一个问题的状态图是一个三元组 (S, F, G) 其中S是问题的初始状态集合, F是问题的状态转换规则集合, G是问题的目标状态集合。 一个问题的全体状态及其关系就构成一个空间, 称为状态空间。所以,状态图也称为状态空间图。
例 3.7 迷宫问题的状态图表示。 我们仍以例3.1中的迷宫为例。我们以每个格子作为一个状态,并用其标识符作为其表示。那么,两个标识符组成的序对就是一个状态转换规则。于是, 该迷宫的状态图表示为 S：So F：｛(So, S4), (S4, So), (S4, S1), (S1, S4), (S1,S2), (S2, S1), (S2, S3), (S3, S2), (S4, S7), (S7, S4), (S4, S5), (S5, S4), (S5, S6), (S6, S5), (S5, S8), (S8, S5), (S8, S9), (S9, S8), (S9, Sg)｝ G：Sg
X1 X2 X3 X８ X0 X4 X7 X6 X5 A＝(X0, X1, X2, X3, X4, X5, X6, X7, X8) 例 3.8 八数码难题的状态图表示。 我们将棋局 X1 X2 X3 X８ X0 X4 X7 X6 X5 用向量 A＝(X0, X1, X2, X3, X4, X5, X6, X7, X8) 表示,Xi为变量,Xi的值就是方格Xi内的数字。于是,向量A就是该问题的状态表达式。
设初始状态和目标状态分别为 So＝(0, 2, 8, 3, 4, 5, 6, 7, 1) Sg＝(0, 1, 2, 3, 4, 5, 6, 7, 8) 易见,数码的移动规则就是该问题的状态变换规则,即操作。经分析, 该问题共有24条移码规则, 可分为9组。
0组规则: 1组规则:
2组规则: 8组规则: 于是, 八数码问题的状态图可表示为 ({So}, {r1, r2, …, r24}, {Sg})
当然,上述24条规则也可以简化为4条: 即空格上移、 下移、左移、右移。不过,这时状态(即棋局)就需要用矩阵来表示。 可以看出,这个状态图中仅给出了初始节点和目标节点, 并未给出其余节点。而其余节点需用状态转换规则来产生。 类似于这样表示的状态图称为隐式状态图, 或者说状态图的隐式表示。
例 3.9 梵塔问题。传说在印度的贝那勒斯的圣庙中,主神梵天做了一个由64个大小不同的金盘组成的“梵塔”, 并把它穿在一个宝石杆上。另外, 旁边再插上两个宝石杆。 然后, 他要求僧侣们把穿在第一个宝石杆上的64个金盘全部搬到第三个宝石杆上。 搬动金盘的规则是：一次只能搬一个；不允许将较大的盘子放在较小的盘子上。于是,梵天预言：一旦64个盘子都搬到了3号杆上, 世界将在一声霹雳中毁灭。这就是梵塔问题。 经计算, 把64个盘子全部搬到3号杆上, 需要穿插搬动盘子 264-1＝18 446 744 073 709 511 615 次。所以直接考虑原问题, 将过于复杂。
设有三根宝石杆,在1号杆上穿有A、B两个金盘, A小于B, A位于B的上面。要求把这两个金盘全部移到另一根杆上,而且规定每次只能移动一个盘子,任何时刻都不能使B位于A的上面。 设用二元组(SA,SB)表示问题的状态, SA表示金盘A所在的杆号, SB表示金盘B所在的杆号, 这样, 全部可能的状态有9种, 可表示如下： (1, 1), (1, 2), (1, 3) (2, 1), (2, 2), (2, 3) (3, 1), (3, 2), (3, 3) 如图3-10所示。
图 3-10 二阶梵塔的全部状态
这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘从第i号杆移到第j号杆上;B(i,j)表示把B盘从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是： A(1,2), A(1,3), A(2,1), A(2,3), A(3,1), A(3,2) B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2) 当然,规则的具体形式应是： IF〈条件〉THENA(i,j) IF〈条件〉THEN B(i, j)
这样由题意,问题的初始状态为(1, 1),目标状态为(3, 3), 则二阶梵塔问题可用状态图表示为 ({(1, 1)}, {A(1, 2), …, B(3, 2)}, {(3, 3)}) 由这9种可能的状态和12种操作, 二阶梵塔问题的状态空间图如图3-11所示。
图 3-11 二阶梵塔状态空间图
例3.10 旅行商问题(Traveling-Salesman Problem,TSP)。 设有n个互相可直达的城市, 某推销商准备从其中的A城出发,周游各城市一遍, 最后又回到A城。 要求为该推销商规划一条最短的旅行路线。 该问题的状态为以A打头的已访问过的城市序列: A… So:A。 Sg: A, …, A。其中“…”为其余n-1个城市的一个序列。
状态转换规则： 规则1 如果当前城市的下一个城市还未去过, 则去该 城市,并把该城市名排在已去过的城市名序列后端。 规则2 如果所有城市都去过一次, 则从当前城市返回 A城, 把A也添在去过的城市名序列后端。
3.2.2 状态图问题求解程序举例 例3.11 下面是一个通用的状态图搜索程序。对于求解的具体问题，只需将其状态图的程序表示并入该程序即可。 /*状态图搜索通用程序*/ DOMAINS state=<领域说明> %例如:state=symbol DATABASE-mydatabase open(state,integer) %用动态数据库实现OPEN表 closed(integer,state,integer) %和CLOSED表 res(state) open1(state,integer) min(state,integer) mark(state) fail—
PREDICATES solve search(state,state) result searching step4(integer,state) step56(integer,state) equal(state,state) repeat resulting(integer) rule(state,state)
GOAL solve. CLAUSES solve: -search(<初始状态>,<目标状态>),result. /* 例如 solve: - search(st(0,1,2,3,4,5,6,7,8),st(0,2,8,3,4,5,6,7,1)),result. */ search(Begin,End): -% 搜索 retractall(_,mydatabase), assert(closed(0,Begin,0)), assert(open(Begin,0)),%步1 将初始节点放入OPEN表 assert(mark(End)), repeat, searching,!.
result: - % 输出解 not(fail_), retract(closed(0,_,0)), closed(M,_,_), resulting(M),!. result: - beep,write(″sorry don't find a road!″). searching: - open(State,Pointer), %步2 若OPEN表空, 则失败,退出 retract(open(State,Pointer)), %步3 取出OPEN表中第一个节点,给其 closed(No, _, _),No2=No+1, % 编号 asserta(closed(No2,State,Pointer)), %放入CLOSED表 !,step4(No2,State). searching: -assert(fail_). %步4 若当前节点为目标节点, 则成功
step4(_,State): -mark(End),equal(State,End). %转步2 step4(No,State): -step56(No,State),!,fail. step56(No,StateX): -%步5 若当前节点不可扩展, 转步2 rule(StateX,StateY), %步6 扩展当前节点X得Y not(open(StateY,_)), %考察Y是否已在OPEN表中 not(closed(_,StateY,_)),%考察Y是否已在CLOSED表中 assertz(open(StateY,No)), %可改变搜索策略 fail. step56(_,_): -!. equal(X,X). repeat. repeat: -repeat. resulting(N): -closed(N,X,M),asserta(res(X)),resulting(M). resulting(_): -res(X),write(X),nl,fail. resulting(_): -!. rule(X,Y): -<问题中的状态转换规则>. % 例如: rule(X,Y): -road(X,Y).
例 3.12 迷宫问题程序。下面仅给出初始状态、目标状态和状态转换规则集, 程序用例3.11的通用程序。 例 3.12 迷宫问题程序。下面仅给出初始状态、目标状态和状态转换规则集, 程序用例3.11的通用程序。 DOMAINS State=symbol CLAUSES solve: - search(a,e), result. /*把该问题的状态转换规则挂接在通用程序的规则上*/ rule(X,Y): -road(X,Y). /* 下面是该问题的状态转换规则(其实也就是迷宫图)集, 需并入通用程序后 */ road(a,b). road(a,c). road(b,f). road(f,g).road(f,ff).road(g,h). road(g,i). road(b,d). road(c,d). road(d,e). road(e,b).
例 3.13 八数码问题程序。我们把前面给出的该问题的状态图表示, 用PROLOG语言翻译如下,搜索程序用例3.11的通用程序。 DOMAINS state=st(integer,integer,integer,integer,integer,integer,integer,integer,integer) CLAUSES solve:-search(st(0,1,2,3,4,5,6,7,8),st(0,2,8,3,4,5,6,7,1)), result. rule(X,Y): -rule1(X,Y). /*把该问题的状态转换规则挂接在通用程序的规则上*/ /* 下面是该问题的状态转换规则(即走步规则)集,需并入通用程序后 */ rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X2,X1,X0,X3,X4,X5,X6,X7,X8)): -X0=0.
rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X4,X1,X2,X3,X0,X5,X6,X7,X8)): -X0=0.
rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X2,X1,X0,X3,X4,X5,X6,X7,X8)): -X2=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X3,X2,X4,X5,X6,X7,X8)): -X3=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X4,X3,X5,X6,X7,X8)): -X3=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X4,X3,X5,X6,X7,X8)): -X4=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X4,X1,X2,X3,X0,X5,X6,X7,X8)): -X4=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X5,X4,X6,X7,X8)): -X4=0. rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X5,X4,X6,X7,X8)): -X5=0.
rule1(st(X0,X1,X2,X3,X4,X5,X6,X7,X8),st(X0,X1,X2,X3,X4,X6,X5,X7,X8)): -X5=0.
例 3.14 旅行商问题程序。 /* 旅行商问题 */ DOMAINS State=st(lists,integer) lists=symbol* Gx,Grule,Fx=integer city1,city2=symbol distance=integer StartingCity=symbol CitySum=integer DATABASE-mydatabase open(State,integer,Gx,Fx) closed(integer,State,integer,Gx)
open1(State,integer,integer,integer) min(State,integer,integer,integer) mark(string,integer) minD(integer) fail_ PREDICATES road(city1,city2,distance) search(StartingCity,CitySum) searching step4(integer,State,Gx) step56(integer,State,Gx) calculator(integer,integer,integer,integer,integer) repeat sort p1
p12(State,integer,integer,integer) rule(State,State,Grule) member(symbol,lists) append(lists,lists,lists) mindist(integer) mindist1 pa(integer) result GOAL clearwindow, write(″Please inout starting city name:″), readln(Start), write(″Please input the sum of citys in the map:″), readint(Sum), search(Start,Sum), result.
CLAUSES search(StartingCity,CitySum): - retractall(_,mydatabase),assert(closed(0,st(［］,0),0,0)), assert(open(st(［StartingCity］,0),0,0,0)), assert(mark(StartingCity,CitySum)), repeat, searching,!. searching: - open(State,BackPointer,Gx,_), retract(open(State,_,_,_)), closed(No,_,_,_),No2=No+1, asserta(closed(No2,State,BackPointer,Gx)), !,step4(No2,State,Gx).
searching: -assert(fail_). result: -not(fail_),closed(_,st(L,_),_,G),write(L,G). result: -beep,write(″sorry don't find a road!″). step4(_,st(L,N),_): -mark(_,StateSum),N=StateSum. step4(No,State,Gx): -step56(No,State,Gx),!,fail. step56(No,st(L,N),Gx): - %Gx为当前节点的代价 rule(st(L,N),StateY,Grule), %Grule为规则的代价(即边代价) not(open(StateY,_,_,_)), %StateY为扩展得到的子节点 not(closed(_,StateY,_,_)), calculator(N,Gx,Grule,Gy,Fy), asserta(open(StateY,No,Gy,Fy)), fail.
step56(_, _, _): -sort,!. % 按估价函数值对OPEN表以升序排序 calculator(N,Gx,Grule,Gy,Fy): - Gy=Gx+Grule, %计算子节点的代价值g(y) mark(_,CitySum), mindist(MinD), Hy=(CitySum-N-1)*MinD, %计算子节点的启发函数值h(y) Fy=Gy+Hy,!. %计算子节点的估价函数值f(y)=g(y)+h(y) mindist(MinD): - road(_,_,D1),assert(minD(D1)),mindist1,minD(MinD),!. mindist1: -road(_,_,D),pa(D),fail. mindist1: -!. pa(D): -minD(Do),Do>D,retract(minD(_)),assert(minD(D)),!. pa(_): -!.
sort: -not(open(_,_,_,_)),!. sort: -repeat,open(X,N,G,F),assert(min(X,N,G,F)),p1,not(open(_,_,_,_)),p2. p1: -open(X,N,G,F),p12(X,N,G,F),fail. p1: -min(X,N,G,F), assertz(open1(X,N,G,F)),retract(open(X,N,G,F)),retract(min(_,_,_,_)),!. p12(_,_,G,Fn): -min(_,_,_,Fo),Fo<=Fn,!. p12(X,N,G,Fn): -retract(min(_,_,_,_)),assert(min(X,N,G,Fn)),!. p2: -open1(X,N,G,F),assertz(open(X,N,G,F)),fail. p2: -retractall(open1(_,_,_,_)),!. repeat. repeat: -repeat. member(X,［X|_］). member(X,［_|Y］): -member(X,Y).
append(［］,L,L). append(［H|T］,L,［H|Tn］): -append(T,L,Tn).[KH*2] rule(st(［H|T］,IN),st(OL,ON),Grule): - %状态变换规则1 mark(StartingCity,StateSum), IN=StateSum-1, road(H,StartingCity,D), append(［StartingCity］,［H|T］,OL), ON=IN+1, Grule=D. rule(st(［H|T］,IN),st(OL,ON),Grule): - %状态变换规则2
/* 交通图 (如) road(xian,beijing,1165). road(xian,shanghai,1511). road(H,Y,D), not(member(Y,［H|T］)), append(［Y］,［H|T］,OL), ON=IN+1, Grule=D. /* 交通图 (如) road(xian,beijing,1165). road(xian,shanghai,1511). … … … */
可以看出,该程序与例3. 11的通用程序基本相同, 但这是一个基于A 可以看出,该程序与例3.11的通用程序基本相同, 但这是一个基于A*算法的启发式图搜索程序。估价函数f(x)为代价函数g(x)和启发函数h(x)之和。 其中代价函数的计算公式为 节点(A…XY)的代价＝起始城市到X城的代价＋X城到Y城的代价 其中的代价可以是距离、 费用或时间等(下同)。 启发函数值的计算公式为 节点(A…XY)的启发值＝(城市总数-已访问过的城市数-1) ×min{所有两城间的代价}
这里把一个节点的启发函数值定义为该节点到目标节点至少还要花费的代价。那么,随着访问城市数的增加, 启发函数值则在逐渐减少。式中减1的原因是每次计算时,总是对刚才扩展到的子节点计算的,而该节点还未计入已扩展数中。 由于这个代价的实际值(h*(x))总不会小于所有城市间最小代价(距离)的整倍数(h(x)),所以,符合A*算法的要求。代价值和启发值在搜索过程中的处理差别是, 前者要不断进行传递和累加, 而后者只是在需要时临时计算, 且不进行传递和累计。
该程序实际是一个旅行商问题的通用程序。 对于一个具体的旅行路径规划, 还需也只需把具体的“地图”用谓词road(City1, City2, Cost)描述出来, 并作为事实并入该程序。 该程序还有一个特点是, 它实际是进行双重搜索： 一方面在显式图(地图)上进行搜索,同时又在由此产生的隐式图(以访问过的城市序列为状态节点的状态图)上进行搜索。而该问题的解, 并不是隐式图中的路径,而是路径中的最后一个节点。 这个节点恰好是地图上的一条路径。
3.3 与 或 图 搜 索 3.3.1 与或图 我们仍用例子引入与或图的概念。 我们仍用例子引入与或图的概念。 例 3.15 如图3-12所示,设有四边形ABCD和A′B′C′D′, 要求证明它们全等。 分析：分别连接B、D和B′、D′, 则原问题可分解为两个子问题： Q1：证明△ABD≌△A′B′D′ Q2：证明△BCD≌△B′C′D′
图3-12 四边形ABCD和A’B’C’D’
于是, 原问题的解决可归结为这两个子问题的解决。 换句话说,原问题被解决当且仅当这两个子问题都被解决。 进一步,问题Q1还可再被分解为 Q11：证明AB＝A′B′ Q12：证明AD＝A′D′ Q13：证明∠A＝∠A′ 或 Q11′： 证明AB＝A′B′ Q12′： 证明AD＝A′D′ Q13′： 证明 BD＝B′D′
问题Q2还可再被分解为 Q21：证明 BC＝B′C′ Q22：证明 CD＝C′D′ Q23：证明 ∠C＝∠C′ 或 Q21′：证明 BC＝B′C′ Q22′：证明 CD＝C′D′ Q23′：证明 BD＝B′D′
现在考虑原问题与这两组子问题的关系, 我们便得到图3-13。图中的弧线表示所连边为“与”关系,不带弧线的边为或关系。这个图中既有与关系又有或关系,因此被称为与或图。但这个与或图是一种特殊的与或图, 称为与或树。
图 3-13 问题的分解与变换
图 3-14 一个典型的与或图
由上例可以看出,与或图可以用来描述一类问题的求解过程。事实上,当我们把待解的原问题作为初始节点, 把由原问题经一系列分解或变换而得到的直接可解的简单问题作为目标节点, 那么,问题求解过程也就是在一个与或图中寻找一个从初始节点到目标节点的路径问题。例如上例,如果我们把Q作为初始节点,把子问题Q11、Q12、Q13…作为目标节点, 则对问题Q的求解就是在图3－13所示的与或图中寻找路径的问题。但可以看出, 与或图中的路径一般不是像状态图中那样的线形路径, 而是图或树形“路径”。因此, 一般称这种路径为解图或解树。所以, 求解与或图问题就是在与或图中搜索解图或解树的问题。
同状态图一样, 与或图也是问题求解的一种抽象表示。事实上,许多问题的求解过程都可以用与或图搜索来描述。如梵塔问题、猴子摘香蕉问题、博弈问题、求不定积分问题、定理证明问题等等。 所以, 研究与或图搜索也具有普遍意义。 用与或图搜索来描述问题的求解过程, 就是将原问题通过有关变换规则不断分解(为子问题)或变换(为等价问题), 直到问题分解或变换为(即归约为)一些直接可解的子问题, 或者不可解也不能再分解或变换的子问题为止。然后根据所得到的搜索树确定原问题的可解性。如果可解, 则由搜索树找出解图或解树。
3.3.2 与或图搜索 1. 搜索方式,解图(树) 同状态图(即或图)的搜索一样, 与或图搜索也分为树式和“线”式两种类型。对于树式搜索来讲,其搜索过程也是不断地扩展节点, 并配以返回指针, 而形成一棵不断生长的搜索树。 但与或图搜索解图(树),不像在或图中那样只是简单地寻找目标节点,而是边扩展节点边进行逻辑判断, 以确定初始节点是否可解。一旦能够确定初始节点的可解性, 则搜索停止。这时, 根据返回指针便可从搜索树中得到一个解图(树)。所以,准确地说,解图(树)实际上是由可解节点形成的一个子图(树), 这个子图(树)的根为初始节点, 叶为终止节点, 且这个子图(树)还一定是与图(树)。
2. 可解性判别 怎样判断一个节点的可解性呢？ 下面我们给出判别准则。 (1) 一个节点是可解, 则节点须满足下列条件之一: ① 终止节点是可解节点。 ② 一个与节点可解, 当且仅当其子节点全都可解。 ③ 一个或节点可解, 只要其子节点至少有一个可解。 (2) 一个节点是不可解, 则节点须满足下列条件之一: ① 非终止节点的端节点是不可解节点。 ② 一个与节点不可解, 只要其子节点至少有一个不可解。 ③ 一个或节点不可解, 当且仅当其子节点全都不可解。
3. 搜索策略 与或图搜索也分为盲目搜索和启发式搜索两大类。前者又分为穷举搜索和盲目碰撞搜索。穷举搜索又分为深度优先和广度优先两种基本策略。
4. 搜索算法 同一般状态图搜索一样,一般与或图搜索也涉及一些复杂的处理。因篇幅所限,我们仅介绍特殊的与或图——与或树的搜索算法。与或树的树式搜索过程可概括为以下步骤： 步1 把初始节点Qo放入OPEN表。 步2 移出OPEN表的第一个节点N放入CLOSED表, 并冠以序号n。
步3 若节点N可扩展, 则做下列工作： (1) 扩展N, 将其子节点配上指向父节点的指针后放入OPEN表。 (2)考察这些子节点中是否有终止节点。 若有, 则标记它们为可解节点, 并将它们也放入CLOSED表, 然后由它们的可解反向推断其先辈节点的可解性, 并对其中的可解节点进行标记。 如果初始节点也被标记为可解节点, 则搜索成功,结束。 (3)删去OPEN表中那些具有可解先辈的节点(因为其先辈节点已经可解, 故已无再考察该节点的必要), 转步2。
步4 若N不可扩展, 则做下列工作： (1)标记N为不可解节点, 然后由它的不可解反向推断其先辈节点的可解性, 并对其中的不可解节点进行标记。如果初始节点So也被标记为不可解节点, 则搜索失败, 退出。 (2)删去OPEN表中那些具有不可解先辈的节点(因为其先辈节点已不可解,故已无再考察这些节点的必要), 转步2。
例 3.16 设有与或树如图3-15所示, 其中1号节点为初始节点,t1、t2、t3、t4均为终止节点, A和B是不可解的端节点。 采用广度(优先)搜索策略, 搜索过程如下： (1) 扩展1号节点, 得2号和3号节点, 依次放入OPEN表尾部。由于这两个节点都非终止节点, 所以接着扩展2号节点。 此时OPEN表中只有3号节点。 (2) 2号节点扩展后,得4号节点和t1节点。此时OPEN表中依次有3号、4号和t1节点。由于t1是终止节点,故标记它为可解节点, 并将它放入CLOSED表, 再判断其先辈节点的可解性,但t1的父节点2是一个与节点, 故仅由t1的可解还不能确定2号节点可解。所以, 就继续搜索。
图 3-15 与或树及其解树
(3) 扩展3号节点,得5号节点和B节点。两者均非终止节点, 所以继续扩展4号节点。 (4) 4号节点扩展后得节点A和t2。t2是终止节点,标记为可解节点, 放入CLOSED表。这时其先辈节点4和2也为可解节点, 但1号节点还不能确定。这时从OPEN表中删去节点A,因为其父节点4已经可解。 (５) 扩展5号节点得t3和t4。由于t3和t4都为终止节点(放入CLOSED表), 故可推得节点5、3、1均为可解节点。 搜索成功, 结束。 这时,由CLOSED表便得到由节点1、2、3、4、5和t1、t2、 t3、t4构成的解树，如图3-15 中的粗线所示。
3.3.3 启发式与或树搜索 广度优先搜索及深度优先搜索都是盲目搜索, 其共同点是： (1) 搜索从初始节点开始,先自上而下地进行搜索,寻找终止节点及端节点, 然后再自下而上地进行可解性标记,一旦初始节点被标记为可解节点或不可解节点, 搜索就不再继续进行。 (2) 搜索都是按确定路线进行的,当要选择一个节点进行扩展时,只是根据节点在与或树中所处的位置,而没有考虑要付出的代价,因而求得的解树不一定是代价最小的解树, 即不一定是最优解树 。
1. 解树的代价 解树的代价就是树根的代价。树根的代价是从树叶开始自下而上逐层计算而求得的。而解树的根对应的是初始节点Qo。 这就是说,在与或树的搜索过程中,代价的计算方向与搜索树的生长方向相反。这一点是与状态图不同的。具体来讲,有下面的计算方法： 设g(x)表示节点x的代价,c(x,y)表示节点x到其子节点y的代价(即边xy的代价), 则 (1) 若x是终止节点, g(x)＝0。
(2) 若x是或节点, 。其中y1, y2, …, yn是x的子节点。 (3) 若x是与节点x, 则有两种计算公式。 ① 和代价法： 。 ② 最大代价法： 。其中y1, y2, …, yn是x的子节点。 (4) 对非终止的端节点x, g(x)＝∞。
例3.17 如图3-16所示的与或树, 其中包括两棵解树, 一棵解树由Qo,A,t1和t2组成；另一棵解树由Qo,B,D,G,t4和t5组成。 在此与或树中,t1,t2,t3,t4,t5为终止节点；E,F是非终止的端节点, 其代价均为∞；边上的数字是该边的代价。 由右边的解树可得： 按和代价： g(A)=11,g(Qo)=13 按最大代价：g(A)=6, g(Qo)=8 由左边的解树可得： 按和代价： g(G)=3, g(D)=4, g(B)=6, g(Qo)=8 按最大代价： g(G)=2, g(D)=3, g(B)=5, g(Qo)=7
图 3-16 含代价的与或树
显然, 若按和代价计算, 左边的解树是最优解树,其代价为8; 若按最大代价计算, 左边的解树仍然是最优解树,其代价是7。但有时用不同的计算代价方法得到的最优解树不相同。
2. 希望树 无论是用和代价法还是最大代价法, 当要计算任一节点x的代价g(x)时, 都要求已知其子节点yi的代价g(yi)。 但是, 搜索是自上而下进行的, 即先有父节点, 后有子节点, 除非节点x的全部子节点都是不可扩展节点, 否则子节点的代价是不知道的。此时节点x的代价g(x)如何计算呢？解决的办法是根据问题本身提供的启发性信息定义一个启发函数, 由启发函数估算出子节点yi的代价g(yi), 然后再按和代价或最大代价算出节点x的代价值g(x)。有了g(x), 节点x的父节点、 祖父节点以及直到初始节点So的各先辈节点的代价g都可自下而上的地逐层推算出来。
当节点yi被扩展后, 也是先用启发函数估算出其子节点的代价, 然后再算出g(yi)。此时算出的g(yi)可能与原先估算出的g(yi)不相同, 这时应该用后算出的g(yi)取代原先估算出的g(yi),并且按此g(yi)自下而上地重新计算各先辈节点的g值。当节点yi的子节点又被扩展时,上述过程又要重复进行一遍。总之,每当有新一代的节点生成时,都要自下而上地重新计算其先辈节点的代价g, 这是一个自上而下地生成新节点,又自下而上地计算代价g的反复进行的过程。
有序搜索的目的是求出最优解树, 即代价最小的解树。 这就要求搜索过程中任一时刻求出的部分解树其代价都应是最小的。为此,每次选择欲扩展的节点时都应挑选有希望成为最优解树一部分的节点进行扩展。 由于这些节点及其先辈节点(包括初始节点So)所构成的与或树有可能成为最优解树的一部分, 因此称它为“希望树”。 在搜索过程中,随着新节点的不断生成, 节点的代价值是在不断变化的, 因此希望树也在不断变化。 在某一时刻,这一部分节点构成希望树,但到另一时刻,可能是另一些节点构成希望树。但不管如何变化, 任一时刻的希望树都必须包含初始节点So,而且希望树总是对最优解树近根部分的某种估计。
下面给出希望树的定义： (1) 初始节点Qo在希望树T中。 (2) 如果节点x在希望树T中, 则一定有： ① 如果x是具有子节点y1,y2, …,yn的“或”节点,则具有 值的那个子节点yi也应在T中。 ② 如果x是“与”节点, 则它的全部子节点都应在T中。
3. 与或树的有序搜索过程 与或树的有序搜索过程是一个不断选择、修正希望树的过程。如果问题有解, 则经有序搜索将找到最优解树。 其搜索过程如下： 步1 把初始节点Qo放入OPEN表中。 步2 求出希望树T, 即根据当前搜索树中节点的代价g求出以Qo为根的希望树T。 步3 依次把OPEN表中T的端节点N选出放入CLOSED表中。
步4 如果节点N是终止节点, 则做下列工作： (1) 标示N为可解节点。 (2) 对T应用可解标记过程, 把N的先辈节点中的可解节点都标记为可解节点。 (3) 若初始节点Qo能被标记为可解节点, 则T就是最优解树,成功退出。 (4) 否则, 从OPEN表中删去具有可解先辈的所有节点。
步5 如果节点N不是终止节点, 且它不可扩展, 则做下列工作： (2) 对T应用不可解标记过程, 把N的先辈节点中的不可解节点都标记为不可解节点。 (3) 若初始节点Qo也被标记为不可解节点, 则失败退出。 (4) 否则, 从OPEN表中删去具有不可解先辈的所有节点。
步6 如果节点N不是终止节点, 但它可扩展, 则可做下列工作： (1) 扩展节点N, 产生N的所有子节点。 (2)把这些子节点都放入OPEN表中, 并为每一个子节点配置指向父节点(节点N)的指针。 (3) 计算这些子节点的g值及其先辈节点的g值。 步7 转步2。
例 3.18 下面我们举例说明上述搜索过程。 设初始节点为Qo, 每次扩展两层,并设Qo经扩展后得到如图3-17(a)所示的与或树, 其中子节点B,C,E,F用启发函数估算出的g值分别是 g(B)=3, g(C)=3, g(E)=3, g(F)=2 若按和代价计算, 则得到 g(A)=8, g(D)=7, g(Qo)=8 (注: 这里把边代价一律按1计算, 下同。 )
此时,Qo的右子树是希望树。下面将对此希望树的节点进行扩展。 设对节点E扩展两层后得到如图3-17(b)所示的与或树, 节点旁的数字为用启发函数估算出的g值, 则按和代价法计算得到 g(G)=7, g(H)=6, g(E)=7, g(D)=11 此时, 由Qo的右子树算出的g(Qo)=12。但是, 由左子树算出的g(Qo)=9。显然, 左子树的代价小, 所以现在改取左子树作为当前的希望树。
假设对节点B扩展两层后得到如图3-17(c)所示的与或树, 节点旁的数字是对相应节点的估算值, 节点L的两个子节点是终止节点, 则按和代价法计算得到 g(L)=2, g(M)=6, g(B)=3, g(A)=8 由此可推算出g(Qo)=9。这时, 左子树仍然是希望树, 继续对其扩展。该扩展节点C。
g(N)=2, g(P)=7, g(C)=3, g(A)=8 假设节点C扩展两层后得到如图3-17(d)所示的与或树, 节点旁的数字是对相应节点的估算值, 节点N的两个子节点是终止节点。 按和代价计算得到 g(N)=2, g(P)=7, g(C)=3, g(A)=8 由此可推算出g(Qo)=9。另外,由于N的两个子节点都是终止节点, 所以N和C都是可解节点。再由前面推出的B是可解节点, 可推出A和Qo都是可解节点。这样就求出了代价最小的解树, 即最优解树——图3-17(d)中粗线部分所示。该最优解树是用和代价法求出来的, 解树的代价为9。
图 3-17 与或树有序搜索
3.4 与或图搜索问题求解 3.4.1 问题的与或图表示 与或图是描述问题求解的另一种有向图。与或图一般表示问题的变换过程(而不是状态变换)。具体讲,它是从原问题出发, 通过运用某些规则不断进行问题分解(得到与分支)和变换(得到或分支),而得到一个与或图。换句话说, 与或图的节点一般代表问题。那么,整个图也就表示问题空间。与或图中的父节点与其子节点之间服从逻辑上的与、或运算关系。所以,与或图表示的问题是否有解, 要进行逻辑判断, 与或图的搜索也受逻辑的制约。
与或图也是一个三元组 (Qo, F, Qn) 这里Qo表示初始问题,F表示问题变换规则集,Qn表示本原问题集。 例如, 高等数学中的积分公式, 就是一些典型的问题分解和变换规则,所以,一般的求不定积分问题就可用与或图来描述。 其实,一个PROLOG程序也就是一个与或图。程序中的询问(即目标)就是初始问题, 规则就是问题变换规则, 事实就是本原问题。
例 3.19 三阶梵塔问题。 对于梵塔问题, 我们也可以这样考虑：为把1号杆上的n个盘子搬到3号杆, 可先把上面的n-1个盘子搬到2号杆上；再把剩下的一个大盘子搬到3号杆；然后再将2号杆上的n-1个盘子搬到3号杆。 这样, 就把原来的一个问题分解为三个子问题。 这三个子问题都比原问题简单, 其中第二个子问题已是直接可解的问题。对于第一和第三两个子问题, 可用上面n个盘子的方法, 做同样的处理。根据这一思想,我们可把三阶梵塔问题分解为下面的三个子问题：
(1) 把A、B盘从1号杆移到2号杆。 (2) 把C盘从1号杆移到3号杆。 (3) 把A、B盘从2号杆移到3号杆。 其中子问题(1)、(3)又分别可分解为三个子问题。 于是, 我们可得到三阶梵塔问题的与或树表示(见图3-18)。
图 3-18 三阶梵塔问题的与或树
需说明的是, 三元组 (i, j, k) i代表金盘A所在的杆号; j代表金盘B所在的杆号, k代表金盘C所在的杆号。
在图3-18所示的与或树中, 共有七个终止节点,对应于七个本原问题, 它们是通过“分解”得到的。若把这些本原问题的解按从左至右的顺序排列, 就得到了原始问题的解： (1, 1, 1) (3, 1, 1) (3, 1, 1) (3, 2, 1) (3, 2, 1) (2, 2, 1) (2, 2, 1) (2, 2, 3) (2, 2, 3) (1, 2, 3) (1, 2, 3) (1, 3, 3) (1, 3, 3) (3, 3, 3)
3.4.2 与或图问题求解程序举例 例 3.20 基于与或图搜索的迷宫问题程序。 /*puzzle room problem*/ 例 3.20 基于与或图搜索的迷宫问题程序。 /*puzzle room problem*/ DOMAINS room list=room* room=symbol PREDICATES road(room,room) path(room,room,room list) go(room,room) member(room,room list)
GOAL go(a,e). CLAUSES go(X,Y):-path(X,Y, ［X］ ).%首先将入口放入表中，该表用来记录走过的路径 path(X,X,L):-write(L).%当path中的两个点相同时，表明走到了出口。程序结束 path(X,Y,L):-%这个语句实际是问题分解规则，它将原问题分解为两个子问题 road(X,Z),%从当前点向前走到下一点Z not(member(Z,L)), path(Z,Y,［Z|L］).%再找Z到出口Y的路径 member(X,［X|-］). member(X,［-|T］)if member(X,T). /* 迷宫图 */ road(a,b).road(a,c).road(b,f).road(f,g).road(f,ff).road(g,h). road(g,i).road(b,d).road(c,d).road(d,e).road(e,b).
可以看出, 该程序只给出了问题分解规则, 即与或树, 而搜索程序是利用了PROLOG自身的解释程序。这正是用PROLOG解决此类问题的特点。该程序执行时也可回溯,且用PROLOG的表记录了搜索路径,所以它又是一种可回溯的线式搜索程序。
例 3.21 梵塔问题程序。 对于梵塔问题, 我们这样考虑：为把1号杆上的n个盘子搬到3号杆,可先把上面的n-1个盘子搬到2号杆上；再把剩下的一个大盘子搬到3号杆；然后再将2号杆上的n-1个盘子搬到3号杆。 这样,就把原来的一个问题分解为三个子问题。 这三个子问题都比原问题简单,其中第二个子问题已是直接可解的问题。 对于第一和第三两个子问题, 可用上面n个盘子的方法, 做同样的处理。 于是, 可得递归程序如下：
/* Hanoi tower */ DOMAINS disk_amount,pole_No=integer PREDICATES move(disk_amount,pole_No,pole_No,pole_No) GOAL move(5,1,2,3). CLAUSES move(0,_,_,_): -!. move(N,X,Y,Z): - /* move N disks from X to Z */ M=N-1, move(M,X,Z,Y),write(X,″to″,Z),move(M,Y,X,Z). 程序中的盘子数取为5。
3.5 博 弈 树 搜 索 3.5.1 博弈树的概念 在博弈过程中, 任何一方都希望自己取得胜利。因此,当某一方当前有多个行动方案可供选择时, 他总是挑选对自己最为有利而对对方最为不利的那个行动方案。 此时,如果我们站在A方的立场上,则可供A方选择的若干行动方案之间是“或”关系, 因为主动权操在A方手里,他或者选择这个行动方案, 或者选择另一个行动方案, 完全由A方自己决定。当A方选取任一方案走了一步后,B方也有若干个可供选择的行动方案, 此时这些行动方案对A方来说它们之间则是“与”关系,因为这时主动权操在B方手里,这些可供选择的行动方案中的任何一个都可能被B方选中, A方必须应付每一种情况的发生。
这样,如果站在某一方(如A方,即在A要取胜的意义下), 把上述博弈过程用图表示出来, 则得到的是一棵“与或树”。 描述博弈过程的与或树称为博弈树,它有如下特点： (1) 博弈的初始格局是初始节点。 (2) 在博弈树中, “或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系, 对方扩展的节点之间是“与”关系。双方轮流地扩展节点。 (3) 所有自己一方获胜的终局都是本原问题, 相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。
3.5.2 极小极大分析法 在二人博弈问题中,为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案, 就需要对当前的情况以及将要发生的情况进行分析,从中选出最优的走步。最常使用的分析方法是极小极大分析法。 其基本思想是： (1) 设博弈的双方中一方为A,另一方为B。然后为其中的一方(例如A)寻找一个最优行动方案。 (2) 为了找到当前的最优行动方案, 需要对各个可能的方案所产生的后果进行比较。具体地说, 就是要考虑每一方案实施后对方可能采取的所有行动, 并计算可能的得分。
(3) 为计算得分,需要根据问题的特性信息定义一个估价函数, 用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。 (4) 当端节点的估值计算出来后, 再推算出父节点的得分, 推算的方法是：对“或”节点, 选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点, 选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。 (5) 如果一个行动方案能获得较大的倒推值, 则它就是当前最好的行动方案。
图 3-19 倒推值的计算
在博弈问题中,每一个格局可供选择的行动方案都有很多, 因此会生成十分庞大的博弈树。据统计,西洋跳棋完整的博弈树约有1040个节点。试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树, 然后进行极小极大分析,找出当前最好的行动方案。在此之后, 再在已选定的分支上扩展一定深度, 再选最好的行动方案。如此进行下去, 直到取得胜败的结果为止。至于每次生成博弈树的深度, 当然是越大越好, 但由于受到计算机存储空间的限制, 只好根据实际情况而定。
例 3.22 一字棋游戏。设有如图3-20(a)所示的九个空格, 由A, B二人对弈, 轮到谁走棋谁就往空格上放一只自己的棋子, 谁先使自己的棋子构成“三子成一线”谁就取得了胜利。 图 3-20 一字棋
设A的棋子用“a”表示, B的棋子用“b”表示。为了不致于生成太大的博弈树,假设每次仅扩展两层。估价函数定义如下： 设棋局为P,估价函数为e(P)。 (1) 若P是A必胜的棋局, 则e(P)=+∞。 (2) 若P是B必胜的棋局, 则e(P)=-∞。 (3) 若P是胜负未定的棋局, 则 e(P)=e(+P)-e(-P)
其中e(+P)表示棋局P上有可能使a成为三子成一线的数目； e(-P)表示棋局P上有可能使b成为三子成一线的数目。例如, 对于图3-20(b)所示的棋局, 则 另外,我们假定具有对称性的两个棋局算作一个棋局。还假定A先走棋, 我们站在A的立场上。 图3-21给出了A的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出, 对于A来说最好的一着棋是S3,因为S3比S1和S2有较大的倒推值。
图 3-21 一字棋极小极大搜索
在A走S3这一着棋后,B的最优选择是S4, 因为这一着棋的静态估值较小,对A不利。不管B选择S4或S5,A都要再次运用极小极大分析法产生深度为2的博弈树,以决定下一步应该如何走棋, 其过程与上面类似, 不再重复。
3.5.3 α-β剪枝技术 上述的极小极大分析法, 实际是先生成一棵博弈树,然后再计算其倒推值。这样做的缺点是效率较低。于是,人们又在极小极大分析法的基础上,提出了α-β剪枝技术。 这一技术的基本思想是,边生成博弈树边计算评估各节点的倒推值, 并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点, 即相当于剪去了博弈树上的一些分枝, 从而节约了机器开销, 提高了搜索效率。具体的剪枝方法如下:
(1) 对于一个与节点MIN, 若能估计出其倒推值的上确界β,并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β, 则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。 (2) 对于一个或节点MAX, 若能估计出其倒推值的下确界α, 并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β, 即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。 这一过程称为β剪枝。
例3.23 图3-22所示的博弈树搜索就采用了α-β剪枝技术。 图 3-22 α-β剪枝
习 题 三 1. 何为状态图和与或图？图搜索与问题求解有什么关系？ 2. 综述图搜索的方式和策略。 1. 何为状态图和与或图？图搜索与问题求解有什么关系？ 2. 综述图搜索的方式和策略。 3. 什么是问题的解? 什么是最优解？ 4. 什么是与或树？什么是可解节点？ 什么是解树？ 5.设有三只琴键开关一字排开, 初始状态为“关、开、 关”, 问连按三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关, 而且只能按一个开关。 请画出状态空间图。 注：琴键开关有这样的特点, 若第一次按下时它为“开”, 则第二次按下时它就变成了“关”。
6. 有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸,但受下列条件限制： (1) 船太小,农夫每次只能带一样东西过河。 (2) 如果没有农夫看管, 则狼要吃羊,羊要吃菜。 请设计一个过河方案, 使得农夫、狼、羊、菜都能不受损失地过河。画出相应的状态空间图。 提示： (1) 用四元组(农夫、狼、羊、菜)表示状态,其中每个元素都可为0或1, 用0表示在左岸, 用1表示在右岸。 (2) 把每次过河的一种安排作为一个算符,每次过河都必须有农夫, 因为只有他可以划船。
7. 请阐述状态空间的一般搜索过程。OPEN表与CLOSED表的作用是什么？ 8. 广度优先搜索与深度优先搜索各有什么特点？ 9. 图3-23是五大城市间的交通示意图, 边上的数字是两城市间的距离。用图搜索技术编写程序, 求解以下问题： (1) 任找一条西安到北京的旅行路线, 并给出其距离。 (2) 找一条从西安到北京, 必须途经上海的路径。 (3) 找一条从西安到北京, 必须途经上海, 但不能去昆明的路径。
图 3-23 交通图
10. 何谓估价函数？ 在估价函数中,g(x)和h(x)各起什么作用？ 11. 局部择优搜索与全局择优搜索的相同处与区别各是什么？ 12. 设有如图3-24所示的一棵与或树,请指出解树；并分别按和代价及最大代价求解树代价； 然后, 指出最优解树。
图 3- 24 与或树
13. 八皇后问题。在一个8×8的方格棋盘上放置八个“皇后”(棋子), 使得其中任何两个都不得在同一行、同一列、 或同一条对角线上。试给出该问题的状态图表示,并用PROLOG语言编程求解之。 若在一步步摆放棋子的过程中,优先考虑棋子放在对角线短的棋格上, 试画出相应的状态空间搜索树。
14. 传教士和野人问题。有三个传教士和三个野人一起来到河边准备渡河, 河边有一条空船,且传教士和野人都会划船, 但每次最多可供两人乘渡。河的任何一岸以及船上一旦出现野人人数超过传教士人数,野人就会把传教士吃掉。为安全地渡河,传教士应如何规划渡河方案？试给出该问题的状态图表示, 并用PROLOG语言编程求解之。 若传教士和野人的数目均为五人,渡船至多可乘三人,请定义一个启发函数, 并给出相应的搜索树。
15. 试用与或树描述下面不定积分的求解过程： ∫(x2+5x+sin2x cos2x)dx