第4章与或图搜索

第四章与或图搜索1问题归约法2与或图3与或图搜索4AO*算法5博弈树的搜索问题:在边长为2的正方形内，任意放置5个点，求证其中必存在两个点，它们之间的距离不大于2。问题可转化为：在四个单位正方形内，任意放置5个点，至少有两个点在同一正方形内。1问题归约法问题:假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积。方法分析:五边形的面积转化为矩形面积。IIIII①②③123I求解步骤：求五边形面积求1面积求2面积求3面积求I面积求II面积求III面积求①面积求②面积求③面积123IIIIII①②③问题归约法:当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为~.本原问题:可直接解答的问题称为~，它是不必证明的、自然成立的.归约法的组成：1）一个初始问题的描述；2）一组把问题变成子问题的算子(分解或转换)；3）

一组本原问题的描述不同的算子对应不同的关系,从而使问题归约的描述可用一个与或图的结构来表示.小结:

2与或图与节点：把单个问题分解为几个子问题来求解。只有当所有子问题都有解，该父辈节点才有解。表示一种“与”关系。或节点：同一问题被转换为几种不同的后继问题。只要有一个后继问题有解，则原问题有解。表示一种“或”关系。与节点由与运算连接（超弧），如图（a）.或节点由或运算连接，如图（b）.定义：与或图就是包含与节点和或节点的图，即存在超弧的图，也称为超图.超图与状态空间图有什么区别？与或图是一种更一般的图.定义：一超弧所相关的边数（K）被称为该超弧的度，实现的连接称为K-连接.K—连接符：从一个父节点指向一组含有K个后继节点的节点集.在与或图中，节点n0有两个连接符：1-连接符指向节点n1；2-连接符指向节点集合{n4、n5}；对于节点n0来讲，n1可称为或节点，n4、n5可称为与节点。

与或图

3与或图搜索含义：在与或图上执行搜索的过程，其目的在于标明起始节点是有解的，即，搜索不是去寻找到目标节点的一条路径，而是寻找一个解图。定义：一个节点被称为能解节点，其递归定义为：1．终节点是能解节点（直接与本原问题相关联）；2．若非终节点有“或”子节点时，当且仅当其子节点至少有一个能解，该非终节点才能解；3．若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才能解。定义：不能解节点的递归定义为:

1．没有后裔的非终节点是不能解的节点；2．若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不能解；3．若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不能解.是由能解节点构成的一个子图，是包含一节点（n）到目的(终)节点集合（N）的、连通的能解节点的子图.在一个与或图G中，从节点n到节点集N的解图记为G，G是G的子图.1．若n是N的一个元素，则G由单个节点n组成；2．若n有一个指向节点集{n1…,nk}的外向连接符K，使得从每一个节点ni到N有一个解图(i=1,…,k)，则G由节点n，连接符K，以及{n1,…,nk}中的每一个节点到N的解图所组成；3．否则n到N不存在解图.如果n=s为初始节点，则解图为所求解问题的解图.解图的定义：若解图的耗散值记为k(n,N)，则可递归计算如下：若n是N的一个元素，则k(n,N)=0；若n有一个外向连接符指向其后继节点集合{n1…,ni}，并设该连接符的耗散值为Cn（一般k-连接符的耗散值=k），则

k(n,N)=Cn+k(n1,N)+…+k(ni,N)具有最小耗散值的解图称为最佳解图，其值也用h*(n)标记。解图耗散值的计算：例：从节点n开始，正确选择一个外向连接符，一直进行下去直到产生的每一个后继节点成为集合N中的一个元素为止。下图给出了n0→{n7，n8}的三个解图（耗散值分别为8，7，5）.解图的求法与或图搜索与状态空间图搜索的区别：搜索目的不同：是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索过程是能否找到可解的叶节点.结果不同：若初始节点被标示为可解，则搜索成功结束；若初始节点被标示为不可解，则搜索失败.节点处理不同：一旦发现不可解节点，应把该节点从图中删去.4与或图启发式搜索算法AO*假设：G；G；h(n)是从节点n到一组终叶节点的一个最优解图的一个代价估计，评价函数q(n)=h(n)AO*过程:1.建立初始搜索图，G:=s，计算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；2.Untils已标记为SOLVED,do:3.Begin4.G:=FIND(G)；根据连接符标记（指针）找出一个待扩展的侯选局部解图G（连接符在11步标记）5.n:=G中的任一非终节点;选一个当前节点6.EXPAND(n),生成子节点集{ni}，如果ni

