第 3 章 图搜索与问题求解 3.1 状态图搜索 3.2 状态图搜索问题求解 3.3 与或图搜索 3.4 与或图搜索问题求解

3.1 状态图搜索 3.1.1 状态图 　　例3.1 迷宫问题。

图 3-2 迷宫的有向图表示

例 3.2 八数码问题。 图 3-3 八数码问题示例

3.1.2 状态图搜索 　1. 搜索方式 　　●树式搜索 ●线式搜索 2. 搜索策略 　　 ●盲目搜索 ●启发式(heuristic)搜索 

3. 搜索算法 图 3-4 OPEN表与CLOSED表示例

步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。 树式搜索算法： 　　 步1 把初始节点So放入OPEN表中。 　　步2 若OPEN表为空, 则搜索失败, 退出。  　　步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。 　　步4 若目标节点Sg=N, 则搜索成功, 结束。  　　步5 若N不可扩展, 则转步2。 步6 扩展N, 生成一组子节点, 对这组子节点做如下处理：

(1) 删除N的先辈节点(如果有的话)。 (2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”, 则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示 )。 (3)对已存在于CLOSED表的节点(如果有的话), 做与(2)同样的处理, 并且再将其移出CLOSED表, 放入OPEN表重新扩展(为了重新计算代价)。 　(4)对其余子节点配上指向N的返回指针后放入OPEN表中某处, 或对OPEN表进行重新排序, 转步2。

图 3-5 修改返回指针示例

　　说明： (1) 这里的返回指针也就是父节点在CLOSED表中的编号。 (2) 步6中修改返回指针的原因是, 因为这些节点又被第二次生成, 所以它们返回初始节点的路径已有两条, 但这两条路径的“长度”可能不同。 那么, 当新路短时自然要走新路。 　　(3) 这里对路径的长短是按路径上的节点数来衡量的, 后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量, 则在需修改返回指针的同时还要修改相应的代价值, 或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。

步5 扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中, 令N＝N1, 转步3。 线式搜索算法： · 不回溯的线式搜索 　　 步1 把初始节点So放入CLOSED表中。 　　步2 令N＝So。 　　步3 若N是目标节点,则搜索成功,结束。  　　步4 若N不可扩展,则搜索失败,退出。  　　步5 扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中, 令N＝N1, 转步3。

步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。 　

3.1.3 穷举式搜索 　1.广度优先搜索　 图 3-6 八数码问题的广度优先搜索

步3 取OPEN表中前面第一个节点N放在CLOSED表中, 并冠以顺序编号n。 　　 广度优先搜索算法： 　　 步1 把初始节点So放入OPEN表中。 　　步2 若OPEN表为空, 则搜索失败,退出。  　　步3 取OPEN表中前面第一个节点N放在CLOSED表中, 并冠以顺序编号n。 　　步4 若目标节点Sg=N,则搜索成功, 结束。  　　步5 若N不可扩展, 则转步2。 　　步6 扩展N, 将其所有子节点配上指向N的指针依次放入OPEN表尾部, 转步2。

　2.深度优先搜索　

步3 取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。 　　 深度优先搜索算法： 　　 步1 把初始节点So放入OPEN表中。 　　步2 若OPEN表为空, 则搜索失败, 退出。  　　步3 取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。 　　步4 若目标节点Sg=N, 则搜索成功,结束。  　　步5 若N不可扩展, 则转步2。 　　步6扩展N, 将其所有子节点配上指向N的返回指针依次放入OPEN表的首部, 转步2。

步3 取OPEN表中前面第一个节点N,放入CLOSED表中, 并冠以顺序编号n。 　3. 有界深度优先搜索 步1 把So放入OPEN表中,置So的深度d(So)=0。 　 步2 若OPEN表为空, 则失败, 退出。  　　步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。

(1) 用于扩展节点的选择, 即用于决定应先扩展哪一个节点, 以免盲目扩展。  3.1.4 启发式搜索 　1. 问题的提出 2. 启发性信息 　　按其用途划分, 启发性信息可分为以下三类：  (1) 用于扩展节点的选择, 即用于决定应先扩展哪一个节点, 以免盲目扩展。  (2) 用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。  (3) 用于删除节点的选择,即用于决定应删除哪些无用节点, 以免造成进一步的时空浪费。

