第三章与或图搜索

第三章与或图搜索问题---问题归约法§3.0引言归约(Reduction)例1 问题1：现有煤气灶、水龙头、水壶和火柴，你怎样烧水？ 答：向水壶中注满水，把水壶放在煤气灶上，擦火柴点燃煤气灶。 问题2：问题1中其他情况不变，只是水壶 中已经灌满了水，你怎样烧水？答：把水壶放在煤气灶上，擦火柴点燃煤气灶或擦火柴点燃煤气灶，把水壶放在煤气灶上。例2 在边长为2的正方形内，任意放置5个点，求证其中必存在两个点，它们之间的距离不大于2。 . 问题可转化为： . 在四个单位正方形内， . 任意放置5个点，至少 . . 有两个点在同一正方形内。IIIII①②③123I例3 假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积。求解步骤：求五边形面积求1面积求2面积求3面积求I面积求II面积求III面积求①面积求②面积求③面积123IIIIII①②③本原问题可直接得到答案的问题称为本原问题例1中的原始的烧水问题例2中根据鸽巢原理直接可回答的问题例3中求矩形面积的问题归约法把原问题转化(分解)为一个或几个子问题，对子问题再归约，直至成为可以直接求解的本原问题。§3.1问题空间及与或图表示梵塔难题的两种解法状态空间法初始数据库 (111)表示C,B,A三个盘都在柱1上目标数据库 (333)表示C,B, A三个盘都在柱3上123

A

B

C状态空间其中(ijk)表示C在柱i,B在柱j,A在柱k上(111)(113)(123)(112)(121)(122)(322)(131)(132)(321)(323)(133)(233)(232)(231)(313)(331)(333)(332)(312)(311)(212)(211)(213)(223)(221)(222)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)采用归约法要把所有圆盘移至柱3，必须先把C盘移至柱3，而在移动C盘至柱3前，柱3必须为空。只有把A、B移至柱2后，才能将C移到柱3。在C移至柱3后，再解决将A、B移至柱3。将上面的分析理一下顺序：就把原问题归约为3个子问题：移动A、B至柱2的双圆盘问题；移动C至柱3的单元盘问题；（本原问题）移动A、B至柱3的双圆盘问题。将梵塔问题归约为本原问题的问题空间(111)(333)(111)(122)(122)(322)(322)(333)(123)

(122)(111)

(113)(113)

(123)(331)

(333)(322)

(321)(321)

(331)小结状态空间法与问题归约法的比较状态空间——问题空间操作——归约求解路径——本原问题归约就是化简，即把复杂问题分解为若干子问题，且使得：每个子问题比原问题好解；这些子问题解决了，原问题就解决了。归约法的分类有序归约(分段归约) 梵塔难题无序归约(分解归约) 求五边形的面积与或图表示法与扩展将一个问题分解为若干子问题，所有的子问题有解，原问题才有解。K-联接符或扩展将一个问题转化为若干子问题，只要一个子问题有解，原问题就有解。单线联接符AP1P2PkP1P2Pknon1n2n4n3n5n6n7n8与或图与或图搜索从代表原始问题的根节点开始，按一定的规则(归约操作)进行与或扩展，直到代表本原问题的终节点。要选择适当的或分枝进行扩展，以求找到一个最佳分解方案。在与或图中搜索最佳分解方案，即在问题空间搜索一个最佳解图。若干概念终节点可解节点不可解节点解图耗散值最佳解图可解过程不可解过程与或图中某一个节点n到节点集N的一个解图类似于普通图中的一条解路径。解图的求法：从节点n开始，正确选择一个外向连接符，在从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止．non1n0n4n3n5non7n8三个解图n5n7n8n0n4n5n7n8（1）（2）（3）·K-连接——表示从父节点到子节点间的连接*也称为父节点的外向连接，*以园弧指示同父子节点间的“与”关系，*K为这些子节点的个数，K>1时成为超连接，*一个父节点可以有多个外向的K-连接。*当所有超连接的K都等于1时，与或图蜕化为一般图。·根、叶、终节点*无父节点的节点——根节点，用于指示问题的初始状态；*无子节点的节点——叶节点。*用于联合表示目标状态的节点——终节点，*终节点必定是叶节点，反之不然；

解图的生成——自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止。*解图纯粹是一种“与”图；*由于与或图中存在“或”关系；可产生或搜索到多个解图（上图），*解图应无环，即任何节点的外向连接均不得指向自己或自己的先辈，否则会使搜索陷入死循环。解图－－－在与或图是无环的假定条件下，解图可递归定义如下：定义：一个与或图Ｇ中，从节点n到节点集Ｎ的解图记为Ｇ’，Ｇ’是Ｇ的子图．

①若n是N的一个元素,则G’由单一节点组成;

②若n有一个指向节点{n1,n2,……nk}的外向连接符K,使得从每一个ni到N有一个解图(i=1,2,……k),则G’由节点n,连接符K,及{n1,n2,……nk}中的每一个节点到N的解图所组成;

③否则n到N不存在解图.同样可以递归定义局部图如下：

①单一节点是局部图