G，G:=ADD({ni},G),计算q(ni)=h(ni)，IFGOAL(ni)THENM(ni,SOLVED);7S:={n};建立含n的节点集合S.（已扩展待修正）8UntilS为空,do:9Begin(m为S中任一节点)10REMOVE(m,S),当mc{S};（m→mc,从底层开始修正）11修改m的耗散值q(m):对m指向节点集(n1i，n2i,…nki)的每一个连接符i分别计算qi,qi(m)=Ci+q(n1i)+…+q(nki),并取q(m):=minqi(m);

加(或修正)指针到minqi(m)的连接符上.IFM(nji,SOLVED)THENM(m,SOLVED);（j=1，2，…，k）若该连接符的所有子节点都是能解的,则m也能解.12IFM(m,SOLVED)(q(m)q0(m))THENADD(ma,S);m能解或修正的耗散值与原先估算q0不同,则把m的所有先辈节点ma添加到S中.（能解或修正向上传递）13end(与8匹配)14

end(与2匹配)两个过程的重复:自上而下的图生长过程（4-6步）:先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终节点进行扩展，并对其后继节点赋估计耗散值和加能解标记.自下而上的估价函数值的修正、连接符的标记和SOLVED的标注过程(7-12):耗散值的修正从刚被扩展的节点n开始，其修正耗散值q(n)取所有估计值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值.只有下层节点耗散值修正后，才可能影响到上一层节点的耗散值，如此一直修正到初始节点.AO*搜索算法过程分析例:各节点启发值如图，k-连接符的耗散值=k,求最佳解图.

应用AO*算法，经四个循环，可找到解图.

在第一次循环扩展节点n0；然后,依次扩展节点n1、n5、n4。在节点n4被扩展之后，节点n0便被标注SOLVED，此时，通过向下跟踪有标记的连接符，便获得了解图.

主要步骤第4步(G’)第5步(n)第6步第7步(S)第11步第12步AO*搜索算法的过程第1循环(n0)(n0)(n1,n5,n4)(n0)比较,选n0→n1;n1不可解;无第2循环n0→n1(n1)(n2,n3)(n1)1)比较,选n1→n3;n3不可解;2)比较,改n0→n5,n4;n5,n4不可解;n0不可解,值变;1)加n0→S;2)无前辈;第3循环n0→n5,n4(n5)(n6,n7,n8)(n5)1)比较,选n5→n7,n8;n7,n8可解,n5可解;2)n0不可解,值变;1)加n0→S;2)无;第4循环n0→n5,n4;(n4)(n5,n8)(n4)1)比较,选n4→n8;n8可解,n4可解;2)n4,n5可解;n0可解,值不变;1)加n0→S;2)无;n0n1n4n52113446542002×5n6n3n2n7n8★★★★★不带括号的数是启发函数h(n)值,带括号数是估价函数q（n）的修正值；短箭头用来标记连接符，标明侯选局部解图；已经标注SOLVED的节点用黑心圆来表示。

讨论当节点n无后继节点?在第11步中对m(n)赋一个高的q值(会传递到s),从而排除了含有n的子图被当作候选局部解图的可能性.在G’中存在多个非终节点时,选择什么样的节点先扩展?一般选择最能导致该局部解图耗散值发生较大变化的节点先进行扩展,可促使及时修改局部解图的标记.同A算法类似,若s→N存在解图,当h(n)≤h*(n)且h(n)满足单调限制条件时(对n到其子节点的每一连接符均需要满足),则AO*一定能找到最佳解图.与A*算法的区别评价函数只考虑h(n):

理由:算法有自下而上的修正费用的的操作,实际上局部解图费用值的估计是在起始节点S比较,计算g既无必要也不可能.不能优先扩展具有最小费用的节点:理由:K-连接符连接的有关子节点对父节点的可解性及费用值的估计都会产生影响.仅适用于无环图,否则耗散值递归计算不收敛:方法:当新生成的节点已在图中时,判断是否为正被扩展节点的先辈节点.控制策略不同:没有OPEN表和CLOSED表,只用生成的解图结构G,h(n)是最佳解图的费用估计.

