问题规约法.pptVIP

2.2.2 问题规约法 1) 问题的归约描述 初始问题集合：初始状态集合 S 算符集合：将问题分解为若干子问题的变换集合F 本原问题集合：目标状态集合G 本原问题：具有明显解答的问题。如状态空间描 述中走动一步可以解决的问题，或具有已知解答 的复杂问题。 三元组合：（S , F, G） 例 “梵塔问题” 状态空间描述： 三个盘子的位置列表(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) “梵塔难题” “梵塔难题” 3）与或图 与或图节点定义 起始节点：原始问题状态； 终叶节点：本原问题状态； 可解解点： 终叶节点 含有 “或” 节点的非终叶节点，其所有后继节点至少有一个可解 含有“与” 节点的非终叶节点，其所有后继节点全部可解 不可解节点： 没有后裔的非终叶节点 含有“或”节点的非终叶节点，其所有后继节点全部不可解 含有“与”节点的非终叶节点，其所有后继节点至少有一个不可解 解图： 一组构成初始问题解的可解节点组成的连通图 4）问题归约举例 例：符号积分：对于任意不定积分给出正确解答 初始问题：求解不定积分 本原问题：简单积分 问题解答： 问题：求解过程的任何一步都有许多可应用 的归约替代算符，算符选择需要启发信息 5）归约方法 归约原理：将状态有哪些信誉好的足球投注网站问题归约为越来越简单的有哪些信誉好的足球投注网站问题，直至所有问题归约为本原问题 复杂问题规划为简单问题的集合 （S,F,G）= {(S,F,{g1}),({g1},F,{g2}), … … , ({gn},F,G)}路标： g1, g2,… …, gn g1?G1,g2?G2,… ….gn?Gn 关键算符：问题求解中具有决定性作用的算符 求解过程中必定使用的步骤 设：f?F为关键算符 Gf --- 路标集合，g?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) 6) 与或图有哪些信誉好的足球投注网站 有哪些信誉好的足球投注网站过程： 起始节点(根)对应于初始问题描述 后继节点（后裔）用归约算符求得（启发信息） 每个后裔设置一个来自父辈节点的指针（用来表示可解或不可解节点走向，并指明一个从根到终叶的解图） 不断扩展节点和设置指针，直至起始节点能被标为可解或不可解节点为止 最优解树（有哪些信誉好的足球投注网站结果） 最小费用的解树（总和费用或最大费用） AO*算法 定义费用： h*(S) --- 以起始节点S为根的最优解树费用 h*(n)--- 以任意节点n为根的解树最小费用 h*(S)由h*(n)递归确定 h*(n)性质 n为终叶节点,h*(n)=0 n含有“或” 后继节点 ni (i=1,2,…,k) ，所有后继节点的最小/大费用为： n含有“与” 后继节点ni (i=1,2,…,k) ，所有后继节点的总和费用为： 解图的递归 AO*算法的可纳性：如果从给定节点到一组节点存在一个解图，且对