状态空间搜索策略精.ppt

《状态空间搜索策略精.ppt》由会员分享，可在线阅读，更多相关《状态空间搜索策略精.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、状态空间搜索策略第1页，本讲稿共51页13.1 搜索1搜索基本概念2搜索的一般过程第2页，本讲稿共51页21.搜索y从已知的事实出发（问题的初始状态）y寻找可用的知识（搜索）y一步一步推出最终结论（问题的目标状态）问题求解搜索第3页，本讲稿共51页3 2 搜索的一般过程OPENOPEN：存放刚刚生成的节点CLOSEDCLOSED：存放将要扩展和/或已经扩展的节点 OPEN OPEN CLOSED CLOSED第4页，本讲稿共51页41）把初始节点S0放入OPEN，并建立只包含S0的图，记为GG。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点取出放入CLOSED，并记为节点n

2、。4）考察节点是否为目标节点，是，得解，退出。5）扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记为集合MM，把这些子节点作为节点n的子节点加入GG。第5页，本讲稿共51页56）针对MM中子节点的不同情况：(1)对于那些未曾在GG中出现过的MM成员设置一个指向父节点（即节点n）的指针，把它们放入OPEN。(2)对于那些先前曾在GG中出现过的MM成员，确定是否需要修改其指向父节点（即节点n）的指针(3)对于对那些先前曾在GG中出现过的、并已经扩展了的MM成员，确定是否需要修改其后继节点指向父节点的指针7 7）按某种搜索策略搜索策略搜索策略搜索策略对OPENOPEN中的节点进行排序。

3、8）转2）。第6页，本讲稿共51页6Tower of Hanoi问题有编号为1、2、3的三个柱子和标识为A、B的尺寸依次为小、大的有中心孔的圆盘；初始状态下盘按A、B顺序堆放在1号柱子上，目标状态下盘以同样次序顺序堆放在3号柱子上，盘子的搬移须遵守以下规则：每次只能搬一个盘子，且较大盘不能压放在较小盘之上。123AB123AB第7页，本讲稿共51页7状态：状态：以三元素组描述问题状态三个元素依次指示盘子A、B所在的柱子编号TowerofHanoi问题状态描述为：S=（1,1），），G=（3,3）算子算子F：A(i,j)：把圆盘A从第i号柱子移到第j号柱子B(i,j)：把圆盘B从第i号柱子移到第

4、j号柱子状态与算子第8页，本讲稿共51页8全部可能的状态：（1,1）（1,2）（1,3）（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（2,3）（3,3）第9页，本讲稿共51页9（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）求解路径第10页，本讲稿共51页10（1,1）AB（2,1）（2,3）（3,3）求解路径第11页，本讲稿共51页1133212311A（2,3）B（1,3）A（1,2）二阶TowerofHanoi塔状态空间图(局部)第12页，本讲稿共51页

5、12 状态空间可描述为一个有向图节点指示状态节点间的有向弧表示状态变迁弧上的标签则指示导致状态变迁的操作算子状态用于记载问题求解（即搜索）过程中某一时刻问题现状状态空间图33212311A（2,3）B（1,3）A（1,2）第13页，本讲稿共51页13搜索图与搜索树33212311A（2,3）B（1,3）A（1,2）通过搜索得到的图为搜索图。由搜索图中的所有节点及反向指针所构成的集合是一棵树，为搜索树。第14页，本讲稿共51页14Tower of Hanoi问题有N个有孔的盘子，最初这些盘子都叠放在柱a上（如图1），要求将这N个盘子借助柱b从柱a移到柱c（如图2），移动时有以下限制，如何移动？每

