人工智能搜索策略.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,搜 索 策 略,搜索问题，人工智能的一个基本问题,在二十世纪五十年代人工智能概念的提出至今，人工智能界已对搜索技术开展了大量研究，取得了丰硕的成果。,搜索是人工智能的一个基本问题，是推理不可分割的一部分。一个问题的求解过程其实就是搜索过程，所以,搜索实际上就是求解问题的一种方法,。,Nilsson,把搜索列为,人工智能研究中的四个核心问题,之一。,本部分将讨论,目标状态和最优路径的确定,，以及,如何从初始状态经过变换得到目标状态,等，将在各节分别讨论一些,通用的搜索策略,，以及,状态空间搜索,和,树搜索策略,。最后简要介绍智能搜索算法的效率和约束满足问题。,3.1,基本概念（,Basic Conception）,现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。,在这一过程中，所要解决的问题是如何寻找可利用的知识，即,如何确定推理路线,，才能使在付出尽量少的代价下把问题圆满解决。,如果存在多条路线可实现对问题的求解，那就又存在着这样的问题，即,如何从这多条求解路线中，选出一条使它的求解代价最小，以提高求解程序的运行效率,。,根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条解决问题的推理路线的过程，就称为,搜索,。,1.,搜索包含两层含义,找到从初始事实到问题最终答案的一条推理路线;,找到的这条路线是时间和空 间复杂度最小的求解路线。,举一个具体的例子,实现一个能够中国象棋下棋的程序。,3.1,基本概念（,Basic Conception）,3.1.1,什么是搜索(,Whats search),2.搜索的种类(,The type of search),搜索分为盲目搜索和启发式搜索两种,盲目搜索又称无信息搜索,，也就是说，在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。这就使得这样的搜索带有盲目性，效率不高。盲目搜索只用于解决比较简单的问题。,启发式搜索又称有信息搜索,，它是指在搜索求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。,3.1.1,什么是搜索(,Whats search),问题求解系统可在,两种基本情况下运用启发式策略,：,一个问题由于在,问题陈述和数据获取方面固有的模糊性,，可能会使它,没有一个确定的解,，即它是一个模糊系统。,虽然一个问题可能有确定解，但是,求解过程中的搜索代价将令人难以接受,，在很多问题中，其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。在这种情况下，,穷尽式搜索策略,如宽度优先和深度优先搜索，在一个给定的较实际的时空内很可能得不到最终的解，而,启发式策略则通过引导搜索向最有希望的方向进行来降低搜索复杂度,。通过仔细考虑，删除某些状态及其后裔，启发式策略可以消除组合爆炸，并得到令人能接受的解。,3.1.1,什么是搜索(,Whats search),3.1.1,什么是搜索(,Whats search),启发式策略的缺点：,极易出错。在解决问题过程中,启发仅仅是下一步将要采取措施的一个猜想,，它常常根据经验和直觉来判断。,由于启发式搜索,只利用特定问题的有限的信息,，如当前,open,表中状态的描述及其之间的关系，,要想准确地预测下一步在状态空间中采取的具体的搜索行为是很难办到的,。,一个启发式搜索可能得到一个次最佳解，也可能一无所获,，这是启发式搜索固有的局限性，而这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来彻底消除。,3.1.2,适合于搜索的知识表示方法,状态空间表示法：,算符、状态、状态空间,与或树表示法：,分解、等价变化；本原问题、,端节点与终止节点、可解节点、不可解节点、解树,状态空间搜索策略分类：,盲目搜索 按事先规定好的路线进行搜索，不使用与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。它包括,广度优先搜索,、,深度优先搜索、有界深度优先搜索,、,代价树的广度优先搜索,以及,代价树的深度优先搜索,。,启发式搜索,搜索过程中使用与问题有关的启发性信息，并以启发性信息指导搜索过程；可以高效地求解结构复杂的问题。它包括,局部择优搜索,、,全局择优搜索,和,A,*,算法,。,3.2,状态空间的搜索策略,3.2.1,状态空间的一般搜索过程,1.状态空间图,状态空间图是一个有向图，当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。如果从状态空间图的角度来看，则对问题的求解就相当于,在有向图上寻找一条从某一节点,(,初始状态节点,),到另一节点,(,目标状态节点,),的路径,。,3.2.1,状态空间的一般搜索过程,2.状态空间搜索法求解问题的基本思想,首先,将问题的初始状态,(,即状态空间图中的初始节点,),当作当前状态，选择适当的算符作用于当前状态，生成一组后继状态,(,或称后继节点,),，,然后,检查这组后继状态中有没有目标状态。,如果有,，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；,若没有,，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。,3.,状态空间的搜索过程需要的两个数据结构,OPEN,表：,用于存放刚生成的节点，这些节点也是待扩展的，所以,OPEN,表也称为未扩展节点表；,CLOSED,表：,CLOSED,表则是用来存放将要扩展或已经扩展的节点，所以它被称为已扩展节点表。,4.状态空间的一般搜索过程描述如下:,把初始节点,S,0,放入,OPEN,表，并建立目前只包含,S,0,的图，记为,G,；,检查,OPEN,表是否为空，若为空则问题无解，退出。,把,OPEN,表的第一个节点取出并放入,CLOSED,表，并记该节点为节点,n,；,检查节点,n,是否是目标节点，如果是目标节点，则说明得到了问题的解，过程成功退出，并返回从节点,n,逆向回溯到,S,0,得出的路径；,3.2.1,状态空间的一般搜索过程,扩展节点,n，,生成一组子节点。把其中,不是节点,n,先辈的那些子节点记做集合,M,，,并把这些子节点作为节点,n,的子节点加入,G,中。,针对,M,中子节点的不同情况，分别进行如下处理：,对于那些未曾在,G,图中出现过的,M,成员设置一个指向父节点（即节点,n）,的指针，并把它们加入,OPEN,表,对于那些先前已在,G,图中出现过的,M,成员，确定是否需要修改它指向父节点的指针。,对于那些先前已在,G,中出现并且已经扩展了的,M,成员，确定是否需要修改其后继节点指向父节点的指针。,按某种搜索策略对,OPEN,表中的节点进行排序。,转第2）步。,3.2.1,状态空间的一般搜索过程,S,9,扩展之后生成的子节点有,S,1,S,6,S,12,S,13,。但是，,S,1,是,S,9,的祖先节点，所以,S,9,的子集,M=S,6,S,12,S,13,其中，,S,13,满足第,1,种情况；,S,12,满第,2,种情况；,S,6,满足第,3,种情况。,下面对上述过程作一些说明：,1),上述过程是状态空间的一般搜索过程，具有通用性，在此之后讨论的各种搜索策略都可看作是它的一个特例。各种搜索策略的主要区别是,对,OPEN,表中节点排序的准则不同,。例如广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。,2),一个节点经一个算符操作后一般只生成一个子节点,，但适,用于一个节点的算符可能有多个,，此时就会生成一组子节点。在这些子节点中可能有些是当前扩展节点,(,即节点,n),的父节点，祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。余下的子节点记作集合,M,，并加入图,G,中。这就是第,5),步要说明的意思。,3),一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节点被再次生成。此时，它究竟应作为哪个节点的后继节点呢？,一般由原始节点到该节点路径上所付出的代价来决定，哪条路径付出的代价小，相应的节点就作为它的父节点,。,4),通过搜索所得到的图称为搜索图，由搜索图中的所有节点及反向指针,(,在第,6),步形成的指向父节点的指针)所构成的集合是一棵树，称为搜索树。,5),在搜索过程中，一旦某个被考察的节点是目标节点,(,第,5),步,),就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成的，而路径由第,7),步形成的反向指针指定。,6),如果在搜索中一直找不到目标节点，而且,OPEN,表中不再有可供扩展的节点，则搜索失败，在第,3),步退出。,7),由于盲目搜索仅适用于其状态空间是树状结构的问题，因此对盲目搜索而言，不会出现一般搜索过程第,6),步中，两点的问题，每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指针方向。,5.,搜索过程举例：,3.2.1,状态空间的一般搜索过程,实心黑点,代表已扩展了节点，它们位于,CLOSED,表上；,空心圆圈,代表未扩展的节点，它们位于,OPEN,表上；,有向边旁边的箭头,是指向父节点的指针，它们是在第,6),步形成的。,假设现在要扩展节点,1,，并且只生成单一的后继节点,2,。但是目前节点,2,已有父节点,3,，即节点,2,在先前扩节点,3,时已被生成了，现在又作为节点,1,的后继节点被再次生成。,一.广度优先搜索,广度优先搜索又称为宽度优先搜索。,基本思想是：从初始节点,S,0,开始，逐层地对节点进行扩展并考察它是否为目标节点，在第,n,层的节点没有全部扩展并考察之前，不对第,n+1,层的节点进行扩展。,OPEN,表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。,3.2.2,状态空间的盲目搜索,广度优先搜索过程:,1),把起始节点放到,OPEN,表中,(,如果该起始节点为一目标节点，则求得一个解答,),；,2),如果,OPEN,是个空表，则没有解，失败退出；否则继续；,3),把第一个节点,(,节点,n),从,OPEN,表移出，并把它放入,CLOSED,扩展节点表中；,4),扩展节点,n,。如果没有后继节点，则转向上述第,2),步；,5),把,n,的所有后继节点放到,OPEN,表的,末端,，并提供从这些后继节点回到,n,的指针；,6),如果,n,的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第,2),步。,一.广度优先搜索,广度优先搜索示意图：,一.广度优先搜索,一.广度优先搜索,广度优先搜索举例：,重排九宫问题。在33的方格棋盘上放置分别标有数字1,2,3,4,5,6,7,8的八张牌，初始状态为,S,0,，,目标状态为,S,g,，,如图所示。,可用的算符有四种,。,按照左,上,右,下的顺序遍历,初始状态,目标状态,解路径：,S0-3-8-16-26,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,缺点：盲目性大，当目标节点距离初始节点较远时将会产生许多无用节点；搜索效率低。,优点：是完备的。,深度优先搜索,在深度优先搜索中，我们首先扩展最新产生的,(,即最深的,),节点。深度相等的节点可以任意排列。,对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径,(,防止搜索过程沿着无益的路径扩展下去,),，往往给出一个节点扩展的最大深度,深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。,二、深度优先搜索,示意图,例：按深度优先搜索生成的八数码难题搜索树,其算法的基本思想与广度优先搜索类似，唯一不同就在第,5),步中：,把,n,的所有后继节点放到,OPEN,表的,首部,，并提供从这些后继节点回到,n,的指针。,缺点：有可能陷入无穷分支。算法是不完备的。,基本思想：对深度优先搜索引入搜索深度的界限（设为,d,m,）当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。,三、有界深度优先搜索,有界深度优先搜索,算法如下：,把起始节点,S,0,放到未扩展节点,OPEN,表中，置,S,0,的深度为,d(S,0,)=0,；,如果,OPEN,为一空表，则失败退出；,OPEN,表的第一个节点,(,节点,n),从,OPEN,表移到,CLOSED,表；,考查结点,n,是否为目标节点。若是，则求得了问题的解，退出；,如果节点,n,的深度,d(,节点,n),等于最大深度,(d,m,),，则转,2),；,若节点,n,不可扩展，则转第,2),步；,扩展节点,n,将其子节点放入,OPEN,表的,首部,，并为其配置指向父节点的指针。然后转第,2),步。,三、有界深度优先搜索,设深度界限,d,m,4,，用有界深度优先搜索方法求解图,由于解的路径长度事先难以预料，所以要恰当地给出,d,m,的值是比较困难的，且所求出的解也不一定是最优解。,改进方法：,先任意给定一个较小的数作为,d,m,，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限,d,m,仍未发现目标节点，并且,CLOSED,表中仍有待扩展节点时就将这些节点送回,OPEN,表，同时增大深度界限，继续向下搜索。如此不断地增大,d,m,，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。,代价树,边上标有代价,(,或费用,),的树称为代价树,。,g(x),表示从初始节点,S,0,到节点,x,的代价；,c(x,1,x,2,),表示从父结点,x,1,到子节点,x,2,的代价。,g(x,2,)=g(x,1,)+c(x,1,x,2,),代价树广度优先搜索,的基本思想:,每次从,OPEN,表中选择节点往,CLOSED,表传送时，总是选择其代价为,最小,的节点。也就是说，,OPEN,表中的节点在任一时刻都是按其代价,从小至大,排序的，代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。,四、代价树广度优先搜索,搜索过程如下：,(1),把初始节点,S,0,放入,OPEN,表，令,g(S,0,)=0,。,(2),如果,OPEN,表为空，则问题无解，退出。,(3),把,OPEN,表的第一个节点,(,记为节点,i),取出放入,CLOSED,表。,(4),考察节点,i,是否为目标节点。若是，则求得了问题的解，退出。,(5),若节点,i,不可扩展，则转第,(2),步。,(6),扩展节点,i,，将其子节点放入,OPEN,表中，且为其配置指向父节点的指针；计算各子节点的代价，并按各节点的代价对,OPEN,表中的,全部节点进行排序,(,按从小到大的顺序,),，然后转第,(2),步。,如果问题有解，该搜索过程一定可以求得它并且求出的是最优解。,举例：五城市间的交通路线图，,A,城市是出发地，,E,城市是目的地，两城市间的交通费用,(,代价,),如图中数字所示。求从,A,到,E,的最小费用交通路线。,四、代价树广度优先搜索,5,为了应用代价树的广度优先搜索方法求解此问题，需先将交通图转换为,代价树,。,转换的方法是,：从起始节点,A,开始，把与它直接相邻的节点作为它的子节点。对其它节点也做相同的处理。但若一个节点已作为某节点的直系先辈节点时，就不能再作为这个节点的子节点。另外，目的节点不再扩展了。,g(x),表示从初始节点,S,0,到节点,x,的代价；,c(x,1,x,2,),表示从父结点,x,1,到子节点,x,2,的代价。,代价树深度优先搜索的过程：,(1),把初始节点,S,0,放入,OPEN,表中。,(2),如果,OPEN,表为空，则问题无解，退出。,(3),把,OPEN,表的第一个节点,(,记为节点,n),取出放入,CLOSED,表。,(4),考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,(5),若节点,n,不可扩展，则转第,(2),步。,(6),扩展节点,n,，将,OPEN,表中所有节点按边代价从小到大的顺序排列,，并为各子节点配置指向父节点的指针，然后转第,(2),步。,四、代价树广度优先搜索,g(x),表示从初始节点,S,0,到节点,x,的代价；,c(x,1,x,2,),表示从父结点,x,1,到子节点,x,2,的代价。,代价树深度优先搜索的过程：,(1),把初始节点,S,0,放入,OPEN,表中。,(2),如果,OPEN,表为空，则问题无解，退出。,(3),把,OPEN,表的第一个节点,(,记为节点,n),取出放入,CLOSED,表。,(4),考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,(5),若节点,n,不可扩展，则转第,(2),步。,(6),扩展节点,n,，将其,子节点按边代价从小到大的顺序放到,OPEN,表的首部,，并为各子节点配置指向父节点的指针，然后转第,(2),步。,五、代价树深度优先搜索,五、代价树深度优先搜索,在代价树的广度优先搜索中，每次都是从,OPEN,表的全体节点中选择一个代价最小的节点送入,CLOSED,表进行考察；,代价树的深度优先搜索是,从刚扩展出的子节点中选一个代价最小的节点送入,CLOSED,表进行考察,。,一般情况下这两种方法得到的结果不一定相同。另外，由于代价树的深度优先搜索有可能进入无穷分支路径，因此它是,不完备的。,前面讨论的搜索方法都是非启发式搜索，它们或者是,按事先规定的路线进行搜索,，或者是,按已经付出的代价决定下一步要搜索的节点,。,它们的一个共同特点是,都没有利用问题本身的特性信息,，在决定要被扩展的节点时，,都没有考虑该节点在解的路径上的可能性有多大,，它,是否有利于问题求解,以及,求出的解是否为最优解,等。,因此这些搜索方法都具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率不高。,3.2.3,状态空间的启发式搜索,启发式搜索要用到,问题自身的某些特性信息,，以指导搜索朝着最有希望的方向前进。由于这种搜索针对性较强，因而原则上只需要搜索问题的部分状态空间，效率较高。,启发性信息：,可用于指导搜索过程，且与具体问题求解有关的控制性信息,陈述性启发信息,：一般被用于更准确、更精练地描述状态，使问题的状态空间缩小，如待求问题的特定状况等属于此类信息。,过程性启发信息,：一般被用于构造操作算子，使操作算子少而精，如一些规律性知识属于此类信息。,控制性启发信息,：它是关于表示控制策略方面的知识，包括协调整个问题求解过程中所使用的各种处理方法、搜索策略、控制结构等有关的知识。,估价函数,用于估价节点重要性或“有希望”程度的函数称为估价函数。其一般形式为：,f(x)=g(x)+h(x),g(x),为从初始节点,S,0,到节点,x,已经实际付出的代价；,h(x),是从节点,x,到目标节点,S,的最优路径的估计代价，,它体现了问题的启发性信息，其形式要根据问题的特性确定。它可以是节点,x,到目标节点的距离或差异，可以是,x,格局的得分，也可以是节点,x,处于最优路径上的概率等等。,h(x),称为启发函数。,3.2.3,状态空间的启发式搜索,估价函数,f(z),表示从初始节点经过节点,Z,到达目标节点的最优路径的代价估计值，它的作用是,估价,OPEN,表中各节点的重要程度，决定它们在,OPEN,表中的次序,。,g(z),指出了搜索的,横向趋势,，它有利于搜索的完备性，但,影响搜索的效率,。如果我们只关心到达目标节点的路径，并且希望有较高的搜索效率，则,g(z),可以忽略，但此时会影响搜索的完备性。,在确定,f(z),时，要权衡各种利弊得失，使,g(z),与,h(z),各占适当的比重。,5.2.3,状态空间的启发式搜索,举例：对,8,数码问题，评估函数可以表示为：,f(z)=d(z)+(z),d(z),表示节点,Z,在搜索树中的深度，,(z),表示节点,Z,不在目标状态中相应位置的数码个数，,(z),就包含了问题的启发式信息。一般来说，某节点,(z),越大，即“不在目标位”的数码个数越多，说明它离目标节点越远。,对初始节点,S,0,，由于,d(S,0,)=0,，,(S,0,)=3,，因此,f(S,0,)=3,。,3.2.3,状态空间的启发式搜索,目标状态,初始状态,几种启发式算法,1.,局部择优搜索,是对深度优先搜索方法的一种改进。,基本思想：,当一个节点被扩展以后，按,f(x),对每一个子节点,计算估价值，并,选择最小者,作为下一个要考查的节点，,由于它,每次都只是在子节点的范围内选择,下一个要考查的节点，范围比较窄，所以称为局部择优搜索。,搜索过程：,(1),把初始节点,s,0,放入,OPEN,表，计算,f(s,0,),；,(2),如果,OPEN,表为空，则问题无解，退出；,(3),把,OPEN,表的第一个节点（记为,n,）取出放入,CLOSED,表；,(4),考查节点,n,是否为目标节点。若是，则求得了问题的解，退出；,(5),若节点,n,不可扩展，则转第,(2),步；,(6),扩展节点,n,，,用估价函数,f(x),计算每个子节点的估价值，并按估价值从大到小的顺序依次放到,OPEN,表的首部,，为每个子节点配置指向父节点的指针。然后转第,(2),步。,几种启发式算法,f(z)=d(z)+(z),d(z),表示节点,Z,在搜索树中的深度，,(z),表示节点,Z,不在目标状态中相应位置的数码个数,目标状态,初始状态,几种启发式算法,深度优先搜索、代价树的深度优先搜索以及局部择优搜索的,相同点：,都是以子节点作为考察范围。,不同点：,它们选择节点的标准不一样。,深度优先搜索,以子节点的深度作为选择标准，后生成的子节点先被考察；,代价树深度优先搜索,以各子节点到父节点的代价作为选择标准，代价小者优先被选择；,局部择优搜索,以估价函数的值作为选择标准，哪一个子节点的,f,值最小就优先被选择。,另外，在局部择优搜索中，,若令,f(x)=g(x),则局部择优搜索就成为代价树的深度优先搜索；若,令,f(x)=d(x),，这里,d(x),表示节点,x,的深度，则局部择优搜索就成为深度优先搜索。,2.,全局择优搜索,每次总是从,OPEN,表的全体节点中选择一个估价值最小的节点。,搜索过程：,(1),把初始节点,S,0,放入,OPEN,表，计算,f(s,0,),；,(2),如果,OPEN,表为空，则搜索失败，退出；,(3),把,OPEN,表中的第一个节点（记为,n,）从表中移出放入,CLOSED,表；,(4),考查节点,n,是否为目标节点。若是，则求得了问题的解，退出；,(5),若节点,n,不可扩展，则转第（,2,）步；,(6),扩展节点,n,，用估价函数,f(x),计算每个子节点的估价值，,并为每个子节点配置指向父节点的指针，把这些子节点都送入,OPEN,表中，然后,对,OPEN,表中的全部节点按估价值从小至大的顺序进行排序；,(7),转第（,2,）步。,几种启发式算法,f(z)=d(z)+(z),d(z),表示节点,Z,在搜索树中的深度，,(z),表示节点,Z,不在目标状态中相应位置的数码个数,目标状态,初始状态,如果使,一般搜索过程,满足如下,限制,，则它就成为,A*,算法：,（1）把,OPEN,表中的节点按估价函数,f(x)=g(x)+h(x),的从小到大进行排序；,（2）代价函数,g(x),是对,g*(x),的估计，,g*(x)0,。,g*(x),是从初始节点,S,0,到节点,x,的最小代价,；,（3）启发函数,h(x),是,h*(x),的下界，即对所有的,x,均有：,h(x),h*(x),。,h*(x),是从节点,x,到目标节点的最小代价,，若有多个目标节点，则为其中最小的一个。,通过,n,的最佳路径：,f,*,(n)=g,*,(n)+h,*,(n),最小的路径，即从,S,出发，通过节点,n,的，到达目标节点的代价和最小的路径。,3.A*,算法,(,最佳图搜索算法,),g(x),比较容易得到，它实际上就是从初始节点,S,0,到节点,x,的路径代价，,恒有,g(x),g*(x),而且在算法执行过程中随着更多搜索信息的获得，,g(x),的值呈下降的趋势。,h(x),的确定,依赖于具体问题领域的启发性信息,，其中,h(x),h,*,(x),的限制是十分重要的，它可保证,A,*,算法能找到最优解。,3.2.3,状态空间的启发式搜索,S,0,x,1,x,2,x,3,3,7,3,2,从节点,S,0,开始，经扩展得到,x,1,与,x,2,，,且,g(x,1,)=3，g(x,2,)=7；,对,x,1,扩展后得到,X,2,与,X,3,此时,g(x,2,)=6，g(x,3,)=5.,显然，后来算出的,g(x,2,),比先前算出的小。,3.2.3,状态空间的启发式搜索,A*,算法描述过程：,(1)把,S,放入,OPEN,表，记,f(S)=h(S),，,令,CLOSED,为空表。,(2)重复下列过程，直至找到目标节点止。若,OPEN,为空表，则宣告失败。,(3)选取,OPEN,表中,未扩展过,的具有,最小,f,值,的节点为最佳节点,BESTNODE，,并把它放入,CLOSED,表。,(4)若,BESTNODE,为一目标节点，则成功求得一解。,(5)若,BESTNODE,不是目标节点，则扩展之，产生后继节点集,SUCCSSOR,i,|i=1,2,n,。,(6),对每个,SUCCSSOR,i,进行下列过程：,(,a),建立从,SUCCSSOR,i,返回,BESTNODE,的指针。,(,b),计算,g(SUCSSOR,i,)=g(BESTNODE)+c(BESNODE,SUCSSOR,i,),。,(c),如果,SUCCSSOR,i,在,OPEN,表,中,则,比较,新旧路径,代价。如果从,S,0,到,SUCSSOR,i,的新路径,旧路径,则重新确定,SUCSSOR,i,的父辈节点为,BESTNODE，,记下较小代价,g(SUCSSOR,i,),并修正,f(SUCSSOR,i,),值。,(,d),如果,SUCCSSOR,i,不在,OPEN,表,中，,在,CLOSE,表中,且从,S,0,到,SUCSSOR,i,的新路径,CLOSED,表中的,g(SUCCSSOR,i,),则,更新,CLOSED,表中的估价函数值,并,从,CLOSED,表中移出节点,SUCCSSOR,i,放入,OPEN,表中,。,(,e),如果,SUCCSSOR,i,不在,OPEN,表,中,也不在,CLOSED,表中,时，求出,SUCCSSOR,i,的估价函数值并将其插入,OPEN,表中。,(7)按照估价函数值将,OPEN,表中的节点排序；,(8),GO LOOP,编号,状态节点,父节点,后继节点表,A*,算法的特性,（,1,）,A*,算法可纳性,对于可解状态空间图（即从初始节点到目标节点有路径存在）来说，如果一个搜索算法能在,有限步内终止,，并且能找到,最优解,，则称该搜索算法是可纳的。,A*,算法是可纳的，即它能在有限步内终止并找到最优解。,（,2,）,A*,算法的最优性,A*,算法的效率在很大程度上取决于,h(x),，在满足,h(x)h*(x),的前提下，,h(x),的值越大越好。,h(x),的值越大，表明它携带的启发性信息越多，搜索时扩展的节点数越少，搜索的效率越高。,（,3,）,h(x),的单调性限制,在,A*,算法中，,每当要扩展一个节点时都要先检查其子节点是否已在,OPEN,表或,CLOSED,表中,，,有时还需要调整指向父节点的指针,，这就,增加了搜索的代价,。如果对启发函数,h(x),加上单调性限制，就可减少检查及调整的工作量，从而减少搜索代价。,3.3,与,/,或树的搜索策略,盲目搜索 包括,与,/,或树的广度优先搜索,、,与,/,或树的深度优先搜索,、,与,/,或树的有界深度优先搜索,启发式搜索,包括,与,/,或树的有序搜索,、,博弈树的启发式搜索,。,用与/或树方法求解问题时，,首先要定义问题的描述方法及分解或变换问题的算符，,然后就可用它们通过搜索生成与/或树，从而求得原始问题的解。,由可解子节点来确定父节点、祖父节点等为可解节点的过程称为,可解标示过程,；,由不可解子节点来确定其父节点、祖父节点等为不可解节点的过程称为,不可解标示过程,。,在与/或树的搜索过程中将反复使用这两个过程，直到初始节点(即原始问题)被标示为可解或不可解节点为止。,3.3,与,/,或树的搜索策略,(1),把原始问题作为初始节点,S,0,，并把它作为当前节点。,(2),应用分解或等价变换算符对当前节点进行扩展。,(3),为每个子节点设置指向父节点的指针。,(4),选择,合适的子节点,作为当前节点，反复执行第,(2),步和第,(3),步，在此期间要,多次调用,可解标示过程,和,不可解标示过程,，直到初始节点被标示为可解节点或不可解节点为止。,由这个搜索过程所形成的,节点,和,指针结构,称为搜索树。与,/,或树搜索的目标是,寻找解树,，从而求得原始问题的解。,3.3.1,与,/,或树的一般搜索过程,说明：,如果在某时刻被选为扩展的节点,不可扩展，并且它不是终止节点,，则此节点就是,不可解节点,。此时可应用,不可解标示过程确定初始节点是否为不可解节点,，如果可以肯定初始节点是不可解的，则搜索失败；否则继续扩展节点。,可解与不可解标示过程都是,自下而上,进行的，即由子节点的可解性确定父节点的可解性。由于与/或树搜索的目标是寻找解树，因此，,如果已确定某个节点为可解节点，则其,不可解的后裔节点,就不再有用,，,可从搜索树中,删去,；,如果已确定某个节点是不可解节点，则其,全部后裔节点都不再有用，,可从搜索树中,删去,，但,当前,这个,不可解节点还不能删去,，因为在判断其先辈节点的可解性时还要用到它。,这是与/或树搜索的两个特有的性质，可用来提高搜索效率。,1.与,/,或树的广度优先搜索,与状态空间的广度优先搜索类似，也是按照“先产生的节点先扩展”的原则进行搜索，只是在搜索过程中要多次调用,可解标示过程,和,不可解标示过程,。,搜索过程,：,(1)把初始节点,S,0,放入,OPEN,表。,(2)把,OPEN,表中的第一个节点(记为节点,n),取出放人,CLOSED,表。,(3)如果节点,n,可扩展，则做下列工作：,扩展节点,n，,将其子节点放入,OPEN,表的,尾部,，并为每个子节点配置指向父节点的指针，以备标示过程使用。,3.3.2,与,/,或树的盲目搜索,考察这些子节点,中是否有终止节点。若有，则标示这些终止节点为可解节点，并应用可解标示过程对其父节点、祖父节点等先辈节点中的可解节点进行标示。,如果初始节点,S,0,也被标示为可解节点，就得到了解树，搜索成功,，退出搜索过程；如果不能确定,S,0,为可解节点，则,从,OPEN,表中删去具有可解先辈的节点,。,转第(2)步。,(4)如果节点,n,不可扩展，则做下列工作：,标示节点,n,为不可解节点。,应用不可解标示过程对,节点,n,的先辈节点中不可解的节点,进行标示。,如果初始节点,S0,也被标示为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程,；如果不能确定,S,0,为不可解节点，则,从,OPEN,表中删去具有不可解先辈的节点,。,3.3.2,与,/,或树的盲目搜索,举例：,P,46,2.10,3.3.2,与,/,或树的盲目搜索,2.与,/,或树的深度优先搜索,和与,/,或树的广度优先搜索过程基本相同，只是要把第,(3),步的第,点改为“,扩展节点,n,，将其子节点放入,OPEN,表的,首部,，,并为每个子节点配置指向父节点的指针，以备标示过程使用,”。这样就可使后产生的节点先被扩展。,3.,与,/,或树的有界深度优先搜索,也可以像状态空间的有界深度优先搜索那样为与,/,或树的深度优先搜索规定一个,深度界限,，使搜索在规定的范围内进行。其搜索过程如下：,(1),把初始节点,S,0,放入,OPEN,表。,(2),把,OPEN,表中的第一个节点,(,记为节点,n),取出放入,CLOSED,表。,(3),如果节点,n,的深度大于等于深度界限,，则转第,(5),步的第,点。,(4),如果节点,n,可扩展，则做下列工作,:,扩展节点,n,，将其子节点放入,OPEN,表的首部，并为每个子节点配置指向父节点的指针，以备标示过程使用。,考察这些子节点中有否终止节点。若有,则标示这些终止节点为可解节点，并应用可解标示过程对其先辈节点中的可解节点进行标示。如果初始节点,S,0,也被标示为可解节点，则搜索成功，退出搜索过程如果不能确定,S,0,为可解节点，则从,OPEN,表中删去具有可解先辈的节点。,转第,(2),步。,(5),如果节点,n,不可扩展，则做下列工作：,标示节点,n,为不可解节点。,应用不可解标示过程对节点,n,的先辈节点中不可解的节点进行标示。如果初始节点,S,0,也被标示为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定,S,0,为不可解节点，则从,OPEN,表中删去具有不可解先辈的节点。,转第,(2),步。,广度优先搜索及深度优先搜索都是盲目搜索，其共同点是：,(1),搜索从初始节点开始，先自上而下地进行搜索，寻找终止节点及端点节，然后再自下而上地进行标示，一旦初始节点被标示为可解节点或不可解节点，搜索就不再继续进行。,(2),搜索都是按确定路线进行的，当要选择一个节点进行扩展时，,只是根据节点在与,/,或树中所处的位置，而没有考虑要付出的代价,，因而求得的解树不一定是代价最小的解树，即,不一定是最优解树,。,3.3.2,与,/,或树的盲目搜索,3.3.3,与,/,或树的启发式搜索,1.与,/,或树的有序搜索,与,/,或树的有序搜索是用来求取代价最小的解树的一种搜索方法，为了求得,代价最小的解树,，就要在每次确定欲扩展的节点时，先,往前多看几步,，计算一下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。,Def:,像这样根据,代价,决定搜索路线的方法称为与,/,或树的有序搜索，它是一种启发式搜索策略。,相关概念：,(1),解树的代价,:,为进行有序搜索，需要计算解树的代价，而解树的代价可通过计算解树中节点的代价得到.,(2),希望树：,下面首先给出,计算节点代价,的方法，然后再,说明如何求解树的代价,。,设用,c(x,y),表示节点,x,到其子节点,y,的代价，则计算节点,x,的代价的方法如下：,(1),如果,x,是终止节点，则定义节点,x,的代价,h(x)=0,；,(2),如果,x,是“或”节点，,y,1,y,2,y,n,是它的子节点，则节点,x,的代价由下式计算得到,h(x)=minc(x,y,i,)+h(y,i,),，,(1in),(3),如果,x,是“与”节点，则节点,x,的代价有两种计算方法：和代价法与最大代价法。,若按和代价法计算，则有,h(z)=(c(z,y,i,)+h(y,i,),若按最大代价法计算，则有,h(z)=max(c(z,y,i,)+h(y,i,),(4),如果,x,不可扩展，且又不是终止节点，则定义,h(z),=,。,3.3.3,与,/,或树的启发式搜索,举例：下图是一棵与/或树，其中包括两棵解树，一棵解树由,S,0,，A，t,1,和,t,2,组成；另一棵解树由,S,0,，B，D，G，t,4,和,t,5,组成。在此与/或树中，,t,1,t,2,t,3,t,4,t,5,为终止节点；,E,F,是端节点，其代价为,；边上的数字是该边的代价。,由左边的解树可得:,按和代价：,h(A)=11,h(S,0,)=13,按最大代价：,h(A)=6,h(S,0,)=8,由右边的解树可得:,按和代价：,h(G)=3,h(D)=4,h(B)=6,h(S,0,)=8,按最大代价：,h(G)=2,h(D)=3,h(B)=5,h(S,0,)=7,(2)