②对于一个局部图的任意叶节点n，选择一个n的外向连接符K，则该局部图、外向连接符K以及K所连接的后继节点一起组成图，仍然组成一个局部图解图的耗散值：K(n,N)表示从节点n到终节点集合N的解图的耗散值,则可递归计算如下若nN,则K(n,N)=0;若n是一个外向连接符指向后继节点{n1,n2,……,nk},并设该联接符的耗散值Cn.则K(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)=8K(n0,N)=7K(n0,N)=5同样,也可以计算一个局部图的耗散值：如果同样将局部图的耗散值记为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的情况下搜索过程还要标记能解节点和不能解加点,为此给出如下定义:能解节点(SOLVED)终节点是能解节点;若非终节点有”或”子节点时,当且仅当其子节点至少有一能解,该非终节点才能解;若非终节点有”与”子节点时,当且仅当其子节点均能解时,该非终节点才能解不能解节点(UNSOLVED)没有后裔的非终节点是不能解节点;若非终节点有”或”子节点时,当且仅当所有子节点均不能解时,该非终节点才不能解;若非终节点有”与”子节点时,当至少有一子节点不能解时,该非终节点才不能解采用问题归约法的问题表示一个初始问题的描述一套把问题变换为子问题的算符或归约操作一套本原问题的描述问题归约法举例求证:一个角的平分线上的点与该角的两边距离相等.已知:

DBA=

DBC A BAAD,BCCD DB为一线段 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°,

X2=90°P2: X1X2=X1X2P3:

X1=

X1

P4:

X1X2X3

Y1Y2Y3X3X1=Y3Y1,

X3X1X2=

Y3Y1Y2,

X1X2X3=

Y1Y2Y3P5:

X1X2X3=90°|X1X2X2X3P6: X2X3=Y2Y3|

X1X2X3

Y1Y2Y3归约操作:(1)用P1~P6的左边与要证的问题的左边相匹配(2)对相匹配的,将其右边与要证问题的右边的条件相比较:若条件已存在,则为本原问题,该问题可解.(b)如缺少条件,则将该条件作为要证的子问题,原问题的条件仍为新的子问题的条件,继续归约.(3)如对一个问题同时有几条本原问题描述可以匹配,则可以采用不同的归约操作(分解方法),亦即对该问题节点进行或扩展.例如:我们要证明的问题的左边是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继续这一过程,就可以得到下面的解图.AD=CD

DBA=

DBC,BAAD,BCCD, DB,

BAD,

BCD

BAD

BCD

DBA=

DBC,BAAD,BCCD, DB,

BAD,

BCDDB=DB|T

BAD=

BCD|T

BAD=90°|BAAD,...

BCD=90°|BCCD,...P6P4P1P5P5P2

DBA=

DBCnon1n2n3n4n5n6n8n7§3.2启发式与或图搜索法估价函数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连接符的(总)耗散值,又若n为终节点,则h(n)=0,则我们称h(n)满足单调限制.可证,对于所有节点有h(n)h*(n),即h是h*的下界.举例说明n0n1n3n6n7n5n80241020设每条弧的耗散值为1

h(n7)=h*(n7)=0h(n8)=h*(n8)=0h(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=5<h*(n3)=6h(n1)=2,C(n1)+h(n3)=1+4=5<h*(n1)=7h(n0)=0,C(n0)+h(n1)=1+2=3<h*(n0)=8AO*算法若h(n)满足单调限制,则下面的与或图搜索算法称为AO*算法(1)建立一个搜索图G,使其仅包含起始节点S,对应于节点S的费用为q(S)=h(S),如S为终节点,则标记S为SOLVED(2)untilS已标记为SOLVEDdo(3)begin(4)通过跟踪G中从S出发的有标记的连接符,计算

G中的一个局部解图G’(5)选择G’的任一未标记为SOLVED的叶节点n(6)扩展节点n,生成它的全部后继节点加入G中.对于未曾在G中出现过的每一个后继节点nj,相应的费用q(nj)=h(nj).对其中的终节点,标记SOLVED,

相应的q值为0(7)建立一个只包含节点n的集合M(8)untilM为空do(9)begin(10)从M中移出后裔不在M中的节点m(即自下而上)(11)根据以下步骤修改节点m的费用q(m):

若m有j个或分枝,对于m的每个或分枝i的与后继节点集{n1i

,……,nki},计算

qi(m)=Ci(m)+q(n1i)++q(nki) 1ij

令q(m)=min(qi(m)) 1ij

并对这个具有最小值的分枝连接符加以标记,如果以前标记在其他分枝连接符上,则删除以前的标记;如果该连接符的全部后继节点都已标记为SOLVED,则标记m为SOLVED(12)如果m已标记为SOLVED,或q(m)不同于以前计算的费用,则把通过有标记连接符连到m上的所有祖先节点都添加到M中去(13)end (9)(14)end (3)算法应用实例如下4n0n1n3n6n7n2n4n8n502020141

n Mmq(m)In0n0n003IIn1n1n125n0n034IIIn5n5

n512n0n045IVn4n4

n411n0

n055n1n3