第三章与或图搜索..ppt

《第三章与或图搜索..ppt》由会员分享，可在线阅读，更多相关《第三章与或图搜索..ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章与或图搜索问题-问题归约法3.0 引言l归约(Reduction)例1 问题1：现有煤气灶、水龙头、水壶和火柴，你怎样烧水？答：向水壶中注满水，把水壶放在煤气灶上，擦火柴点燃煤气灶。问题2：问题1中其他情况不变，只是水壶中已经灌满了水，你怎样烧水？答：把水壶放在煤气灶上，擦火柴点燃煤气灶或擦火柴点燃煤气灶，把水壶放在煤气灶上。例2 在边长为2的正方形内，任意放置5个点，求证其中必存在两个点，它们之间的距离不大于2。.问题可转化为：.在四个单位正方形内，.任意放置5个点，至少.有两个点在同一正方形内。IIIII123I例3假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积。求解步骤

2、：求五边形面积求 1面积求 2面积求 3面积求 I面积求 II面积求 III面积求面积求面积求面积123IIIIIIl本原问题可直接得到答案的问题称为本原问题l例1中的原始的烧水问题l例2中根据鸽巢原理直接可回答的问题l例3中求矩形面积的问题l归约法把原问题转化(分解)为一个或几个子问题，对子问题再归约，直至成为可以直接求解的本原问题。3.1问题空间及与或图表示l梵塔难题的两种解法状态空间法l初始数据库 (1 1 1)表示C,B,A三个盘都在柱1上l目标数据库 (3 3 3)表示C,B,A三个盘都在柱3上123 A B Cl状态空间其中(i j k)表示C在柱i,B在柱j,A在柱k上(1 1

3、1)(1 1 3)(1 2 3)(1 1 2)(1 2 1)(1 2 2)(3 2 2)(1 3 1)(1 3 2)(3 2 1)(3 2 3)(1 3 3)(2 3 3)(2 3 2)(2 3 1)(3 1 3)(3 3 1)(3 3 3)(3 3 2)(3 1 2)(3 1 1)(2 1 2)(2 1 1)(2 1 3)(2 2 3)(2 2 1)(2 2 2)StMOVE(A,1,3)MOVE(B,1,2)MOVE(A,3,2)MOVE(C,1,3)MOVE(A,2,1)MOVE(B,2,3)MOVE(A,1,3)l采用归约法要把所有圆盘移至柱3，必须先把C盘移至柱3，而在移动C盘至柱3

4、前，柱3必须为空。只有把A、B移至柱2后，才能将C移到柱3。在C移至柱3后，再解决将A、B移至柱3。l将上面的分析理一下顺序：就把原问题归约为3个子问题：移动A、B至柱2的双圆盘问题；移动C至柱3的单元盘问题；（本原问题）移动A、B至柱3的双圆盘问题。将梵塔问题归约为本原问题的问题空间(1 1 1)(3 3 3)(1 1 1)(1 2 2)(1 2 2)(3 2 2)(3 2 2)(3 3 3)(1 2 3)(1 2 2)(1 1 1)(1 1 3)(1 1 3)(1 2 3)(3 3 1)(3 3 3)(3 2 2)(3 2 1)(3 2 1)(3 3 1)l小结状态空间法与问题归约法的比较

5、l状态空间问题空间l操作归约l求解路径本原问题归约就是化简，即把复杂问题分解为若干子问题，且使得：l每个子问题比原问题好解；l这些子问题解决了，原问题就解决了。归约法的分类l有序归约(分段归约)梵塔难题l无序归约(分解归约)求五边形的面积l与或图表示法与扩展l将一个问题分解为若干子问题，所有的子问题有解，原问题才有解。lK-联接符或扩展l将一个问题转化为若干子问题，只要一个子问题有解，原问题就有解。l单线联接符AP1P2PkP1P2Pknon1n2n4n3n5n6n7n8与或图与或图搜索l从代表原始问题的根节点开始，按一定的规则(归约操作)进行与或扩展，直到代表本原问题的终节点。l要选择适当的

