第五章-搜索策略资料优秀PPT.ppt

第五章 搜寻策略5.1 概述5.2 状态空间搜寻5.3 与或树搜寻w2搜寻分为盲目搜寻和启发式搜寻。盲目搜寻是依据预定的限制策略进行搜寻，在搜寻过程中获得的中间信息不用来改进限制策略。启发式搜寻是在搜寻中加入了与问题有关的启发性信息，用以指导搜寻朝着最有希望的方向前进，加速问题的求解过程并找到最优解。w3w问题求解过程可以看作一个搜寻过程。状态空间表示法是用来表示问题及其搜寻过程的一种方法。它是人工智能中最基本的一种形式化方法。w状态空间用“状态”和“算符”来表示问题。w状态w状态用以描述问题求解过程中不同时刻的状况，是一个数据结构，一般用一组变量的有序组合表示：wSK=(Sk0,Sk1,)w当每一个重量的值确定时，就得到了一个具体的状态。w算符w引起状态中某些重量发生变更，从而使问题从一个状态变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。w状态空间w由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：w(S,F,G)w其中S是问题全部初始状态的集合；F是算符的集合；G是目标状态的集合。w状态空间的图示形式称为状态空间图。w4设用SK=(Sk0,Sk1)表示问题的状态，SK0表示金片A所在的柱号，Sk1表示金片B所在的柱号，全部可能的状态有九种：S0=(1,1),S1=(1,2),S2=(1,3)S3=(2,1),S4=(2,2),S5=(2,3)S6=(3,1),S7=(3,2),S8=(3,3)问题的初始状态集合为S=S0,目标状态集合为G=S4,S8。算符分别用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)w5用状态空间方法表示问题，首先必需定义状态的描述形式，把问题的一切状态都表示出来。其次要定义一组算符。问题的求解过程是一个不断把算符作用于状态的过程。假如在运用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。算符的一次运用，就使问题由一种状态转变为另一种状态。运用算符最少的解或者总代价最少的解称为最优解。对任何一个状态，可运用的算符可能不止一个。这样由一个状态所生成的后继状态就可能有多个。此时首先对哪一个状态进行操作，就取决于搜寻策略。w6与或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较困难问题的求解。对于一个困难问题，干脆求解往往比较困难。此时可通过下述方法进行简化：分解把一个困难问题分解为若干个较为简洁的子问题，每个子问题又可接着分解。重复此过程，直到不须要或者不能再分解为止。如此形成“与”树。等价变换利用同构或同态的等价变换，把原问题变换为若干个较为简洁求解的新问题。如此形成“或”树。w7w8本原问题不能再分解或变换，而且干脆可解的子问题。端节点与终止节点在与/或树中，没有子节点的节点统称为端节点；本原问题所对应的节点称为终止节点。可解节点在与/或树中，满足下列条件之一者，称为可解节点：它是一个终止节点；它是一个“或”节点，且其子节点中至少有一个是可解节点；它是一个“与”节点，且其子节点全部是可解节点。不行解节点关于可解节点的三个条件全部不满足的节点w9解树由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。w10w11w12盲目搜寻的特点：搜寻按规定的路途进行，不运用与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。启发式搜寻要运用与问题有关的启发性信息，并以这些启发性信息指导搜寻过程，可以高效地求解结构困难的问题。广度优先搜寻依据“先扩展出的节点先被考察”的原则进行搜寻；深度优先搜寻依据“后扩展出的节点先被考察”的原则进行搜寻；有界深度优先搜寻的原则与深度优先搜寻相同，但是它规定了深度限界，使搜寻不得无限制地向纵深方向发展；代价树的广度优先搜寻依据“哪个节点到根节点的代价小就先考察哪个节点”的原则进行搜寻；代价树的深度优先搜寻依据“当前节点的哪个子节点到其父节点的代价小就先考察哪个子节点”的原则进行搜寻；局部择优搜寻依据“当前节点的哪个子节点到目标节点的估计代价小就先考察哪个子节点”的原则进行搜寻；全局择优搜寻依据“哪个节点到目标节点的估计代价小就先考察哪个节点”的原则进行搜寻；w13OPEN表和CLOSE表OPEN表用于存放刚生成的节点。对于不同的搜寻策略，节点在OPEN表中的排列依次是不同的。CLOSE表用于存放将要扩展或者已经扩展的节点。OPEN表CLOSE表w14状态节点父节点编号 状态节点 父节点1.把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；2.检查OPEN表是否为空，若为空则问题无解，退出；3.把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；4.考察节点n是否为目标节点。若是，则求得了问题的解，退出；5.扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；6.针对M中子节点的不同状况，分别进行如下处理：7.对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；8.对于那些从前已经在G中出现过的M成员，确定是否须要修改它指向父节点的指针；9.对于那些从前已在G中出现并且已经扩展了的M成员，确定是否须要修改其后继节点指向父节点的指针；10.按某种搜寻策略对OPEN表中的节点进行排序；11.转第2步。w151.上述是一个通用过程，各种搜寻策略的主要区分是对OPEN表中节点排序的准则不同。2.一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。3.一个新生成的节点，它可能是第一次被生成的节点，也可能是从前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节点被再次生成。此时，它原委应作为哪个节点的不后继节点？一般由原始节点到该节点的代价来确定，代价小的相应节点就作为父节点。4.在搜寻过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。5.假如在搜寻中始终找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜寻失败。w16基本思想：从初始节点S0起先，逐层地对节点进行扩展并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n1层的节点进行扩展。OPEN表中节点总是按进入的先后依次排列，先进入的节点排在前面，后进入的排在后面。w171.把初始节点S0放入OPEN表。2.假如OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不行扩展，则转第2步。6.扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。w18w19优点：只要问题有解，用广度优先搜寻总可以得到解，而且得到的是路径最短的解。缺点：广度优先搜寻盲目性较大，当目标节点距初始节点较远时将会产生很多无用节点，搜寻效率低。w20基本思想：从初始节点S0起先，在其子节点中选择一个节点进行考察。若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，始终如此向下搜寻。当达到某个子节点，且该子节点既不是目标节点，又不能接着扩展时，才选择其兄弟节点进行考察。深度优先搜寻与广度优先搜寻的唯一区分是：广度优先搜寻是将节点n的子节点放入到OPEN表的尾部，而深度优先搜寻是把节点n的子节点放入到OPEN表的首部。w211.把初始节点S0放入OPEN表。2.假如OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不行扩展，则转第2步。6.扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。w22w23在深度优先搜寻中，搜寻一旦进入某个分支，就将沿着该分支始终向下搜寻。假如目标节点恰好在此分支上，则可较快地得到解。但是，假如目标节点不在此分支上，而该分支又是一个无穷分支，则就不行能得到解。所以深度优先搜寻是不完备的，即使问题有解，它也不确定能求得解。用深度优先求得的解，不确定是路径最短的解。w24w基本思想：w对深度优先搜寻引入搜寻深度的界限（设为dm），当搜寻深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜寻。w搜寻过程：w把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。w假如OPEN表为空，则问题无解，退出。w把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。w考察节点n是否为目标节点。若是，则求得了问题的解，退出。w若节点n的深度d(节点n)=dm，则转第2步。w若节点n不行扩展，则转第2步。w扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。w25假如问题有解，且其路径长度dm，则上述搜寻过程确定能求得解。但是，若解的路径长度dm,则上述搜寻过程就得不到解。这说明在有界深度优先搜寻中，深度界限的选择是很重要的。要恰当地给出dm的值是比较困难的。即使能求出解，它也不确定是最优解。w261.先随意设定一个较小的数作为dm，然后进行上述的有界深度优先搜寻，当搜寻达到了指定的深度界限dm仍未发觉目标节点，并且CLOSE表中仍有待扩展节点时，就将这些节点送回OPEN表，同时增大深度界限dm，接着向下搜寻。如此不断地增大dm，只要问题有解，就确定可以找到它。但此时找到的解不确定是最优解。2.为了找到最优解，可增设一个表R，每找到远程目标节点Sg后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后接着搜寻。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以后求得的解确定是最优解。w27设深度界限dm4w28盲目搜寻具有较大的盲目性，产生的无用节点较多，搜寻空间较大，效率不高。启发式搜寻要用到问题自身的某些特性信息，以指导搜寻朝着最有希望的方向前进。由于这种搜寻针对性较强，因而原则上只须要搜寻问题的部分状态空间，效率较高。w29可用于指导搜寻过程，且与具体问题求解有关的限制性信息称为启发性信息。用于估价节点重要性的函数称为估价函数。其一般形式为：f(x)=g(x)+h(x)其中g(x)为从初始节点S0到节点x已经实际付出的代价；h(x)是从节点x到目标节点Sg的最优路径的估计代价，它体现了问题的启发性信息，其形式要依据问题的特性确定。例如它可以是节点x到目标节点的距离，或者节点x处于最优路径上的概率等等。h(x)称为启发函数。g(x)指出了搜寻的横向趋势。它有利于搜寻的完备性，但影响搜寻的效率。假如我们只关切到达目标节点的路径，并且希望有较高的搜寻效率，则g(x)可以忽视，但此时会影响搜寻的完备性。w30设有如下结构的移动牌游戏：该游戏规则：当一个牌移入相邻的空位置时，费用为一个单位。一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加1。要求把全部的B都移至W的右边，请设计估价函数中的h(x)。解：依据要求可知，W左边的B越少越接近目标，因此可用W左边B的个数作为h(x),即h(x)=3(每个W左边B个数的总和)这里乘以系数3是为了扩大h(x)在f(x)中的比重。w31BBBWWWE基本思想：当一个节点被扩展以后，按f(x)对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点。搜寻过程：把初始节点S0放入OPEN表，令g(S0)=0。假如OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不行扩展，则转第2步。扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值从小到大的依次放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。深度优先搜寻、代价树的深度优先搜寻以及局部择优搜寻都是以子节点作为考察范围的。但是前二者可以看作局部择优搜寻的特例。w32基本思想：在代价树的广度优先搜寻中，每次都是从OPEN表的全体节点中选择一个代价最小的节点送入CLOSE表进行考察。而代价树的深度优先搜寻是从刚扩展出的子节点中选一个代价最小的节点送入CLOSE表进行考察。搜寻过程：把初始节点S0放入OPEN表，令g(S0)=0。假如OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不行扩展，则转第2步。扩展节点n，将其子节点按代价从小到大的依次放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。代价树的深度有限搜寻是不完备的。w33w34基本思想：每当要选择一个节点进行考察时，局部择优搜寻只是从刚生成的子节点中进行选择，选择的范围比较狭窄。全局择优搜寻每次总是从OPEN表的全体节点中选择一个估价值最小的节点。搜寻过程：把初始节点S0放入OPEN表，计算f(S0)。假如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的格局与目标节点格局不相同的牌数。w35边上标有代价(或费用)的树称为代价树。用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价则有：g(x2)=g(x1)+c(x1,x2)基本思想：每次从OPEN表中选择节点往CLOSE表传送时，总是选择其代价最小的节点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置。假如问题有解，代价树的广度优先搜寻确定可以求得解，并且求出的是最优解。w361.把初始节点S0放入OPEN表，令g(S0)=0。2.假如OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不行扩展，则转第2步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针。计算各子节点的代价，并按各节点的代价对OPEN表中的全部节点进行排序(按从小到大的依次)，然后转第2步。w37w38假如使一般搜寻过程满足如下限制，则它就称为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)是从初始节点S0到节点x的最小代价；h*(x)是从节点x到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。w39在A*算法中，g(x)事实上就是从初始节点S0到节点x的路径代价，恒有g(x)g*(x)。而且在算法执行过程中随着更多搜寻信息的获得，g(x)的值呈下降的趋势。例如：H(x)的确定依靠于具体问题领域的启发性信息，其中h(x)h*(x)的限制特别重要，它保证A*算法能找到最优解。w40可纳性对于可解状态空间图(即从初始节点到目标节点有路径存在)来说，假如一个搜寻算法能在有限步那终止，并且能找到最优解，则称该搜寻算法是可纳的。A*算法是可纳的。A*算法的最优性A*算法的搜寻效率在很大程度上取决于h(x)，在满足h(x)h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它携带的启发性信息越多，搜寻时扩展的节点数越少，搜寻的效率越高。h(x)的单调性限制在A*算法中，每当要扩展一个节点时都要先检查其子节点是否已在OPEN表或CLOSE表中，有时还要调整指向父节点的指针，这就增加了搜寻的代价。假如对启发函数h(x)加上单调性限制，就可削减检查及调整的工作量，从而削减搜寻代价。w41所谓单调性限制是指h(x)满足如下两个条件：1、h(Sg)=0;2、设xj是节点xi的随意子节点，则有h(xi)-h(xj)c(xi,xj)，即h(xi)h(xj)+c(xi,xj)其中，Sg是目标节点；c(xi,xj)是节点xi到其子节点xj的代价。可以证明，当A*算法的启发函数h(x)满足单调性限制时，可得到如下两个结论：1、若A*算法选择节点xn进行扩展，则g(xn)=g*(xn)2、由A*算法所扩展的节点序列其f值是非递减的。这两个结论都是在h(x)满足单调性限制时才成立的。否则，它们不确定成立。w425.3.1 与或树的一般搜寻过程5.3.2 与或树的广度优先搜寻5.3.3 与或树的深度优先搜寻5.3.4 与或树的有序搜寻5.3.5 博弈树的启发式搜寻5.3.6 剪枝技术w43完备性对于一类可解的问题和一个搜寻过程，假如运用该搜寻过程确定能求得该类问题的解，则称该搜寻过程为完备的，否则为不完备的。广度优先搜寻、代价树的广度优先搜寻、改进后的有界深度优先搜寻以及A*算法都是完备的搜寻过程，其它搜寻过程都是不完备的。w44一个搜寻过程的搜寻效率不仅取决于过程自身的启发实力，而且还与被解问题的有关属性等多种因素有关。目前虽已有多种定义和计算搜寻效率的方法，但都有确定的局限性。外显率外显率定义为P=L/T其中，L为从初始节点到目标节点的路径长度；T为整个搜寻过程中所生成的节点总数。外显率反映了搜寻过程中从初始节点向目标节点前进时搜寻区域的宽度。当L=T时，P=1，表示搜寻过程中每次只生成一个节点，它恰好是解路径上的节点，搜寻效率最高。P越小表示搜寻时产生的无用节点愈多，搜寻效率愈低。w45有效分枝因数B定义为B+B2+BL=T其中，B是有效分枝因数，它表示在整个搜寻过程中每个有效节点平均生成的子节点数目；L为路径长度；T为节点总数。当B1时，L=T，此时所生成的节点数最少，搜寻效率最高。不难证明，有效分枝因数与外显率之间由如下关系：P=(L(B-1)/(B(BL-1)T=B(BL-1)/(B-1)由此可以看出，当B确定时，L愈大则P愈小；当L确定时，B愈大则P愈小；对同一个L而言，B愈大则T愈大。w4647与与/或树的搜寻策略就是确定节点是否为可解或不行解节点。或树的搜寻策略就是确定节点是否为可解或不行解节点。在整个确定过程中，会循环用到两个过程，分别为：在整个确定过程中，会循环用到两个过程，分别为：可解标示过程：可解标示过程：由可解子节点来确定父节点、祖父节点等为可解节点的回溯由可解子节点来确定父节点、祖父节点等为可解节点的回溯向上过程向上过程不行解标示过程：不行解标示过程：由不行解子节点来确定其父节点、祖父节点等为不行解节点由不行解子节点来确定其父节点、祖父节点等为不行解节点的回溯向上过程的回溯向上过程这两个过程都是自下而上进行的，即由子节点的可解性确定这两个过程都是自下而上进行的，即由子节点的可解性确定父父(或祖先或祖先)节点的可解性节点的可解性5.3.1 5.3.1 与与/或树的搜寻策略或树的搜寻策略48与与/或树的搜寻策略或树的搜寻策略与与与与/或树的一般搜寻过程：或树的一般搜寻过程：或树的一般搜寻过程：或树的一般搜寻过程：1 1 1 1）把原始问题作为初始节点）把原始问题作为初始节点）把原始问题作为初始节点）把原始问题作为初始节点S0S0S0S0，并把它作为当前节点，并把它作为当前节点，并把它作为当前节点，并把它作为当前节点2 2 2 2）应用分解或等价变换算符对当前节点进行扩展。）应用分解或等价变换算符对当前节点进行扩展。）应用分解或等价变换算符对当前节点进行扩展。）应用分解或等价变换算符对当前节点进行扩展。3 3 3 3）为每个子节点设置指向父节点的指针。）为每个子节点设置指向父节点的指针。）为每个子节点设置指向父节点的指针。）为每个子节点设置指向父节点的指针。4 4 4 4）选择合适的子节点作为当前节点，反复执行第）选择合适的子节点作为当前节点，反复执行第）选择合适的子节点作为当前节点，反复执行第）选择合适的子节点作为当前节点，反复执行第2 2 2 2）步和第步和第步和第步和第3 3 3 3）步，在此期间要多次调用可解标示过程和不）步，在此期间要多次调用可解标示过程和不）步，在此期间要多次调用可解标示过程和不）步，在此期间要多次调用可解标示过程和不行解标示过程，直到初始节点被标示为可解节点或不行解标示过程，直到初始节点被标示为可解节点或不行解标示过程，直到初始节点被标示为可解节点或不行解标示过程，直到初始节点被标示为可解节点或不行解节点为止。行解节点为止。行解节点为止。行解节点为止。49与与/或树搜寻的两个特性：或树搜寻的两个特性：(1)(1)假如已确定某个节点是可解节点，则删去其不行假如已确定某个节点是可解节点，则删去其不行解的后裔节点解的后裔节点(2)(2)假如已确定某个节点是不行解节点，删去其全部假如已确定某个节点是不行解节点，删去其全部后裔节点，保留该结点后裔节点，保留该结点505.3.2 5.3.2 与与/或树的宽度优先搜寻或树的宽度优先搜寻搜寻过程：搜寻过程：与状态空间的宽度优先搜寻类似，依据与状态空间的宽度优先搜寻类似，依据“先产生的先产生的节点先扩展节点先扩展”的原则进行搜寻，在整个搜寻过程中多的原则进行搜寻，在整个搜寻过程中多次调用可解标示过程和不行解标示过程。次调用可解标示过程和不行解标示过程。51例设有如图所示的与例设有如图所示的与/或树，节点按图中所标或树，节点按图中所标注的依次号进行扩展。其中标有注的依次号进行扩展。其中标有t1 t1、t2 t2、t3 t3、t4t4的节点均为终止节点，的节点均为终止节点，A A和和B B为不行解的端为不行解的端节点。节点。1 12 23 34 4t1t15 5B BA At2t2t4t4t5t5525.3.3 5.3.3 与与/或树的有界深度优先搜寻或树的有界深度优先搜寻其搜寻过程：其搜寻过程：与与/或树的深度优先搜寻过程和与或树的深度优先搜寻过程和与/或树的或树的宽度优先搜寻过程基本相同，只是将扩展节点宽度优先搜寻过程基本相同，只是将扩展节点的子节点放入的子节点放入OPENOPEN表的首部，并为每个子节表的首部，并为每个子节点配置指向父节点的指针。点配置指向父节点的指针。与与/或树的有界深度优先搜寻同样也规定一或树的有界深度优先搜寻同样也规定一个深度界限，使搜寻在规定的范围内进行个深度界限，使搜寻在规定的范围内进行535.3.4 5.3.4 与与/或树的有序搜寻或树的有序搜寻 与与/或树的有序搜寻可用来求取代价最小的解树，是一种启或树的有序搜寻可用来求取代价最小的解树，是一种启发式搜寻策略发式搜寻策略 1.1.解树的代价解树的代价 可通过计算树中节点的代价得到。可通过计算树中节点的代价得到。设设c(x,y)c(x,y)表示节点表示节点x x到其子节点到其子节点y y的代价，计算节点的代价，计算节点x x代价的方代价的方法如下：法如下：1 1）假如）假如x x是终止节点，则定义节点是终止节点，则定义节点x x的代价的代价h(x)=0;h(x)=0;2 2）假如）假如x x是是“或或”节点，节点，y1,y2,yny1,y2,yn是它的子节点，则节点是它的子节点，则节点x x的代价为的代价为 h(x)=minc(x,yi)+h(yi)1in h(x)=minc(x,yi)+h(yi)1in541.1.解树的代价解树的代价3 3）假如）假如x x是是“与与”节点，则节点节点，则节点x x的代价有两种计算的代价有两种计算方法：和代价法与最大代价法。方法：和代价法与最大代价法。若按和代价法计算，则有：若按和代价法计算，则有：n n h(x)=h(x)=(c(x,yi)+h(yi)(c(x,yi)+h(yi)i=1i=1若按最大代价法计算，则有：若按最大代价法计算，则有：h(x)=maxc(x,yi)+h(yi)h(x)=maxc(x,yi)+h(yi)1in1in4 4）假如）假如x x是不行扩展，且又不是终止节点，则定义是不行扩展，且又不是终止节点，则定义h(x)=h(x)=。55例例 图为一棵与图为一棵与/或树，其中包括两棵解树，一棵解或树，其中包括两棵解树，一棵解树由树由S S0 0，A A，t t1 1和和t t2 2组成；另一棵解树由组成；另一棵解树由S S0 0，B B，D D，G G，t t4 4和和t t5 5组成。在此与组成。在此与/或树中或树中,t,t1 1、t t2 2、t t3 3、t t4 4、t t5 5 为终止节点；为终止节点；E E、F F是端节点，其代价为是端节点，其代价为；边上的；边上的数字是边的代价。数字是边的代价。56S S0 0A At1t1t2t26 65 52 2B BD DG Gt4t4t5t52 22 21 11 12 2S S0 0左边的解树左边的解树右边的解树右边的解树57 1)1)若按和代价计算，右解树是最优解树，其代价为若按和代价计算，右解树是最优解树，其代价为8 8；2)2)若按最大代价计算，右解树仍旧是最优解树，其代价为若按最大代价计算，右解树仍旧是最优解树，其代价为7 7。有时用不同的计算代价方法得到的最优解树不相同。有时用不同的计算代价方法得到的最优解树不相同。S S0 0A At1t1t2t26 65 52 2B BD DG Gt4t4t5t52 22 21 11 12 2S S0 0由左边的解树可得：由左边的解树可得：按和代价：按和代价：h(A)=11,h(Sh(A)=11,h(S0 0)=13)=13 按最大代价：按最大代价：h(A)=6,h(Sh(A)=6,h(S0 0)=8)=8由右边的解树可得：由右边的解树可得：按和代价：按和代价：h(G)=3,h(D)=4,h(B)=6,h(Sh(G)=3,h(D)=4,h(B)=6,h(S0 0)=8)=8按最大代价：按最大代价：h(G)=2,h(D)=3,h(B)=5,h(Sh(G)=2,h(D)=3,h(B)=5,h(S0 0)=7)=7582.2.希望树希望树定义：定义：每次选择欲扩展的节点时希望成为最优解树一部分的节点每次选择欲扩展的节点时希望成为最优解树一部分的节点进行扩展。由这些节点及其先辈节点所构成的与进行扩展。由这些节点及其先辈节点所构成的与/或树或树 ，称为，称为希望树希望树1 1）初始节点）初始节点S0S0在希望树在希望树T T中。中。2 2）假如节点）假如节点x x在希望树在希望树T T中，则确定有：中，则确定有：假如假如x x是具有子节点是具有子节点y1,y2,yny1,y2,yn的的“或或”节点节点,则具有则具有:minc(x,yi)+h(yi)1in minc(x,yi)+h(yi)1in值的那个子节点值的那个子节点yi yi也应在也应在T T中。中。假如假如x x是是“与与”节点，则它的全部子节点都应在节点，则它的全部子节点都应在T T中。中。59博弈问题（或对抗性搜寻）为什么可以用与博弈问题（或对抗性搜寻）为什么可以用与/或图表示呢？或图表示呢？可以这样来看待这个问题：可以这样来看待这个问题：当轮到我方走棋时，只需从若干个可以走的棋中，选当轮到我方走棋时，只需从若干个可以走的棋中，选择一个棋走就可以了。从这个意义上说，若干个可以走的择一个棋走就可以了。从这个意义上说，若干个可以走的棋是棋是“或或”的关系。而对于轮到对方走棋时，对于我方来的关系。而对于轮到对方走棋时，对于我方来说，必需能够应付对手的每一种走棋。这就相当于这些棋说，必需能够应付对手的每一种走棋。这就相当于这些棋与与/或的关系。因此，博弈问题可以看成是一个与或的关系。因此，博弈问题可以看成是一个与/或图，但或图，但是与一般的与是与一般的与/或图并不一样，是一种特殊的与或图并不一样，是一种特殊的与/或图或图5.3.5 5.3.5 博弈树的启发式搜寻博弈树的启发式搜寻60n n1.1.1.1.博弈树的概念博弈树的概念博弈树的概念博弈树的概念:n n 描述博弈过程的与描述博弈过程的与描述博弈过程的与描述博弈过程的与/或树或树或树或树n n博弈树特点：博弈树特点：博弈树特点：博弈树特点：n n1 1 1 1）博弈的初始格局是初始节点）博弈的初始格局是初始节点）博弈的初始格局是初始节点）博弈的初始格局是初始节点n n2 2 2 2）在博弈树中，）在博弈树中，）在博弈树中，）在博弈树中，“或或或或”节点和节点和节点和节点和“与与与与”节点是逐层交节点是逐层交节点是逐层交节点是逐层交替出现的。自己一方扩展的节点之间是替出现的。自己一方扩展的节点之间是替出现的。自己一方扩展的节点之间是替出现的。自己一方扩展的节点之间是“或或或或”关系，关系，关系，关系，对方扩展的节点之间是对方扩展的节点之间是对方扩展的节点之间是对方扩展的节点之间是“与与与与”关系。双方轮番地扩展关系。双方轮番地扩展关系。双方轮番地扩展关系。双方轮番地扩展节点节点节点节点n n3 3 3 3）全部能使自己一方获胜的终局都是本原问题，相）全部能使自己一方获胜的终局都是本原问题，相）全部能使自己一方获胜的终局都是本原问题，相）全部能使自己一方获胜的终局都是本原问题，相应的节点是可解节点，全部使对方获胜的终局都是不应的节点是可解节点，全部使对方获胜的终局都是不应的节点是可解节点，全部使对方获胜的终局都是不应的节点是可解节点，全部使对方获胜的终局都是不行解节点行解节点行解节点行解节点61u在二人博弈过程中，要依据当前以及将要发生的状在二人博弈过程中，要依据当前以及将要发生的状在二人博弈过程中，要依据当前以及将要发生的状在二人博弈过程中，要依据当前以及将要发生的状况进行分析从而做出有利于自己的行动方案，从中选况进行分析从而做出有利于自己的行动方案，从中选况进行分析从而做出有利于自己的行动方案，从中选况进行分析从而做出有利于自己的行动方案，从中选出最优方案。出最优方案。出最优方案。出最优方案。2.2.极大微小分析法极大微小分析法621 1）设博弈的双方中一方为）设博弈的双方中一方为A A，另一方为，另一方为B B。极大微小分析法是为其中的一。极大微小分析法是为其中的一方（例如方（例如A A）找寻一个最优行动方案的方法。）找寻一个最优行动方案的方法。2 2）为了找到当前的最优行动方案，须要对各个方案可能产生的后果进行）为了找到当前的最优行动方案，须要对各个方案可能产生的后果进行比较。具体地说，就是要考虑每一个方案实施后对方可能实行的全部行动，比较。具体地说，就是要考虑每一个方案实施后对方可能实行的全部行动，并计算可能的得分并计算可能的得分3 3）为了计算得分，须要依据问题的特性信息定义一个估价函数，用来估）为了计算得分，须要依据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。4 4）当端节点的估值计算出来后，再推算出父节点的得分。）当端节点的估值计算出来后，再推算出父节点的得分。推算的方法：推算的方法：对对“或或”节点：选其子节点中一个最大的得分作为父节点的得分，这是节点：选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；为了使自己在可供选择的方案中选一个对自己最有利的方案；对对“与与”节点：选其子节点中一个最小的得分作为父节点的得分，这是节点：选其子节点中一个最小的得分作为父节点的得分，这是为了立足最坏的状况。这样计算出的父节点的得分称为倒推值。为了立足最坏的状况。这样计算出的父节点的得分称为倒推值。5 5）假如一个行动方案能获得较大的倒推值，则它就是当前最好的方案。）假如一个行动方案能获得较大的倒推值，则它就是当前最好的方案。2.2.极大微小分析法基本思想极大微小分析法基本思想 63计算博弈树倒推值示例计算博弈树倒推值示例(节点估值已给出节点估值已给出)643.3.剪枝技术剪枝技术q由于在极大微小分析法中，要计算倒推值，效率低。由于在极大微小分析法中，要计算倒推值，效率低。假如可以实现将节点与计算估值及倒推值同时实现，假如可以实现将节点与计算估值及倒推值同时实现，就可以删去一些不必要的节点，从而削减搜寻及计算就可以删去一些不必要的节点，从而削减搜寻及计算的工作量，提高效率，提出了的工作量，提高效率，提出了 剪枝技术剪枝技术q概念：概念：q 通过边生成节点边计算方法，从而剪去某些分枝通过边生成节点边计算方法，从而剪去某些分枝的技术称为的技术称为 剪枝技术剪枝技术q 值：对于一个值：对于一个“与与”节点来说，它取当前子节点节点来说，它取当前子节点中的最小倒推值作为它的倒推值的上界中的最小倒推值作为它的倒推值的上界q 值：对于一个值：对于一个“或或”节点来说，它取当前子节点节点来说，它取当前子节点中的最大倒推值作为它的倒推值的下界中的最大倒推值作为它的倒推值的下界65 剪枝技术的一般规律剪枝技术的一般规律 1 1）任何）任何“或或”节点节点x x的的 值假如不能降低其父节点的值假如不能降低其父节点的 值，则对节点值，则对节点x x以下的分枝可停止搜寻，并使以下的分枝可停止搜寻，并使x x的倒的倒推值为推值为 。这种剪枝称为。这种剪枝称为 剪枝。剪枝。2 2）任何）任何“与与”节点节点x x的的 值假如不能上升其父节点的值假如不能上升其父节点的 值，则对节点值，则对节点x x以下的分枝可停止搜寻，并使以下的分枝可停止搜寻，并使x x的倒的倒推值为推值为 。这种剪枝称为。这种剪枝称为 剪枝。剪枝。22 3 366S22NVGMDFILFUQT9 31-1-13 68-1203-57 4-2 6-1 8-7-1 032值值 21-1值值 22值值 2 66 0 00 -50 67S2NVGMDFILUQT9 31-16803-568245-36213221253798LEBMNPFSACGHIIDJK41作业：如图的博弈树，已经给出相应节点的估值（1）请计算各节点倒推值（2）应用 剪枝技术剪枝技术剪去不必要的分枝。