6、次只能移动一个盘子；大盘不能放在小盘上。第15页，本讲稿共51页15重排九宫问题S028314765在3*3的方格棋盘上放置分别标语有数字的八张牌：1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8初始状态为S0目标状态为Sg。可使用的操作算符：位于空格的左、下、右、上左、下、右、上左、下、右、上左、下、右、上的牌移入空格。S223184765Sg123847 65S12318 4765S312384765第16页，本讲稿共51页1632 盲目搜索1广度优先搜索2深度优先搜索3有限深度优先搜索4代价树广度优先搜索5代价树深度优先搜索第17页，本讲稿共51页17 1 广度优先搜索1）

7、把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN的尾部尾部尾部尾部，并为每一个子节点都配一个指向父节点的指针，然后转2）。第18页，本讲稿共51页18重排九宫问题重排九宫问题重排九宫问题重排九宫问题第19页，本讲稿共51页19第20页，本讲稿共51页20第21页，本讲稿共51页21第22页，本讲稿共51页22 2 深度优先搜索1）把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出

8、。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN的首部首部首部首部，并为每一个子节点都配一个指向父节点的指针，然后转2）。第24页，本讲稿共51页24重排九宫问题重排九宫问题第25页，本讲稿共51页25重排九宫问题重排九宫问题第26页，本讲稿共51页26重排九宫问题重排九宫问题第27页，本讲稿共51页27重排九宫问题重排九宫问题第28页，本讲稿共51页28重排九宫问题重排九宫问题第29页，本讲稿共51页293 有界深度优先搜索搜索过程：1）把初始节点S0放入OPE

9、N，置S0的深度d(S0)。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n的深度d(节点n)=dm，转2）。6）若节点n不可扩展，转2）。7）扩展节点n，将其子节点放入OPEN的首部，并为每一个子节点都配一个指向父节点的指针，然后转2）。见p269例6.6第32页，本讲稿共51页324 代价树广度优先搜索边上标有代价(或费用)的树为代价树.在代价树中,若有g(x)表示从初始节点S0到节点x的代价,用c(x1,x2)表示从父节点x1到子节点x2的代价,则有:g(x2)=g(x1)

10、+c(x1,x2)第33页，本讲稿共51页334 代价树广度优先搜索搜索过程：1）把初始节点S0放入OPEN，令g(S0)=0。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，并按各节点的代价对OPEN表中的全部节点进行排序（从小到大），然后转2）。第34页，本讲稿共51页34代价树广度优先搜索第35页，本讲稿共51页355 代价树深度优先搜索搜索过程：1）把初始

11、节点S0放入OPEN，令g(S0)=0。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点按边代价从小到大进行排序放入OPEN首部，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，然后转2）。第36页，本讲稿共51页361.宽度优先、深度优先搜索，其主要的差别是OPEN表中待扩展节点的顺序问题。2.盲目搜索(弱方法)效率低，耗费过多的计算空间与时间。3.若选择最有希望的节点加以扩展，则搜索效率将会大为提高。小结第37页，本讲稿

12、共51页373.3 启发式搜索启发式搜索：启发式搜索：启发式搜索是利用问题本身的某些启发信息，以启发式搜索是利用问题本身的某些启发信息，以制导搜索朝着最有希望的方向前进。制导搜索朝着最有希望的方向前进。启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望有希望通向目标节点的不同程度，我们总是希望能找找到最有希望通向目标节点的待扩展节点优先扩展。一种最常用的方法是定义一个评价函数,:f(x)=g(x)+h(x)f(x)=g(x)+h(x)g(x)为从初始节点s0到节点x已经实际付出的代价；h(x)是从节点x到目标节点Sg的最短路径的估计,它体现了问题的启发性信息。h

13、(x)称为启发函数。第38页，本讲稿共51页38 1 局部择优搜索 局部择优搜索局部择优搜索局部择优搜索局部择优搜索：当一个节点被扩展后，按当一个节点被扩展后，按当一个节点被扩展后，按当一个节点被扩展后，按f(x)f(x)f(x)f(x)对每个子节点计对每个子节点计对每个子节点计对每个子节点计算估价值，并选择最小者作为下一个要考查的节点。由于它每算估价值，并选择最小者作为下一个要考查的节点。由于它每算估价值，并选择最小者作为下一个要考查的节点。由于它每算估价值，并选择最小者作为下一个要考查的节点。由于它每次都只是在子节点的范围中选择要考查的子节点，所以称为局次都只是在子节点的范围中选择要考查的

