《问题规约法》PPT课件

1、2.2.2 问题规约法,1) 问题的归约描述 初始问题集合：初始状态集合 S 算符集合：将问题分解为若干子问题的变换集合F 本原问题集合：目标状态集合G 本原问题：具有明显解答的问题。如状态空间描 述中走动一步可以解决的问题，或具有已知解答 的复杂问题。 三元组合：（S , F, G,S,F,G,与,或,2）归约求解,一个问题可能存在多少归约算符？ 规约多样性,子问题的可解算符如何寻找？ 子问题的解空间搜索,本原问题如何寻找？ 本原问题,状态空间搜索,状态空间描述,例 “梵塔问题,一个僧侣在大佛前解决“世界末日”问题,a 初始状态 b 目标状态 梵塔问题,梵塔问题求解过程,1,2,3,A,B,

2、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

3、) (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 -1=18446744073709551615,iii ii） i=2,3,31558000秒/年,1片/秒,世界末日约58万亿年,3）与或图,或节点,与节点,与或图节点定义 起始节点：原始问题状态； 终叶节点：本原问题状态； 可解解点： 终叶节点 含有 “或” 节点的非终叶节点，

4、其所有后继节点至少有一个可解 含有“与” 节点的非终叶节点，其所有后继节点全部可解,不可解节点： 没有后裔的非终叶节点 含有“或”节点的非终叶节点，其所有后继节点全部不可解 含有“与”节点的非终叶节点，其所有后继节点至少有一个不可解 解图： 一组构成初始问题解的可解节点组成的连通图,起始节点,终叶节点,4）问题归约举例 例：符号积分：对于任意不定积分给出正确解答,积分归约形式,初始问题：求解不定积分 本原问题：简单积分 问题解答： 问题：求解过程的任何一步都有许多可应用 的归约替代算符，算符选择需要启发信息,5）归约方法 归约原理：将状态搜索问题归约为越来越简单的搜索问题，直至所有问题归约为本

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=g

6、oto(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

7、,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) 与或图搜索 搜索过程： 起始节点(根)对应于初始问题描述 后继节点（后裔）用归约算符求得（启发信息） 每个后裔设置一个来自父辈节点的指针（用来表示可解或不可解节点走向，并指明一个从根到终叶的解图） 不断扩展节点和设置指针，直至起始节点能被标为可解或不可解节点为止,搜索策略（搜索过程控制） 宽度优先搜索 深度优先搜索：扩展深度界限内的节点 与

8、或树有序搜索 搜索费用（搜索效率评估） 总和费用：解树上所有弧线费用之和 最大费用：解树中最大路径费用之和 单位弧线：费用为1的弧线(单位弧线构成的解树中，总和费用为节点数-1；最大费用为解树中最大串步度量) 例 已知两个解树如图，求这两个解树的总和费用及最大费用,两个解树及其费用,解树A：总和费用20；最大费用15 解树B：总和费用18；最大费用17,最优解树（搜索结果） 最小费用的解树（总和费用或最大费用） AO*算法 定义费用： h*(S) - 以起始节点S为根的最优解树费用 h*(n)- 以任意节点n为根的解树最小费用 h*(S)由h*(n)递归确定,最小费用解树,S h*(S,h*(

9、n,h*(n)性质 n为终叶节点,h*(n)=0 n含有“或” 后继节点 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

10、(n) = (Fib(n-1) + Fib(n-2)， n 1,建立G仅包含S q(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

11、)=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）博弈树搜索 博弈与博弈图 双人完备博弈：两选手对垒，轮流依次走步，其中一方完全知道对方已经走过的棋步和今后可能的走步。结果：一方赢，另一方输，平局。 随机博弈：不考虑结果，取决于机遇的博弈。 博弈图：博弈中应用规则寻找走步路线的图,例 “grun

12、dy博弈”。一堆硬币，一位选手将硬币分为不等的两堆；然后，两选手轮流分，直到某一堆只剩一个或两个硬币为止。首先遇到这种情况的选手输。 解：设共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,MI

13、N,博弈树搜索的极大极小过程 几个概念 简单博弈：棋类的残局 复杂博弈：不可能搜索的终局 国际象棋博弈树10120个节点，若1/3纳秒生成一个后继节点，生成国际象棋的博弈树大约需要1021个世纪 目标：搜索一步好棋 不断修改终局条件 搜索限制：时间、存储空间、节点深度,静态估价函数：有利于MAX估价为正，有利于MIN估价为负，平手估价为0 极大极小过程 ：利用静态评估函数寻找最佳棋路的过程。 例 一字棋 规则：先在横、竖、对角线排成一字者赢 解：令 MAX- MIN - P- 位置,静态评估函数： e(P) = MAX空位置-MIN空位置 e(P) = - P为MAX的获胜位置 e(P) =

14、- - 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,