盲目搜索启发式搜索.ppt

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,盲目搜索,按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。效率低、主要用于简单问题求解。,启发式搜索,在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。,搜索原理,什么是搜索？,根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。,与图有关的术语,状态空间图,由节点,(,不一定是有限的节点,),及连接节点的分枝的集合构成。,有限节点图,节点数目有限的图称为有限节点图。,有向图,一对节点用分枝线连接起来，从一个节点指向另一个节点。这种图叫做有向图。始节点叫父节点或双亲节点，终节点叫子节点。,扩展求解父节点的所有子节点，叫做扩展,。,路径在一系列节点,n,1,n,2,n,m,中，从,n,1,开始，,n,i,总有分枝连接,n,i+1,，称从,n,1,到,n,m,之间的分枝集合是路径。路径中不包含两个及以上相同的分枝，如果,n,1,和,n,m,是同一个节点，则称这种路径为闭路。不构成闭路的称为树。,在用状态空间图来表示问题时，对问题的求解就是求出从初始节点到目标节点的路径。,图搜索,策略,1.,图搜索的定义,一种计算机在状态图中寻找路径的方法。,2.CLOSED,表的引入,编号,节点号,父节点号,CLOSED,表,(,记录扩展过的节点,),OPEN,表的引入,节点号,父节点号,OPEN,表,(,记录待扩展的节点,),举例：八数码魔方例子中,OPEN,表变化过程,节点号,父节点号,S,0,空,A,S,0,B,S,0,C,S,0,D,S,0,E,A,F,A,CLOSED,表变化过程,编号,节点号,父节点号,0,S,0,空,1,A,S,0,2,B,S,0,图搜索的一般过程,(1),建立一个只含有起始节点,S,的搜索图,G,，把,S,放到一个叫做,OPEN,表的未扩展节点表中。,(2),建立一个叫做,CLOSED,的已扩展节点表，其初始为空表。,(3)LOOP,：若,OPEN,表是空表，则失败退出。,(4),选择,OPEN,表上的第一个节点，把它从,OPEN,表移出并放进,CLOSED,表中。称此节点为节点,n,。,(5),若,n,为一目标节点，则有解并成功退出，此解是追踪图,G,中沿着指针从,n,到,S,这条路径而得到的,(,指针将在第,7,步中设置,),。,图搜索的一般过程,(6),扩展节点,n,，同时生成不是,n,的祖先的那些后继节点的集合,M,。把,M,的这些成员作为,n,的后继节点添入图,G,中。,(7),对那些未曾在,G,中出现过的,(,既未曾在,OPEN,表上或,CLOSED,表上出现过的,)M,成员设置一个通向,n,的指针。把,M,的这些成员加进,OPEN,表。对已经在,OPEN,或,CLOSED,表上的每一个,M,成员，确定是否需要更改通到,n,的指针方向。对已在,CLOSED,表上的每个,M,成员，确定是否需要更改图,G,中通向它的每个后裔节点的指针方向。,(8),按某一任意方式或按某个探试值，重排,OPEN,表。,(9)GO LOOP,。,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,n,为目标节点吗？,把,n,的后继节点放入,OPEN,表的末端，提供返回节点,n,的指针,修改指针方向,重排,OPEN,表,失败,成功,图搜索一般过程的框图,是,是,否,否,13,一、盲目搜索,盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。主要包括宽度优先搜索、等深度优先搜索等。,特点：,1,）搜索按规定的路线进行，不使用与问题有关的启发性信息。,2,）适用于其状态空间图是树状结构的一类问题。,14,1,、,宽度优先搜索,定义：,如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索,(breadth-first search),。,基本思想：,从初始节点,S,开始，逐层地对节点进行扩展并考察它是否为目标节点，在第,n,层的节点没有全部扩展并考察之前，不对第,n,1,层的节点进行扩展。,OPEN,表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。,15,宽度优先搜索示意图,2025/1/11 周六,16,宽度优先搜索算法：,(1),把起始节点放到,OPEN,表中,(,如果该起始节点为一目标节点，则求得一个解答,),。,(2),如果,OPEN,是个空表，则没有解，失败退出；否则继续。,(3),把第一个节点,(,节点,n),从,OPEN,表移出，并把它放入,CLOSED,扩展节点表中。,(4),扩展节点,n,。如果没有后继节点，则转向上述第,(2),步。,(5),把,n,的所有后继节点放到,OPEN,表的末端，并提供从这些后继节点回到,n,的指针。,(6),如果,n,的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第,(2),步。,17,宽度优先搜索算法框图,18,宽度优先搜索方法分析：,宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第,8,步具体化为本算法中的第,6,步，这实际是将,OPEN,表作为,“,先进先出,”,的队列进行操作。,宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径,(,如果没有路径存在，那么对有限图来说，就说该法失败退出；对于无限图来说，则永远不会终止,),。,19,例如：宽度优先搜索用于八数码难题。这个问题就是要把初始棋局变为如下目标棋局的问题：,搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序,(,按顺时针方向移动空格,),。图中最后一个节点是目标节点。,20,八数码难题的宽度优先搜索树,26,21,对应动态演示图,2025/1/11 周六,22,2,、,深度优先搜索,基本思想：,从初始节点,S,开始，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点中选择一个节点进行考察，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。,2025/1/11 周六,23,深度优先搜索示意图,2025/1/11 周六,24,在深度优先搜索中，首先扩展最新产生的,(,即最深的,),节点（深度相等的节点可以任意排列）。其结果是搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后,n,步，而且保持,n,尽可能小。,3,、深度优先搜索,2025/1/11 周六,25,3.1.3,深度优先搜索,2025/1/11 周六,26,对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径,(,防止搜索过程沿着无益的路径扩展下去,),，往往给出一个节点扩展的最大深度,深度界限,。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。,有界深度优先搜索,定义节点的深度如下：,(1),起始节点,(,即根节点,),的深度为,0,。,(2),任何其它节点的深度等于其父辈节点深度加上,1,。,2025/1/11 周六,27,含有深度界限的深度优先搜索算法：,(1),把起始节点,S,放到未扩展节点,OPEN,表中。如果此节点为一目标节点，则得到一个解。,(2),如果,OPEN,为一空表，则失败退出。,(3),把第一个节点,(,节点,n),从,OPEN,表移到,CLOSED,表。,(4),如果节点,n,的深度等于最大深度，则转向,(2),。,(5),扩展节点,n,，产生其全部后裔，并把它们放入,OPEN,表的前头。如果没有后裔，则转向,(2),。,(6),如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向,(2),。,有界深度优先搜索,2025/1/11 周六,28,算法动态演示图,2025/1/11 周六,29,例如：按深度优先搜索生成八数码难题搜索树，设置深度界限为,5,。下图绘出了搜索树，粗线条的路径表明含有,5,条应用规则的一个解。从图可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路径，等等。,2025/1/11 周六,30,八数码难题的深度优先搜索树,2025/1/11 周六,31,二、启发式搜索,盲目搜索的不足：,效率低，耗费过多的计算空间与时间。,宽度优先搜索、深度优先搜索，或等代价搜索算法,是按事先规定的路线进行搜索，或按已经付出的代价决定下一步要搜索的节点，其主要差别是,OPEN,表中待扩展节点的顺序问题。如果找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。,2025/1/11 周六,32,二、启发式搜索,盲目搜索的共同特点：,没有利用问题本身的特性信息，在决定要被扩展的节点时，都没有考虑该节点在解的路径上的可能性有多大，它是否有利于问题求解以及求出的解是否为最优解等。,2025/1/11 周六,33,二、启发式搜索,启发信息,进行搜索技术一般需要某些有关具体问题领域特性的、与具体问题求解过程有关的、并可指导搜索过程朝着最有希望方向前进的控制信息，把此种信息叫做,启发信息,。把利用启发信息的搜索方法叫做,启发性搜索方法,。,特点：重排,OPEN,表，选择最有希望的节点加以扩展,种类：最佳优先搜索、,A*,算法等,2025/1/11 周六,34,1,、启发式搜索策略,启发信息按其用途可分为,3,种：,(1),用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。,(2),在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。,(3),用于决定某些应该从搜索树中抛弃或修剪的节点。,2025/1/11 周六,35,2,、估价函数,用来估算节点希望程度的量度，叫做,估价函数,(evaluation function),。,估价函数的任务就是估计,OPEN,表中各节点的重要程度。,一个节点的,“,希望,”,(promise),有几种不同的定义方法,:,1),估算目标节点到此节点的距离；,2),解答路径包括被估价过的节点，并计算全条路径的长度或难度。,2025/1/11 周六,36,2,、估价函数,用符号,f,来标记估价函数，用,f(n),表示节点,n,的估价函数值。暂时令,f,为任意函数，以后将会提出,f,是从起始节点约束地通过节点,n,而到达目标节点的最小代价路径上的一个估算代价。一般形式：,f(n)=g(n)+h(n),g(n),是从,s,0,到,n,的实际代价。,h(n),是从节点,n,到目标节点,s,g,的估计代价。,2025/1/11 周六,37,3,、有序搜索,用估价函数,f,来排列,GRAPHSEARCH,第,8,步中,OPEN,表上的节点。根据习惯，,OPEN,表上的节点按照它们,f,函数值的递增顺序排列。根据推测，某个具有低估价值的节点较有可能处在最佳路径上。应用某个算法,(,例如等代价算法,),选择,OPEN,表上具有最小,f,值的节点作为下一个要扩展的节点。这种搜索方法叫做,有序搜索,或,最佳优先搜索,，而其算法就叫做,有序搜索算法,或,最佳优先算法,。可见它总是选择最有希望的节点作为下一个要扩展的节点。有序搜索,(ordered search),又称为,最好优先搜索,(best-first search),。,2025/1/11 周六,38,3,、有序搜索,尼尔逊（,Nilsson,）曾提出一个有序搜索的基本算法。,估价函数,f,按照如下方法确定：,一个节点希望程度越大，其,f,值就越小。被选为扩展的节点，是估价函数最小的节点。,2025/1/11 周六,39,有序状态空间搜索算法,(1),把起始节点,S,放到,OPEN,表中，计算,f(S),并把其值与节点,S,联系起来。,(2),如果,OPEN,是个空表，则失败退出，无解。,(3),从,OPEN,表中选择一个,f,值最小的节点,i,。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点,i,。,(4),把节点,i,从,OPEN,表中移出，并把它放入,CLOSED,的扩展节点表中。,(5),如果,i,是个目标节点，则成功退出，求得一个解。,2025/1/11 周六,40,(6),扩展节点,i,生成其全部后继节点。对于,i,的每一个后继节点,j,：,(a),计算,f(j),。,(b),如果,j,既不在,OPEN,表中，又不在,CLOSED,表中，则用估价函数,f,把它添入,OPEN,表。从,j,加一指向其父辈节点,i,的指针，以便一旦找到目标节点时记住一个解答路径。,(c),如果,j,已在,OPEN,表上或,CLOSED,表上，则比较刚刚对,j,计算过的,f,值和前面计算过的该节点在表中的,f,值。如果新的,f,值较小，则,(i),以此新值取代旧值。,(ii),从,j,指向,i,，而不是指向它的父辈节点。,(iii),如果节点,j,在,CLOSED,表中，则把它移回,OPEN,表,(7),转向,(2),，即,GO TO(2),。,有序状态空间搜索算法,2025/1/11 周六,41,注释：,步骤（,6.c,）是一般搜索图所需要的，该图中可能有一个以上的父辈节点。具有最小估价函数,f,（,j,）的节点被选作父辈节点。但是，由于搜索树，它最多只有一个父辈节点，所以步骤（,6.c,）可以略去。,有序状态空间搜索算法,2025/1/11 周六,42,有序搜索算法框图,2025/1/11 周六,43,有序搜索的有效性直接取决于,f,的选择，如果选择的,f,不合适，有序搜索就,可能失去一个最好的解甚至全部的解,。如果没有适用的准确的希望量度，那么,f,的选择将涉及两个方面的内容：一方面是时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。,有序状态空间搜索算法,2025/1/11 周六,44,有序搜索例子,使用八数码难题例子说明过程,GRAPHSEARCH,是如何应用估价函数排列节点的。,采用简单的估价函数,f(n)=d(n)+W(n),其中：,d(n),是搜索树中节点,n,的深度；,W(n),用来计算对应于节点,n,的数据库中错放的棋子个数。,2025/1/11 周六,45,起始节点棋局,2 8 3,1 6 4,7 5,的,f,值,等于,1+4=5,。,有序搜索例子,2025/1/11 周六,46,八数码难题的有序搜索树,2025/1/11 周六,47,2025/1/11 周六,48,从图可见，这里所求得的解答路径和用其它搜索方法找到的解答路径相同。不过，估价函数的应用显著地减少了被扩展的节点数,(,如果我们只用估价函数,f(n)=d(n),，那么我们就得到宽度优先搜索过程,),。,八数码难题的有序搜索树,2025/1/11 周六,49,正确地选择估价函数对确定搜索结果具有决定性的作用。使用不能识别某些节点真实希望的估价函数会形成非最小代价路径；而使用一个过多地估计了全部节点希望的估价函数,(,就像宽度优先搜索方法得到的估价函数一样,),又会扩展过多的节点。,八数码难题的有序搜索树,2025/1/11 周六,50,4,、,A,*,算法,A*,算法的估价函数：,令估价函数,f,使得在任意节点上其函数值,f(n),能估算出从节点,S,到节点,n,的最小代价路径的代价与从节点,n,到某一目标节点的最小代价路径的代价之总和，也就是说,f(n),是约束通过节点,n,的一条最小代价路径的代价的一个估计。因此，,OPEN,表上具有最小,f,值的那个节点就是所估计的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。,2025/1/11 周六,51,A*,算法中几个有用的记号：,令,k(n,i,，,n,j,),表示任意两个节点,n,i,和,n,j,之间最小代价路径的实际代价,(,对于两节点间没有通路的节点，函数,k,没有定义,),。于是，从节点,n,到某个具体的目标节点,t,i,，某一条最小代价路径的代价可由,k(n,t,i,),给出。,令,h*(n),表示整个目标节点集合,t,i,上所有,k(n,t,i,),中最小的一个，因此，,h*(n),就是从,n,到目标节点最小代价路径的代价，而且从,n,到目标节点能够获得,h*(n),的任一路径就是一条从,n,到某个目标节点的最佳路径,(,对于任何不能到达目标节点的节点,n,，函数,h*,没有定义,),。,2025/1/11 周六,52,通常感兴趣的是想知道从已知起始节点,S,到任意节点,n,的一条最佳路径的代价,k(S,n),。,为此，引进一个新函数,g*,，这将使引入的记号得到某些简化。对所有从,S,开始可达到,n,的路径来说，函数,g*,定义为,g*(n)=k(S,n),2025/1/11 周六,53,因而,f*(n),值就是从,S,开始约束通过节点,n,的一条最佳路径的代价，而,f*(S)=h*(S),是一条从,S,到某个目标节点中间无约束的一条最佳路径的代价。,其次，定义函数,f*,，使得在任一节点,n,上其函数值,f*(n),就是从节点,S,到节点,n,的一条最佳路径的实际代价加上从节点,n,到某目标节点的一条最佳路径的代价之和，即,f*(n)=g*(n)+h*(n),2025/1/11 周六,54,希望估价函数,f,是,f*,的一个估计，此估计可由下式给出：,f(n)=g(n)+h(n),其中：,g,是,g*,的估计；,h,是,h*,的估计。对于,g(n),来说，一个明显的选择就是搜索树中从,S,到,n,这段路径的代价，这一代价可以由从,n,到,S,寻找指针时，把所遇到的各段弧线的代价加起来给出,(,这条路径就是到目前为止用搜索算法找到的从,S,到,n,的最小代价路径,),。这个定义包含了,g(n)g*(n),。对于,h*(n),的估计,h(n),，它依赖于有关问题的领域的启发信息。,h,叫做,启发函数,。,2025/1/11 周六,55,A,算法和,A*,算法的定义,定义,1,在,GRAPHSEARCH,过程中，如果第,8,步的重排,OPEN,表是依据,f(x)=g(x)+h(x),进行的，则称该过程为,A,算法。,定义,2,在,A,算法中，如果对所有的,x,，,h(x)h*(x),成立,则称,h(x),为,h*(x),的下界，它表示某种偏于保守的估计。,2025/1/11 周六,56,定义,3,采用,h*(x),的下界,h(x),为启发函数的,A,算法，称为,A*,算法。当,h=0,时，,A*,算法就变为有序搜索算法。,A*,算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择,f,值最小的节点作为扩展节点。因此，,f,是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点,n,的估价函数值为两个分量：从起始节点到节点,n,的代价以及从节点,n,到目标节点的代价。,2025/1/11 周六,57,A*,算法,(1),把,S,放入,OPEN,表，记,f=h,，令,CLOSED,为空表。,(2),重复下列过程，直至找到目标节点为止。若,OPEN,为空表，则宣告失败。,(3),选取,OPEN,表中未设置过的具有最小,f,值的节点为最佳节点,BESTNODE,，并把它放入,CLOSED,表。,(4),若,BESTNODE,为一目标节点，则成功求得一解。,(5),若,BESTNODE,不是目标节点，则扩展之，产生后继节点,SUCCSSOR,。,2025/1/11 周六,58,(6),对每个,SUCCSSOR,进行下列过程：,(a),建立从,SUCCSSOR,返回,BESTNODE,的指针。,(b),计算,g(SUC)=g(BES)+k(BES,SUC),。,(c),如果,SUCCSSOROPEN,，则称此节点为,OLD,，并把它添至,BESTNODE,的后继节点表中。,(d),比较新旧路径代价。如果,g(SUC),g(OLD),则重新确定,OLD,的父辈节点为,BESTNODE,，记下较小代价,g(OLD),并修正,f(OLD),值。,(e),若至,OLD,节点的代价较低或一样，则停止扩展节点。,A*,算法,2025/1/11 周六,59,(f),若,SUCCSSOR,不在,OPEN,表中，则看其是否在,CLOSED,表中。,(g),若,SUCCSSOR,在,CLOSED,表中，则转向,c,。,(h),若,SUCCSSOR,既不在,OPEN,表中，又不在,CLOSED,表中，则把它放入,OPEN,表中，并添入,BESTNODE,后裔表，然后转向,(7),。,(7),计算,f,值。,(8)GO LOOP,A*,算法,2025/1/11 周六,60,A*,算法框图,