《问题规约法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
5、, 1, 1)S = (1, 1, 1)S = (1, 1, 1) 目标状态：目标状态：目标状态：目标状态：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,
6、3l约束：约束：约束：约束： c=i,c=i,c=i,c=i, Move(x,j,i),Move(x,j,i), x=a,bx=a,b b=i, b=i, b=i, b=i, Move(x,j,i), x=aMove(x,j,i), x=a 问题归约问题归约 双圆盘问题双圆盘问题双圆盘问题双圆盘问题 : : (111) (111) (122) (122) 单圆盘问题单圆盘问题单圆盘问题单圆盘问题 : : (122) (322(122) (322） 本原本原本原本原 双圆盘问题双圆盘问题双圆盘问题双圆盘问题 : : (322) (333(322) (333） 双圆盘问题双圆盘问题双圆盘问题双圆盘
7、问题 : : (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）（322）（333）（113）（123）（122122）（321）（331）（333） “梵塔难题梵塔难题”（111. 1111. 1） （iii. iiii. i），），），），i=2,3i=2,3（111 i111 i） i=2,3i=2,31 12 23 3N=1N=1（111
8、ii111 ii） i=2,3i=2,3+2+2+2+22 2+2+24 4+2+26363 =2=264 64 -1=18446744073709551615-1=18446744073709551615（iii iiiii ii） i=2,3i=2,331558000秒秒/年年1片片/秒秒世界末日约世界末日约58万亿年万亿年3 3）与或图）与或图 A A N M H B C D E F或节点或节点或节点或节点与节点与节点与节点与节点与或图节点定义与或图节点定义与或图节点定义与或图节点定义起始节点：原始问题状态；起始节点：原始问题状态；起始节点：原始问题状态；起始节点：原始问题状态；终叶节点
9、：本原问题状态；终叶节点：本原问题状态；终叶节点：本原问题状态；终叶节点：本原问题状态； 可解解点：可解解点：可解解点：可解解点：u终叶节点终叶节点终叶节点终叶节点u含有含有含有含有 “ “或或或或” ” 节点的节点的节点的节点的非非非非终叶节点，其所有后终叶节点，其所有后终叶节点，其所有后终叶节点，其所有后继节点继节点继节点继节点至少有一个可解至少有一个可解至少有一个可解至少有一个可解u含有含有含有含有“ “与与与与” ” 节点的节点的节点的节点的非非非非终叶节点，其终叶节点，其终叶节点，其终叶节点，其所有后继所有后继所有后继所有后继节点全部可解节点全部可解节点全部可解节点全部可解不可解节点
10、：不可解节点：不可解节点：不可解节点：u没有后裔的没有后裔的没有后裔的没有后裔的非非非非终叶节点终叶节点终叶节点终叶节点u含有含有含有含有“ “或或或或” ”节点的节点的节点的节点的非非非非终叶节点，其终叶节点，其终叶节点，其终叶节点，其所有后继节所有后继节所有后继节所有后继节点全部点全部点全部点全部不不不不可解可解可解可解u含有含有含有含有“ “与与与与” ”节点的非终叶节点，其所有后继节节点的非终叶节点，其所有后继节节点的非终叶节点，其所有后继节节点的非终叶节点，其所有后继节点点点点至少有一个至少有一个至少有一个至少有一个不不不不可解可解可解可解 解图：解图：解图：解图： 一组构成初始问题
11、解的可解节点组成的连通图一组构成初始问题解的可解节点组成的连通图一组构成初始问题解的可解节点组成的连通图一组构成初始问题解的可解节点组成的连通图起始节点起始节点起始节点起始节点终叶节点终叶节点终叶节点终叶节点4 4）问题归约举例）问题归约举例 例：例：例：例：符号积分：对于任意不定积分给出正确解答符号积分：对于任意不定积分给出正确解答符号积分：对于任意不定积分给出正确解答符号积分：对于任意不定积分给出正确解答“与与”节点节点“或或”节点节点积分归约形式积分归约形式积分归约形式积分归约形式初始问题：求解不定积分初始问题：求解不定积分本原问题：简单积分本原问题：简单积分问题解答：问题解答： 问题：
12、求解过程的问题：求解过程的任何一步任何一步都有许多可应用都有许多可应用的归约替代算符，的归约替代算符，算符选择算符选择需要启发信息需要启发信息 5 5）归约方法）归约方法 归约原理：归约原理：归约原理：归约原理：将状态搜索问题归约为越来越简单将状态搜索问题归约为越来越简单将状态搜索问题归约为越来越简单将状态搜索问题归约为越来越简单的搜索问题，直至所有问题归约为本原问题的搜索问题，直至所有问题归约为本原问题的搜索问题，直至所有问题归约为本原问题的搜索问题，直至所有问题归约为本原问题 复杂问题规划为简单问题的集合复杂问题规划为简单问题的集合复杂问题规划为简单问题的集合复杂问题规划为简单问题的集合
13、（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 1 1,g,g,g,g2 2 2 2 G G G G2 2 2 2,
14、, , , .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 - - - - 路标集合，路标集合，路标集合，路标集合，g g
15、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 )关键算符作用关键算符作用 差别：差别：差别：差别：当前状态与目标状态的距离当前状态与目标状态的距离当前状态与目标状态的距离当前状态与目标状态的距离 候选算符：候选算符：候选算符：候选算符：对应差别的状态空间算符或算符集合对应差别的状态空间算符或算符集合对应差别的状态空间算符或算符集合对应
16、差别的状态空间算符或算符集合 例例例例 猴子与香蕉问题猴子与香蕉问题猴子与香蕉问题猴子与香蕉问题 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=
17、pushbox(V)=pushbox(V) (b,0,b,0) pushbox(V) (V,0,V,0)(b,0,b,0) pushbox(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(
18、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(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
19、) 与或图搜索与或图搜索 搜索过程：搜索过程：l起始节点起始节点起始节点起始节点( (根根根根) )对应于初始问题描述对应于初始问题描述对应于初始问题描述对应于初始问题描述l后继节点（后继节点（后继节点（后继节点（后裔后裔后裔后裔）用归约算符求得（）用归约算符求得（）用归约算符求得（）用归约算符求得（启发信息启发信息启发信息启发信息）l每个后裔设置一个来自父辈节点的指针（每个后裔设置一个来自父辈节点的指针（每个后裔设置一个来自父辈节点的指针（每个后裔设置一个来自父辈节点的指针（用来用来用来用来表示可解或不可解节点走向，并指明一个从根表示可解或不可解节点走向，并指明一个从根表示可解或不可解节点走
20、向，并指明一个从根表示可解或不可解节点走向，并指明一个从根到终叶的解图到终叶的解图到终叶的解图到终叶的解图）l 不断扩展节点和设置指针，直至起始节点能被不断扩展节点和设置指针，直至起始节点能被不断扩展节点和设置指针，直至起始节点能被不断扩展节点和设置指针，直至起始节点能被标为可解或不可解节点为止标为可解或不可解节点为止标为可解或不可解节点为止标为可解或不可解节点为止 搜索策略（搜索策略（搜索策略（搜索策略（搜索过程控制搜索过程控制搜索过程控制搜索过程控制）l 宽度优先搜索宽度优先搜索宽度优先搜索宽度优先搜索l 深度优先搜索：扩展深度界限内的节点深度优先搜索：扩展深度界限内的节点深度优先搜索：扩
21、展深度界限内的节点深度优先搜索：扩展深度界限内的节点l 与或树有序搜索与或树有序搜索与或树有序搜索与或树有序搜索 搜索费用（搜索费用（搜索费用（搜索费用（搜索效率评估搜索效率评估搜索效率评估搜索效率评估）l 总和费用：解树上所有弧线费用之和总和费用：解树上所有弧线费用之和总和费用：解树上所有弧线费用之和总和费用：解树上所有弧线费用之和l 最大费用：解树中最大路径费用之和最大费用：解树中最大路径费用之和最大费用：解树中最大路径费用之和最大费用：解树中最大路径费用之和l 单位弧线：费用为单位弧线：费用为单位弧线：费用为单位弧线：费用为1 1 1 1的弧线的弧线的弧线的弧线( ( ( (单位弧线构成
22、的单位弧线构成的单位弧线构成的单位弧线构成的解树中，总和费用为解树中，总和费用为解树中，总和费用为解树中，总和费用为节点数节点数节点数节点数-1-1-1-1；最大费用为解；最大费用为解；最大费用为解；最大费用为解树中最大串步度量树中最大串步度量树中最大串步度量树中最大串步度量) ) ) ) 例例例例 已知两个解树如图，求这两个解树的已知两个解树如图，求这两个解树的已知两个解树如图，求这两个解树的已知两个解树如图，求这两个解树的总和费用总和费用总和费用总和费用及及及及最大费用最大费用最大费用最大费用两个解树及其费用两个解树及其费用 456A5634712Btttt解树A：总和费用20；最大费用1
23、5解树B：总和费用18；最大费用17 最优解树（最优解树（最优解树（最优解树（搜索结果搜索结果搜索结果搜索结果） 最小费用的解树（最小费用的解树（总和费用或最大费用总和费用或最大费用） AOAO* *算法算法算法算法 定义费用：定义费用：定义费用：定义费用： h h* *(S)(S) - - 以起始节点以起始节点以起始节点以起始节点S S S S为根的最优解树费用为根的最优解树费用为根的最优解树费用为根的最优解树费用 h h* *(n)(n)- 以任意节点以任意节点以任意节点以任意节点n n n n为根的解树最小费用为根的解树最小费用为根的解树最小费用为根的解树最小费用 h h h h* *(
24、S)(S)(S)(S)由由由由h h h h* *(n)(n)(n)(n)递归确定递归确定递归确定递归确定最小费用解树最小费用解树S h*(S)h*(n) h h h h* * * *(n)(n)(n)(n)性质性质性质性质l ln n n n为终叶节点为终叶节点为终叶节点为终叶节点,h,h,h,h* * * *(n)=0(n)=0(n)=0(n)=0l ln n含有含有含有含有“ “或或或或” ” 后继节点后继节点后继节点后继节点 n ni i (i=1,2,k) (i=1,2,k) ，所有，所有，所有，所有后继节点的最小后继节点的最小后继节点的最小后继节点的最小/ /大费用为：大费用为：大
25、费用为：大费用为：l ln n含有含有含有含有“ “与与与与” ” 后继节点后继节点后继节点后继节点n ni i (i=1,2,k)(i=1,2,k) ，所有，所有，所有，所有后继节点的总和费用为：后继节点的总和费用为：后继节点的总和费用为：后继节点的总和费用为：h*(n)n1 n2 n3 n4 nkh*(ni)l n n n n不可解，不可解，h*(n)h*(n)不定不定（无定义）（无定义）l n n n n可解，则可解，则可解，则可解，则h*(n)h*(n)h*(n)h*(n)有限有限有限有限 超图超图:K-:K-链接的与或图链接的与或图( (不仅仅由单纯的与节点不仅仅由单纯的与节点和或节
26、点组成和或节点组成) )2-2-2-2-2- 解图的递归解图的递归G递归指由简单的基本情况定义的一类对递归指由简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被象或方法，并规定其他所有情况都能被还原为其基本情况还原为其基本情况典型的递归典型的递归斐波那契数列斐波那契数列Fib(0) = 0 基本情况基本情况 Fib(1) = 1 基本情况基本情况 递归定义递归定义Fib(n) = (Fib(n-1) + Fib(n-2)， n 1建立建立G G仅包含仅包含S Sq(s)=h(s)q(s)=h(s)S可解？可解？Y成功成功N选选择择任任意意n ni i，生生成成全全部部后后裔裔n nj
27、 j放放入入G G，q(nq(nj j)=h)=h(n(nj j) )nj可解？可解？Y标记标记n nj j可解可解h(nh(nj j)=0)=0N选选择择后后裔裔在在G G中中的的节节点点m m，q qi i(m)=c(m)=ci i+q(n+q(n1i1i)+q(n)+q(n2i2i)+)+ +q+q(n(nkiki) )q(m)=minq(m)=minqi(m) nij可解？可解？m m可可解解, ,修修正正父父辈费用辈费用YN AO AO*算法的可纳性：算法的可纳性：如果从给定节点到一组节如果从给定节点到一组节点存在一个解图，且对所有节点满足：点存在一个解图，且对所有节点满足： h(n
28、)h(n) h h* *(n)(n)，h 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（终叶结点终叶结点） 画出不同循环次数的画出不同循环次数的AOAO*算法搜索图算法搜索图 AOAO*算法四次循环得到的最优解图算法四次循环得到的最优解图113n1n5n42n34n244n62n7n80025 5第一次循环第一次循环第二次循环第二次循环第三次循环第三次循环第四次
29、循环第四次循环n011n5n42n8007 7 7 7）博弈树搜索）博弈树搜索）博弈树搜索）博弈树搜索 博弈与博弈图博弈与博弈图博弈与博弈图博弈与博弈图 双人完备博弈：双人完备博弈：双人完备博弈：双人完备博弈：两选手对垒，轮流依次走步，其两选手对垒，轮流依次走步，其两选手对垒，轮流依次走步，其两选手对垒，轮流依次走步，其中一方完全知道对方已经走过的棋步和今后可能中一方完全知道对方已经走过的棋步和今后可能中一方完全知道对方已经走过的棋步和今后可能中一方完全知道对方已经走过的棋步和今后可能的走步。的走步。的走步。的走步。结果：一方赢，另一方输，平局。结果：一方赢，另一方输，平局。结果：一方赢，另一
30、方输，平局。结果：一方赢，另一方输，平局。 随机博弈：随机博弈：随机博弈：随机博弈：不考虑结果，取决于机遇的博弈。不考虑结果，取决于机遇的博弈。不考虑结果，取决于机遇的博弈。不考虑结果，取决于机遇的博弈。 博弈图：博弈中应用规则寻找走步路线的图博弈图：博弈中应用规则寻找走步路线的图博弈图：博弈中应用规则寻找走步路线的图博弈图：博弈中应用规则寻找走步路线的图 例例例例 “ “grundygrundygrundygrundy博弈博弈博弈博弈” ”。一堆硬币，一位选手将硬币。一堆硬币，一位选手将硬币。一堆硬币，一位选手将硬币。一堆硬币，一位选手将硬币分为不等的两堆；然后，两选手轮流分，直到某一分为不
31、等的两堆；然后，两选手轮流分，直到某一分为不等的两堆；然后，两选手轮流分，直到某一分为不等的两堆；然后，两选手轮流分，直到某一堆只剩一个或两个硬币为止。首先遇到这种情况的堆只剩一个或两个硬币为止。首先遇到这种情况的堆只剩一个或两个硬币为止。首先遇到这种情况的堆只剩一个或两个硬币为止。首先遇到这种情况的选手输。选手输。选手输。选手输。 解：设共解：设共解：设共解：设共7 7 7 7个硬币，两选手分别为个硬币，两选手分别为个硬币，两选手分别为个硬币，两选手分别为 MAX, MINMAX, MINMAX, MINMAX, MIN 状态空间描述：状态空间描述：状态空间描述：状态空间描述：（数字（数字（
32、数字（数字1 1 1 1，数字，数字，数字，数字2 2 2 2，说明，说明，说明，说明) ) ) ) 数字数字数字数字i-i-i-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）
33、（4,2,1,MIN） 博弈树搜索的极大极小过程博弈树搜索的极大极小过程 几个概念几个概念 简单博弈简单博弈简单博弈简单博弈：棋类的残局棋类的残局棋类的残局棋类的残局 复杂博弈：复杂博弈：复杂博弈：复杂博弈：不可能搜索的终局不可能搜索的终局不可能搜索的终局不可能搜索的终局 国际象棋博弈树国际象棋博弈树国际象棋博弈树国际象棋博弈树1010120120个节点，若个节点，若个节点，若个节点，若1/31/3纳秒生成一个后纳秒生成一个后纳秒生成一个后纳秒生成一个后继节点，生成国际象棋的博弈树大约需要继节点，生成国际象棋的博弈树大约需要继节点，生成国际象棋的博弈树大约需要继节点，生成国际象棋的博弈树大约需
34、要10102121个世个世个世个世纪纪纪纪 目标：目标：目标：目标：搜索一步好棋搜索一步好棋搜索一步好棋搜索一步好棋 不断修改终局条件不断修改终局条件不断修改终局条件不断修改终局条件 搜索限制：搜索限制：搜索限制：搜索限制：时间、存储空间、节点深度时间、存储空间、节点深度时间、存储空间、节点深度时间、存储空间、节点深度 静态估价函数：静态估价函数：静态估价函数：静态估价函数：有利于有利于有利于有利于MAXMAXMAXMAX估价为估价为估价为估价为正正正正，有利于，有利于，有利于，有利于MINMINMINMIN估价为估价为估价为估价为负负负负，平手估价为，平手估价为，平手估价为，平手估价为0 0
35、 0 0 极大极小过程极大极小过程极大极小过程极大极小过程 ：利用静态评估函数寻找最佳棋路利用静态评估函数寻找最佳棋路利用静态评估函数寻找最佳棋路利用静态评估函数寻找最佳棋路的过程。的过程。的过程。的过程。 例例 一字棋一字棋 规则：先在横、竖、对角线排成一字者规则：先在横、竖、对角线排成一字者赢赢 解：令解：令 MAX- MIN - P- 位置位置静态评估函数：静态评估函数：e(P) = MAXe(P) = MAX空位置空位置-MIN-MIN空位置空位置e(P) = e(P) = - P - P为为MAXMAX的获胜位置的获胜位置e(P) = e(P) = - - - P - P为为MINM
36、IN的获胜位置的获胜位置e(P) = MAX空位置空位置-MIN空位置空位置 = 6 4 =2 MAX MAX胜算更大！胜算更大！ 棋盘位置对称性：棋盘位置对称性：图图2-2-13 2-2-13 一字棋极大一字棋极大- -极小搜索过程第一阶段极小搜索过程第一阶段4-5=-16-5=1 5-5=0 6-5=15-5=0-15-6= -15-5= 05-6= -16-6= 04-6= -2-25-4=16-4=21图图2-2-14 2-2-14 一字棋极大一字棋极大- -极小搜索过程第二阶段极小搜索过程第二阶段4-2=2 3-2=15-2=33-2=14-2=2 3-2=114-3=13-3=05
37、-3=23-3=04-3=13-2=14-2=2 4-2=25-2=33-2=14-2=2 4-2=24-3=14-3=13-3=00 010 0图图2-2-15 2-2-15 一字棋极大一字棋极大- -极小搜索过程第三阶段极小搜索过程第三阶段2-1=1 3-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 2）过程过程: :极大极小搜索的优化算法极大极小搜索的优化算法 -1-1-1-1=-1 +1 1 1=-10 0 0 0 0 0 0 0 = 0 +1 2 2 1 1 1 1 1
38、 1 1 1 2 2 0 0 2 2 1 1 = 2 1 1 2 2 2 1 1 1 0 -1 = = 0 0计算方法：计算方法：MAXMAX节点的节点的值等于其后继节点当前最值等于其后继节点当前最大大的最终倒的最终倒退值退值MINMIN节点的节点的值等于其后继节点当前最值等于其后继节点当前最小小的最终倒的最终倒退值退值特点：特点：MAXMAX节点的节点的值永不减少值永不减少MINMIN节点的节点的值永不增加值永不增加终止搜索规则：终止搜索规则： 任何任何MAXMAX节点的节点的值大于或值大于或等于它的祖先等于它的祖先节点节点MINMIN的的值，则可以终止该值，则可以终止该MAXMAX节点以节点以下的搜索。下的搜索。任何任何MINMIN节点的节点的值小于或值小于或等于它的祖先等于它的祖先MAXMAX节点节点的的值，则可以终止该值，则可以终止该MINMIN节点以节点以下的搜索。下的搜索。