5博弈树的搜索问题:二人完备博弈：1．由二人对垒，轮流走步，自己的走步自己选择2．信息完备:任何一方都完全知道对方过去的走步情况和今后可能的走步，不包括碰运气的情况表示方法:利用与或图表示来描述博弈问题.理由:由于在博弈中,决定自己走步时只需考虑对自己有利的一步——或，而考察对方时，则应考虑对方所有可能的走步——与.求解方法:特殊的与或图搜索算法——博弈树搜索.理由:由于两人严格地轮流走步，使博弈状态图呈现出严格的与或图的交替层次.1)Grundy博弈

例：假设桌上放有一堆（7个）钱币，由两人轮流进行分堆，要求每人每次只把其中某堆钱币分成数目不相等的两小堆，最后不能分下去的人被判负.综合数据库：（x1，x2，…，xn，M）表示某个选手走步的状态.其中,x1，x2，…，xn表示n堆钱币不同的个数，M代表选手(MIN或MAX).规则：控制策略:博弈双方总是偏向最有利于自己的状态前进，己方会尽力将赢的几率最大化,而使对手方偏离取胜目标.(5,1,1,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(3,2,2,MIN)(4,2,1,MIN)(7,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,1,1,1,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)ABC搜索策略分析（以MAX方的角度）对MAX节点(MIN控制)，MAX必须都能够获胜，即MAX必须考虑应付MIN的所有招法，故它为与节点.对MIN节点(MAX控制)，MAX只需证明有一步能走赢就可以，即MAX只要考虑有一步棋使MIN无法招架就成，故它为或节点.因此,对弈过程的搜索图就呈现出与或图表示的形式，从图可见，MAX方存在完全取胜的策略.于是,寻找MAX方取胜的策略便和求与或图的解图(能解→能胜)一致起来，即MAX要获胜，在各层必须对所有与节点取胜，但只需对一个或节点取胜.2)博弈树的极大极小搜索法思想：预先考虑双方对弈若干步之后的局势，从当前侯选的走步中选一个相对好的走步来走，即在有限搜索深度范围内进行求解.方法：定义一个评价函数f，以便对棋局的势态（节点）作出优劣估值.一般规定:有利于MAX(我)的势态，f(n)取正值;有利于MIN(敌)的势态，f(n)取负值;势均力敌，f(n):=0.若f(n):=，表示MAX方获胜;若f(n):=-，表示MIN方获胜.选步的过程:假定开始由MAX选择走一步棋，如何选择一步好棋？首先，对给定的格局MAX给出可能的走法，接着,MIN对MAX的每一步走法，又给出可能的走法，这样进行若干次（规定深度），得到一组端节点.此时,计算每个端节点相应的静态函数值;然后由底向上逐级计算倒推估值，在MIN处(与节点)取其下层估值中最小者，在MAX处(或节点)取其下层估值最大者。一直到MAX的开始棋局，取其下层估值中最大的格局作为要走的第一步.当用端节点的静态估计函数值求倒推值时，针对两位选手的控制力应采用不同的策略，从下往上逐层交替使用极大和极小的选值方法，故称为极大极小过程.ＡＢＣＳＤＥＦＧＨＩＪ9-600-2-4-3-6-2-4-2MAX取极大值MIN取极小值端节点例.向前看两步时f(n)的求值过程极大极小过程MIN-MAX：1.T:=(s,MAX)，OPEN:=(s)，CLOSED:=();开始时树由初始节点构成，OPEN表只含有s.2.LOOP1:IFOPEN=()THENGOLOOP2;3.n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);将n放到CLOSED表的前面，使第5步操作时深度大的节点优先被取出.(OPEN表先进先出,CLOSED表后进先出)4.IFn可直接判定为赢,输或平局THENf(n):=-0，GOLOOP1ELSEEXPAND(n){ni}，ADD({ni}，T)IFd{ni}kTHENADD({ni},OPEN),GOLOOP1ELSE计算f(ni)GOLOOP1;ni达到深度k,计算端节点f值.5.LOOP2：IFCLOSED=NIL,THENGOLOOP3ELSEnd=FIRST(CLOSED);6.IF(nd

MAX)(f(nciMIN)有值)THENf(nd):=max{f(nci)},REMOVE(nd，CLOSED);若MAX所有子节点均有值,则该MAX取其极大值.ELSEIF(nd

MIN)(f(nciMAX)有值)THENf(nd):=min{f(nci)},REMOVE(nd，CLOSED);若MIN所有子节点均有值，则该MIN取其极小值.7.GOLOOP2;8.LOOP3:IFf(s)≠NILTHENEXIT(ENDM(Move,T));s有值,或则结束或标记走步.例：在九宫格棋盘上，甲乙（MAX和MIN）二人轮流在空格中放入自己的棋子（一次一枚），谁先使自己的三子成一线就获胜，设甲先走用（）表示，乙用（）表示，p表示某种格局，f(p)表示对格局的评价值。赢线定义:将棋盘的整行、整列或整条对角线称为赢线。如,一条赢线上只有（或）方的棋子或为空，而没有对方的棋子，那么这条赢线就称为（或）方的赢线。f(p)定义：1）MAX胜，f(p)=+

