第3章 图搜索及问题求解

主讲：李辉Email：lihui@第3章

图搜索与问题求解第3章图搜索与问题求解3.5博弈树搜索3.1状态图搜索3.2状态图搜索问题求解3.3与或图搜索3.4与或图搜索问题求解主要内容3.1状态图搜索-搜索与求解搜索是人工智能技术中进行问题求解的基本技术，不管是符号智能还是计算智能，最终往往都归结为某种搜索，用某种搜索算法去实现。图搜索模拟的是人脑分析问题、解决问题的过程，是基于领域知识的问题求解技术。计算智能是借鉴或模拟某些自然现象或生命现象而实现的搜索和问题求解技术。图搜索技术是人工智能中的核心技术之一。

3.1.1状态图例3.1走迷宫走迷宫问题就是从该有向图的初始节点出发，寻找目标节点的问题，或者是寻找通向目标节点的路径问题。3.1.1状态图例3.2八数码难题(重排九宫问题)

2831476512384765初始棋局目标棋局以上两个问题抽象来看，都是某个有向图中寻找目标或路径的问题，在人工智能技术中，把这种描述问题的有向图称为状态空间图，简称状态图。棋局作为节点，相邻节点通过移动数码一个一个产生出来，所有节点由它们的相邻关系连成一个有向图。3.1.2状态图搜索搜索：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。搜索过程中经过的节点和边，按原图的连接关系，便会构成一个树型的有向图，这种树型有向图称为搜索树。搜索进行中，搜索树会不断增长，直到当搜索树中出现目标节点，搜索便停止。这时从搜索树中就可很容易地找出从初始节点到目标节点的路径（解）来。3.1.2状态图搜索1搜索方式树式搜索

在搜索过程中记录所经过的所有节点和边。树式搜索所记录的轨迹始终是一棵树，这棵树也就是搜索过程中所产生的搜索树。线式搜索在搜索过程中只记录那些当前认为在所找路径上的节点和边。不回溯线式搜索可回溯线式搜索3.1.2状态图搜索2搜索策略盲目搜索无向导的搜索，树式盲目搜索就是穷举搜索，不回溯的线式搜索是随机碰撞式搜索，回溯的线式搜索也是穷举式搜索。启发式搜索是利用“启发性信息”引导的搜索策略。“启发性信息”就是与问题有关的有利于尽快找到问题解的信息或知识。启发式搜索分为不同的策略，如全局择优，局部择优，最佳图搜索。按扩展顺序不同分为广度优先和深度优先。3.1.2状态图搜索3

搜索算法搜索的目的是为了寻找初始节点到目标节点的路径，搜索过程中就得随时记录搜索轨迹。ClOSED表动态数据结构来记录考察过的节点。OPEN表的动态数据结构来专门登记当前待考查的节点。节点父节点编号编号节点父节点编号OPEN表CLOSED表3.1.2状态图搜索树式搜索算法

步1

把初始节点S0放入OPEN表中。

步2

若OPEN表为空，则搜索失败，退出。

步3

取OPEN表中第一个节点N放在CLOSED表中；并冠以顺序编号n；

步4

若目标节点Sg=N，成功退出。

步5

若N不可扩展，转步2。

步6

扩展N，生成一组节点，对这组子节点作如下处理：3.1.2状态图搜索（1）删除N的先辈节点（如果有的话）。（2）对已存在于OPEN表中的节点（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针，使其沿新路径返回。（3）对已存在于CLOSED表的节点，作与（2）同样的处理，并且将其移出CLOSED表，放入OPEN表中重新扩展。（4）对其余子节点配上指向N的返回指针后放入OPEN表中某处，或对OPEN表进行重新排序，转步2。3.1.2状态图搜索图

3-5修改返回指针示例