14、子节点，所以称为局次都只是在子节点的范围中选择要考查的子节点，所以称为局次都只是在子节点的范围中选择要考查的子节点，所以称为局部择优搜索。部择优搜索。部择优搜索。部择优搜索。深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的，这是它们的共同处。子节点作为考察范围的，这是它们的共同处。子节点作为考察范围的，这是它们的共同处。子节点作为考察范围的，这是它们的共同处。在在在在局部择优搜索局部择优搜索局部择优搜

15、索局部择优搜索中，若令中，若令中，若令中，若令f(x)=g(x),f(x)=g(x),f(x)=g(x),f(x)=g(x),则局部择优搜索就成为则局部择优搜索就成为则局部择优搜索就成为则局部择优搜索就成为代价代价代价代价树的深度优先搜索树的深度优先搜索树的深度优先搜索树的深度优先搜索；若令；若令；若令；若令f(x)=d(x),f(x)=d(x),f(x)=d(x),f(x)=d(x),这里这里这里这里d(x)d(x)d(x)d(x)表示节点表示节点表示节点表示节点x x x x的深度的深度的深度的深度,则局部择优搜索就成为则局部择优搜索就成为则局部择优搜索就成为则局部择优搜索就成为深度优先搜

16、索深度优先搜索深度优先搜索深度优先搜索。所以深度优先搜索和代价树。所以深度优先搜索和代价树。所以深度优先搜索和代价树。所以深度优先搜索和代价树的深度优先搜索可看作局部择优搜索的两个特例。的深度优先搜索可看作局部择优搜索的两个特例。的深度优先搜索可看作局部择优搜索的两个特例。的深度优先搜索可看作局部择优搜索的两个特例。第39页，本讲稿共51页392全局择优搜索全局择优搜索全局择优搜索：每次都是从每次都是从OPENOPEN表的全体节点中选择一个估价表的全体节点中选择一个估价值最小的节点进行扩展。值最小的节点进行扩展。在在全局全局择优搜索择优搜索择优搜索择优搜索中，如果中，如果f(x)=g(x),f

17、(x)=g(x),则它就成为代价树的广度则它就成为代价树的广度优先搜索；若令优先搜索；若令f(x)=d(x)f(x)=d(x)（这里（这里d(x)d(x)表示节点表示节点x x的深度）的深度）,则则它就成为广度优先搜索。所以广度优先搜索和代价树的广度它就成为广度优先搜索。所以广度优先搜索和代价树的广度优先搜索可看作全局择优搜索的两个特例。优先搜索可看作全局择优搜索的两个特例。第40页，本讲稿共51页40例用全局择优搜索求解重排九宫问题，其初始状态和目标全局择优搜索求解重排九宫问题，其初始状态和目标状态如图所示：状态如图所示：设估价函数为设估价函数为f(x)=d(x)+h(x)f(x)=d(x)

18、+h(x)其中其中d(x)d(x)表示节点表示节点x x的的深度，深度，h(x)h(x)表示表示节点x的格局与目标节点格局不相同的牌数第41页，本讲稿共51页41搜索树八数码问题第42页，本讲稿共51页42第43页，本讲稿共51页43 3 启发式搜索算法A基本思想：定义一个评价函数f:f（n）g（n）h（n）其中n是被评价的节点。g*(n)：表示从初始节点s到节点n的最短路径的代价；h*(n)：表示从节点n到目标节点g的最短路径的代价；f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的代价。而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和

