算法设计状态空间的各种搜索1017概要.pptx

状态空间的各种搜索状态空间的各种搜索一一.概述概述l广度优先搜索法广度优先搜索法：以接近起始节点的程度依次扩展节点，即对下一层节点搜索前，必须先搜索完本层所有节点l深度优先搜索法深度优先搜索法：首先扩展最新产生的节点，每层只对一个节点进行扩展，除非搜索失败或已达到预先约定的最大深度，才会退回去搜索原来忽略节点二二.广度优先搜索广度优先搜索1.定义:树上节点的扩展是沿着深度的“断层”进行的,即要对下一深度的任一节点进行搜索扩展之前,先要对当前(层)深度的每一个节点进行搜索,这种搜索能保证找到步数最少二二.广度优先搜索广度优先搜索2.算法:(1)把初始节点放入待扩展节点的open表中,此表开始只有起始节点,其结构为队结构(先进先出),节点是先产生先扩展(2)如表open空(即待扩展节点已全部扩展完),失败退出(3)把open表中队列前的节点取出,按合适的途径扩展全部子节点,并把新产生的子节点依次加入open表后,同时提供子节点返回父节点指针,若无子节点返回(2)(4)如果有任一子节点为目标节点,则找到一个解,打印路径,退出返回(2)二二.广度优先搜索广度优先搜索例1 有一个瓶中装有80ml化学溶液,实验中需要把它精确地平分成两份,没有量具,只有两杯子容量分别为50ml和30ml,编程求将溶液平分的过程.三三.深度优先搜索深度优先搜索首先扩展最新产生的节点,使搜索沿着状态空间某条单一路径从起始节点向下进行,只有搜索到没有子节点产生时,才考虑另一条替换路径,且替换路径应先选与原路径差异最小的.为避免路径太长,防止搜索过程沿无益路径扩展下去,往往给出节点扩展最大深度.如任何节点达到深度界限,可作为没有子节点的节点处理,不再深入搜索下去.三三.深度优先搜索深度优先搜索例2.8数码问题作业作业l完成8数码问题l已知:给定的源状态,求出要求的目标态l深优可用栈来存储节点,每生成一个节点就放入栈中(除了已经达到限定深度的节点外,因达到限定深度节点无需再扩展),每次我们选栈顶节点再进行扩展,直至找到目标节点为止.扩展顺序 扩展前栈内节点标号 选取扩展节点标号11122,3,4,5532,3,4,6,7742,3,4,6,8852,3,4,6662,3,4,111172,3,4482,3,14,151592,3,14,1616 102,3,17,1818三三.深度优先搜索深度优先搜索三三.深度优先搜索深度优先搜索l深优搜索算法:(1)从初始节点开始,将待扩展节点依次放到open中(后进先出)(2)如表open空,即所有待扩展节点已全部扩展完毕,则失败退出(3)取open表中最新加入的节点,即栈顶节点出栈,按适当规则扩展所有子节点,同时记录这些节点的父指针,并将这些节点依次放入open表中.若无子节点,返回(2)(4)如某一子节点为目标节点,则求得解.沿指针所示,打印路径.若只需要一个解,则退出.否则返回(2)继续搜索新的目标节点.讨论:例3:在m*m(m10态-11态-12态-13态 -14态-15态-16态三三.深度优先搜索深度优先搜索四四.等代价搜索等代价搜索l在等代价搜索中,每一节点之间的连线上都有两节点间代价值.若题目要求解最小代价路径时,可使用等代价搜索法.它沿着等代价路径断层进行扩展.其特殊情况是所有连线上的代价都相同,等代价搜索为宽度优先搜索.四四.等代价搜索等代价搜索设定:i节点到j节点代价为m(i,j)起始节点为s到节点i的代价为cost(i)搜索时按cost(i)递增顺序扩展其节点算法：(1)把起始节点s放入open表中(待扩展节点表)，令cost(s)=0(2)如open表空，则失败退出(3)从open表中选择一个节点i，要求cost(i)最小，如i非目标节点，将i节点移出open表，并扩展其子节点(4)对i的每一个子节点j，计算cost(j)=cost(i)+m(i,j),并把这些子节点放入open表中，同时记录j的父指针后返回(2)扩展规则：按代价值大小选取节点进行扩展四四.等代价搜索等代价搜索例5.假设A,B,C,D,E各个城市之间旅费如下表所列。左边一列是起点，上面一行是终点，即从A到B旅费为7，B到A的旅费为6.某人想从一个城市出发游览各城市一遍，再回到出发地，而所用旅费最少.试编一程序，求出从各地出发回到出发地的所有最佳路线。A B C D E A 0 7 3 10 15 B 6 0 5 13 12 C 4 8 0 5 10 D 9 1 6 0 11 E 17 14 9 8 0四四.等代价搜索等代价搜索分析：城市间旅费=节点间代价，制约条件是代价最小，先扩展代价最小的节点。如从A-B-E，cost(B)=7,cost(E)=cost(B)+m(B,E)=7+12=19.设计以A为起点，用等代价搜索得出部分搜索树，连线上数字为从父节点到子节点的代价.节点上方小圆圈内数字为节点扩展顺序，方框左上方为从A到该节点总代价.五五.A*算法算法l所谓A*算法是优先对那些最有希望的节点进行扩展，也即这种搜索必须引进一个估计节点”搜索价值”的量度函数(也叫估价函数)，估价函数由起始节点到该节点的一条最佳路径的实际代价与该节点到目标节点的一条最佳路径的估计代价之和组成.节点n估价函数为：五五.A*算法算法l估价函数的启发能力常通过简单乘以大于1正整数而加以提高，故有 guesscost(n)=cost(n)+H*guess(n)H值过大，会过分地强调启发分量，H值过小，会变成等代价搜索五五.A*算法算法(1)从起始节点s开始，将待扩展节点放入待扩展节点表(open表)中，并令cost(s)=0(2)若open表空，则退出(3)从open表中，选取具有最小guesscost值的节点b移出open表，若b为目标节点，则获一解，退出，如要求多解，则转(2)继续(4)若b不为目标节点，则扩展其子节点，若无子节点，返回(2)，否则对所扩展的所有子节点作如下处理：i)对b生成的节点i，计算从起始节点到该节点的实际代价和估价函数值.cost(i)=cost(b)+m(b,i)其中m(b,i)为b节点到i节点的代价 guesscost(i)=cost(i)+guess(i)*H五五.A*算法算法ii)对重复产生的子节点D，比较从起点节点经新路径到达该点的代价与旧路径到该点的代价，若不小于(即cost(D新)=cost(D旧)，则删除此节点，否则对D及相关节点的父指针及cost值进行调整(以新指针及新cost值取代之)iii)对新产生子节点，设定指向父辈节点的指针，按guesscost值大小添加到open表中适当位置(5)返回(2)继续五五.A*算法算法例：炸迷宫问题 有一个N*N迷宫，每一格或是空，或者是实，如果有一人位于迷宫的一空格(x,y)中，则他仅能到达相邻的空格(指上下左右).现有一人从(1,1)始点出发，目标是(N,N)，他随身带着K个炸弹(0=K=N)，一个炸弹的威力能把与他相邻的一个实格炸成空格.编一程序，求出R个被炸实格位置(0=R=7)(2)该迷宫能由使用者移动光标选择任一点，并能通过某一个键(自定义)使此格由实格变空或者由空变实(图2)(3)完成题所要求的任务，输出结果应显示被炸格及路径.(图3)五五.A*算法算法在A*算法中，估价函数guesscost(n)=cost(n)+guess(n)*Hcost(n)=从(1,1)到格n的实际代价，即为走过空格总数+实格总数*100guess(n)=格n到目标节点距离.例如n为(3,2),目标是(5,5),则guess(n)=(5-3)+(5-2)=3六六.分枝限界法分枝限界法l设计策略：利用分枝限界的方法构造一棵搜索树，求出搜索树中每个节点上的实际花费函数，找出花费函数的极大(小)值.也即分枝限界法是建立一个局部路径(或分枝)的队列，每次都优先扩展当前具有最大(小)消耗值分枝路径的端节点n(其估价函数为f(n)=g(n),直到生成含有目标节点的路径.六六.分枝限界法分枝限界法l例：图中各点间连线表示从一处到另一处所消耗的费用，试编一程序求任意两地之间的最小费用(代价最小)的路线，并打印所付出费用.六六.分枝限界法分枝限界法设求从v1-v5所付出代价最小路径设变量s=从始点到某点总代价(1)第一步扩展v1获得第一级子节点:v1-v2:2v1-v3:4V1-v4:5六六.分枝限界法分枝限界法(2)第二步扩展v2，获得第二级子节点v3,v7此时各条路径总代价v1-v2-v3:3v1-v2-v7:8v1-v3:4v1-v4:5选4条路径中代价最小的一条优先扩展，即v1-v2-v3六六.分枝限界法分枝限界法(3)第三步扩展v3，获第三级子节点v4,v5此时各条路径总代价v1-v2-v3-v4:7v1-v2-v3-v5:6,到达目的节点，但可能不是最小代价v1-v3:4v1-v4:5再选费用最小路径v1-v3来扩展六六.分枝限界法分枝限界法(4)第四步扩展v3,第二级子节点:v2,v4,v5其各路径总代价为：v1-v2-v3-v4:7v1-v2-v3-v5:6v1-v2-v7:8v1-v3-v2:5v1-v3-v4:8v1-v3-v5:7v1-v4:5选最小费用路径v1-v3-v2及v1-v4优先扩展这两条路径六六.分枝限界法分枝限界法(5)第五步优先扩展v2,v3,得v1-v3-v2的第二级子节点v7,v1-v4的第二级子节点v3,v6扩展后各条路经总代价是v1-v2-v3-v4:7v1-v2-v3-v5:6 该路经已到达目标节点，且为最小代价，故v1-v2-v3-v5为所求v1-v2-v7:8v1-v3-v2-v7:11v1-v3-v4:8v1-v3-v5:7v1-v4-v3:9v1-v4-v6:11作业作业