3.启发函数 4.启发式搜索算法 1) 全局择优搜索 2) 局部择优搜索 　　启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数, 通常记为h(x)。 4.启发式搜索算法 　1) 全局择优搜索 　2) 局部择优搜索

全局择优搜索算法： 步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。

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

●算法与前面的“全局择优法” 仅有引导搜索的函数不同，前者为启发函数h(x)，后者为代价g(x)。 　　2.分支界限法(最小代价优先法) 　 ●基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察, 而不管这个节点在搜索树的什么位置上。 ●算法与前面的“全局择优法” 仅有引导搜索的函数不同，前者为启发函数h(x)，后者为代价g(x)。  ●但注意：代价值g(x)是从初始节点So方向计算而来的,而启发函数值h(x)则是朝目标节点方向计算的。 　

例：用代价树搜索求解例3.6中给出的问题。 用分支界限法得到的路径为 A→C→D→E 这是一条最小费用路径(费用为8)。 　　3. 最近择优法(瞎子爬山法) 　把局部择优法算法中的h(x)换成g(x)就可得最近择优法的算法。  例：用代价树搜索求解例3.6中给出的问题。 用分支界限法得到的路径为 A→C→D→E 这是一条最小费用路径(费用为8)。

3.1.6 A算法和A*算法 　　1.估价函数　　 f(x)＝g(x)＋h(x)

步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。 　　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)是从节点x到目标节点的最小代价, 即最佳路径上的实际代价(若有多个目标节点则为其中最小的一个),则它就称为A*算法。 　 如果对上述A算法再限制其估价函数中的启发函数h(x)满足： 对所有的节点x均有 h(x)≤h*(x) 其中h*(x)是从节点x到目标节点的最小代价, 即最佳路径上的实际代价(若有多个目标节点则为其中最小的一个),则它就称为A*算法。

3.1.7 状态图搜索策略小结

3.2 状态图搜索问题求解 3.2.1 问题的状态图表示 1. 状态 　　1. 状态 　　 状态就是问题在任一确定时刻的状况,它表征了问题特征和结构等。状态在状态图中表示为节点。状态一般用一组数据表示。在程序中用字符、数字、记录、数组、结构、对象等表示。

　　2. 状态转换规则 　　状态转换规则就是能使问题状态改变的某种操作、规则、 行为、变换、关系、函数、算子、过程等等。状态转换规则也称为操作,问题的状态也只能经定义在其上的这种操作而改变。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。

3. 状态图表示 一个问题的状态图是一个三元组 (S, F, G) 其中S是问题的初始状态集合, F是问题的状态转换规则集合, G是问题的目标状态集合。 一个问题的全体状态及其关系就构成一个空间, 称为状态空间。所以,状态图也称为状态空间图。

　　例 3.7 迷宫问题的状态图表示。  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

例 3.8　八数码难题的状态图表示。 我们将棋局 X1 X2 X3 X８ X0 X4 X7 X6 X5 用向量 A＝(X0, X1, X2, X3, X4, X5, X6, X7, X8) 表示, Xi为变量,Xi的值就是所在方格内的数字。于是,向量A就是该问题的状态表达式。

设初始状态和目标状态分别为 So＝(0, 2, 8, 3, 4, 5, 6, 7, 1) Sg＝(0, 1, 2, 3, 4, 5, 6, 7, 8)

0组规则: 1组规则:

2组规则: 8组规则: 于是, 八数码问题的状态图可表示为 ({So}, {r1, r2, …, r24}, {Sg})

　　例3.9 梵塔问题。传说在印度的贝那勒斯的圣庙中,主神梵天做了一个由64个大小不同的金盘组成的“梵塔”, 并把它穿在一个宝石杆上。另外, 旁边再插上两个宝石杆。 然后, 他要求僧侣们把穿在第一个宝石杆上的64个金盘全部搬到第三个宝石杆上。 搬动金盘的规则是：一次只能搬一个；不允许将较大的盘子放在较小的盘子上。于是,梵天预言：一旦64个盘子都搬到了3号杆上, 世界将在一声霹雳中毁灭。 盘子的搬动次数： 264-1＝18 446 744 073 709 511 615

