第五章-搜索策略资料

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 搜索策略,5.1,概述,5.2,状态空间搜索,5.3,与或树搜索,2,搜索分为盲目搜索和启发式搜索。,盲目搜索是按照预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。,启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。,3,问题求解过程可以看作一个搜索过程。状态空间表示法是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的一种形式化方法。,状态空间用“状态”和“算符”来表示问题。,状态,状态用以描述问题求解过程中不同时刻的状况，是一个数据结构，一般用一组变量的有序组合表示：,S,K,=(S,k0,S,k1,),当每一个分量的值确定时，就得到了一个具体的状态。,算符,引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。,状态空间,由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：,(S,F,G),其中,S,是问题所有初始状态的集合；,F,是算符的集合；,G,是目标状态的集合。,状态空间的图示形式称为状态空间图。,4,设用,S,K,=(S,k0,S,k1,),表示问题的状态，,S,K0,表示金片,A,所在的柱号，,S,k1,表示金片,B,所在的柱号，全部可能的状态有九种：,S,0,=(1,1), S,1,=(1,2) , S,2,=(1,3),S,3,=(2,1), S,4,=(2,2) , S,5,=(2,3),S,6,=(3,1), S,7,=(3,2) , S,8,=(3,3),问题的初始状态集合为,S=S,0,目标状态集合为,G=S,4,S,8,。,算符分别用,A(i,j),及,B(i,j),。,A(i,j),表示把,A,金片从第,i,号柱移到第,j,号柱。,B(i,j),与之同理。算符共有,12,个。,在状态空间图中，从初始节点,(1,1),到目标节点,(2,2),或,(3,3),的任何一条通路都是问题的一个解。,其中最短的路径长度是,3,，,它由,3,个算符组成。,例如,:A(1,3),B(1,2),A(3,2),5,用状态空间方法表示问题，首先必须定义状态的描述形式，把问题的一切状态都表示出来。其次要定义一组算符。,问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。,算符的一次使用，就使问题由一种状态转变为另一种状态。使用算符最少的解或者总代价最少的解称为最优解。,对任何一个状态，可使用的算符可能不止一个。这样由一个状态所生成的后继状态就可能有多个。此时首先对哪一个状态进行操作，就取决于搜索策略。,6,与或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解。,对于一个复杂问题，直接求解往往比较困难。此时可通过下述方法进行简化：,分解,把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解。重复此过程，直到不需要或者不能再分解为止。如此形成“与”树。,等价变换,利用同构或同态的等价变换，把原问题变换为若干个较为容易求解的新问题。如此形成“或”树。,7,8,本原问题,不能再分解或变换，而且直接可解的子问题。,端节点与终止节点,在与,/,或树中，没有子节点的节点统称为端节点；本原问题所对应的节点称为终止节点。,可解节点,在与,/,或树中，满足下列条件之一者，称为可解节点：,它是一个终止节点；,它是一个,“,或,”,节点，且其子节点中至少有一个是可解节点；,它是一个,“,与,”,节点，且其子节点全部是可解节点。,不可解节点,关于可解节点的三个条件全部不满足的节点,9,解树,由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。,10,11,12,盲目搜索的特点：,搜索按规定的路线进行，不使用与问题有关的启发性信息；,适用于其状态空间图是树状结构的一类问题。,启发式搜索要使用与问题有关的启发性信息，并以这些启发性信息指导搜索过程，可以高效地求解结构复杂的问题。,广度优先搜索按照,“,先扩展出的节点先被考察,”,的原则进行搜索；,深度优先搜索按照,“,后扩展出的节点先被考察,”,的原则进行搜索；,有界深度优先搜索的原则与深度优先搜索相同，但是它规定了深度限界，使搜索不得无限制地向纵深方向发展；,代价树的广度优先搜索按照,“,哪个节点到根节点的代价小就先考察哪个节点,”,的原则进行搜索；,代价树的深度优先搜索按照,“,当前节点的哪个子节点到其父节点的代价小就先考察哪个子节点,”,的原则进行搜索；,局部择优搜索按照,“,当前节点的哪个子节点到目标节点的估计代价小就先考察哪个子节点,”,的原则进行搜索；,全局择优搜索按照,“,哪个节点到目标节点的估计代价小就先考察哪个节点,”,的原则进行搜索；,13,OPEN,表和,CLOSE,表,OPEN,表用于存放刚生成的节点。对于不同的搜索策略，节点在,OPEN,表中的排列顺序是不同的。,CLOSE,表用于存放将要扩展或者已经扩展的节点。,OPEN,表,CLOSE,表,14,状态节点,父节点,编号,状态节点,父节点,把初始节点,S,0,放入,OPEN,表，并建立目前只包含,S,0,的图，记为,G,；,检查,OPEN,表是否为空，若为空则问题无解，退出；,把,OPEN,表的第一个节点取出放入,CLOSE,表，并计该节点为,n,；,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出；,扩展节点,n,，生成一组子节点。把其中不是节点,n,先辈的那些子节点记做集合,M,，并把这些子节点作为节点,n,的子节点加入,G,中；,针对,M,中子节点的不同情况，分别进行如下处理：,对于那些未曾在,G,中出现过的,M,成员设置一个指向父节点（即节点,n,）的指针，并把它们放入,OPEN,表；,对于那些先前已经在,G,中出现过的,M,成员，确定是否需要修改它指向父节点的指针；,对于那些先前已在,G,中出现并且已经扩展了的,M,成员，确定是否需要修改其后继节点指向父节点的指针；,按某种搜索策略对,OPEN,表中的节点进行排序；,转第,2,步。,15,上述是一个通用过程，各种搜索策略的主要区别是对,OPEN,表中节点排序的准则不同。,一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。,一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节点被再次生成。此时，它究竟应作为哪个节点的不后继节点？一般由原始节点到该节点的代价来决定，代价小的相应节点就作为父节点。,在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。,如果在搜索中一直找不到目标节点，而且,OPEN,表中不再有可供扩展的节点，则搜索失败。,16,基本思想：,从初始节点,S,0,开始，逐层地对节点进行扩展并考察它是否为目标节点。在第,n,层的节点没有全部扩展并考察之前，不对第,n,1,层的节点进行扩展。,OPEN,表中节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。,17,把初始节点,S,0,放入,OPEN,表。,如果,OPEN,表为空，则问题无解，退出。,把,OPEN,表的第一个节点（记为节点,n,）取出放入,CLOSE,表。,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,若节点,n,不可扩展，则转第,2,步。,扩展节点,n,，将其子节点放入,OPEN,表的,尾,部，并为每一个子节点都配置指向父节点的指针，然后转第,2,步。,18,19,优点：,只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。,缺点：,广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。,20,基本思想：,从初始节点,S,0,开始，在其子节点中选择一个节点进行考察。若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索。当达到某个子节点，且该子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。,深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点,n,的子节点放入到,OPEN,表的尾部，而深度优先搜索是把节点,n,的子节点放入到,OPEN,表的首部。,21,把初始节点,S,0,放入,OPEN,表。,如果,OPEN,表为空，则问题无解，退出。,把,OPEN,表的第一个节点（记为节点,n,）取出放入,CLOSE,表。,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,若节点,n,不可扩展，则转第,2,步。,扩展节点,n,，将其子节点放入,OPEN,表的,首,部，并为每一个子节点都配置指向父节点的指针，然后转第,2,步。,22,23,在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。,用深度优先求得的解，不一定是路径最短的解。,24,基本思想：,对深度优先搜索引入搜索深度的界限（设为,d,m,），当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。,搜索过程：,把初始节点,S,0,放入,OPEN,表中，置,S,0,的深度,d(S,0,)=0,。,如果,OPEN,表为空，则问题无解，退出。,把,OPEN,表的第一个节点（记为节点,n,）取出放入,CLOSE,表。,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,若节点,n,的深度,d(,节点,n)=d,m,，则转第,2,步。,若节点,n,不可扩展，则转第,2,步。,扩展节点,n,，将其子节点放入,OPEN,表的,首,部，并为每一个子节点都配置指向父节点的指针，然后转第,2,步。,25,如果问题有解，且其路径长度,d,m,，则上述搜索过程一定能求得解。但是，若解的路径长度,d,m,则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。,要恰当地给出,d,m,的值是比较困难的。即使能求出解，它也不一定是最优解。,26,先任意设定一个较小的数作为,d,m,，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限,d,m,仍未发现目标节点，并且,CLOSE,表中仍有待扩展节点时，就将这些节点送回,OPEN,表，同时增大深度界限,d,m,，继续向下搜索。如此不断地增大,d,m,，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。,为了找到最优解，可增设一个表,R,，每找到远程目标节点,S,g,后，就把它放入到,R,的前面，并令,d,m,等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以后求得的解一定是最优解。,27,设深度界限,d,m,4,28,盲目搜索具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率不高。,启发式搜索要用到问题自身的某些特性信息，以指导搜索朝着最有希望的方向前进。由于这种搜索针对性较强，因而原则上只需要搜索问题的部分状态空间，效率较高。,29,可用于指导搜索过程，且与具体问题求解有关的控制性信息称为启发性信息。,用于估价节点重要性的函数称为估价函数。其一般形式为：,f(x) = g(x)+h(x),其中,g(x),为从初始节点,S,0,到节点,x,已经实际付出的代价；,h(x),是从节点,x,到目标节点,S,g,的最优路径的估计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定。例如它可以是节点,x,到目标节点的距离，或者节点,x,处于最优路径上的概率等等。,h(x),称为启发函数。,g(x),指出了搜索的横向趋势。它有利于搜索的完备性，但影响搜索的效率。如果我们只关心到达目标节点的路径，并且希望有较高的搜索效率，则,g(x),可以忽略，但此时会影响搜索的完备性。,30,设有如下结构的移动牌游戏：,该游戏规则：,当一个牌移入相邻的空位置时，费用为一个单位。,一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加,1,。,要求把所有的,B,都移至,W,的右边，请设计估价函数中的,h(x,),。,解：根据要求可知，,W,左边的,B,越少越接近目标，因此可用,W,左边,B,的个数作为,h(x,),即,h(x,)=3(,每个,W,左边,B,个数的总和,),这里乘以系数,3,是为了扩大,h(x,),在,f(x,),中的比重。,31,B,B,B,W,W,W,E,基本思想：,当一个节点被扩展以后，按,f(x,),对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点。,搜索过程：,把初始节点,S,0,放入,OPEN,表，令,g(S,0,)=0,。,如果,OPEN,表为空，则问题无解，退出。,把,OPEN,表的第一个节点（记为节点,n,）取出放入,CLOSE,表。,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,若节点,n,不可扩展，则转第,2,步。,扩展节点,n,，用估价函数,f(x,),计算每个子节点的估价值，并按估价值从小到大的顺序放到,OPEN,表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第,2,步。,深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的。但是前二者可以看作局部择优搜索的特例。,32,基本思想：,在代价树的广度优先搜索中，每次都是从,OPEN,表的全体节点中选择一个代价最小的节点送入,CLOSE,表进行考察。而代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入,CLOSE,表进行考察。,搜索过程：,把初始节点,S,0,放入,OPEN,表，令,g(S,0,)=0,。,如果,OPEN,表为空，则问题无解，退出。,把,OPEN,表的第一个节点（记为节点,n,）取出放入,CLOSE,表。,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,若节点,n,不可扩展，则转第,2,步。,扩展节点,n,，将其子节点按代价从小到大的顺序放到,OPEN,表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第,2,步。,代价树的深度有限搜索是不完备的。,33,34,基本思想：,每当要选择一个节点进行考察时，局部择优搜索只是从刚生成的子节点中进行选择，选择的范围比较狭窄。全局择优搜索每次总是从,OPEN,表的全体节点中选择一个估价值最小的节点。,搜索过程：,把初始节点,S,0,放入,OPEN,表，计算,f(S,0,),。,如果,OPEN,表为空，则问题无解，退出。,把,OPEN,表的第一个节点（记为节点,n,）取出放入,CLOSE,表。,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,若节点,n,不可扩展，则转第,2,步。,扩展节点,n,，用估价函数,f(x,),计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入,OPEN,表中，然后对,OPEN,表中的全部节点按估价值从小至大的顺序进行排序，然后转第,2,步。,广度优先搜索、代价树的广度优先搜索以及全局择优搜索都是以当前所有节点作为考察范围的。但是前二者可以看作全局择优搜索的特例。,设估价函数为,f(x)=d(x)+h(x),其中，,d(x),表示节点,x,的深度，,h(x),表示节点,x,的格局与目标节点格局不相同的牌数。,35,边上标有代价,(,或费用,),的树称为代价树。,用,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,表中选择节点往,CLOSE,表传送时，总是选择其代价最小的节点。也就是说，,OPEN,表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置。,如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解。,36,把初始节点,S,0,放入,OPEN,表，令,g(S,0,)=0,。,如果,OPEN,表为空，则问题无解，退出。,把,OPEN,表的第一个节点（记为节点,n,）取出放入,CLOSE,表。,考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,若节点,n,不可扩展，则转第,2,步。,扩展节点,n,，将其子节点放入,OPEN,表中，并为每一个子节点都配置指向父节点的指针。计算各子节点的代价，并按各节点的代价对,OPEN,表中的全部节点进行排序,(,按从小到大的顺序,),，然后转第,2,步。,37,38,如果使一般搜索过程满足如下限制，则它就称为,A*,算法：,1,、把,OPEN,表中的节点按估价函数,f(x)=g(x)+h(x),的值从小至大进行排序（一般搜索过程的第,7,步）。,2,、,g(x),是对,g*(x),的估计，,g(x)0,。,3,、,h(x),是,h*(x),的下界，即对所有的,x,均有：,h(x)h*(x),其中，,g*(x),是从初始节点,S,0,到节点,x,的最小代价；,h*(x),是从节点,x,到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。,39,在,A*,算法中，,g(x,),实际上就是从初始节点,S,0,到节点,x,的路径代价，恒有,g(x)g,*(x),。而且在算法执行过程中随着更多搜索信息的获得，,g(x,),的值呈下降的趋势。,例如：,H(x,),的确定依赖于具体问题领域的启发性信息，其中,h(x)h,*(x),的限制十分重要，它保证,A*,算法能找到最优解。,40,可纳性,对于可解状态空间图,(,即从初始节点到目标节点有路径存在,),来说，如果一个搜索算法能在有限步那终止，并且能找到最优解，则称该搜索算法是可纳的。,A*,算法是可纳的。,A*,算法的最优性,A*,算法的搜索效率在很大程度上取决于,h(x,),，在满足,h(x)h,*(x),的前提下，,h(x,),的值越大越好。,h(x,),的值越大，表明它携带的启发性信息越多，搜索时扩展的节点数越少，搜索的效率越高。,h(x,),的单调性限制,在,A*,算法中，每当要扩展一个节点时都要先检查其子节点是否已在,OPEN,表或,CLOSE,表中，有时还要调整指向父节点的指针，这就增加了搜索的代价。如果对启发函数,h(x,),加上单调性限制，就可减少检查及调整的工作量，从而减少搜索代价。,41,所谓单调性限制是指,h(x),满足如下两个条件：,1,、,h(S,g,)=0;,2,、设,x,j,是节点,x,i,的任意子节点，则有,h(x,i,)-h(x,j,)c(x,i,x,j,),，即,h(x,i,)h(x,j,)+c(x,i,x,j,),其中，,S,g,是目标节点；,c(x,i,x,j,),是节点,x,i,到其子节点,x,j,的代价。,可以证明，当,A*,算法的启发函数,h(x),满足单调性限制时，可得到如下两个结论：,1,、若,A*,算法选择节点,x,n,进行扩展，则,g(x,n,)=g*(x,n,),2,、由,A*,算法所扩展的节点序列其,f,值是非递减的。,这两个结论都是在,h(x),满足单调性限制时才成立的。否则，它们不一定成立。,42,5.3.1,与或树的一般搜索过程,5.3.2,与或树的广度优先搜索,5.3.3,与或树的深度优先搜索,5.3.4,与或树的有序搜索,5.3.5,博弈树的启发式搜索,5.3.6,剪枝技术,43,完备性,对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称该搜索过程为完备的，否则为不完备的。,广度优先搜索、代价树的广度优先搜索、改进后的有界深度优先搜索以及,A*,算法都是完备的搜索过程，其它搜索过程都是不完备的。,44,一个搜索过程的搜索效率不仅取决于过程自身的启发能力，而且还与被解问题的有关属性等多种因素有关。目前虽已有多种定义和计算搜索效率的方法，但都有一定的局限性。,外显率,外显率定义为,P=L/T,其中，,L,为从初始节点到目标节点的路径长度；,T,为整个搜索过程中所生成的节点总数。,外显率反映了搜索过程中从初始节点向目标节点前进时搜索区域的宽度。当,L=T,时，,P=1,，表示搜索过程中每次只生成一个节点，它恰好是解路径上的节点，搜索效率最高。,P,越小表示搜索时产生的无用节点愈多，搜索效率愈低。,45,有效分枝因数,B,定义为,B+B,2,+,+B,L,=T,其中，,B,是有效分枝因数，它表示在整个搜索过程中每个有效节点平均生成的子节点数目；,L,为路径长度；,T,为节点总数。,当,B,1,时，,L=T,，此时所生成的节点数最少，搜索效率最高。,不难证明，有效分枝因数与外显率之间由如下关系：,P=(L(B-1)/(B(B,L,-1),T=B(B,L,-1)/(B-1),由此可以看出，,当,B,一定时，,L,愈大则,P,愈小；,当,L,一定时，,B,愈大则,P,愈小；,对同一个,L,而言，,B,愈大则,T,愈大。,46,47,与,/,或树的搜索策略就是确定节点是否为可解或不可解节点。在整个确定过程中，会循环用到两个过程，分别为：,可解标示过程：,由可解子节点来确定父节点、祖父节点等为可解节点的回溯向上过程,不可解标示过程：,由不可解子节点来确定其父节点、祖父节点等为不可解节点的回溯向上过程,这两个过程都是自下而上进行的，即由子节点的可解性确定父,(,或祖先,),节点的可解性,5.3.1,与,/,或树的搜索策略,48,与,/,或树的搜索策略,与,/,或树的一般搜索过程：,1,）,把原始问题作为初始节点,S,0,，并把它作为当前节点,2,）,应用分解或等价变换算符对当前节点进行扩展。,3,）,为每个子节点设置指向父节点的指针。,4,）,选择合适的子节点作为当前节点，反复执行第,2,）步和第,3,）步，在此期间要多次调用,可解标示过程,和,不可解标示过程,，直到初始节点被标示为可解节点或不可解节点为止。,49,与,/,或树搜索的两个特性：,(1),如果已确定某个节点是可解节点，则删去其不可解的后裔节点,(2),如果已确定某个节点是不可解节点，删去其全部后裔节点，保留该结点,50,5.3.2,与,/,或树的宽度优先搜索,搜索过程：,与状态空间的宽度优先搜索类似，按照,“,先产生的节点先扩展,”,的原则进行搜索，在整个搜索过程中多次调用可解标示过程和不可解标示过程。,51,例,设有如图所示的与,/,或树，节点按图中所标注的顺序号进行扩展。其中标有,t,1,、,t,2,、,t,3,、,t,4,的节点均为,终止节点,，,A,和,B,为不可解的,端节点,。,1,2,3,4,t1,5,B,A,t2,t4,t5,52,5.3.3,与,/,或树的有界深度优先搜索,其搜索过程：,与,/,或树的深度优先搜索过程和与,/,或树的宽度优先搜索过程基本相同，只是将扩展节点的子节点放入,OPEN,表的,首部,，并为每个子节点配置指向父节点的指针。,与,/,或树的有界深度优先搜索同样也规定一个深度界限，使搜索在规定的范围内进行,53,5.3.4,与,/,或树的有序搜索,与,/,或树的有序搜索可用来求取代价最小的解树，是一种启发式搜索策略,1.,解树的代价,可通过计算树中节点的代价得到。,设,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,54,1.,解树的代价,3,）如果,x,是,“,与,”,节点，则节点,x,的代价有两种计算方法：和代价法与最大代价法。,若按和代价法计算，则有：,n,h(x)=,(,c(x, y,i,)+h(y,i,),i=1,若按最大代价法计算，则有：,h(x)=maxc(x, y,i,)+h(y,i,),1in,4,）如果,x,是不可扩展，且又不是终止节点，则定义,h(x)=,。,55,例,图为一棵与,/,或树，其中包括两棵解树，一棵解树由,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,是端节点，其代价为,；边上的数字是边的代价。,56,S,0,A,t1,t2,6,5,2,B,D,G,t4,t5,2,2,1,1,2,S,0,左边的解树,右边的解树,57,1),若按和代价计算，右解树是最优解树，,其代价为,8,；,2),若按最大代价计算，右解树仍然是最优解树，,其代价为,7,。,有时用不同的计算代价方法得到的最优解树不相同。,S,0,A,t1,t2,6,5,2,B,D,G,t4,t5,2,2,1,1,2,S,0,由左边的解树可得： 按和代价：,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,58,2.,希望树,定义：,每次选择欲扩展的节点时希望成为最优解树一部分的节点进行扩展。由这些节点及其先辈节点所构成的与,/,或树 ，称为希望树,1,）初始节点,S,0,在希望树,T,中。,2,）如果节点,x,在希望树,T,中，则一定有：,如果,x,是具有子节点,y,1,y,2,y,n,的,“,或,”,节点,则具有,:,minc(x, y,i,)+h(y,i,) 1in,值的那个子节点,y,i,也应在,T,中。,如果,x,是,“,与,”,节点，则它的全部子节点都应在,T,中。,59,博弈问题（或对抗性搜索）为什么可以用与,/,或图表示呢？,可以这样来看待这个问题：,当轮到我方走棋时，只需从若干个可以走的棋中，选择一个棋走就可以了。从这个意义上说，若干个可以走的棋是,“,或,”,的关系。而对于轮到对方走棋时，对于我方来说，必须能够应付对手的每一种走棋。这就相当于这些棋与,/,或的关系。因此，博弈问题可以看成是一个与,/,或图，但是与一般的与,/,或图并不一样，是一种特殊的与,/,或图,5.3.5,博弈树的启发式搜索,60,1.,博弈树的概念,:,描述博弈过程的与,/,或树,博弈树特点：,1,）博弈的初始格局是初始节点,2,）在博弈树中，,“,或,”,节点和,“,与,”,节点是逐层交替出现的。自己一方扩展的节点之间是,“,或,”,关系，对方扩展的节点之间是,“,与,”,关系。双方轮流地扩展节点,3,）所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点，所有使对方获胜的终局都是不可解节点,61,在二人博弈过程中，要根据当前以及将要发生的情况进行分析从而做出有利于自己的行动方案，从中选出最优方案。,2.,极大极小分析法,62,1,）设博弈的双方中一方为,A,，另一方为,B,。极大极小分析法是为其中的一方（例如,A,）寻找一个最优行动方案的方法。,2,）为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较。具体地说，就是要考虑每一个方案实施后对方可能采取的所有行动，并计算可能的得分,3,）为了计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。,4,）当端节点的估值计算出来后，再推算出父节点的得分。,推算的方法：,对“,或,”节点：选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；,对“,与,”节点：选其子节点中一个最小的得分作为父节点的得分，这是为了立足最坏的情况。这样计算出的父节点的得分称为倒推值。,5,）如果一个行动方案能获得较大的倒推值，则它就是当前最好的方案。,2.,极大极小分析法,基本思想,63,计算博弈树倒推值示例,(,节点估值已给出,),64,3., ,剪枝技术,由于在极大极小分析法中，要计算倒推值，效率低。如果可以实现将节点与计算估值及倒推值同时实现，就可以删去一些不必要的节点，从而减少搜索及计算的工作量，提高效率，提出了, ,剪枝技术,概念：,通过边生成节点边计算方法，从而剪去某些分枝的技术称为, ,剪枝技术,值：,对于一个,“,与,”,节点来说，它取当前子节点中的最小倒推值作为它的倒推值的上界,值：,对于一个,“,或,”,节点来说，它取当前子节点中的最大倒推值作为它的倒推值的下界,65, ,剪枝技术的一般规律,1,）,任何,“,或,”,节点,x,的,值如果不能降低其父节点的,值，则对节点,x,以下的分枝可停止搜索，并使,x,的倒推值为,。这种剪枝称为,剪枝,。,2,）,任何,“,与,”,节点,x,的,值如果不能升高其父节点的,值，则对节点,x,以下的分枝可停止搜索，并使,x,的倒推值为,。这种剪枝称为,剪枝,。,2,3,66,S,2,2,N,V,G,M,D,F,I,L,F,U,Q,T,9,3,1,-1,-1,3,6,8,-1,2,0,3,-5,7,4,-2,6,-1,8,-7,-1,0,3,2,值,2,1,-1,值,2,2,值,2,6,6,0,0,0,-5,0,67,S,2,N,V,G,M,D,F,I,L,U,Q,T,9,3,1,-1,6,8,0,3,-5,68,2,4,5,-3,6,2,1,3,2,2,1,2,5,3,7,9,8,L,E,B,M,N,P,F,S,A,C,G,H,II,D,J,K,4,1,作业：如图的博弈树，已经给出相应节点的估值,（,1,）请计算各节点倒推值,（,2,）应用, ,剪枝技术,剪去不必要的分枝。,