6、或分枝进行扩展，以求找到一个最佳分解方案。l在与或图中搜索最佳分解方案，即在问题空间搜索一个最佳解图。若干概念l终节点 可解节点 不可解节点 解图 耗散值 最佳解图 可解过程 不可解过程 与或图中某一个节点n到节点集N的一个解图类似于普通图中的一条解路径。l解图的求法：从节点n开始，正确选择一个外向连接符，在从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止non1n0n4n3n5non7n8三个解图n5n7n8n0n4n5n7n8（1）（2）（3）l K-连接连接表示从父节点到子节点间的连接 *也称为父节点的外向连接，

7、*以园弧指示同父子节点间的“与”关系，*K为这些子节点的个数，K1时成为超连接，*一个父节点可以有多个外向的K-连接。*当所有超连接的K都等于1时，与或图蜕化为一般图。l 根、叶、终节点根、叶、终节点 *无父节点的节点根节点，用于指示问题的初始状态；*无子节点的节点叶节点。*用于联合表示目标状态的节点终节点，*终节点必定是叶节点，反之不然；l 解图的生成解图的生成自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止。*解图纯粹是一种“与”图；*由于与或图中存在“或”关系；可产生或搜索到多个解图（上图），*解图应无环，即任何节点

8、的外向连接均不得指向自己或自己的先辈，否则会使搜索陷入死循环。l解图在与或图是无环的假定条件下，解图解图在与或图是无环的假定条件下，解图可递归定义如下：可递归定义如下：定义：一个与或图中，从节点定义：一个与或图中，从节点n到节点集的解到节点集的解图记为图记为，是的子图是的子图 若若n是是N的一个元素的一个元素,则则G由单一节点组成由单一节点组成;若若n有一个指向节点有一个指向节点n1,n2,nk的外向连接的外向连接符符K,使得从每一个使得从每一个ni到到N有一个解图有一个解图(i=1,2,k),则则G由节点由节点n,连接符连接符K,及及n1,n2,nk中的每一个中的每一个节点到节点到N的解图所

9、组成的解图所组成;否则否则n到到N不存在解图不存在解图.l同样可以递归定义局部图如下：同样可以递归定义局部图如下：单一节点是局部图单一节点是局部图 对于一个局部图的任意叶节点对于一个局部图的任意叶节点n，选择一个，选择一个n的外向连接符的外向连接符K，则该局部图、外向连接符，则该局部图、外向连接符K以及以及K所连接的后继节点一起组成图，仍然组成一个局所连接的后继节点一起组成图，仍然组成一个局部图部图l解图的耗散值：K(n,N)表示从节点n到终节点集合N的解图的耗散值,则可递归计算如下若nN,则 K(n,N)=0;若n是一个外向连接符指向后继节点n1,n2,nk,并设该联接符的耗散值Cn.则 K

10、(n,N)=cn+k(n1,N)+k(n2,N)+k(nk+N)n0n4n7n8n512223N=n7,n8 K(n0,N)=cn0+k(n4,N)+k(n5,N)=cn0+cn5+k(n7,n7)+k(n8,n8)+cn4+k(n5,N)=cn0+cn5+k(n7,n7)+k(n8,n8)+cn4+cn5+k(n7,n7)+k(n8,n8)=2+2+0+0+1+2+0+0=7在假设K连接符的耗散值为K的情况下non1n0n4n3n5n6n7n8三个解图耗散值n5n7n8n0n4n5n7n8（1）（2）（3）具有最小耗散值的解图称为最佳解图,其值也用h*(n)标记N=n7,n8 K(n0,N)

