RGZN_3图搜索技术中的问题归约.doc

图搜索技术-问题归约(Problem Reduction) 某些比较复杂的问题求解方法含有子问题的概念。应用这种方法去分析原始问题以产生一个子问题的集合。这样，对该子问题集合的某个具体子集的解答就意味着是对原始问题的一个解答。例如“猴子和香蕉”问题的例子。为了解答“猴子和香蕉”这个总问题，我们可以把它归约为下列四个子问题：子问题：猴子从位置走到位置；子问题：猴子把箱子从位置推到位置；子问题：猴子爬上箱顶；子问题：猴子摘到香蕉。如果我们能够得到这四个子问题的一组解答，那么我们也就求得“猴子和香蕉”问题的一个解答。每个子问题可用任何一种可行的方法加以解答。可用上一章中的状态空间法求解，也可用归约的方法再进行分析并产生出子子问题等等。任何首先产生子问题然后又解决子问题的解题方法，叫问题归约法。 状态空间法 问题归约方法节点: 状态 问题算符: 一状态 另一状态 将大问题分解为一批小问题 求解: 在一个图(纯”或”图)中 在一个”与或”图中找一找一条”解路” 棵”解树” A结论A例: 已知结论I,L,K成立,试证明结论A成立。 解树CBGCFEDB LKIIHLKJ一个采用问题归约的问题表示可由下列三部分组成：1.一个初始问题描述；如对结论的A描述2.一套把问题变换为子问题的算符；3.一套本原问题描述。如 I,L,K采用问题归约法 生成与或图的足够部分以问题求解 证明始点是可解的3.1.1 示例（梵塔难题）它的一种通常的提法如下：有三个柱子（1、2和3）和三个不同尺寸的圆盘（A、B和C）。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部三个圆盘都堆在柱子1上：最大的圆盘C在底部；最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上。搬动圆盘时，每次只许移一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。柱1 2 3 起始状态柱 1 2 3 目标状态当然，这个问题可用状态空间法来求解。状态 （i，j，k） 描述：大片在i上；中片在柱子j上；而小片在柱子k上。起始状态 （1，1，1）目标状态 （3，3，3）状态空间搜索图为：（1，1，1） （1，1，3）（1，1，2） （1，2，3）（1，3，2）（1，2，1）（1，2，2）（3，2，2） ： ：（3，2，3）（3，2，1） ：（3，1，3）（3，3，1）（3，3，2）（3，1，2）（3，1，1）（3，3，3）梵塔难题也可以由简单的问题归约方法来求解。梵塔问题的一种传统提法是64个圆盘，而不仅仅是三个圆盘。如果按照前述有关规则来把64个不同尺寸的圆盘从柱子1移至柱子3，那么需要搬动圆盘2641264=1064log21019.27次！问题归约解法始问题 （1，1，1） （3，3，3）算符： 将大问题（难度为n）分解为若干个小问题（难度= n-1）移n片从a到b的问题将一片从a到b的子问题将n-1片从c到b的子问题将n-1片从a到c的子问题 本原问题：一次只移一片的问题，即状态空间中只需迈一步 就可解决的问题问题归约图（1,1,1）=（3,3,3）（1,2,2）=（3,2,2）（3,2,2）=（3,3,3）（1,1,1）=（1,2,2）（1,1,1）（1,1,3）（1,1,3）（1,2,3）（1,2,3）（1,2,2）（3,2,2）（3,2,1）（3,2,1）（3,3,1）（3,3,1）（3,3,3） 状态i到目标状态问题可把状态空间中每一状态（节点）看成是从该状态到目标状态所形成的问题：状态 i 状态j到目标状态的子问题状态i到状态j的子问题状态j3.1.2 问题归约方法中的问题描述 用状态空间表示来描述某个问题往往是方便的。我们已经知道，任何状态空间搜索问题可以由下列三部分来表示： 1.初始状态的集合S； 2.把一些状态描述变换为另一些描述的算符集合F； 3.目标状态集合G。 于是，三元组合（S，F，G）就规定了一个问题，并且可作为一个问题描述。对于梵塔难题，基本上也应用了这种表示法。3.1.3 问题归约算符定理证明中问题的归约形式：问题表示： 令S代表我们要证明是正确的论点，T代表前提论点的集合。这样，我们就令 S|T （读做S给T）描述已知T前提的S证明问题。即：若有前提论点集合T,则必有结论S的证明问题归约方式： STST, XXT一般情况下，需加入个前提，从而归约方式变成： STST, X1, Xn.Xn-1T, XnXnT3.1.4 本原问题描述l 状态空间搜索中走动一步就可解决的问题l 具有已知解答的可能是相当复杂的问题 第二节 与或图表示3.2.1 与或图例如，设想问题A既可由求解问题B和C，也可由求解问题D、E和F，或者由单独求解问题G来解决。这一关系可由如下图所示的结构来表示。图中各节点由它们所表示的问题来标记。AANG替换集合GMDCBFE FEDBC 要使含有一个以上子问题的每个节点集合都聚集在它们各自的父辈节点之下，从而需引入附加节点M,N M和N 作为附加节点分别为B,C D,E,F的唯一父辈节点，将M和N理解为具有问题描述作用。问题A被归约为单一替换子问题M、N、G.可解节点:1.终叶节点是可解节点（因为它们与本原问题相关连）。2.如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解时，此非终叶节点才是可解的。3.如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。不可解节点:1.没有后裔的非终叶节点为不可解节点。2.如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。3.如果某个非终叶节点含有与后继节点，那么只有当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。3.2.2 与或图构成规则综上所述，可把与或图的构成规则概括于下：1.与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。2.对应于本原问题的节点，叫做终叶节点，它没有后裔。3.对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。例如上图说明把问题A归结为三个不同的子问题集合：N、M和G。如果集合N、M或G中有一个能够解答，那么问题A就可解答。所以把N、M和G叫做或节点。4.上图进一步表示集合N、M和G的组成情况。图中，M=B，C，N=D，E，F，而G由单一问题构成。一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。为了区别与或节点，我们把具有共同父辈的与节点后裔的所有弧线用另外一段小弧线连接起来。A5特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，图可以简化DFE 在上述图形中，每个节点代表一个明显的问题或问题集合。除了起始节点外，每个节点只有一个父辈节点。因此，实际上，这些图是与或树。第三节 与或图的盲目搜索3.3.1 与或图搜索过程可解标示过程： 一旦生成了某个可解节点，就要“自下而上”地根据祖先节点与该可解节点的“与或”关系来标记其祖先节点的可解性。若初始节点能被标示为可解，则算法就成功结束。不可解标示过程： 一旦生成了某个不可解节点，也要“自下而上”地根据各祖先节点与该节点的“与或”关系来标记其祖先节点的可解性。若初始节点一被标示为不可解的，则搜索就不成功地终止。3.3.2 与或树的宽度优先搜索 FIFO 将S放入OPEN表 从OPEN表首取出一个没作过删除标记的节点n放入CLOSED表中扩展节点n，将其后继依次放入OPEN表尾，并提供返n指针 n有后继否? N Y有后继为终叶节点否? N Y将终叶点标为可解应用可解标示过程 S 可解否 ? Y 成功退出 N对OPEN表中可解节点以及具有可解祖先的节点作删除标记 (非终叶且无后继) 标示n为不可解节点应用不可解标示过程S为不可解节点否? Y 失败退出 N对OPEN表中不可解节点以及具有不可解祖先的节点作删除标记 1扩展前8个OPEN表下之部分内容 2 3 4 5 6 78 9 B C D 10 11 12 A 扩展8个节点删除标记 节点名称 指针9BCD101112A扩展第9个节点后删除标记 节点名称 指针BCD101112A 1 2 3 扩展第9个节点,其后继均 4 5 6 7 终叶节点8 9 B C D 10 11 12 A t t节点旁边的数字表明节点的扩展次序3.3.3 与或树的深度优先搜索l OPEN表为栈式用法 (FILO)l 到达深度界限处的节点视为不可解节点 深度优先搜索程序的步骤如下：1.把起始节点S放入OPEN表。2.把OPEN表中的第一个节点移出，并把它放入CLOSED表，称这个节点为节点n。3.如果节点n的深度等于深度界限，则把n标示为不可解的，并转向步骤5；否则，继续下列过程。4.扩展节点n，生成其全部后裔。以任意顺序把这些后裔放进OPEN表的首端，并设置返回n的指针。如果不存在后裔，则标示为不可解的，并继续下一步；否则，转向步骤9。3.把不可解标示过程用于此搜索树。6.如果起始节点标示为不可解的，则失败退出；否则，继续下一步。7.从OPEN表中删去任何含有不可解祖先的节点。8.转向步骤2。9.如果任何后裔为终叶节点，则把它们标示为可解的，并继续下一步；否则，转向步骤2。10.把可解标示过程应用于此搜索树。11.如果起始节点标示为可解的，则含有解树而成功退出，此解树证明该起始节点是可解的；否则，继续下一步。12.从OPEN表中删去任何可解的或含有可解祖先的节点。13.转向步骤2。第四节 与或树的有序搜索搜索策略从当前已生成的部分图中,自上而下找出最有希望的可能解树T,之后,从T上找一叶点n来扩展当始点S可解(或不可解)时结束自下而上对与n有关的祖先节点进行费用修正 3.4.1 解树的费用定义: 总和费用 解树上所有弧线费用的总和最大费用 解树上具有最大路径费用的那条路径之费用 4 4 5 5 2 6 t 6 3 1 7 t t t 解答B ( 右分枝解)总和费用 = 4 + 6 + 1 + 7 = 18最大费用 = 4 + 6 + 7 = 17 解答A ( 左分枝解)总和费用 = 4 + 5 + 5 + 6 = 20最大费用 = 4 + 5 + 6 = 15定义: 最优解树: 具有最小费用的解树,以任一节点n为根的 最优解树之费用记为h*(n) h*(s) 初始问题最优解树之费用3.4.2 费用估计在直接搜索中的应用找一函数h ,使h(n) 为 h*(n)的一个估计h(n) 可以按如下方式进行计算: n为终叶节点，则h(n) = h*（n）= 0； n为刚被生成之节点,则靠估计函数计算出其h(n); n为非终叶节点，且已扩展有 k个子代n1，n2，nk，则由算法已算出h(n1)，h(n2)，h(nk)之值，重新按下式计算出h（n）之值: I ) 若n具有或后继n1，n2，nk，则Min1ikh（n）= C(n,ni)+h(ni) kI=1 II) 若n具有与后继n1，n2，nk，而且采用总和费用时,则 h（n）= C(n,ni)+h(ni)III) 若n具有与后继n1，n2，nk，而且采用最大费用时,则Max1ik h（n）= C(n,ni)+h(ni)注: 算法靠上述方式”自下而上”地重新计算受到新扩展节点影响的所有祖先节点的h（n）值,基于如下观点: 越靠近下层(本原问题),对费用的估计h（n）就越准确, 所以说是不断地按目前具有最好估值的h（n）去修正那些上层相关节点的h值。例: 设扩展S后得两组与节点(B,C)及(E,F),并设定弧线费用为1,采用总和费用计算: S A D B C E F .B、C、E、F 新生成点，设由估价函数算出h(B)=3 h(C)=3 h(E)=3 h(F)=2h(A)= C(n,ni)+h(ni) = 1 + 3 + 1 + 3 = 8h(D)= C(n,ni)+h(ni) = 1 + 3 + 1 + 2 = 7Min1i2 h（S）= C(n,ni)+h(ni)= min 1+8,1+7 = 8最有希望的可能解树T：当前已生成的部分图中，自S起按“与或”关系到某些“叶点”为止的具有最小估计费用的那棵树。确定方法： (1) 起始节点S在T上；(2) 若当前已产生的搜索树包含节点n和n的“与”后继，则所有这些后继均在T上；(3) 若当前已产生的搜索树包含节点n和n的“或”后继ni（i=1，2，k），那么具有c(n，ni)+h(ni)为最小的那一个ni在T上。 3.4.3 与或树的有序搜索算法 将S放入OPEN表 自上而下算出当前已生成图中最有希望的可解解树T 从OPEN表中节点T中节点 集合中选一个没作过删除标记的节点n，放入CLOSED表中n为终叶节点否? N 应用后继算符至n Y将n标为可解节点 n有后继否？ Y N应用可解标示过程 将n标为不可解S 可解否 ? Y 成功 应用不可解标示过程 N 退出对OPEN表中可解节点 S 不可解否? Y 失败以及具有可解祖先的 退出节点作删除标记 对OPEN表中不可解节 点以及具有不可解 祖先的节点作删除标记 扩展节点n，将其后继放入OPEN表；提供返n指针；算出各后继点ni 的h(ni)值；自下而上重算受到新扩展点影响的所有祖先节点的h值 例： 下设弧线费用为1 S A D B C E F 3 3 3 2第一循环.T ： （S）扩展S 各端代价分别为3，3，3，2h(B)=3 h(C)=3 h(E)=3 h(F)=2自下而上算出 h(A)= 8 h(D)= 7 h(S) = 8 S A D B C E F W V 3 2 2 2第二循环.T ： （S D E,F ）选n=E 扩展E (2级) 各端估计代价分别为3，2，2，2重算祖先节点W、V、E、D、S之h值h(W)=7 h(V)=6 h(E)=7（原为3）h(D)=1+ h(E)+1+h(F)=11h(S) = 9端节点： 搜索过程中已发现为终叶节点的节点； 搜索过程中已发现为非终叶且无后裔的节点； 其后裔尚未由搜索过程产生的节点；第五节 AO*算法3.3.1 与或图的解图及其费用 在一棵与或树中，加到一个节点上的“与”或者“或”标记取决于该节点与其父辈节点的关系。一种情况是由总数据库标记的一代父辈节点拥有一组与后继节点，每一个后继节点都用一个分量数据库来标记。另一种情况是由分量数据库标记的一个父辈节点拥有一组或后继节点，每个后继节点都用对该分量数据库应用一条选出的规则而得到的新数据库来标记。 我们所要讨论的一般是与或图，而不是与或树这种特殊情况，因为应用不同序列的规则可能生成相同的数据库。例如，用来标记某一节点的某一分量数据库，既可以从已分解的一个复合节点得到，也可以使用某一条规则从另一个节点得到。在这种情况下，对于其中一个父辈节点来说它可以叫做或节点，而对另一个父辈节点它又可以叫做与节点。因此，我们一般不把一个与或图的节点叫做与节点或者或节点，而是引入某个适合于图的更一般的标记。不过，我们仍然把这些结构叫做与或图，并在讨论与或树时继续采用与节点和或节点等术语。这里我们把与或图定义为超图，并且不用弧线来连接节点对，而用几条超弧线来连接一个父辈节点和它的一组后继节点。这些超弧线又叫做连接符。每个k连接符是从一个父辈节点指向一个含有k个后继节点的集合（如果所有连接符都是单一连接符，那么我们便得到一个普通图的特例）。 在与或树中，每个节点最多只有一个父辈节点。在与或树和与或图中，我们把没有任何父辈节点的节点叫做根节点。在与或图中，我们把没有后继节点的节点叫作叶节点（对于与或树则叫做端节点）。第六节 博弈树搜索3.6.1 博弈与博弈树我们可以应用前面讨论过的那些搜索技术来寻求某几类博弈的策略。我们所考虑的博弈都是双人完备博弈。这些博弈由两位选手对垒，两人轮流依次走步，其中任何一方都完全知道对方过去已经走过的棋步和今后可能的走步。l 从我方（MAX方）观点看，所有敌方能走出的节点都是“与”节点，因为只有所有这些敌方可走出的点都对我方有利，该节点才对我方有利。l 从我方（MAX方）观点看，所有我方能走出的节点都是“或”节点，因为我方走出的节点只要有一个点对我方有利，该节点就对我方有利。 MAX方走MIN方走Grundy博弈：规则：1） 双方每走一步，都要把某一堆分成数量不相等的两堆。2） 最后不能再分者为输。假设我们把这两位选手分别叫做MAX和MIN，并让MIN先走。初状态： 7枚硬币在一堆（7，MIN）（4，3，MAX）（5，2，MAX）（6，1，MAX） （3，3，1，MIN）（3，2，2，MIN）（4，2，1，MIN）（5，1，1，MIN） （2,2,2,1,MAX）（3,2,1,1,MAX）（4,1,1,1,MAX） （2,2,1,1,1,MIN）（3,1,1,1,1,MIN） （2,1,1,1,1,1,MAX）其数据库由一个无序的数字序列加上一个说明组成，其中数字代表在不同堆中的硬币数目，而说明表示下一步该轮到谁来分。因此，（7，MIN）为初始状态。从初始状态开始，MIN有三种可选择的分法，分别为（6，1，MAX），（5，2，MAX）或（4，3，MAX）。这一博弈的完