《问题规约法》PPT课件.ppt
2.2.2 问题规约法,1)问题的归约描述 初始问题集合：初始状态集合 S 算符集合：将问题分解为若干子问题的变换集合F 本原问题集合：目标状态集合G 本原问题：具有明显解答的问题。如状态空间描 述中走动一步可以解决的问题，或具有已知解答 的复杂问题。三元组合：（S,F,G）,S,F,G,“与”,”或“,2）归约求解,一个问题可能存在多少归约算符？规约多样性,子问题的可解算符如何寻找？子问题的解空间搜索,本原问题如何寻找？本原问题,状态空间搜索？,状态空间描述？,例“梵塔问题”,一个僧侣在大佛前解决“世界末日”问题,a 初始状态 b 目标状态 梵塔问题,梵塔问题求解过程,1,2,3,A,B,C,状态空间描述：三个盘子的位置列表(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,b b=i,Move(x,j,i),x=a,问题归约 双圆盘问题:(111)(122)单圆盘问题:(122)(322）本原 双圆盘问题:(322)(333）双圆盘问题:(k i i)(k j j)(k i i)(k i j)(k k j)(k k i)(k j i)(k j j),“梵塔难题”,（111）,（122）,（322）,（333）,（113）,（123）,（122）,（321）,（331）,（333）,“梵塔难题”,（111.1）（iii.i），i=2,3,（111 i）i=2,3,1,2,3,N=1,（111 ii）i=2,3,+2,+22,+24,+263,=264,（iii ii）i=2,3,31558000秒/年,1片/秒,世界末日约58万亿年,3）与或图,或节点,与节点,与或图节点定义起始节点：原始问题状态；终叶节点：本原问题状态；可解解点：终叶节点含有“或”节点的非终叶节点，其所有后继节点至少有一个可解含有“与”节点的非终叶节点，其所有后继节点全部可解,不可解节点：没有后裔的非终叶节点含有“或”节点的非终叶节点，其所有后继节点全部不可解含有“与”节点的非终叶节点，其所有后继节点至少有一个不可解 解图：一组构成初始问题解的可解节点组成的连通图,起始节点,终叶节点,4）问题归约举例 例：符号积分：对于任意不定积分给出正确解答,积分归约形式,初始问题：求解不定积分本原问题：简单积分问题解答：问题：求解过程的任何一步都有许多可应用的归约替代算符，算符选择需要启发信息,5）归约方法 归约原理：将状态搜索问题归约为越来越简单的搜索问题，直至所有问题归约为本原问题 复杂问题规划为简单问题的集合（S,F,G）=(S,F,g1),(g1,F,g2),(gn,F,G)路标：g1,g2,gn g1G1,g2G2,.gnGn,（S，F，G）,=（S，F，Gf）（f（g），F，G）,g1,g2,g3,g4,关键算符：问题求解中具有决定性作用的算符 求解过程中必定使用的步骤 设：fF为关键算符 Gf-路标集合，gGf 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 Gf4,f4,(a,0,b,0),(c,0,c,0)g3 Gf3,f3,(f3(g3),Gf3),(f1(g2),Gf2),(a,0,b,0),(b,0,b,0)g2 Gf2,f2,(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),f1,1,2,3,4,5,f1,6)与或图搜索 搜索过程：起始节点(根)对应于初始问题描述后继节点（后裔）用归约算符求得（启发信息）每个后裔设置一个来自父辈节点的指针（用来表示可解或不可解节点走向，并指明一个从根到终叶的解图）不断扩展节点和设置指针，直至起始节点能被标为可解或不可解节点为止,搜索策略（搜索过程控制）宽度优先搜索 深度优先搜索：扩展深度界限内的节点 与或树有序搜索 搜索费用（搜索效率评估）总和费用：解树上所有弧线费用之和 最大费用：解树中最大路径费用之和 单位弧线：费用为1的弧线(单位弧线构成的解树中，总和费用为节点数-1；最大费用为解树中最大串步度量)例 已知两个解树如图，求这两个解树的总和费用及最大费用,两个解树及其费用,解树A：总和费用20；最大费用15解树B：总和费用18；最大费用17,最优解树（搜索结果）最小费用的解树（总和费用或最大费用）AO*算法 定义费用：h*(S)-以起始节点S为根的最优解树费用 h*(n)-以任意节点n为根的解树最小费用 h*(S)由h*(n)递归确定,最小费用解树,S h*(S),h*(n),h*(n)性质n为终叶节点,h*(n)=0n含有“或”后继节点 ni(i=1,2,k)，所有后继节点的最小/大费用为：n含有“与”后继节点ni(i=1,2,k)，所有后继节点的总和费用为：,n1 n2 n3 n4 nk,h*(ni),n不可解，h*(n)不定（无定义）n可解，则h*(n)有限,超图:K-链接的与或图(不仅仅由单纯的与节点和或节点组成),2-,2-,2-,2-,2-,解图的递归,G,递归指由简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况,典型的递归斐波那契数列Fib(0)=0 基本情况 Fib(1)=1 基本情况 递归定义Fib(n)=(Fib(n-1)+Fib(n-2)，n 1,建立G仅包含Sq(s)=h(s),Y,成功,N,选择任意ni，生成全部后裔nj放入G，q(nj)=h(nj),Y,标记nj可解h(nj)=0,N,选择后裔在G中的节点m，qi(m)=ci+q(n1i)+q(n2i)+q(nki)q(m)=minqi(m),m可解,修正父辈费用,Y,N,AO*算法的可纳性：如果从给定节点到一组节点存在一个解图，且对所有节点满足：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)=2 h(n7)=h(n8)=0（终叶结点）画出不同循环次数的AO*算法搜索图,AO*算法四次循环得到的最优解图,1,1,3,n1,n5,n4,2,n3,4,n2,4,4,n6,2,n7,n8,0,0,2,5,5,第一次循环第二次循环第三次循环第四次循环,n0,1,1,n5,n4,2,n8,0,0,7）博弈树搜索 博弈与博弈图 双人完备博弈：两选手对垒，轮流依次走步，其中一方完全知道对方已经走过的棋步和今后可能的走步。结果：一方赢，另一方输，平局。随机博弈：不考虑结果，取决于机遇的博弈。博弈图：博弈中应用规则寻找走步路线的图,例“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=2 MAX胜算更大！棋盘位置对称性：,图2-2-13 一字棋极大-极小搜索过程第一阶段,4-5=-1,6-5=1,5-5=0,6-5=1,5-5=0,-1,5-6=-1,5-5=0,5-6=-1,6-6=0,4-6=-2,-2,5-4=1,6-4=2,1,图2-2-14 一字棋极大-极小搜索过程第二阶段,4-2=2,3-2=1,5-2=3,3-2=1,4-2=2,3-2=1,1,4-3=1,3-3=0,5-3=2,3-3=0,4-3=1,3-2=1,4-2=2,4-2=2,5-2=3,3-2=1,4-2=2,4-2=2,4-3=1,4-3=1,3-3=0,0,1,0,图2-2-15 一字棋极大-极小搜索过程第三阶段,2-1=1,3-1=2,2-1=1,3-1=2,1,-,3-1=2,2-2=0,3-1=2,-,-,2-2=0,2-2=0,3-2=1,-,-,2-1=1,3-1=2,3-1=2,-,-,2-1=1,2-1=1,2-1=1,-,2）过程:极大极小搜索的优化算法,-1,-1,=-1+1,1,=-1,0,0,0,0,=0+1,2,1,1,1,1,2,0,2,1,=2,1,1,2,2,2,1,1,1,0,-1,=0,计算方法：MAX节点的值等于其后继节点当前最大的最终倒退值MIN节点的值等于其后继节点当前最小的最终倒退值特点：MAX节点的值永不减少MIN节点的值永不增加,终止搜索规则：任何MAX节点的值大于或等于它的祖先节点MIN的值，则可以终止该MAX节点以下的搜索。任何MIN节点的值小于或等于它的祖先MAX节点的值，则可以终止该MIN节点以下的搜索。,