树式算法的几点说明返回指针指的是父节点在CLOSED表中的编号。步6中修改指针的原因是返回初始节点的路径有两条，要选择“短”的那条路径。这里路径长短以节点数来衡量，在后面将会看到以代价来衡量。按代价衡量修改返回指针的同时还要修改相应的代价值。3.1.2状态图搜索树式搜索例对于已存在于OPEN表中的节点（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径短，则修改这些节点在OPEN表中的原返回指针，使其沿原路径返回。Path1Path2S0mnP先扩展后扩展P在n之前已是某一节点m的后继如图所示：说明从S0→P至少有两条路，这时有两种情况：f（Path2）<f（Path1），当前路径较好，要修改P的指针，使其指向n，即搜索之后的最佳路径。否则，原路径好。3.1.2状态图搜索对已存在于CLOSED表的节点，作与（2）同样的处理，并将其移出CLOSED表，放入OPEN表中重新扩展。S0过去生成P的路径现在生成P的路径过去对Ps的最优路径PsPmnka.P在n之前已是某一节点m的后继，所以需要做如同（2）同样的处理，如图右部所示。b.P在Closed表中，说明P的后继也在n之前已经生成，称为Ps。对Ps而言同样可能由于n→P这一路径的加入，又必须比较多条路径之后而取代价小的一条，如图左部所示。3.1.2状态图搜索例：设当前搜索图和搜索树如图所示S0nPmPs’PsS0nPmPs’PsFF3.1.2状态图搜索若启发函数f(n)为从S0到节点n的最短路径的长度，用边的数目来考察，当前扩展的节点是搜索图中的n,P是n的后继S0nPmPs’PsnPPs’PsS0mFF3.1.2状态图搜索不回溯线式搜索算法

步1

把初始节点S0放入CLOSED表中；

步2

令N＝S0

；

步3

若N是目标节点，则搜索成功，结束。

步4若N不可扩展，则搜索失败，退出。

步5

扩展N，选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中，令N＝N1，转步3。3.1.2状态图搜索可回溯的线式搜索步1把初始节点S0放入CLOSED表中；步2令N＝S0

；步3若N是目标节点，则搜索成功，结束。步4若N不可扩展，则移出CLOSED表中的末端节点Ne

，若Ne＝S0，则搜索失败，退出。否则以CLOSED表新的末端节点Ne作为

N，即令N＝Ne，转步4；步5扩展N，选取其一个未在CLOSED表中出现过的子节点N1放入

CLOSED表中，令N＝N1

，转步3。3.1.3穷举式搜索广度优先搜索策略始终在同一级节点中考查，当同一级节点考查完了之后，才考查下一级节点。搜索树自顶向下一层一层逐渐生成。算法ABCDEFGHIJKLMNOPQRSTU广度优先搜索OPENCLOSEDOPENCLOSEDABCDEFGHIJKLMNOPQRSTUA广度优先搜索22OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDA广度优先搜索23OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEF广度优先搜索24OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEFCGH广度优先搜索25OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEFCGHDIJ广度优先搜索26OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEFCGHDIJEKL广度优先搜索3.1.3穷举式搜索广度优先搜索的特点广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。3.1.3穷举式搜索八数码问题28314765初始状态81324765目标状态3.1.3穷举式搜索28314765123184765923184765828143765102837146578321476562831457611283147652231847653283147654283164751228316475138321476514283714651523418765161238476517281437651828314576192836417520283167542183214765222831647558132476523八数码广度优先搜索3.1.3穷举式搜索深度优先搜索搜索策略

在搜索树的每一层始终先扩展一个子节点，不断地向纵深前进，直到不能再前进，才从当前节点返回到上一级节点，从另一方向继续前进。算法

ABCDEFGHIJKLMNOPQRSTU深度优先搜索OPENCLOSEDABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA深度优先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDABCD深度优先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDADCBIJ深度优先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDADCBIR深度优先搜索J3.1.3穷举式搜索深度优先搜索的特点OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制，即有界深度优先搜索。3.1.3穷举式搜索2318476528314765283147652831647528314765128316475328316754428316475228316754281637545…八数码深度优先搜索3.1.4启发式搜索启发式搜索的目的利用知识来引导搜索，达到减少搜索范围，降低问题复杂度。启发性信息的强弱