11、=8K(n0,N)=7K(n0,N)=5l同样,也可以计算一个局部图的耗散值：如果同样将局部图的耗散值记为K(n,N),则有若n是局部图的一个叶节点,则K(n,N)=h(n);否则 K(n,N)=cn+k(n1,N)+k(n2,N)+k(ni+N)其中n1,n2,nk 是n的与扩展子节点,Cn是该联接符的耗散值,h(n)表示节点n到目标节点集的最佳解图耗散值的估计.n0n4n5123N=n5 K(n0,N)=0+2+1=3在假设K连接符的耗散值为K的情况下搜索过程还要标记能解节点和不能解加点搜索过程还要标记能解节点和不能解加点,为此给出如下定义为此给出如下定义:l能解节点能解节点(SOLVED

12、)1.终节点是能解节点终节点是能解节点;2.若非终节点有若非终节点有”或或”子节点时子节点时,当且仅当其当且仅当其子节点至少有一能解子节点至少有一能解,该非终节点才能解该非终节点才能解;3.若非终节点有若非终节点有”与与”子节点时子节点时,当且仅当其当且仅当其子节点均能解时子节点均能解时,该非终节点才能解该非终节点才能解不能解节点不能解节点(UNSOLVED)1.没有后裔的非终节点是不能解节点没有后裔的非终节点是不能解节点;2.若非终节点有若非终节点有”或或”子节点时子节点时,当且仅当所当且仅当所有子节点均不能解时有子节点均不能解时,该非终节点才不能该非终节点才不能解解;3.若非终节点有若非终

13、节点有”与与”子节点时子节点时,当至少有一当至少有一子节点不能解时子节点不能解时,该非终节点才不能解该非终节点才不能解l采用问题归约法的问题表示一个初始问题的描述一套把问题变换为子问题的算符或归约操作一套本原问题的描述l问题归约法举例求证:一个角的平分线上的点与该角的两边距离相等.已知:DBA=DBCABAAD,BCCDDB为一线段 D BAD为一三角形 B C BCD为一三角形试证:AD=CD问题表示:用S|T来描述一个证明问题,其中S为要证明 的论点,T为前提,于是上述问题可表示为:AD=CD DBA=DBC,BAAD,BCCD,DB,BAD,BCD 本原问题:P1:X1=X2|X1=90

14、,X2=90P2:X1X2=X1X2P3:X1=X1 P4:X1X2X3 Y1Y2Y3 X3X1=Y3Y1,X3X1X2=Y3Y1Y2,X1X2X3=Y1Y2Y3P5:X1X2X3=90|X1X2 X2X3P6:X2X3=Y2Y3|X1X2X3 Y1Y2Y3 归约操作:(1)用P1P6的左边与要证的问题的左边相匹配(2)对相匹配的,将其右边与要证问题的右边的条件相比较:(a)若条件已存在,则为本原问题,该问题可解.(b)如缺少条件,则将该条件作为要证的子问题,原问 题的条件仍为新的子问题的条件,继续归约.(3)如对一个问题同时有几条本原问题描述可以匹配,则可以采用不同的归约操作(分解方法),亦

15、即对该问题节点进行或扩展.例如:我们要证明的问题的左边是AD=CD,与之匹配的只有P6:X2X3=Y2Y3|X1X2X3 Y1Y2Y3 注意,要和原问题中已指定的实体匹配,必须有 X2=A,X3=D,Y2=C,Y3=D因此P6的右边只能匹配为 X1AD Y1CD,而在T中指定的三角形只有 BAD和 BCD,故P6匹配为:AD=CD|BAD BCD右边就是原始问题归约成的要证明的子问题即 BAD BCD|T类似地,用P4来匹配这一子问题,得到能证明该子问题的三个前提:DB=DB,DBA=DBC,BAD=BCD注意到 DBA=DBCT,所以要证的子问题为:DB=DB|T,BAD=BCD|T继续这一

16、过程,就可以得到下面的解图.AD=CD DBA=DBC,BAAD,BCCD,DB,BAD,BCD BAD BCD DBA=DBC,BAAD,BCCD,DB,BAD,BCDDB=DB|TBAD=BCD|TBAD=90|BAAD,.BCD=90|BCCD,.P6P4P1P5P5P2DBA=DBCnon1n2n3n4n5n6n8n73.2 启发式与或图搜索法l估价函数h设h*(n)是从搜索图中一个节点n到一个终节点集合N的一个解图的实际耗散值,h(n)是对h*(n)的估计.若在n的一个解图中,n有k个与后继节点n1,nk,且 h(n)C(n)+h(n1)+h(nk)其中,C(n)为k连接符的(总)耗