19、h*（n）三个函数值的的估计值，是一种预测。第44页，本讲稿共51页44利用评价函数f(n)g(n)h(n)来排列OPEN表节点顺序的图搜索算法称为A算法。A算法每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。第45页，本讲稿共51页45 4 最佳图搜索算法A（Optimal Search）在在A算法中的算法中的f(x)=g(x)+h(x)中每一节点中每一节点x都有都有h(x)h*(x)h(x)是的是的h*(x)下界下界 则该则该A算法称为算法称为 A*算法。算法。下面

20、从理论上讨论下面从理论上讨论A*算法的几个重要特性：算法的几个重要特性：(1)A*算法的可采纳性算法的可采纳性 可采纳性可采纳性：对于一个可解状态空间图（即从：对于一个可解状态空间图（即从S0到到G存在路径），存在路径），如果搜索算法能找到一条最佳路径，则称该搜索算法是可采纳如果搜索算法能找到一条最佳路径，则称该搜索算法是可采纳的（即算法找到一条最佳路径解后终止）。的（即算法找到一条最佳路径解后终止）。结论结论1：A*算法是可采纳的。算法是可采纳的。第46页，本讲稿共51页46（2）A*算法的最优性算法的最优性（即信息量的比较）（即信息量的比较）A*算法的搜索效率在很大程度上取决于算法的搜索效

21、率在很大程度上取决于h(x)，在满足，在满足h(x)h*(x)下，下，h(x)的值越大，表明携带启发性信息越多。的值越大，表明携带启发性信息越多。结论结论2：设有两个：设有两个A*算法算法A1*和和A2*：A1*：f1(x)=g1(x)+h1(x)A2*：f2(x)=g2(x)+h2(x)对所有的非目标节点对所有的非目标节点x均有：均有：h2(x)h1(x)（A2*比比A1*有更多的信息）有更多的信息）则则A1*扩展节点数不会比扩展节点数不会比A2*扩展节点少。扩展节点少。即即A2*的扩展节点集是的扩展节点集是A1*扩展节点集的子集。扩展节点集的子集。（通过搜索树深度应用数学归纳法证明）。（通

22、过搜索树深度应用数学归纳法证明）。第47页，本讲稿共51页47（3）A*算法的改进算法的改进(h(x)的单调性限制的单调性限制)单调性限制：单调性限制：h(sg)=0 设设xj是是xi的任意子节点有：的任意子节点有：h(xi)h(xj)+c(xi,xj)结论结论3：当：当h满足单调性限制，则满足单调性限制，则A*算法扩展的每个节点算法扩展的每个节点x都满足：都满足：g(x)=g*(x)保证每次扩展的路径是最优路径。保证每次扩展的路径是最优路径。且且A*算法所扩展的节点序列的算法所扩展的节点序列的f值是非递减的。值是非递减的。第48页，本讲稿共51页48例题例题 八数码问题八数码问题:初始状态和

23、目标状态初始状态和目标状态试用试用A*算法求解该问题算法求解该问题.第49页，本讲稿共51页49解：（解：（1）估价函数）估价函数 f1(n)=d(n)+w(n)d(n)节点深度节点深度 w(n)不在位数码的个数（不在位数码的个数（w(n)h*(n)）（2）估价函数）估价函数f2(n)=d(n)+P(n)d(n)节点深度节点深度 p(n)所有不在位数码正位需水平、垂直移动步数所有不在位数码正位需水平、垂直移动步数（每一数码与目标之间距离之和）（每一数码与目标之间距离之和）（P(n)h*(n)）该问题用上述两种估价函数的启发式搜索的搜索图如下：该问题用上述两种估价函数的启发式搜索的搜索图如下：第50页，本讲稿共51页50Sg2867543176185432386754211286754381267543172865438675432116875424687532187654321S0786543216875432168754321qA168754W=4P=5f2=5W=3P=4f2=5W=5P=6f2=7W=5P=6f2=7W=3P=5f2=7W=3P=3f2=5W=4P=5f2=7W=4W=2P=2f2=5W=4P=4f2=7W=1P=1f2=5W=0P=0f2=5W=2P=2f2=7W=3第51页，本讲稿共51页51