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

第3章图搜索与问题求解第3章图搜索与问题求解3.1状态图搜索3.2状态图搜索问题求解3.3与或图搜索3.4与或图搜索问题求解第3章图搜索与问题求解3.1状态图搜索3.1.1状态图例3.1迷宫问题。第3章图搜索与问题求解图3-2迷宫的有向图表示第3章图搜索与问题求解图3-3八数码问题示例例3.2八数码问题。第3章图搜索与问题求解3.1.2状态图搜索1.搜索方式●树式搜索●线式搜索2.搜索策略●盲目搜索●启发式(heuristic)搜索第3章图搜索与问题求解图3-4OPEN表与CLOSED表示例3.搜索算法第3章图搜索与问题求解树式搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3移出OPEN表中第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,生成一组子节点,对这组子节点做如下处理：第3章图搜索与问题求解(1)删除N的先辈节点(如果有的话)。(2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”,则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示)。(3)对已存在于CLOSED表的节点(如果有的话),做与(2)同样的处理,并且再将其移出CLOSED表,放入OPEN表重新扩展(为了重新计算代价)。(4)对其余子节点配上指向N的返回指针后放入OPEN表中某处,或对OPEN表进行重新排序,转步2。第3章图搜索与问题求解图3-5修改返回指针示例第3章图搜索与问题求解说明：(1)这里的返回指针也就是父节点在CLOSED表中的编号。(2)步6中修改返回指针的原因是,因为这些节点又被第二次生成,所以它们返回初始节点的路径已有两条,但这两条路径的“长度”可能不同。那么,当新路短时自然要走新路。(3)这里对路径的长短是按路径上的节点数来衡量的,后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量,则在需修改返回指针的同时还要修改相应的代价值,或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。第3章图搜索与问题求解线式搜索算法：·不回溯的线式搜索步1把初始节点So放入CLOSED表中。步2令N＝So。步3若N是目标节点,则搜索成功,结束。步4若N不可扩展,则搜索失败,退出。步5扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中,令N＝N1,转步3。第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章图搜索与问题求解3.1.3穷举式搜索1.广度优先搜索图3-6八数码问题的广度优先搜索第3章图搜索与问题求解广度优先搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的指针依次放入OPEN表尾部,转步2。第3章图搜索与问题求解2.深度优先搜索第3章图搜索与问题求解深度优先搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的返回指针依次放入OPEN表的首部,转步2。第3章图搜索与问题求解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。第3章图搜索与问题求解3.1.4启发式搜索1.问题的提出2.启发性信息按其用途划分,启发性信息可分为以下三类：(1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。(2)用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。(3)用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。第3章图搜索与问题求解3.启发函数启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)。4.启发式搜索算法1)2)局部择优搜索第3章图搜索与问题求解全局择优搜索算法：步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章图搜索与问题求解图3-8八数码问题的全局择优搜索第3章图搜索与问题求解例3.5用全局择优搜索法解八数码难题。初始棋局和目标棋局同例3。解设启发函数h(x)为节点x的格局与目标格局相比数码不同的位置个数。以这个函数制导的搜索树如图3-8所示。此八数问题的解为：So,S1,S2,S3,Sg。第3章图搜索与问题求解3.1.5加权状态图搜索1.加权状态图与代价树例3.6图3-9(a)是一个交通图,设A城是出发地,E城是目的地,边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。第3章图搜索与问题求解图3-9交通图及其代价树第3章图搜索与问题求解代价树的搜索。所谓代价,可以是两点之间的距离、交通费用或所需时间等等。通常用g(x)表示从初始节点So到节点x的代价,用c(xi,xj)表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有g(xj)＝g(xi)＋c(xi,xj)而g(So)＝0第3章图搜索与问题求解2.分支界限法(最小代价优先法)●基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察,而不管这个节点在搜索树的什么位置上。●算法与前面的“全局择优法”仅有引导搜索的函数不同，前者为启发函数h(x)，后者为代价g(x)。●但注意：代价值g(x)是从初始节点So方向计算而来的,而启发函数值h(x)则是朝目标节点方向计算的。第3章图搜索与问题求解3.最近择优法(瞎子爬山法)把局部择优法算法中的h(x)换成g(x)就可得最近择优法的算法。例：用代价树搜索求解例3.6中给出的问题。A→C→D→E这是一条最小费用路径(费用为8)。第3章图搜索与问题求解3.1.6A算法和A*算法1.估价函数f(x)＝g(x)＋h(x)第3章图搜索与问题求解2.A算法A算法是基于估价函数f(x)的一种加权状态图启发式搜索算法。其具体步骤如下：步1把附有f(So)的初始节点So放入OPEN表。步2若OPEN表为空,则搜索失败,退出。步3移出OPEN表中第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。第3章图搜索与问题求解步6扩展N,生成一组附有f(x)的子节点,对这组子节点做如下处理：(1)考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点,若有则删除之；对于其余节点,也删除之,但由于它们又被第二次生成,因而需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f(x)值,修改原则是“抄f(x)”。(2)对其余子节点配上指向N的返回指针后放入OPEN表中,并对OPEN表按f(x)值以升序排序,转步2。第3章图搜索与问题求解算法中节点x的估价函数f(x)的计算方法是f(xj)＝g(xj)＋h(xj)＝g(xi)＋c(xi,xj)＋h(xj)(xj是xi的子节点)至于h(x)的计算公式则需由具体问题而定。可以看出,A算法其实就是对于本节开始给出的图搜索一般算法中的树式搜索算法,再增加了估价函数f(x)的一种启发式搜索算法。第3章图搜索与问题求解3.A*算法如果对上述A算法再限制其估价函数中的启发函数h(x)满足：对所有的节点x均有h(x)≤h*(x)其中h*(x)是从节点x到目标节点的最小代价,即最佳路径上的实际代价(若有多个目标节点则为其中最小的一个),则它就称为A*算法。第3章图搜索与问题求解3.1.7状态图搜索策略小结第3章图搜索与问题求解3.2状态图搜索问题求解3.2.1问题的状态图表示1.状态状态就是问题在任一确定时刻的状况,它表征了问题特征和结构等。状态在状态图中表示为节点。状态一般用一组数据表示。在程序中用字符、数字、记录、数组、结构、对象等表示。第3章图搜索与问题求解2.状态转换规则就是能使问题状态改变的某种操作、规则、行为、变换、关系、函数、算子、过程等等。状态转换规则也称为操作,问题的状态也只能经定义在其上的这种操作而改变。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。第3章图搜索与问题求解3.状态图表示一个问题的状态图是一个三元组(S,F,G)其中S是问题的初始状态集合,F是问题的状态转换规则集合,G是问题的目标状态集合。一个问题的全体状态及其关系就构成一个空间,称为状态空间。所以,状态图也称为状态空间图。第3章图搜索与问题求解例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章图搜索与问题求解X1X2X3X８X0X4X7X6X5例3.8八数码难题的状态图表示。用向量A＝(X0,X1,X2,X3,X4,X5,X6,X7,X8)表示,Xi为变量,Xi的值就是所在方格内的数字。于是,向量A就是该问题的状态表达式。我们将棋局第3章图搜索与问题求解So＝(0,2,8,3,4,5,6,7,1)Sg＝(0,1,2,3,4,5,6,7,8)第3章图搜索与问题求解0组规则:;0)()0(;0)()0(;0)()0(;0)()0(80804606034040220201XnXnXXrXnXnXXrXnXnXXrXnXnXXr1组规则:;0)()0(;0)()0(8181621215XnXnXXrXnXnXXr第3章图搜索与问题求解2组规则:;0)()0(;0)()0(;0)()0(020293232812127XnXnXXrXnXnXXrXnXnXXr8组规则:;0)()0(;0)()0(;0)()0(787824080823181822XnXnXXrXnXnXXrXnXnXXr于是,八数码问题的状态图可表示为({So},{r1,r2,…,r24},{Sg})第3章图搜索与问题求解例3.9梵塔问题。传说在印度的贝那勒斯的圣庙中,主神梵天做了一个由64