17、散值,又若n为终节点,则h(n)=0,则我们称h(n)满足单调限制.可证,对于所有节点有h(n)h*(n),即h是h*的下界.举例说明n0n1n3n6n7n5n80241020设每条弧的耗散值为1 h(n7)=h*(n7)=0 h(n8)=h*(n8)=0 h(n6)=2,C(n6)+h(n7)+h(n8)=2=h*(n6)h(n5)=1,C(n5)+h(n7)+h(n8)=2+0+0=2=h*(n5)h(n3)=4,C(n3)+h(n6)+h(n5)=2+2+1=5h*(n3)=6 h(n1)=2,C(n1)+h(n3)=1+4=5h*(n1)=7 h(n0)=0,C(n0)+h(n1)=1

18、+2=3h*(n0)=8lAO*算法若h(n)满足单调限制,则下面的与或图搜索算法称为AO*算法(1)建立一个搜索图G,使其仅包含起始节点S,对应 于节点S的费用为q(S)=h(S),如S为终节点,则标 记S为SOLVED(2)until S已标记为SOLVED do(3)begin(4)通过跟踪G中从S出发的有标记的连接符,计算 G中的一个局部解图G(5)选择G的任一未标记为SOLVED的叶节点n(6)扩展节点n,生成它的全部后继节点加入G中.对 于未曾在G中出现过的每一个后继节点nj,相应的 费用q(nj)=h(nj).对其中的终节点,标记SOLVED,相应的q值为0(7)建立一个只包含节

