《问题规约法》PPT课件.ppt
《《问题规约法》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《问题规约法》PPT课件.ppt(43页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2.2.2 问题规约法问题规约法1)1)问题的归约描述问题的归约描述问题的归约描述问题的归约描述l 初始问题集合:初始问题集合:初始问题集合:初始问题集合:初始状态集合初始状态集合初始状态集合初始状态集合 S Sl 算符集合:算符集合:算符集合:算符集合:将问题分解为若干子问题的变换集合将问题分解为若干子问题的变换集合将问题分解为若干子问题的变换集合将问题分解为若干子问题的变换集合F Fl 本原问题集合:本原问题集合:本原问题集合:本原问题集合:目标状态集合目标状态集合目标状态集合目标状态集合GG 本原问题:本原问题:本原问题:本原问题:具有明显解答的问题。如状态空间描具有明显解答的问题。如状
2、态空间描具有明显解答的问题。如状态空间描具有明显解答的问题。如状态空间描 述中述中述中述中走动一步可以解决走动一步可以解决走动一步可以解决走动一步可以解决的问题,或具有的问题,或具有的问题,或具有的问题,或具有已知解答已知解答已知解答已知解答 的复杂问题。的复杂问题。的复杂问题。的复杂问题。三元组合:三元组合:三元组合:三元组合:(S,F,GS,F,G)SFG“与与”或或“2)归约求解)归约求解一个问题可能存在多少归约算符?一个问题可能存在多少归约算符?一个问题可能存在多少归约算符?一个问题可能存在多少归约算符?规约多样性规约多样性规约多样性规约多样性子问题的可解算符如何寻找?子问题的可解算符
3、如何寻找?子问题的可解算符如何寻找?子问题的可解算符如何寻找?子问题的解空间搜索子问题的解空间搜索子问题的解空间搜索子问题的解空间搜索本原问题如何寻找?本原问题如何寻找?本原问题如何寻找?本原问题如何寻找?本原问题本原问题本原问题本原问题状态空间搜索?状态空间搜索?状态空间描述?状态空间描述?例例 “梵塔问题梵塔问题”一个僧侣在大佛前解决一个僧侣在大佛前解决一个僧侣在大佛前解决一个僧侣在大佛前解决“世界末日世界末日世界末日世界末日”问题问题问题问题 a a 初始状态初始状态初始状态初始状态 b b 目标状态目标状态目标状态目标状态 梵塔问题梵塔问题梵塔问题梵塔问题 梵塔问题求解过程梵塔问题求解
4、过程梵塔问题求解过程梵塔问题求解过程1 12 23 3A AB BC Cl状态空间描述:状态空间描述:状态空间描述:状态空间描述:三个盘子的位置列表三个盘子的位置列表三个盘子的位置列表三个盘子的位置列表(a,b,c)(a,b,c)(a,b,c)(a,b,c)a=1,2,3;b=1,2,3;c=1,2,3 a=1,2,3;b=1,2,3;c=1,2,3 a=1,2,3;b=1,2,3;c=1,2,3 a=1,2,3;b=1,2,3;c=1,2,3 初始状态:初始状态:初始状态:初始状态:S=(1,1,1)S=(1,1,1)S=(1,1,1)S=(1,1,1)目标状态:目标状态:目标状态:目标状态
5、:G=(3,3,3)G=(3,3,3)G=(3,3,3)G=(3,3,3)l算符集合:算符集合:算符集合:算符集合:Move(x,i,j)Move(x,i,j)Move(x,i,j)Move(x,i,j):x=A,B,C;i=1,2,3;j=1,2,3x=A,B,C;i=1,2,3;j=1,2,3x=A,B,C;i=1,2,3;j=1,2,3x=A,B,C;i=1,2,3;j=1,2,3l约束:约束:约束:约束:c=i,c=i,c=i,c=i,Move(x,j,iMove(x,j,i),),x=x=a,ba,b b=i,b=i,b=i,b=i,Move(x,j,iMove(x,j,i),x=a
6、),x=a 问题归约问题归约 双圆盘问题双圆盘问题双圆盘问题双圆盘问题:(111)(122)(111)(122)单圆盘问题单圆盘问题单圆盘问题单圆盘问题:(122)(322(122)(322)本原本原本原本原 双圆盘问题双圆盘问题双圆盘问题双圆盘问题:(322)(333(322)(333)双圆盘问题双圆盘问题双圆盘问题双圆盘问题:(k i i)(k j j)(k i i)(k j j)(k i i)(k i j)(k k j)(k k i)(k j i)(k i i)(k i j)(k k j)(k k i)(k j i)(k j j)(k j j)“梵塔难题梵塔难题”(111111)(122
7、)(322)(333)(113)(123)(122122)(321)(331)(333)“梵塔难题梵塔难题”(111.1111.1)(iii.iiii.i),),),),i=2,3i=2,3(111 i111 i)i=2,3 i=2,31 12 23 3N=1N=1(111 ii111 ii)i=2,3 i=2,3+2+2+2+22 2+2+24 4+2+26363 =2=264 64(iii iiiii ii)i=2,3 i=2,331558000秒秒/年年1片片/秒秒世界末日约世界末日约58万亿年万亿年3 3)与或图)与或图 A A N M H B C D E F或节点或节点或节点或节点与
8、节点与节点与节点与节点与或图节点定义与或图节点定义与或图节点定义与或图节点定义起始节点:原始问题状态;起始节点:原始问题状态;起始节点:原始问题状态;起始节点:原始问题状态;终叶节点:本原问题状态;终叶节点:本原问题状态;终叶节点:本原问题状态;终叶节点:本原问题状态;可解解点:可解解点:可解解点:可解解点:u终叶节点终叶节点终叶节点终叶节点u含有含有含有含有“或或或或”节点的节点的节点的节点的非非非非终叶节点,其所有后继终叶节点,其所有后继终叶节点,其所有后继终叶节点,其所有后继节点节点节点节点至少有一个可解至少有一个可解至少有一个可解至少有一个可解u含有含有含有含有“与与与与”节点的节点的
9、节点的节点的非非非非终叶节点,其终叶节点,其终叶节点,其终叶节点,其所有后继所有后继所有后继所有后继节点全部可解节点全部可解节点全部可解节点全部可解不可解节点:不可解节点:不可解节点:不可解节点:u没有后裔的没有后裔的没有后裔的没有后裔的非非非非终叶节点终叶节点终叶节点终叶节点u含有含有含有含有“或或或或”节点的节点的节点的节点的非非非非终叶节点,其终叶节点,其终叶节点,其终叶节点,其所有后继节所有后继节所有后继节所有后继节点全部点全部点全部点全部不不不不可解可解可解可解u含有含有含有含有“与与与与”节点的非终叶节点,其所有后继节节点的非终叶节点,其所有后继节节点的非终叶节点,其所有后继节节点
10、的非终叶节点,其所有后继节点点点点至少有一个至少有一个至少有一个至少有一个不不不不可解可解可解可解 解图:解图:解图:解图:一组构成初始问题解的可解节点组成的连通图一组构成初始问题解的可解节点组成的连通图一组构成初始问题解的可解节点组成的连通图一组构成初始问题解的可解节点组成的连通图起始节点起始节点起始节点起始节点终叶节点终叶节点终叶节点终叶节点4 4)问题归约举例)问题归约举例 例:例:例:例:符号积分:对于任意不定积分给出正确解答符号积分:对于任意不定积分给出正确解答符号积分:对于任意不定积分给出正确解答符号积分:对于任意不定积分给出正确解答“与与”节点节点“或或”节点节点积分归约形式积分
11、归约形式积分归约形式积分归约形式初始问题:求解不定积分初始问题:求解不定积分本原问题:简单积分本原问题:简单积分问题解答:问题解答:问题:求解过程的问题:求解过程的任何一步任何一步都有许多可应用都有许多可应用的归约替代算符,的归约替代算符,算符选择算符选择需要启发信息需要启发信息 5 5)归约方法)归约方法 归约原理:归约原理:归约原理:归约原理:将状态搜索问题归约为越来越简单将状态搜索问题归约为越来越简单将状态搜索问题归约为越来越简单将状态搜索问题归约为越来越简单的搜索问题,直至所有问题归约为本原问题的搜索问题,直至所有问题归约为本原问题的搜索问题,直至所有问题归约为本原问题的搜索问题,直至
12、所有问题归约为本原问题 复杂问题规划为简单问题的集合复杂问题规划为简单问题的集合复杂问题规划为简单问题的集合复杂问题规划为简单问题的集合 (S,F,GS,F,GS,F,GS,F,G)=(S,F,g=(S,F,g=(S,F,g=(S,F,g1 1 1 1),(g),(g),(g),(g1 1 1 1,F,g,F,g,F,g,F,g2 2 2 2),),),),(g (g (g (gn n n n,F,G),F,G),F,G),F,G)路标:路标:路标:路标:g g g g1 1 1 1,g,g,g,g2 2 2 2,g,g,g,gn n n n g g g g1 1 1 1 G G G G1 1
13、 1 1,g,g,g,g2 2 2 2 G G G G2 2 2 2,.g,.g,.g,.gn n n n G G G Gn n n nSFG(S,F,G)=(S,F,Gf)()(f(g),),F,G)g1g2g3g4 关键算符:关键算符:关键算符:关键算符:问题求解中具有决定性作用的算符问题求解中具有决定性作用的算符问题求解中具有决定性作用的算符问题求解中具有决定性作用的算符 求解过程中必定使用的步骤求解过程中必定使用的步骤求解过程中必定使用的步骤求解过程中必定使用的步骤 设:设:设:设:f f f f F F F F为关键算符为关键算符为关键算符为关键算符 G G G Gf f f f -
14、路标集合,路标集合,路标集合,路标集合,g g g g G G G Gf f f f f(g)-f(g)-f(g)-f(g)-关键算符关键算符关键算符关键算符f f f f作用于作用于作用于作用于g g g g的结果的结果的结果的结果(S,F,G)(S,F,Gf)(f(g),F,G)(f(g),F,G)关键算符作用关键算符作用 差别:差别:差别:差别:当前状态与目标状态的距离当前状态与目标状态的距离当前状态与目标状态的距离当前状态与目标状态的距离 候选算符:候选算符:候选算符:候选算符:对应差别的状态空间算符或算符集合对应差别的状态空间算符或算符集合对应差别的状态空间算符或算符集合对应差别的状
15、态空间算符或算符集合 例例例例 猴子与香蕉问题猴子与香蕉问题猴子与香蕉问题猴子与香蕉问题 S=(a,0,b,0),G=(c,1,c,1)S=(a,0,b,0),G=(c,1,c,1)S=(a,0,b,0),G=(c,1,c,1)S=(a,0,b,0),G=(c,1,c,1)算符集合:算符集合:算符集合:算符集合:f f1 1=goto(U)=goto(U)(a,0,b,0)goto(U)(U,0,b,0)(a,0,b,0)goto(U)(U,0,b,0)f f2 2=pushbox(V)=pushbox(V)(b,0,b,0)pushbox(V)(V,0,V,0)(b,0,b,0)pushbo
16、x(V)(V,0,V,0)f f3 3=climbbox=climbbox (V,0,V,0)climbbox (V,1,V,0)(V,0,V,0)climbbox (V,1,V,0)f f4 4=grasp=grasp (c,1,c,0)grasp (c,1,c,1)(c,1,c,0)grasp (c,1,c,1)如何寻找关键算符?如何寻找关键算符?如何寻找关键算符?如何寻找关键算符?(a,0,b,0),(c,1,c,1)(f(f4 4(g(g4 4),G),G)(a,0,b,0),(c,1,c,0),g4 Gf4f4(a,0,b,0),(c,0,c,0)g3 Gf3f3(f f3 3(g(
17、g3 3),),Gf3)(f(f1 1(g(g2 2),),Gf2)(a,0,b,0),(b,0,b,0)g2 Gf2f2(a,0,b,0),(a,0,b,0)g1 Gf1(f(f3 3(g(g1 1),),Gf1)f2(a,0,b,0),Gf2)g2 Gf2(f(f1 1(g(g2 2),),Gf2)(b,0,b,0),Gf1)g1 Gf1(f(f1 1(g(g1 1),),Gf1)f112345f16)与或图搜索与或图搜索 搜索过程:搜索过程:l起始节点起始节点起始节点起始节点(根根根根)对应于初始问题描述对应于初始问题描述对应于初始问题描述对应于初始问题描述l后继节点(后继节点(后继节点
18、(后继节点(后裔后裔后裔后裔)用归约算符求得()用归约算符求得()用归约算符求得()用归约算符求得(启发信息启发信息启发信息启发信息)l每个后裔设置一个来自父辈节点的指针(每个后裔设置一个来自父辈节点的指针(每个后裔设置一个来自父辈节点的指针(每个后裔设置一个来自父辈节点的指针(用来用来用来用来表示可解或不可解节点走向,并指明一个从根表示可解或不可解节点走向,并指明一个从根表示可解或不可解节点走向,并指明一个从根表示可解或不可解节点走向,并指明一个从根到终叶的解图到终叶的解图到终叶的解图到终叶的解图)l 不断扩展节点和设置指针,直至起始节点能被不断扩展节点和设置指针,直至起始节点能被不断扩展节
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 问题规约法 问题 规约 PPT 课件
限制150内