第五章状态空间搜索策略.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020年5月29日星期五,#,09 十一月 2026,第五章状态空间搜索策略,5.1 搜索的概念及种类,5.2 盲目搜索,5.3 启发式搜索,5.1 搜索的概念及种类,搜索的概念：,找到从初始事实到问题最终答案的一条推理路线，找到的这条路线是时间和空间复杂度最小的求解路线,搜索种类：,“盲目搜索”,，即系统根据事先确定好的某种固定排序（依次或随机）调用规则。,“启发式搜索”,，即考虑问题领域可应用的知识，根据具体情况动态地确定规则的排序，优先调用较合适的规则使用。,搜索例子：回溯搜索算法,BACKTRACK（DATA）,DATA：当前状态。,返回值：,成功,：返回从当前状态到目标状态的路径（以规则表的形式表示）,失败,：返回FAIL。,四皇后问题,皇后问题,在一个4*4的国际象棋棋盘上，一次一个地摆布四枚棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击。,四皇后问题（续）,综合数据库：DATA=L(表），L的元素属于ij，1,i,j,4。DATA非空，其表元素表示棋子所在的行和列,规则集：if 1,i,4 且在i-1行上有一个皇后 then 在第ij位置放上皇后。,搜索策略,固定次序：R,11,R,12,R,13,R,21,R,22,R,44,(),(),Q,(1,1),(),Q,Q,(1,1),(1,1)(2,3),(),Q,(1,1),(1,1)(2,3),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),Q,(1,2)(2,4)(3,1)(4,3),5.1 搜索的概念及种类,5.2 盲目搜索,5.3 启发式搜索,5.2.1 状态空间图的一般搜索算法,5.2.2 宽度优先搜索策略,5.2.3 深度优先搜索策略,5.2.4 代价树的宽度优先搜索策略,5.2.5 代价树的,深度优先搜索策略,5.2 盲目搜索策略5.2.1 状态空间图的一般搜索算法,状态空间,表示法：用来表示问题及其搜索过程的一种方法。(P62),主要构成：,（1）状态，描述问题求解过程中不同时刻状况的数据结构；,（2）算符：使问题由一个状态变为另一个状态的操作。,（3）状态空间：一个问题的全部状态及一切可用算符构成的集合。一般包括3部分（初始状态集合S，算符集合F，目标状态集合G）,（4）,问题的求解：,从S出发经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列构成了问题的一个求解,状态空间图：,把状态空间的问题求解过程用图的形式表示出来。,节点代表状态，弧代表算符,5.2.1 状态空间图的一般搜索算法,几个概念：,扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。,已扩展节点：已经求出了其后继节点的节点。,未扩展节点：尚未求出后继节点的节点。,OPEN表：存放未扩展的节点，记录当前节点及其父节点。,CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。,图2.26的节点（1，1）能生成两个后继节点（2，1）（3，1）,状态空间的一般搜索算法,一般搜索算法的描述：,建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中,建立CLOSED表，且置为空表,判断OPEN表是否为空表，若为空，则问题无解，退出,选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n,考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到S0的路径得到。若不是转,扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中,对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点，设置一个指向父节点n的指针，并把这些节点放入OPEN表中；,对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；,对于已在G中出现过并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针,。,按,某一任意方式或某种策略,重排OPEN表中节点的顺序,转,特例,图的一些概念：,（1）节点深度：,根节点深度=0，其它节点深度=父节点深度+1,（2）路径,设一节点序列为(n,0,n,1,n,k,)，对于i=1,k，若节点n,i-1,具有一个后继节点n,i,，则该序列称为从n,0,到n,k,的路径。,（3）路径的消耗值,一条路径的消耗值等于连接这条路径各节点间所有消耗值的总和。用C(n,i,n,j,)表示从n,i,到n,j,的路径的消耗值。,0,1,2,3,节点类型说明,.,.,.,.,.,mk,mj,ml,n,扩展点n，产生,mk：没在OPEN和CLOSED表中出现过,mj：在OPEN表中出现过,ml：在CLOSED表中出现过,S,1,2,3,6,4,5,将要扩展节点6,S,1,2,6,4,5,3,修改4节点的返回指针,S,1,2,6,4,5,3,将要扩展节点1,S,1,2,6,4,5,修改2和4的返回指针,5.2 无信息图搜索过程盲目搜索策略,5.2.2 宽度优先搜索,5.2.3 深度优先搜索,5.2.4 代价树的宽度优先,5.2.5 代价树的深度优先,1、定义,如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。,2、特点,这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,5.2.2 宽度优先搜索策略,3、宽度优先搜索算法,(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。,(2)如果OPEN是个空表，则没有解，失败退出；否则继续。,(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。,(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。,(5)把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。,(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。,例：,把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：,1 2 3,8 4,7 6 5,5.2.2 宽度优先搜索策略,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,目标,8,2 3 4,1 8,7 6 5,4,宽度优先搜索的性质,当问题有解时，一定能找到解。,当问题为单位消耗值，且问题有解时，一定能找到最优解。,算法与问题无关，具有通用性。,时间效率和空间效率都比较低。,1、定义,在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。,这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。,2、特点,首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。,3、深度界限,为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。,5.2.3 深度优先搜索策略,3、深度优先搜索算法,(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。,(2)如果OPEN是个空表，则没有解，失败退出；否则继续。,(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。,(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出,（5）如果没有后继节点，则转向上述第(2)步。,(6)扩展节点n，把n的所有后继节点放到OPEN表,前,端，并提供从这些后继节点回到n的指针。转向第(2)步。,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,10,11,12,13,1 2 3,8 4,7 6 5,目标,深度优先搜索的性质,一般不能保证找到最优解。,当深度限制不合理时，可能找不到解。,最坏情况时，搜索空间等同于穷举。,1、定义,状态空间图中各节点之间有向边的代价是不同的，有向边上标有代价的搜索树成为代价搜索树。,2、特点,每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。,3、C(i,j):从节点i到其后继节点j的连线代价；,g（x）:从初始节点到任意节点x的路径代价；,g(j)=g(i)+C(i,j).,5.2.4 代价树的宽度优先搜索,4、代价树的宽度优先搜索算法,(1)把起始节点放到OPEN表中，令g(S0)=0。,(2)如果OPEN是个空表，则没有解，失败退出；否则继续。,(3)把OPEN表中代价最小的节点（即排在最前端的节点n），移入CLOSED的扩展节点表中。,(4)如果n是目标节点，问题得解，退出。否则继续。,(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。,(6)对节点n进行扩展，将他们的所有后继节点放到OPEN表中，并对每个后继节点j计算其总代价g(j)=g(j)+C(i,j),为每个后继节点指向n节点的指针，然后根据节点的代价大小对OPEN表中的所有节点进行从小到大的排序。,(7)转向第(2)步。,例子：推销员旅行问题P193,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,6,6,B,A,7,7,C,A,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,6,6,B,A,7,11,7,5,C,D,A,B,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,6,6,B,A,7,11,14,15,7,5,7,8,C,D,D,E,A,B,C,C,节点扩展顺序：A，B，C，D，D，E,路线：A-C-E,代价树的宽度优先搜索,每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表进行扩展或判断。,代价树的深度优先搜索,从刚刚扩展的节点的后继节点中选择一个代价最小的节点移入CLOSED表中，并进行扩展或判断。,5.2.5 代价树的深度优先搜索,4、代价树的深度优先搜索算法,(1)把起始节点放到OPEN表中，令g(S0)=0。,(2)如果OPEN是个空表，则没有解，失败退出；否则继续。,(3)把OPEN表中的第一个节点（代价最小的节点n），移入CLOSED表。,(4)如果n是目标节点，问题得解，退出。否则继续。,(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。,(6)对节点n进行扩展，并将其,后继节点按有向边代价（C(i,j)）从小到大排序后放到OPEN表前端,，并为每个后继节点设置指向n节点的指针。,(7)转向第(2)步。,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,6,6,B,A,7,7,C,A,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,6,6,B,A,7,11,7,5,C,D,A,B,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,6,6,B,A,7,11,17,18,7,5,7,8,C,D,E,C,A,B,D,D,节点扩展顺序：A，B，C，D，E,路线：A-B-D-E,A,C,B,D,E,7,6,8,7,6,5,g,C,节点n,父节点,A,6,6,B,A,7,11,14,15,7,5,7,8,C,D,D,E,A,B,C,C,节点扩展顺序：A，B，C，D，D，E,路线：A-C-E,5.1 搜索的概念及种类,5.2 盲目搜索,5.3 启发式搜索,5.3.1 启发信息与估价函数,5.3.2 最佳优先搜索,5.3.3 A*搜索算法,5.3 启发式图搜索 5.3.1启发信息与估价函数,定义,利用与问题有关的知识（即：,启发信息,）来引导搜索，达到减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索方法。,核心问题：,启发信息应用，启发能力度量和如何获得启发信息。,启发信息的,强度,强：降低搜索工作量，但可能导致找不到最优解。,弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。,希望：,引入启发知识，在保证找到最佳解的前提下，尽可能减少搜索范围，提高搜索效率。,搜索算法的效果：,可以用启发能力的强弱来度量。,考虑,解路径的消耗值,和,求得路径所需搜索的消耗值,两者的某种组合最小。,考虑搜索方法对求解所有可能遇见的问题，其平均的组合消耗最小。,问题的关键,如何寻找最有希望的节点,启发搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度。,我们总希望能找到最有希望通向目标节点的待扩展节点优先扩展。,基本思想,定义一个,估价函数f,（Evaluation Function），对当前的搜索状态进行评估，找出一个“最有希望”的节点来扩展。,估价函数的格式：,f(n)=g(n)+h(n),f(n)：估价函数,g(n)：代价函数，,初始节点到节点n已实际付出的代价,h(n)：启发函数，,从节点n到目标节点的最优路径的估计代价,5.3.2 最佳优先搜索,局部最佳优先搜索,全局最佳优先搜索,局部最佳优先搜索,：,(1)把起始节点放到OPEN表中，并计算估价函数f(S0)。,(2)如果OPEN是个空表，则没有解，失败退出；否则继续。,(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表。,(4)如果n是目标节点，问题得解，退出。否则继续。,(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。,(6)对节点n进行扩展，,并对其所有后继节点计算估价函数f（n）的值,，并按其值从小到大排序后放到OPEN表前端，并为每个后继节点设置指向n节点的指针。,(7)转向第(2)步。,全局最佳优先搜索,：,(1)把起始节点放到OPEN表中，并计算估价函数f(S0)。,(2)如果OPEN是个空表，则没有解，失败退出；否则继续。,(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表。,(4)如果n是目标节点，问题得解，退出。否则继续。,(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。,(6)对节点n进行扩展，,并对其所有后继节点计算估价函数f（n）的值，,并为每个后继节点设置指向n节点的指针。把这些后继节点都送入OPEN表，然后,对OPEN表中的全部节点按照估价函数值从小到大的顺序排序。,(7)转向第(2)步。,例子,定义评价函数：,f(n)=g(n)+h(n)=d(n)+h(n)；,d(n)：代表节点的深度，表示从初始节点到当前节点的消耗值；,h(n)：为当前节点“不在位”的牌数。,2 8 3,1 6 4,7 5,1 2 3,8 4,7 6 5,h计算举例,h(n)=4,2,8,3,1,6,4,7 5,1 2 3,4,5,7 6,8,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,7 8 4,6 5,s0(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。,令k(ni，nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。于是，从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合ti上所有k(n,ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n，函数h*没有定义)。,5.3.3 A*算法,估价函数,f(n)=g(n)+h(n)是对下列函数的一种估计或近似：,f*(n)=g*(n)+h*(n),f*(n)：,从初始节点到节点n的一条最佳路径的实际代价加上从节点n到目标节点的最佳路径的代价之和。,g*(n)：,从初始节点到节点n之间,最小路径,的实际代价,h*(n)：,从节点n到目标节点的,最小代价路径,上代价,恒有：,g*(n)g(n),在A*算法中，要求启发函数h(n)是,h*(n)的下界。,h(n)h*(n),极端情况下，若h(n)=0，一定能找到最佳解路径,