强：降低搜索的工作量，但可能导致找不到最优解。

弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。3.1.4启发式搜索启发函数启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数，通常记为h（x）。定义启发函数的参考思路一个节点到目标节点的某种距离或差异的量度。一个节点处在最佳路径上的概率根据主观经验的主观打分等。启发式搜索算法启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。3.1.4启发式搜索全局择优搜索全局择优搜索就是利用启发函数制导的一种启发式搜索方法。该方法亦称为最好优先搜索法。基本思想：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。3.1.4启发式搜索全局择优搜索算法

步1

把初始节点S0放入OPEN表中，计算h（S0

）；步2

若OPEN表为空，则搜索失败，退出。步3

移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4

若目标节点Sg＝N，则搜索成功结束。步5

若N不可扩展，则转步2。步6

扩展N，计算每个子节点x的函数值h（x），并将所有子节点配以指向N的返回指针后放入OPEN表中，再对OPEN表中所有子节点按其函数值的大小以升序排列，转步2。A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRST全局择优算法OPENCLOSEDA-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDA-5全局择优算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6全局择优算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4E-5F-5D-5全局择优算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5F-5H-3G-4全局择优算法A-5B-4C-4D-6E-5F-5G-4IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5F-5O-2G-4H-3H-3P-3全局择优算法A-5B-4C-4D-6E-5F-5G-4IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5F-5O-2G-4H-3H-3P-3全局择优算法3.1.4启发式搜索-全局择优搜索算法启发函数h(x)为节点x与目标格局相比数码不同的位置个数。从图看出解为：S0，S1，S2，S3，

Sg。3.1.4启发式搜索-局部择优搜索算法基本思想是当每一个节点被扩展后，按h(x)对每一个子节点计算启发值，并选择最小者作为下一个要考察的节点，由于每次都只是在子节点的范围内选择下一个要考察的节点，范围比较狭窄，所以称为局部择优搜索。步6

扩展N，计算N每个子节点x的函数值h（x），并将N的子节点按估计值升序排列放入OPEN表的首部，为每个子节点配置指向节点N的指针，转步2。3.1.5加权状态图搜索例3.6交通图A城是出发地，E是目的地，数字表示两城之间交通费用。求A到E的最小费用的旅行路线。ADCEB464332边上附有数值的状态图称为加权状态图或赋权状态图，这种数值称为权值。3.1.5加权状态图搜索加权状态图的搜索加权状态图的搜索与权值有关，并且要用权值来导航。具体来讲，加权状态图的搜索算法，要在一般状态图搜索算法基础上再增加权值的计算与传播过程，并且要由权值来确定节点的扩展顺序。代价的计算

g（x）表示从初始节点S0到节点x的代价。

c（xi，xj）表示父节点xi到子节点xj的代价

g（xj）＝g（xi）＋c（xi，xj）

g（x0）＝03.1.5加权状态图搜索加权状态图转换为代价树搜索从初始节点出发，先把每一个与初始节点相邻的节点作为该节点的子节点。然后对其他节点依次类推，但对其他节点x，不能将其父节点及祖先再作为x的子节点。ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B33.1.5加权状态图搜索分支界限法其基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察，而不管这个节点在搜索树的什么位置上。与全局择优法的区别选取扩展节点标准计算方法分支界限法代价值g（x）g（x）与节点所处的位置有关，与边也有关系，从初始节点S0计算而来。全局择优法启发函数值h（x）h（x）与节点有关，与边可能有关或无关，从目标节点方向计算而来。3.1.5加权状态图搜索最近择优法（瞎子爬山法）基本思想：每次仅考察N的子节点的g（x），选取N的子节点中代价最小的子节点进行扩展。最近择优法与局部择优法的区别：选取扩展节点标准计算方法最近择优法代价值g（x）g（x）与节点所处的位置有关，与边也有关系，从初始节点S0计算而来。局部择优法启发函数h（x）h（x）与节点有关，与边可能有关或无关，从目标节点方向计算而来。内容回顾：树式搜索策略比较全局局部深度d(x)宽度优先搜索深度优先搜索启发值h(x)全局择优搜索局部择优搜索代价值g(x)分支界限法瞎子爬山法范围标准S0Sg23ab4615cdgfhijk5f543789h（x），有利于搜索纵向发展，提高搜索效率，但影响完备性。g（x），有利于搜索横向发展，提高完备性，但影响搜索效率。穷举式搜索启发式搜索加权状态图搜索3.1.6A算法估价函数