　二阶梵塔问题 设有三根宝石杆,在1号杆上穿有A、B两个金盘, A小于B, A位于B的上面。用二元组(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〈条件〉THENA(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 二阶梵塔状态空间图

A … So: A。  Sg: A, …, A。 其中“…”为其余n-1个城市的一个序列。 　 例3.10 旅行商问题(Traveling-Salesman Problem,TSP)。 设有n个互相可直达的城市, 某推销商准备从其中的A城出发,周游各城市一遍, 最后又回到A城。要求为该推销商规划一条最短的旅行路线。  该问题的状态为以A打头的已访问过的城市序列: A … So: A。  Sg: A, …, A。 其中“…”为其余n-1个城市的一个序列。

规则2 如果所有城市都去过一次, 则从当前城市返回A城, 把A也添在去过的城市名序列后端。 　　状态转换规则：  　　规则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语言翻译如下,搜索程序用通用程序。 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). … … … */

估价函数f(x)为代价函数g(x)和启发函数h(x)之和。 其中代价函数的计算公式为 节点(A…XY)的代价＝起始城市到X城的代价＋X城到Y城的代价 其中的代价可以是距离、 费用或时间等(下同)。  启发函数值的计算公式为 节点(A…XY)的启发值＝(城市总数-已访问过的城市数-1) ×min{所有两城间的代价}

该程序实际是一个旅行商问题的通用程序。 对于一个具体的旅行路径规划, 还需也只需把具体的“地图”用谓词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′ 于是, 原问题的解决可归结为这两个子问题的解决。 换句话说,原问题被解决当且仅当这两个子问题都被解决。

Q11：证明AB＝A′B′ Q12：证明AD＝A′D′ Q13：证明∠A＝∠A′ 或 Q11′： 证明AB＝A′B′ 　　 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-14 一个典型的与或图

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。 　　(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是一个与节点, 故仅由t1的可解还不能确定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 中的粗线所示。

设g(x)表示节点x的代价,c(x,y)表示节点x到其子节点y的代价(即边xy的代价), 则 3.3.3 启发式与或树搜索 　1. 解树的代价 　　解树的代价就是树根的代价。计算方法如下： 　　设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 含代价的与或树

　　 2. 希望树 希望树的定义：  　(1) 初始节点Qo在希望树T中。  　(2) 如果节点x在希望树T中, 则一定有：  　 ① 如果x是具有子节点y1,y2, …,yn的“或”节点,则具有 值的那个子节点yi也应在T中。  ② 如果x是“与”节点, 则它的全部子节点都应在T中。

　　3. 与或树的有序搜索过程 　　与或树的有序搜索过程是一个不断选择、修正希望树的过程。如果问题有解, 则经有序搜索将找到最优解树。  其搜索过程如下：  　　步1 把初始节点Qo放入OPEN表中。  步2 求出希望树T, 即根据当前搜索树中节点的代价g求出以Qo为根的希望树T。  　步3 依次把OPEN表中T的端节点N选出放入CLOSED表中。

　　步4 如果节点N是终止节点, 则做下列工作：  (1) 标示N为可解节点。  (2) 对T应用可解标记过程, 把N的先辈节点中的可解节点都标记为可解节点。  (3) 若初始节点Qo能被标记为可解节点, 则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)

　　例 3.19　三阶梵塔问题。  　我们可把三阶梵塔问题分解为下面的三个子问题： (1) 把A、B盘从1号杆移到2号杆。  　 (2) 把C盘从1号杆移到3号杆。  　 (3) 把A、B盘从2号杆移到3号杆。  其中子问题(1)、(3)又分别可分解为三个子问题。  　 于是, 可得到三阶梵塔问题的与或树表示(见图3-18)。

图 3-18 三阶梵塔问题的与或树 三元组 (i, j, k)中的i, j, k分别代表金盘A， B， C所在的杆号。

　　所得原问题的解： (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 基于与或图搜索的迷宫问题程序。 GOAL go(a,e). DOMAINS 3.4.2 与或图问题求解程序举例　 例 3.20 基于与或图搜索的迷宫问题程序。 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).

path(X,Y,[X,X1|L1])：-path(X1,Y,L1).%回溯 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的路径 path(X,Y,[X,X1|L1])：-path(X1,Y,L1).%回溯 　　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).

例 3.21 梵塔问题程序。 DOMAINS disk_amount,pole_No=integer PREDICATES 例 3.21　梵塔问题程序。 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。