2）MIN胜，f(p)=-

3）若p不是可定胜负的格局，则f(p)=fMAX(p)-fMIN(p)考虑走两步的搜索过程,并兼顾棋盘对称性条件第一次调用算法产生的搜索树如下图所示，图中端节点下面是计算的f(p)值，非端节点的倒推值标记在圆圈内.结论:第1步的最好走法是把棋子下到中央位置.(为了使初始节点具有最大的倒推值)fMAX(p)=4fMIN(p)=6f(p)=4-6=-2一字棋第1阶段的搜索树√√√√√√√√√√√√√√√√

一字棋第2阶段的搜索树

√√一字棋第3阶段的搜索树

3)-搜索过程极大极小搜索缺陷:把生成树和棋局估值两个过程完全分离，即先生成全部的搜索树，然后再进行端节点估值和倒推值计算，这导致效率降低.例:一个MIN节点要全部生成A、B、C、D节点，然后逐个计算其静态估值，最后在求倒推值阶段，才赋给这个MIN节点的倒推值-.如何改进?改进思路:若两个过程同时进行，再依一定的条件判断，有可能尽早剪掉一些无用的分支，那么就可能减少搜索量，这是-搜索的思想.例：生成节点A后，马上进行静态估值，得知f（A）=-后，便可断定再生成其余节点并进行估值计算是多余的，故可马上对MIN节点赋倒推值-，不会影响MAX的最好优先走步的选择.实现方法:采用有界深度优先策略进行搜索，这样当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值.一字棋第1阶段-剪枝方法1-6→f(1)=-1→初始S,f(S)>=-1,此时该MAX层下界值=-1;7-8→f(7)<=-1,此时该MIN层上界值

=-1≥,节点7的其他子节点不必再生成，因S的极大值不可能比这个值还小，再生成是多余的，故可剪枝.在搜索过程中,通过记录并比较倒推值的上、下界并进行比较，就可以实现修剪操作，这种技术统称为-剪枝技术.在实际修剪中，、的值可以随时修正，但满足如下条件：极大值层的倒推值下界值永不下降，实际的倒推值取其后继节点最终确定的倒推值中最大的一个倒推值.极小值层的倒推值上界值永不上升，其倒推值取其后继节点最终确定的倒推值中最小的一个倒推值.在一个分支上进行-剪枝的判断规则：剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值，即（先辈层）≥（后继层），则可终止该MIN层中这个MIN节点以下的搜索，并设置这个MIN节点的最终的倒推值为.(位置：MIN层的剪枝)剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即（后继层）≥（先辈层），则可终止该MAX层中这个MAX节点以下的搜索，并设置这个MAX节点的最终倒推值为.(位置：MAX层的剪枝)-过程：保存和值，且满足条件时便进行剪枝，当初始节点的全部后继节点的最终倒推值都给出时，过程即结束，而最好的优先走步就是走向具有最高倒推值的那个后继节点.比较是在极大值层节点和极小值层节点间进行的(非直系).比较时是与先辈层节点(已经有了值的那些节点),不仅限于父辈.只有一个节点的值固定以后,其值才能够向其父节点传递.-剪枝搜索得到的最佳走步与极大极小方法得到的结果一致,但效率会提高.生成搜索图和剪枝过程同时进行.注意几个问题:⑴0≤0(2)(3)5(4)=0(