19、点n的集合M(8)until M为空 do(9)begin(10)从M中移出后裔不在M中的节点m(即自下而上)(11)根据以下步骤修改节点m的费用q(m):若m有j个或分枝,对于m的每个或分枝 i 的与 后继节点集n1i,n ki,计算 qi(m)=Ci(m)+q(n1i)+q(nki)1 i j 令 q(m)=min(qi(m)1 i j 并对这个具有最小值的分枝连接符加以标记,如 果以前标记在其他分枝连接符上,则删除以前的 标记;如果该连接符的全部后继节点都已标记 为SOLVED,则标记m为SOLVED(12)如果m已标记为SOLVED,或q(m)不同于以前计 算的费用,则把通过有标记连接

20、符连到m上的所 有祖先节点都添加到M中去(13)end(9)(14)end(3)算法应用实例如下4n0n1n3n6n7n2n4n8n502020141 n M m q(m)I n0 n0 n0 0 3II n1 n1 n1 2 5 n0 n0 3 4III n5 n5 n5 1 2 n0 n0 4 5IV n4 n4 n4 1 1 n0 n0 5 5n1n3n7n2n4n8n5n0n0n1n0n5n0n4n7n4n8n5n02110 3440045GG52n62lAO*算法的基本思想自上而下的图生长运算(第4至6步):通过跟踪有标记的连接符,寻找最好的局部解图,并扩展其非终叶节点自下而上的费用

21、修正,连接符标记,SOLVED标记的过程(第7至12步):从刚被扩展的节点开始,利用其后继节点最新计算的费用重新计算其费用值,并把外向连接符标记到所估计的最佳路径上.在图中这个费用计算是向上传递的.当一个连接符的全部后继节点都已标记为SOLVED,SOLVED标记也向上传递.(把祖先节点加入M)l讨论节点n无后继节点,则可在第11步中对m赋一个高的q值,这个高的q值会依次传递到s,使得含有n节点的子图具有高的q(s)，从而排除了被当作候选局部解图的可能性?在G中选择什么样的节点先扩展?一般可以选择一个最能导致该局部解图耗散值发生较大变化的那个节点先进行扩展,因为选择这个节点先扩展,会促使及时修

22、改局部解图的标记.同A算法类似,若sN存在解图,当h(n)h*(n)且h(n)满足单调限制条件时,则AO*一定能找到最佳解图.当h(n)0时,AO*也蜕化为宽度优先算法.这里单调限制条件是指:对隐含图中,从节点sn1,n2,.nk 的每一个连接符都施加限制,即假定h(n)C+h(n1)+h(h2)+h(nk)其中C是连接符的耗散值.如果h(n)满足单调限制,且h(ti)=0(tiN)那么单调限制意味着h是h*的下界范围，即对所有节点n有h(n)h*(n)l讨论与A*算法比较l估价函数只考虑h(n),因为算法有自下而上的修正费用的的操作,实际上局部解图费用值的估计是在起始节点S比较,计算g既无必

23、要也不可能.lK-连接符对父节点的可解性及费用值的估计都产生影响,因而不能象A*算法那样优先扩展具有最小费用的节点.l没有OPEN表和CLOSED表,增加了局部解图G,h(n)是最佳解图的费用估计,而不是最佳路径的估计.3.3 博弈树搜索l博弈与博弈图博弈:两棋手按一定规则轮流走步,双方都知道对方的走步,当满足一定条件时,走步结束,这时,或一方取胜,或为和局.博弈的特点:双人对弈,一人一步，信息完备,零合Grundy博弈Grundy博弈:两人面前放一堆硬币,一人先把其分为不相等的两堆,另一人把已分的任一堆再分成不相等的两堆,这样轮流分下去,直到每堆只剩下一枚或两枚硬币为止,最后一位分硬币者取胜

24、.Grundy博弈的博弈图(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)分析:博弈图中MAX取胜的路线有点像与或图的一个解图.由MIN走的那些节点的后继节点和与节点相像,即MAX取胜的一个解必须是能从所有这些后继节点中取胜;而MAX的后继节点则和或节点相似,即MAX只要从这些后继节点中的一个取胜即可.l极大极小搜索法 极

25、大极小搜索方法是博弈树搜索的基本方法,现在博弈树搜索中最常用的剪枝搜索方法,就是从这一方法发展而来的.一字棋的棋局总数9!=362,880 国际象棋与围棋 解决办法:向前看几步极大极小搜索法l思想:对每个节点p计算其估价函数值f(p),该值越大,说明p所对应的棋局对我方越有利.在轮到我方走时,选择f(p)大的节点走;而论到对方走时,应考虑对方会选f(p)最小的节点走.因此,在博弈图搜索时,可采用一步走f(p)值极大的节点(我方走),一步走f(p)值极小的节点(对方走),这样交替前进的方法.这种搜索法称为极大极小搜索法.l估价函数是静态的，可根据势态优劣特征来定义（主要用于对端点的“价值”进行度

26、量）下面是一个表示考虑两步棋的例子图中端节点给出的数字是用静态的计算得到的其它节点不用估计，而是采用倒推的办法取值l过程MINIMAX T:=(s,MAX),OPEN:=(s),CLOSED:=();开始时树由初始节点构成,OPEN表只含有sLOOP1:IF OPEN=()THEN GO LOOP2;N:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,COLSED);9-600-2-4-3-6-2-4-2MAX取极大值MIN取极小值IF n可直接判定为赢输或平局 THEN f(n):=-0,GOTO LOOP1 ELSE EXPAND(n)ni,ADD(ni,T)IF d(

27、ni)k THEN ADD(ni,OPEN),GOTO LOOP1 ELSE计算 f(ni),GOTO LOOP1;ni到达深度K,计算各端节点f值LOOP2:IF CLOSED=NIL THEN GO LOOP3ELSE np:=FIRST(CLOSED);IF(npMAX)(f(nci)MIN)有值)THEN f(np):=maxf(nci),REMOVE(np,CLOSED);若MAX所有子节点均有值,则该MAX取其极大值.IF(npMIN)(f(ncj)MAX)有值)THEN f(np):=minf(ncj),REMOVE(np,CLOSED);若MIN所有子节点均有值,则该MIN取其

