问题规约法

SFG“与””或“2）归约求解一个问题可能存在多少归约算符？规约多样性子问题的可解算符如何寻找？子问题的解空间搜索本原问题如何寻找？本原问题状态空间搜索？状态空间描述？例“梵塔问题”一个僧侣在大佛前解决“世界末日”问题a初始状态b目标状态梵塔问题梵塔问题求解过程123ABC状态空间描述：三个盘子的位置列表(a,b,c)a=1,2,3;b=1,2,3;c=1,2,3初始状态：S=(1,1,1)目标状态：G=(3,3,3)算符集合：Move(x,i,j)：x=A,B,C;i=1,2,3;j=1,2,3约束：c=i,Move(x,j,i),x=a,bb=i,Move(x,j,i),x=a问题归约①双圆盘问题:(111)→(122)②单圆盘问题:(122)→(322）本原③双圆盘问题:(322)→(333）双圆盘问题:(kii)→(kjj)(kii)→(kij)→(kkj)→(kki)→(kji)→(kjj)“梵塔难题”（111）（122）（322）（333）（113）（123）（122）（321）（331）（333）“梵塔难题”（111...…1）（iii...…i），i=2,3（111……i）i=2,3123N=1（111…ii）i=2,3+2+22+24+263………=264-1=18446744073709551615（iii…ii）i=2,331558000秒/年1片/秒世界末日约58万亿年3）与或图ANMHBCDEF或节点与节点与或图节点定义起始节点：原始问题状态；终叶节点：本原问题状态；可解解点：终叶节点含有“或”节点的非终叶节点，其所有后继节点至少有一个可解含有“与”节点的非终叶节点，其所有后继节点全部可解不可解节点：没有后裔的非终叶节点含有“或”节点的非终叶节点，其所有后继节点全部不可解含有“与”节点的非终叶节点，其所有后继节点至少有一个不可解解图：一组构成初始问题解的可解节点组成的连通图起始节点终叶节点4）问题归约举例例：符号积分：对于任意不定积分给出正确解答“与”节点“或”节点积分归约形式vdudvuudvniniiidxxfdxxf11)()(dxxfdxxkf)()(dzzzxdxx)44(91)32(363/223/22)32(xzdctgxxdxcos155162522tgx5411112224zzzdzz111224zzz222292134xdxxxdx9213422xxxyxsindxxx2/524)1(ydyyyydyydxxxyxcoscossinsin)cos1(sin)1(542/524sin2/524dyyy44cossinyyctgysincosydyctg4ctgyz)1(24zzdzyytgycossinydytg4tgyzdzzz241dzzz)111(22dzzzdzzzdzzz)111(1111222424dzdzz2dzz112dzdwarctgzw2ytgzdzzzz4224)1)(1(32初始问题：求解不定积分本原问题：简单积分问题解答：问题：求解过程的任何一步都有许多可应用的归约替代算符，算符选择需要启发信息dxxx2/524)1()(arcsin)(arcsin31arcsin3xtgxtgx5）归约方法归约原理：将状态搜索问题归约为越来越简单的搜索问题，直至所有问题归约为本原问题复杂问题规划为简单问题的集合（S,F,G）={(S,F,{g1}),({g1},F,{g2}),……,({gn},F,G)}路标：g1,g2,……,gng1G1,g2G2,…….gnGnSFG（S，F，G）={（S，F，Gf）（f（g），F，G）}g1g2g3g4关键算符：问题求解中具有决定性作用的算符求解过程中必定使用的步骤设：fF为关键算符Gf---路标集合，gGff(g)---关键算符f作用于g的结果(S,F,G)(S,F,Gf)(f(g),F,G)关键算符作用差别：当前状态与目标状态的距离候选算符：对应差别的状态空间算符或算符集合例猴子与香蕉问题S=(a,0,b,0),G=(c,1,c,1)算符集合：f1=goto(U)(a,0,b,0)goto(U)(U,0,b,0)f2=pushbox(V)(b,0,b,0)pushbox(V)(V,0,V,0)f3=climbbox(V,0,V,0)climbbox(V,1,V,0)f4=grasp(c,1,c,0)grasp(c,1,c,1)如何寻找关键算符？((a,0,b,0),(c,1,c,1))({f4(g4)},G)((a,0,b,0),(c,1,c,0)),g4Gf4f4((a,0,b,0),(c,0,c,0))g3Gf3f3({f3(g3)},Gf3)({f1(g2)},Gf2)((a,0,b,0),(b,0,b,0)g2Gf2f2((a,0,b,0),(a,0,b,0))g1Gf1({f3(g1)},Gf1)f2({(a,0,b,0)},Gf2)g2Gf2({f1(g2)},Gf2)({(b,0,b,0)},Gf1)g1Gf1({f1(g1)},Gf1)f112345f16)与或图搜索搜索过程：起始节点(根)对应于初始问题描述后继节点（后裔）用归约算符求得（启发信息）每个后裔设置一个来自父辈节点的指针（用来表示可解或不可解节点走向，并指明一个从根到终叶的解图）不断扩展节点和设置指针，直至起始节点能被标为可解或不可解节点为止搜索策略（搜索过程控制）宽度优先搜索深度优先搜索：扩展深度界限内的节点与或树有序搜索搜索费用（搜索效率评估）总和费用：解树上所有弧线费用之和最大费用：解树中最大路径费用之和单位弧线：费用为1的弧线(单位弧线构成的解树中，总和费用为节点数-1；最大费用为解树中最大串步度量)例已知两个解树如图，求这两个解树的总和费用及最大费用两个解树及其费用456A5634712Btttt解树A：总和费用20；最大费用15解树B：总和费用18；最大费用17最优解树（搜索结果）最小费用的解树（总和费用或最大费用）AO*算法定义费用：h*(S)---以起始节点S为根的最优解树费用h*(n)---以任意节点n为根的解树最小费用h*(S)由h*(n)递归确定最小费用解树Sh*(S)h*(n)h*(n)性质n为终叶节点,h*(n)=0n含有“或”后继节点ni(i=1,2,…,k)，所有后继节点的最小/大费用为：n含有“与”后继节点ni(i=1,2,…,k)，所有后继节点的总和费用为：)](),(min[)(**iinhnncnhMIN])(),([)(1**kiiinhnncnhh*(n)n1n2n3n4……nk)](),(max[)(**iinhnncnhMAXh*(ni)n不可解，h*(n)不定（无定义）n可解，则h*(n)有限n0n1n2n4n3n6n5n7n8超图:K-链接的与或图(不仅仅由单纯的与节点和或节点组成)2-2-2-2-2-解图的递归G递归指由简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况典型的递归斐波那契数列Fib(0)=0[基本情况]Fib(1)=1[基本情况][递归定义]Fib(n)=(Fib(n-1)+Fib(n-2))，n1建立G仅包含Sq(s)=h(s)S可解？Y成功N选择任意ni，生成全部后裔nj放入G，q(nj)=h(nj)nj可解？Y标记nj可解h(nj)=0N选择后裔在G中的节点m，qi(m)=ci+q(n1i)+q(n2i)+……+q(nki)q(m)=min[qi(m)]nij可解？m可解,修正父辈费用YNAO*算法的可纳性：如果从给定节点到一组节点存在一个解图，且对所有节点满足：h(n)h*(n)，h单调则算法总能找到一个最佳解图例假设图中可以得到下列估计：h(n0)=0,h(n1)=2,h(n2)=4,h(n3)=4,h(n4)=1,h(n5)=1,h(n6)=2h(n7)=h(n8)=0（终叶结点）画出不同循环次数的AO*算法搜索图AO*算法四次循环得到的最优解图113n1n5n42n34n244n62n7n800255第一次循环第二次循环第三次循环第四次循环n011n5n42n8007）博弈树搜索博弈与博弈图双人完备博弈：两选手对垒，轮流依次走步，其中一方完全知道对方已经走过的棋步和今后可能的走步。结果：一方赢，另一方输，平局。随机博弈：不考虑结果，取决于机遇的博弈。博弈图：博弈中应用规则寻找走步路线的图例“grundy博弈”。一堆硬币，一位选手将硬币分为不等的两堆；然后，两选手轮流分，直到某一堆只剩一个或两个硬币为止。首先遇到这种情况的选手输。解：设共7个硬币，两选手分别为MAX,MIN状态空间描述：（数字1，数字2，…，说明)数字i---被分堆中的硬币数目说明---下一选手Grundy博弈图（7，MIN）（6,1,MAX）（5,2,MAX）（4,3,MAX）（5,1,1,MIN）（4,2,1,MIN）（3,2,2,MIN）（3,3,1,MIN）（4,1,1,1,MAX）（3,2,1,1,MAX）（2,2,2,1,MAX）（3,1,1,1,1,MIN）（2,2,1,1,1,MIN）（2,1,1,1,1,MAX）（4,2,1,MIN）博弈树搜索的极大极小过程几个概念简单博弈：棋类的残局复杂博弈：不可能搜索的终局国际象棋博弈树10120个节点，若1/3纳秒生成一个后继节点，生成国际象棋的博弈树大约需要1021个世纪目标：搜索一步好棋不断修改终局条件搜索限制：时间、存储空间、节点深度静态估价函数：有利于MAX估价为正，有利于MIN估价为负，平手估价为0极大极小过程：利用静态评估函数寻找最佳棋路的过程。例一字棋规则：先在横、竖、对角线排成一字者赢解：令MAX-MIN-P---位置静态评估函数：e(P)=MAX空位置-MIN空位置e(P)=--P为MAX的获胜位置e(P)=---P为MIN的获胜位置e(P)=MAX空位置-MIN空位置=6–4=2MAX胜算更大！棋盘位置对称性：图2-2-13一字棋极大-极小搜索过程第一阶段4-5=-16-5=15-5=06-5=15-5=0-15-6=-15-5=05-6=-16-6=04-6=-2-25-4=16-4=21图2-2-14一字棋极大-极小搜索过程第二阶段4-2=23-2=15-2=33-2=14-2=23-2=114-3=13-3=05-3=23-3=04-3=13-2=14-2=24-2=25-2=33-2=14-2=24-2=24-3=14-3=13-3=0010图2-2-15一字棋极大-极小搜索过程第三阶段2-1=13-1=22-1=13-1=21-∞3-1=22-2=03-1=2-∞-∞2-2=02-2=03-2=1-∞-∞2-1=13-1=23-1=2-∞-∞2-1=12-1=12-1=1-∞2）α─β过程:极大极小搜索的优化算法-1-1α=-1+11β=-10000α=0+1211112021β=2∞11222∞∞∞1110-1α=0计算方法：①MAX节点的α值等于其后继节点当前最大的最终倒退值②MIN节点的β值等于其后继节点当前最小的最终倒退值特点：①MAX节点的α值永不减少②MIN节点的β值永不增加终止搜索规则：①任何MAX节点的α值大于或等于它的祖先节点MIN的β值，则可以终止该MAX节点以下的搜索。②任何MIN节点的β值小于或等于它的祖先MAX节点的α值，则可以终止该MIN节点以下的搜索。