第3章图搜索与问题求解课件.ppt

主讲：李 辉Email：,第3章图搜索与问题求解,第3章 图搜索与问题求解,3.5 博弈树搜索,3.1 状态图搜索,3.2 状态图搜索问题求解,3.3 与或图搜索,3.4 与或图搜索问题求解,主要内容,3.1 状态图搜索-搜索与求解,搜索是人工智能技术中进行问题求解的基本技术，不管是符号智能还是计算智能，最终往往都归结为某种搜索，用某种搜索算法去实现。图搜索模拟的是人脑分析问题、解决问题的过程，是基于领域知识的问题求解技术。计算智能是借鉴或模拟某些自然现象或生命现象而实现的搜索和问题求解技术。,图搜索技术是人工智能中的核心技术之一。,3.1.1 状态图,例3.1走迷宫,走迷宫问题就是从该有向图的初始节点出发，寻找目标节点的问题，或者是寻找通向目标节点的路径问题。,3.1.1 状态图,例3.2八数码难题(重排九宫问题),初始棋局,目标棋局,以上两个问题抽象来看，都是某个有向图中寻找目标或路径的问题，在人工智能技术中，把这种描述问题的有向图称为状态空间图，简称状态图。,棋局作为节点，相邻节点通过移动数码一个一个产生出来，所有节点由它们的相邻关系连成一个有向图。,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表中的原返回指针，使其沿原路径返回。,Path1,Path2,S0,m,n,P,先扩展,后扩展,P在n之前已是某一节点m的后继,如图所示：说明从S0P至少有两条路，这时有两种情况：f（Path2） f（Path1），当前路径较好，要修改P的指针，使其指向n，即搜索之后的最佳路径。否则，原路径好。,3.1.2 状态图搜索,对已存在于CLOSED表的节点，作与（2）同样的处理，并将其移出CLOSED表，放入OPEN表中重新扩展。,S0,过去生成P的路径,现在生成P的路径,过去对Ps的最优路径,Ps,P,m,n,k,a.P在n之前已是某一节点m的后继，所以需要做如同（2）同样的处理，如图右部所示。b.P在Closed表中，说明P的后继也在n之前已经生成，称为Ps。对Ps而言同样可能 由于nP这一路径的加入，又必须比较多条路径之后而取代价小的一条，如图左部所示。,3.1.2 状态图搜索,例：设当前搜索图和搜索树如图所示,S0,n,P,m,Ps,Ps,S0,n,P,m,Ps,Ps,F,F,3.1.2 状态图搜索,若启发函数f(n)为从S0到节点n的最短路径的长度，用边的数目来考察，当前扩展的节点是搜索图中的n,P是n的后继,S0,n,P,m,Ps,Ps,n,P,Ps,Ps,S0,m,F,F,3.1.2 状态图搜索,不回溯线式搜索算法 步1 把初始节点S0放入CLOSED表中； 步2 令N S0 ； 步3 若N是目标节点，则搜索成功，结束。 步4 若N不可扩展，则搜索失败，退出。 步5 扩展N，选取其一个未在CLOSED表中出现过的 子节点N1放入 CLOSED表中，令NN1，转步3。,3.1.2 状态图搜索,可回溯的线式搜索步1 把初始节点S0放入CLOSED表中；步2 令N S0 ；步3 若N是目标节点，则搜索成功，结束。步4 若N不可扩展，则移出CLOSED表中的末端节点Ne ，若NeS0， 则搜索失败，退出。否则以CLOSED表新的末端节点Ne作为 N，即令N Ne，转步4；步5 扩展N，选取其一个未在CLOSED表中出现过的子节点N1放入 CLOSED表中，令N N1 ，转步3。,3.1.3 穷举式搜索,广度优先搜索策略 始终在同一级节点中考查，当同一级节点考查完了之后，才考查下一级节点。搜索树自顶向下一层一层逐渐生成。算法,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,广度优先搜索,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,广度优先搜索,22,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,B,C,D,A,广度优先搜索,23,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,B,C,D,A,B,E,F,广度优先搜索,24,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,B,C,D,A,B,E,F,C,G,H,广度优先搜索,25,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,B,C,D,A,B,E,F,C,G,H,D,I,J,广度优先搜索,26,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,B,C,D,A,B,E,F,C,G,H,D,I,J,E,K,L,广度优先搜索,3.1.3 穷举式搜索,广度优先搜索的特点广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。,3.1.3 穷举式搜索,八数码问题,3.1.3 穷举式搜索,八数码广度优先搜索,3.1.3 穷举式搜索,深度优先搜索搜索策略 在搜索树的每一层始终先扩展一个子节点，不断地向纵深前进，直到不能再前进，才从当前节点返回到上一级节点，从另一方向继续前进。算法,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,深度优先搜索,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,深度优先搜索,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,B,C,D,深度优先搜索,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,D,C,B,I,J,深度优先搜索,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,A,D,C,B,I,R,深度优先搜索,J,3.1.3 穷举式搜索,深度优先搜索的特点OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制，即有界深度优先搜索。,3.1.3 穷举式搜索,八数码深度优先搜索,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-5,B-4,C-4,D-6,E-5,F-5,G-4,H-3,I,J,K,L,M,N,O-2,P-3,Q,R,S,T,全局择优算法,A-5,B-4,C-4,D-6,E-5,F-5,G-4,H-3,I,J,K,L,M,N,O-2,P-3,Q,R,S,T,A-5,全局择优算法,A-5,B-4,C-4,D-6,E-5,F-5,G-4,H-3,I,J,K,L,M,N,O-2,P-3,Q,R,S,T,B-4,A-5,C-4,D-6,全局择优算法,A-5,B-4,C-4,D-6,E-5,F-5,G-4,H-3,I,J,K,L,M,N,O-2,P-3,Q,R,S,T,B-4,A-5,C-4,E-5,F-5,D-5,全局择优算法,A-5,B-4,C-4,D-6,E-5,F-5,G-4,H-3,I,J,K,L,M,N,O-2,P-3,Q,R,S,T,B-4,A-5,C-4,D-6,E-5,F-5,H-3,G-4,全局择优算法,A-5,B-4,C-4,D-6,E-5,F-5,G-4,I,J,K,L,M,N,O-2,P-3,Q,R,S,T,B-4,A-5,C-4,D-6,E-5,F-5,O-2,G-4,H-3,H-3,P-3,全局择优算法,A-5,B-4,C-4,D-6,E-5,F-5,G-4,I,J,K,L,M,N,O-2,P-3,Q,R,S,T,B-4,A-5,C-4,D-6,E-5,F-5,O-2,G-4,H-3,H-3,P-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的最小费用的旅行路线。,A,D,C,E,B,4,6,4,3,3,2,边上附有数值的状态图称为加权状态图或赋权状态图，这种数值称为权值。,3.1.5 加权状态图搜索,加权状态图的搜索加权状态图的搜索与权值有关，并且要用权值来导航。具体来讲，加权状态图的搜索算法，要在一般状态图搜索算法基础上再增加权值的计算与传播过程，并且要由权值来确定节点的扩展顺序。代价的计算 g（x）表示从初始节点S0到节点x的代价。 c（xi，xj）表示父节点xi到子节点xj的代价 g（ xj ）g（ xi ） c（xi，xj） g（ x0 ）0,3.1.5 加权状态图搜索,加权状态图转换为代价树搜索从初始节点出发，先把每一个与初始节点相邻的节点作为该节点的子节点。然后对其他节点依次类推，但对其他节点x，不能将其父节点及祖先再作为x的子节点。,A,D,C,E,B,4,6,4,3,3,2,3,2,3,4,6,2,3,4,4,6,3,2,C1,B1,D1,D2,E1,C2,E2,D3,C3,B2,E4,E3,6,B3,3.1.5 加权状态图搜索,分支界限法其基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察，而不管这个节点在搜索树的什么位置上。与全局择优法的区别,3.1.5 加权状态图搜索,最近择优法（瞎子爬山法）基本思想：每次仅考察N的子节点的g（x），选取N的子节点中代价最小的子节点进行扩展。最近择优法与局部择优法的区别：,内容回顾：树式搜索策略比较,S0,Sg,2,3,a,b,4,6,1,5,c,d,g,f,h,i,j,k,5,f,5,4,3,7,8,9,h（x），有利于搜索纵向发展，提高搜索效率，但影响完备性。,g（x），有利于搜索横向发展，提高完备性，但影响搜索效率。,穷举式搜索,启发式搜索,加权状态图搜索,3.1.6 A算法,估价函数 将启发函数与代价函数相结合，为了防止在单独利用启发函数的时候误入歧途。 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 问题的状态图表示,状态空间（State Space）问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。状态空间一般用赋值有向图表示，记为： （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)。,翻动钱币的操作抽象为改变上述状态的算子， 即Fa, b, c a:把钱币q0翻转一次 b:把钱币q1翻转一次 c:把钱币q2翻转一次 问题的状态空间为,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）,a,c,a,b,a,c,a,b,c,b,b,c,3.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 问题的状态图表示,B,A,A,A,A,A,B,A,B,B,B,B,B,3.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）梵塔问题用状态图表示为： ,3.2.1 问题的状态图表示,1,1,2,1,3,1,2,3,3,3,1,3,3,2,1,2,2,2,A(1,2),A(1,2),B(3,2),A(3,1),B(1,3),A(2,3),3.2.1 问题的状态图表示,例3.8重排九宫问题（八数码难题）,将棋局用向量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组。,初始棋局,目标棋局,3.2.1 问题的状态图表示,0组规则 r1(X0=0 ) (X2=n ) X0 = n X2 =0； r2(X0=0 ) (X4=n ) X0 = n X4 =0； r3(X0=0 ) (X6=n ) X0 = n X6 =0； r4(X0=0 ) (X8=n ) X0 = n X8 =0；1组规则 r5(X1=0 ) (X2=n ) X1 = n X2 =0； r6(X1=0 ) (X8=n ) X1 = n X8 =0；8组规则: r22(X8=0 ) (X1=n ) X8 = n X1 =0； r23(X8=0 ) (X0=n ) X8 = n X0=0； r24(X8=0 ) (X7=n ) X8 = n X7 =0；,3.2.1 问题的状态图表示,八数码的状态图可表示为 （S0, r1 , r2 , , r24 , Sg）八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。,3.3 与或图搜索,例3.15 证明四边形全等。分析：连接BD， BD，原来问题可以分解为两个子问题： Q1：证明ABC ABC Q2：证明BCD BCD原来问题可以分为两个子问题解决。,3.3.1 与或图,问题Q1还可以再被分解为： Q11 ：证明AB AB Q12 ：证明AD AD Q13 ：证明A A或 Q11 ：证明ABAB Q12 ：证明ADAD Q13 ：证明BDBD ,问题Q2还可以再被分解为： Q21 ：证明BC BC Q22 ：证明CD CD Q23 ：证明 C C 或 Q21 ：证明BC B C Q22 ：证明CDC D Q23 ：证明BD BD ,3.3.1 与或图,将原问题用图的形式表示如下：,弧线表示所连边为“与”的关系,不带弧线的边为或关系,问题的解,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)=7,3.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 下面我们举例说明上述搜索过程。 设初始节点为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计算, 下同。 ),3.3.3 启发式与或树搜索,此时,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。显然, 左子树的代价小, 所以现在改取左子树作为当前的希望树。,3.3.3 启发式与或树搜索,3.3.3 启发式与或树搜索,假设对节点B扩展两层后得到如图3-17(c)所示的与或树, 节点旁的数字是对相应节点的估算值, 节点L的两个子节点是终止节点, 则按和代价法计算得到,g(L)=2, g(M)=6, g(B)=3, g(A)=8,由此可推算出g(Qo)=9。这时, 左子树仍然是希望树, 继续对其扩展。该扩展节点C。,假设节点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.3.3 启发式与或树搜索,3.4 与或图搜索问题求解,与或图是描述问题求解的另一种有向图。与或图的节点一般代表问题，整个图表示问题空间。与或图也是一个三元组 （Q0 , F , Qn） Q0表示初始问题，F表示问题变换规则集，Qn表示本原问题集,分解与树,与树问题分解,3.4 与或图搜索问题求解,3.4 与或图搜索问题求解,变换或树,或树问题变换,例3.19 三阶梵塔问题。 对于梵塔问题，我们也可以这样考虑：为把1号杆上的n个盘子搬到3号杆，可先把上面的n-1个盘子搬到2号杆上；再把剩下的一个大盘子搬到3号杆；然后再将2号杆上的n-1个盘子搬到3号杆。这样，就把原来的一个问题分解为三个子问题。这三个子问题都比原问题简单，其中第二个子问题已是直接可解的问题。对于第一和第三两个子问题，可用上面n个盘子的方法，做同样的处理。 梵塔问题示例,3.4.1 问题的与或图表示,图 3-18 三阶梵塔问题的与或树,3.4.1 问题的与或图表示,在图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.1 问题的与或图表示,本章我们讲述了状态图搜索算法：树式搜索、线式搜索、穷举式搜索、启发式搜索、加权状态图搜索状态图搜索问题求解与或图搜索：搜索算法，启发式与或图搜索与或图图搜索问题求解,1.5 本章小结,本章总结,