将启发函数与代价函数相结合，为了防止在单独利用启发函数的时候误入歧途。

f（x）＝g（x）＋h（x）f（x）是初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值总和。是g（x）与h（x）的折中。3.2状态图搜索问题求解3.2.1问题的状态图表示

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

2.状态转换规则（操作operator）引起状态中某些分量发生改变，从而使一个具体状态变化到另一个具体状态的作用。描述了状态之间的关系。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。

3.2.1问题的状态图表示状态空间（StateSpace）问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。状态空间一般用赋值有向图表示，记为：（S，F，G）S：问题的可能有的初始状态的集合；F：操作的集合；G：目标状态的集合。3.2.1问题的状态图表示例3.7迷宫问题的状态图表示。S：SoF：｛(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.2.1问题的状态图表示补充例1三枚钱币，能否从下面状态翻动三次后出现全正或全反状态。反正反正正正反反反初始状态θs目标状态集合{θ0,θ7}3.2.1问题的状态图表示引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为0，反面为1，全部可能的状态为：

Q0=(0,0,0);Q1=(0,0,1);Q2=(0,1,0)Q3=(0,1,1);Q4=(1,0,0);Q5=(1,0,1)Q6=(1,1,0);Q7=(1,1,1)。翻动钱币的操作抽象为改变上述状态的算子，即F＝{a,b,c}

a:把钱币q0翻转一次

b:把钱币q1翻转一次

c:把钱币q2翻转一次问题的状态空间为<{Q5},{Q0Q7},{a,b,c}>3.2.1问题的状态图表示状态空间图（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，1）（1，1，1）acabacabcbbc3.2.1问题的状态图表示

例3.9

二阶梵塔问题一号杆有A、B两个金盘，A小于B。要求将AB移至三号杆，每次只可移动一个盘子，任何时刻B不能在A上。用二元组（SA，SB）表示状态，SA表示A所在杆号，SB表示B所在杆号，全部状态如下：（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）3.2.1问题的状态图表示AB123S0：（1，1）123S1：（1，2）123S2：（1，3）AA123S5：（2，3）123S4：（2，2）123S3：（2，1）123S8：（3，3）123S7：（3，2）123S6：（3，1）AAAAABABBBBB3.2.1问题的状态图表示转换规则：A（i，j）表示金盘A从第i号杆移到j号杆

B（i，j）表示金盘B从第i号杆移到j号杆

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）初始状态（1，1），目标状态（3，3）梵塔问题用状态图表示为：

<{(1,1)},{A(1,2),…，B(3,2)},{(3,3)}>3.2.1问题的状态图表示1,12,13,12,33,31,33,21,22,2A(1,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)3.2.1问题的状态图表示例3.8重排九宫问题（八数码难题）X1X2X3X8X0X4X7X6X5将棋局用向量A＝(X0，X1，

X2，

X3，

X4，

X5，

X6，

X7，

X8)表示，其中Xi为变量，值表示方格Xi内的数字。初始状态S0＝（0，2，8，3，4，5，6，7，1）目标状态Sg

＝（0，1，2，3，4，5，6，7，8）数码的移动规则就是该问题的状态变化规则。经分析，该问题共有24条规则，分为9组。2831476512384765初始棋局目标棋局3.2.1问题的状态图表示0组规则

r1(X0=0

)(X2=n

)X0=nX2=0；

r2(X0=0

)(X4=n

)X0=nX4=0；

r3(X0=0

)(X6=n

)X0=nX6=0；

r4(X0=0

)(X8=n

)X0=nX8=0；1组规则

r5(X1=0

)(X2=n

)X1=nX2=0；

r6(X1=0

)(X8=n

)X1=nX8=0；8组规则:

r22(X8=0

)(X1=n

)X8=nX1=0；

r23(X8=0

)(X0=n

)X8=nX0=0；

r24(X8=0

)(X7=n

)X8=nX7=0；X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X53.2.1问题的状态图表示八数码的状态图可表示为（{S0},{r1,r2,…,r24},{Sg}）八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。3.3与或图搜索例3.15证明四边形全等。分析：连接BD，B´D´，原来问题可以分解为两个子问题：

Q1：证明ΔABC≌ΔA′B′C′

Q2：证明ΔBCD≌ΔB′C′D′原来问题可以分为两个子问题解决。ABDCA´B´D´C´3.3.1与或图问题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.3.1与或图将原问题用图的形式表示如下：QQ1Q2Q11Q12Q13Q11'Q12'Q13'Q21Q22Q23Q21'Q22'Q23'弧线表示所连边为“与”的关系不带弧线的边为或关系问题的解3.3.1与或图与或图的几个概念直接可解的问题称为本原问题。本原问题对应的节点称为终止节点。无子节点的节点称为端节点。子节点为与关系，则该节点为与节点。子节点为或关系，则该节点为或节点。3.3.2与或图搜索1.搜索方式,解图(树)与或图搜索也分为树式和“线”式两种类型。与或图搜索解图(树),不只是寻找目标节点,而是边扩展节点边进行逻辑判断,以确定初始节点是否可解。一旦能够确定初始节点的可解性,则搜索停止。根据返回指针便可从搜索树中得到一个解图(树)。解图(树)实际上是由可解节点形成的一个子图(树),这个子图(树)的根为初始节点,叶为终止节点,且这个子图(树)还一定是与图(树)。

3.3.2与或图搜索2.可解性判别

怎样判断一个节点的可解性呢？下面给出判别准则。

(1)一个节点是可解,则节点须满足下列条件之一: ①终止节点是可解节点。

②一个与节点可解,当且仅当其子节点全都可解。

③一个或节点可解,只要其子节点至少有一个可解。

(2)一个节点是不可解,则节点须满足下列条件之一: ①非终止节点的端节点是不可解节点。

②一个与节点不可解,只要其子节点至少有一个不可解。

③

一个或节点不可解,当且仅当其子节点全都不可解。

3.3.2与或图搜索4.搜索算法

与或树的树式搜索过程可概括为以下步骤：

步1把初始节点Qo放入OPEN表。步2移出OPEN表的第一个节点N放入CLOSED表,并冠以序号n。

步3若节点N可扩展,则做下列工作：

(1)扩展N,将其子节点配上指向父节点的指针后放入OPEN表。

(2)考察这些子节点中是否有终止节点。若有,则标记它们为可解节点,并将它们也放入CLOSED表,然后由它们的可解反向推断其先辈节点的可解性,并对其中的可解节点进行标记。如果初始节点也被标记为可解节点,则搜索成功,结束。

(3)删去OPEN表中那些具有可解先辈的节点(因为其先辈节点已经可解,故已无再考察该节点的必要),转步2。

3.3.2与或图搜索步4若N不可扩展,则做下列工作：

(1)标记N为不可解节点,然后由它的不可解反向推断其先辈节点的可解性,并对其中的不可解节点进行标记。如果初始节点So也被标记为不可解节点,则搜索失败,退出。

(2)删去OPEN表中那些具有不可解先辈的节点(因为其先辈节点已不可解,故已无再考察这些节点的必要),转步2。

3.3.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.3.2与或图搜索(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启发式与或树搜索3.3.3启发式与或树搜索广度优先搜索及深度优先搜索都是盲目搜索,其共同点是：

(1)搜索从初始节点开始,先自上而下地进行搜索,寻找终止节点及端节点,然后再自下而上地进行可解性标记,一旦初始节点被标记为可解节点或不可解节点,搜索就不再继续进行。

(2)搜索都是按确定路线进行的,当要选择一个节点进行扩展时,只是根据节点在与或树中所处的位置,而没有考虑要付出的代价,因而求得的解树不一定是代价最小的解树,即不一定是最优解树

。

为了求得最优解树，要在每次扩展节点时计算扩展该节点要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定搜索路线的方法称为与或树的有序搜索，是一种重要的启发式搜索策略。3.3.3启发式与或树搜索

1.解树的代价解树的代价就是树根的代价。树根的代价是从树叶开始自下而上逐层计算而求得的。而解树的根对应的是初始节点Qo。这就是说,在与或树的搜索过程中,代价的计算方向与搜索树的生长方向相反。这一点是与状态图不同的。具体来讲,有下面的计算方法：设g(x)表示节点x的代价,c(x,y)表示节点x到其子节点y的代价(即边xy的代价),则

(1)若x是终止节点,g(x)＝0。3.3.3启发式与或树搜索

(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)=73.3.3启发式与或树搜索课堂练习-习题三.12

12.设有如图3-24所示的一棵与或树，请指出解树；并分别按和代价及最大代价求解树代价；然后，指出最优解树。

一棵解树由S0,A,D,t1,t2,t3组成；另一棵解树由S0,B,E,t4,t5组成；左边解树：

按和代价：g(D)=4,g(A)=7,g(S0)=12

按最大代价：g(D)=2,g(A)=5,g(S0)=10右边解树：

按和代价：g(E)=2,g(B)=11,g(S0)=18

按最大代价：g(E)=2,g(B)=7,g(S0)=14按和代价计算，左边的解树为最优解树，按最大代价计算，仍是左边的解树为最优解树。因此，左边的解树为最优解树。3.3.3启发式与或树搜索有序搜索的目的是求出最优解树,即代价最小的解树。这就要求搜索过程中任一时刻求出的部分解树其代价都应是最小的。为此,每次选择欲扩展的节点时都应挑选有希望成为最优解树一部分的节点进行扩展。由于这些节点及其先辈节点(包括初始节点So)所构成的与或树有可能成为最优解树的一部分,因此称它为“希望树”。下面给出希望树的定义：

(1)初始节点Qo在希望树T中。

(2)如果节点x在希望树T中,则一定有：①如果x是具有子节点y1,y2,…,yn的“或”节点,则具有值的那个子节点yi也应在T中。②如果x是“与”节点,则它的全部子节点都应在T中。3.3.3启发式与或树搜索

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

(1)标示N为可解节点。

(2)对T应用可解标记过程,把N的先辈节点中的可解节点都标记为可解节点。

(3)若初始节点Qo能被标记为可解节点,则T就是最优解树,成功退出。

(4)否则,从OPEN表中删去具有可解先辈的所有节点。步5如果节点N不是终止节点,且它不可扩展,则做下列工作：

(1)标示N为不可解节点。

(2)对T应用不可解标记过程,把N的先辈节点中的不可解节点都标记为不可解节点。

(3)若初始节点Qo也被标记为不可解节点,则失败退出。

(4)否则,从OPEN表中删去具有不可解先辈的所有节点。步6如果节点N不是终止节点,但它可扩展,则可做下列工作：

(1)扩展节点N,产生N的所有子节点。

(2)把这些子节点都放入OPEN表中,并为每一个子节点配置指向父节点(节点N)的指针。

(3)计算这些子节点的g值及其先辈节点的g值。步7转步2。3.3.3启发式与或树搜索

例3.18

下面我们举例说明上述搜索过程。