28、极小值.GOTO LOOP2LOOP3:IF f(s)NIL THEN EXIT(ENDM(Move,T);s有值,则结束或标记走步.l极大极小搜索法举例:一字棋在博弈树中一般用方块表示轮到我方走棋的节点,称为最大节点;用圆圈表示轮到对方走棋的节点,称为最小节点.棋局中,我方(MAX)棋子用表示,对方(MIN)棋子用表示.开始由我方先走,搜索深度为2.估价函数:我方获胜f(p)=-对方获胜 空格视为时我方三连子成线数-其他情况 空格视为时对方三连子成线数f(p)=6-4=2f(p)=5-6=-1 棋局中,我方(MAX)棋子用表示,对方(MIN)棋子用表示.开始由我方先走,搜索深度为2.估价函数

29、:我方获胜f(p)=-对方获胜 空格视为时我方三连子成线数-其他情况 空格视为时对方三连子成线数1-1-211010-1-10-10-2 12MAXMIN11213121010201112231221100 111212-101001122111-ABCDl-搜索法极大极小搜索法的缺点 它是把搜索树的生成和格局估计值这两个过程分开来进行的.即先生成全部搜索树,然后再进行端节点静态估值和倒推值计算,这显然会导致低效率.值极大节点f值的下界值极小节点f值的上界和值的计算MAX节点的值等于其后继节点当前最大的最终倒推值.MIN节点的值等于其后继节点当前最小的最终倒推值.=-1-1=-11010-1-

30、10-10-2ABC=-2、值的性质lMAX节点的值永不减少lMIN节点的值永不增加终止搜索规则l修剪:若任何MIN节点的值小于或等于它的任一祖先节点MAX的值,则可终止该MIN节点以下的搜索,并可将其最终倒推值设为它的值.l修剪:若任何MAX节点的值大于或等于它的任一祖先节点MIN的值,则可终止该MAX节点以下的搜索,并可将其最终倒推值设为它的值.举例:如下的搜索过程.假定节点的生成次序是从上到下,从左到右进行的.05-333-302-2352300000-3-3033 30522-5-5-5222MAXMAXMINMINl注意:博弈树搜索的目标就是找到当前棋局的一步走法,所以剪枝搜索的结果

31、是得到了一个最佳走步,而不是象一般的图搜索或者与或图搜索那样,得到的是从初始节点到目标节点(集)的一条路径或者解图.-剪枝的效率问题:若以最理想的情况进行搜索,当搜索树深度为D,分枝因数为B时.不使用-剪枝技术,搜索树的端节点数为Nd=BD;若使用-剪枝技术,可以证明理想条件下生成的端节点数最少,有 Nd=2BD/2-1(D为偶数);Nd=B(D+1)/2+B(D-1)/2-1(D为奇数).这就是说,在一般条件下使用-搜索技术,在同样的资源限制下,可以向前考虑更多的走步数,这样选取当前的最好优先走步,将带来更大的取胜优势.l其他改进方法 其他改善极大极小过程性能的基本方法有以下几种:不严格限制

32、搜索的深度.当到达深度限制时,如出现博弈格局有可能发生较大变化时(如出现兑子),则应多搜索几层,使格局进入较稳定状态后再中止,这样可使倒推计算值的结果比较合理,避免考虑不充分产生的影响.这是等候状态平稳后中止搜索的方法.当算法给出所选的走步后,不要马上停止搜索,而是在原先估计可能的路径上再往前搜索几步,再次检验会不会出现意外.这是一种增添辅助搜索的方法.对某些博弈的开局阶段和残局阶段,往往总结了一些固定的对弈模式,因此可以利用这些知识编好走步表,以便在开局和结局时使用查表法.只是在进入中盘阶段后,再调用其他有效的搜索算法,来选择最优的走步.使用-剪枝技术,当不满足剪枝条件()时.若值比 值大不了多少或极相近,这时也可以进行剪枝,以便有条件把搜索集中到会带来更大效果的其他路径上,这就是中止对效益不大的一些子树的搜索,以提高搜索效率.补充习题:给出用-搜索法搜索下面的博弈树所得到的搜索树,并在搜索到的节点上注明,值和最终倒推值.0 1 2 -1 0 -1 1 2 3 0 -3