第三章与或图搜索..ppt

第三章与或图搜索问题---问题归约法§3.0 引言l归约(Reduction)–例1 问题1：现有煤气灶、水龙头、水壶和火柴，你怎样烧水？答：向水壶中注满水，把水壶放在煤气灶上，擦火柴点燃煤气灶•问题2：问题1中其他情况不变，只是水壶中已经灌满了水，你怎样烧水？ 答：把水壶放在煤气灶上，擦火柴点燃煤气灶或擦火柴点燃煤气灶，把水壶放在煤气灶上例2 在边长为2的正方形内，任意放置5个点，求证其中必存在两个点，它们之间的距离不大于2 .问题可转化为： .在四个单位正方形内， . 任意放置5个点，至少 . . 有两个点在同一正方形内IIIII①②③123I例3假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积 求解步骤：求五边形面积求 1面积求 2面积求 3面积求 I面积求 II面积求 III面积求①面积求②面积求③面积123IIIIII①②③l本原问题–可直接得到答案的问题称为本原问题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 Cl状态空间其中(i j k)表示C在柱i, B在柱j, A在柱k上(1 1 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前，柱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小结–状态空间法与问题归约法的比较l状态空间——问题空间l操作——归约l求解路径——本原问题–归约就是化简，即把复杂问题分解为若干子问题，且使得：l每个子问题比原问题好解；l这些子问题解决了，原问题就解决了–归约法的分类l有序归约(分段归约)梵塔难题l无序归约(分解归约)求五边形的面积l与或图表示法–与扩展l将一个问题分解为若干子问题， 所有的子问题有解，原问题才有解lK-联接符–或扩展l将一个问题转化为若干子问题，只要一个子问题有解，原问题就有解。

l单线联接符AP1P2PkP1P2Pknon1n2n4n3n5n6n7n8与或图–与或图搜索l从代表原始问题的根节点开始，按一定的规则(归约操作)进行与或扩展，直到代表本原问题的终节点l要选择适当的或分枝进行扩展，以求找到一个最佳分解方案l在与或图中搜索最佳分解方案，即在问题空间搜索一个最佳解图–若干概念l终节点 可解节点 不可解节点 解图 耗散值 最佳解图 可解过程 不可解过程 与或图中某一个节点n到节点集N的一个解图类似于普通图中的一条解路径l解图的求法：从节点n开始，正确选择一个外向连接符，在从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止．non1n0n4n3n5non7n8三个解图n5n7n8n0n4n5n7n8（1）（2）（3）l· K-连接连接——表示从父节点到子节点间的连接 * 也称为父节点的外向连接， * 以园弧指示同父子节点间的“与”关系， * K为这些子节点的个数，K>1时成为超连接， * 一个父节点可以有多个外向的K-连接 * 当所有超连接的K都等于1时，与或图蜕化为一般图。

l· 根、叶、终节点根、叶、终节点 * 无父节点的节点——根节点，用于指示问题的初始状态； * 无子节点的节点——叶节点 * 用于联合表示目标状态的节点——终节点， * 终节点必定是叶节点，反之不然；l 解图的生成解图的生成——自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止 * 解图纯粹是一种“与”图； *由于与或图中存在“或”关系；可产生或搜索到多个解图（上图）， * 解图应无环，即任何节点的外向连接均不得指向自己或自己的先辈，否则会使搜索陷入死循环l解图－－－在与或图是无环的假定条件下，解图解图－－－在与或图是无环的假定条件下，解图可递归定义如下：可递归定义如下： 定义：一个与或图Ｇ中，从节点定义：一个与或图Ｇ中，从节点n到节点集Ｎ的解到节点集Ｎ的解图记为Ｇ图记为Ｇ’，Ｇ，Ｇ’是Ｇ的子图．是Ｇ的子图． ①①若若n是是N的一个元素的一个元素,则则G’由单一节点组成由单一节点组成; ②②若若n有一个指向节点有一个指向节点{n1,n2,……nk}的外向连接的外向连接符符K,使得从每一个使得从每一个ni到到N有一个解图有一个解图(i=1,2,……k),则则G’由节点由节点n,连接符连接符K,及及{n1,n2,……nk}中的每一个中的每一个节点到节点到N的解图所组成的解图所组成; ③③否则否则n到到N不存在解图不存在解图.l同样可以递归定义局部图如下：同样可以递归定义局部图如下： ①①单一节点是局部图单一节点是局部图 ②②对于一个局部图的任意叶节点对于一个局部图的任意叶节点n，选择一个，选择一个n的外向连接符的外向连接符K，则该局部图、外向连接符，则该局部图、外向连接符K以及以及K所连接的后继节点一起组成图，仍然组成一个局所连接的后继节点一起组成图，仍然组成一个局部图部图l解图的耗散值：K(n,N)表示从节点n到终节点集合N的解图的耗散值,则可递归计算如下–若nN, 则 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l同样,也可以计算一个局部图的耗散值：如果同样将局部图的耗散值记为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)1.终节点是能解节点终节点是能解节点;2.若非终节点有若非终节点有”或或”子节点时子节点时,当且仅当其当且仅当其子节点至少有一能解子节点至少有一能解,该非终节点才能解该非终节点才能解;3.若非终节点有若非终节点有”与与”子节点时子节点时,当且仅当其当且仅当其子节点均能解时子节点均能解时,该非终节点才能解该非终节点才能解不能解节点不能解节点(UNSOLVED)1.没有后裔的非终节点是不能解节点没有后裔的非终节点是不能解节点;2.若非终节点有若非终节点有”或或”子节点时子节点时,当且仅当所当且仅当所有子节点均不能解时有子节点均不能解时,该非终节点才不能该非终节点才不能解解;3.若非终节点有若非终节点有”与与”子节点时子节点时,当至少有一当至少有一子节点不能解时子节点不能解时,该非终节点才不能解该非终节点才不能解l采用问题归约法的问题表示–一个初始问题的描述–一套把问题变换为子问题的算符或归约操作–一套本原问题的描述l问题归约法举例求证: 一个角的平分线上的点与该角的两边距离相等.已知: DBA= DBCABAAD, BCCDDB为一线段 D BAD为一三角形 B C BCD为一三角形试证: AD=CD问题表示: 用S|T来描述一个证明问题, 其中S为要证明 的论点, T为前提, 于是上述问题可表示为:AD=CD DBA= DBC, BAAD, BCCD, DB,  BAD,  BCD 本原问题:P1: X1=  X2 |  X1=90°,  X2=90°P2:X1X2=X1X2P3: X1=  X1 P4: X1X2X3   Y1Y2Y3 X3X1=Y3Y1,  X3X1X2=  Y3Y1Y2,  X1X2X3=  Y1Y2Y3P5:  X1X2X3= 90°| X1X2  X2X3P6: X2X3=Y2Y3 |  X1X2X3   Y1Y2Y3 归约操作:(1)用P1~P6的左边与要证的问题的左边相匹配(2)对相匹配的, 将其右边与要证问题的右边的条件相比较: (a)若条件已存在, 则为本原问题, 该问题可解.(b)(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=  DBCT, 所以要证的子问题为:DB=DB|T,  BAD=  BCD|T继续这一过程, 就可以得到下面的解图.AD=CD DBA= DBC, BAAD, BCCD, DB,  BAD,  BCD BAD   BCD DBA= DBC, BAAD, BCCD, DB,  BAD,  BCDDB=DB|TBAD= BCD| TBAD= 90°| BAAD, ... BCD= 90°| BCCD, ... P6P4P1P5P5P2DBA= DBCnon1n2n3n4n5n6n8n7§3.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连接符的(总)耗散值, 又若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=5