人工智能搜索2

1、4.3问题归约法问题归约法n归约归约(Reduction)问题：现有煤气灶、水龙头、水壶和火柴，问题：现有煤气灶、水龙头、水壶和火柴，你怎样烧水？你怎样烧水？答：向水壶中注满水，把水壶放在煤气灶上，答：向水壶中注满水，把水壶放在煤气灶上，擦火柴点燃煤气灶。擦火柴点燃煤气灶。 问题可转化为：在四个单位正方形内，任意放置5个点，至少有两个点在同一正方形内。例2 n在边长为2的正方形内，任意放置5个点，求证其中必存在两个点，它们之间的距离不大于2。. . . . . IIIII123I例3:假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积。求解步骤：求五边形面积求 1面积求 2面积求 3面

2、积求 I面积求 II面积求 III面积求 面积求 面积求 面积123IIIIIIn本原问题本原问题n可直接得到答案的问题称为本原问题可直接得到答案的问题称为本原问题n例例1中的原始的烧水问题中的原始的烧水问题n例例2中根据鸽巢原理直接可回答的问题中根据鸽巢原理直接可回答的问题n例例3中求矩形面积的问题中求矩形面积的问题n归约法归约法n把原问题转化把原问题转化(分解分解)为一个或几个子问题，为一个或几个子问题，对子问题再归约，直至成为可以直接求解对子问题再归约，直至成为可以直接求解的本原问题。的本原问题。问题归约问题归约n复杂问题的解决方法复杂问题的解决方法n问题归约问题归约:n含义含义: 把复

3、杂问题转换为若干需要同时处理的较为把复杂问题转换为若干需要同时处理的较为简单的子问题后再加以分别求解的策略简单的子问题后再加以分别求解的策略,可以递归可以递归地进行地进行,直到把问题转换为本原问题的集合直到把问题转换为本原问题的集合.n方法方法: 分解分解,变换变换4.3.1与与/或图的表示法或图的表示法n与或图是一个超图，节点间通过连接符连接。nK-连接符：.K个n与或图表示法与或图表示法n与节点与节点n将一个问题分解为若干子问将一个问题分解为若干子问题，题， 所有的子问题有解，原所有的子问题有解，原问题才有解。问题才有解。nK-联接符联接符n与节点与节点n将一个问题转化为若干子问将一个问题

4、转化为若干子问题，只要一个子问题有解，题，只要一个子问题有解，原问题就有解。原问题就有解。n单线联接符单线联接符AP1P2PkP1P2Pk与或图的表示法与或图的表示法n与或图的构成n与节点：分解问题n或节点：变换问题n弧:相关节点的联结n终止节点：本原问题与或图表示法特点与或图表示法特点n与或图表示问题特点与或图表示问题特点n可分解的问题可分解的问题n可变换的问题可变换的问题n例：如何上班问题例：如何上班问题n开自家车开自家车n车况好（自己修车，他人修车）车况好（自己修车，他人修车）n足够燃料（车开到加油站，自带燃料）足够燃料（车开到加油站，自带燃料）n步行步行n身体状况好身体状况好n足够的时

5、间足够的时间n公交车公交车n步行到车站步行到车站n骑车到车站骑车到车站n例：如何上班问题例：如何上班问题 上班问题上班问题开自家车开自家车步行步行乘公交车乘公交车车况好车况好燃料足燃料足他人修他人修自己修自己修他人修他人修加油站加油站自带燃油自带燃油燃油箱燃油箱身体好身体好时间够时间够步行到车站步行到车站骑车到车站骑车到车站n与或图表示法与或图表示法n与节点，或节点与节点，或节点n终止节点终止节点:本原问题本原问题n端节点端节点:无子节点的节点无子节点的节点可解节点定义：可解节点定义： n（1）终止节点是可解节点（因为它们与本原）终止节点是可解节点（因为它们与本原问题相关联）问题相关联）n（2

6、）如果某个非叶节点是含有或后继节点，）如果某个非叶节点是含有或后继节点，那么只有当后继节点至少有一个是可解的时，那么只有当后继节点至少有一个是可解的时，此非叶节点才是可解的。此非叶节点才是可解的。n（3）如果某个非终止节点含有与后继节点，）如果某个非终止节点含有与后继节点，那么只要当其后继节点全部为可解时，此非那么只要当其后继节点全部为可解时，此非终止节点才是可解的。终止节点才是可解的。不可解节点定义：不可解节点定义： n（1）没有后裔的非终止节点为不可解节点）没有后裔的非终止节点为不可解节点n（2）如果某个非终止节点含有或后继节点，）如果某个非终止节点含有或后继节点，那么只要当其全部后裔为不

7、可解时，此非终那么只要当其全部后裔为不可解时，此非终止节点才是不可解节点止节点才是不可解节点n（3）如果某个非终止节点含有与后继节点，）如果某个非终止节点含有与后继节点，那么只要当其后裔至少有一个为不可解节点那么只要当其后裔至少有一个为不可解节点时，此非终止节点才是不可解的时，此非终止节点才是不可解的n与或图解图与或图解图1可解节点可解节点23B端节点（不可扩展节点）端节点（不可扩展节点）54t1At2t3t4终止节点终止节点n问题归约举例: 上班问题开自家车步行车况好燃料足自己修他人修加油站自带燃油燃油箱身体好时间够步行到车站骑车到车站上班问题乘公交车问题归约举例问题归约举例(“梵塔梵塔”问

8、题问题)3阶阶“梵塔梵塔”问题问题(Tower of Hanoi Problem):n有三个柱子有三个柱子(1，2和和3)和两个不同尺寸的圆盘和两个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上在柱子上,最初最初,全部三个圆盘都堆在柱子全部三个圆盘都堆在柱子1上上(最大的最大的在底部在底部,最小的在顶部最小的在顶部)。要求把所有。要求把所有 圆盘都移到另圆盘都移到另一个柱子上，搬动规则为：一个柱子上，搬动规则为： (1)一次只能搬一个圆盘一次只能搬一个圆盘 (2)不能将大圆盘放在小圆盘上不能将大圆盘放在小圆盘上 (3)可

9、以利用空柱子。可以利用空柱子。n用问题分解方法来描述问题用问题分解方法来描述问题：n状态的表示n柱的编号用i,j,k来代表 (i,j,k)表示问题的状态其中: i代表A所在的柱子, j 代表B所在的柱子，k代表C所在的柱子n初始状态(1,1,1)，目标状态(2,2,2) (3,3,3,)(1,1,1)132C(2,2,2)123AB(3,3,3)123ABABCCn初始状态(1,1,1)，目标状态 (3,3,3,)n分解的关键状态(1,2,2)132C(3,2,2)123AB(3,3,3)123ABABCCn3阶“梵塔”问题与或图方法(1,1,1)(3,3,3)(1,1,1)(1,2,2) (

10、1,2,2)(3,2,2)(3,2,2)(3,3,3)(1,1,1)(1,1,3) (1,2,3)(1,2,2)(1,1,3)(1,2,3)(3,2,2)(3,3,3)(3,2,2)(3,2,1)(3,3,1)(3,3,3)4.3.2 与或图的搜索与或图的搜索n与或图搜索的一般过程与或图搜索的一般过程n可解标示过程与不可解标示过程可解标示过程与不可解标示过程n与或图的基本搜索方法与或图的基本搜索方法n与或图搜索与图搜索的不同与或图搜索与图搜索的不同耗散值耗散值(代价代价)k(n, N) = Cn+k(n1, N)+k(ni, N)其中：其中：N为终节点集为终节点集 Cn为连接符的耗散值为连接符

11、的耗散值.i个个nn1n2nin例例n5n6non2n3n4n7n8n1与或树搜索的一般过程与或树搜索的一般过程n基本思想：基本思想：n扩展（自上而下）扩展（自上而下）n标示（自下而上）标示（自下而上）n结束条件：初始节点为可解或不可解结束条件：初始节点为可解或不可解n搜索过程：搜索过程：（1 1）把原始问题作为初始节点）把原始问题作为初始节点S0,S0,并将其作为当前节点并将其作为当前节点（2 2）按解图生成的方法按解图生成的方法,分步生成候选的局部解图集分步生成候选的局部解图集,从中选择从中选择局部解图局部解图 扩展，同时使用标示过程扩展，同时使用标示过程对当前节点进行扩展对当前节点进行扩

12、展（3 3）为每个子节点设置指向父节点的指针）为每个子节点设置指向父节点的指针（4 4）用适当的策略（宽度深度启发式）选择）用适当的策略（宽度深度启发式）选择局部解图扩展局部解图扩展,反复反复应用（应用（2 2）（）（3 3）步，在此期间要多次应用可解标示过程和不）步，在此期间要多次应用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节可解标示过程，直到初始节点被标示为可解节点或不可解节点。点。n可解与不可解标示过程可解与不可解标示过程n可解标示过程：由可解子节点来确定父节可解标示过程：由可解子节点来确定父节点，祖父节点等为可解节点的过程点，祖父节点等为可解节点的过程n不可解

13、标示过程：由不可解子节点来确定不可解标示过程：由不可解子节点来确定父节点，祖父节点等为不可解节点的过程父节点，祖父节点等为不可解节点的过程n与或树的搜索方法分类与或树的搜索方法分类n盲目搜索盲目搜索n启法式搜索启法式搜索n有序搜索有序搜索n博奕树博奕树与或图搜索与图搜索的不同与或图搜索与图搜索的不同n终止搜索的条件不同 n对已生成结点处理不同 n结果不同 n例 梵塔问题4.3.3与或图的启发式搜索与或图的启发式搜索n局部图局部图n局部图定义局部图定义n局部图代价计算举例局部图代价计算举例n希望图希望图n基本思想基本思想n搜索算法使用的数据结构搜索算法使用的数据结构n与或图的启发式搜索方法与或图

14、的启发式搜索方法n解图的代价:k(n,N)nn是局部图中的一个叶节点是局部图中的一个叶节点, 则则 k(n,N)=h(n)nn是是K-连接节点连接节点, n1,n2,.ni是它的子节点,k(n,N)=Cn+k(n1,N)+h(n2,N)+.+k(ni,N)n例例n例（局部解图的计算例（局部解图的计算Cn=k,h值如图）值如图）S0(9)A(8)B(3)D(11)C(3)E(7)F(2)n希望图希望图：在搜索过程中任一时刻求出的局部解图其代价都是最小的。这个局部解图即是希望图n例例A(8)D(7)C(3)E(3)F(2)h(S0)=8B(3)f(S0)=9n例（局部解图的计算Cn=k）S0（8）

15、A(8)B(3)D(7)C(3)E(3)F(2)基本思想基本思想n目标：寻找最小代价的解树，最优解图(树)n方法：按解图生成的方法,分步生成局部解图,重新计算节点的耗散值（代价）, 从中选择一个代价最小的局部解图用于扩展，同时使用标示过程。搜索算法使用的数据结构搜索算法使用的数据结构n基本数据结构基本数据结构 nG: 搜索图搜索图nG: 被选中的待扩展局部解图被选中的待扩展局部解图(希望图希望图)nS: 待重新估值的节点集合待重新估值的节点集合ns: 根节点根节点,即初始状态节点即初始状态节点nn: 被选中的待扩展节点被选中的待扩展节点n连结符标记（指针），扩展指针连结符标记（指针），扩展指针

16、估价函数估价函数hn设设h*(n)是从搜索图中一个节点是从搜索图中一个节点n到一个终节到一个终节点集合的一个解图的实际耗散值点集合的一个解图的实际耗散值, h(n)是对是对h*(n)的估计的估计. 若在若在n的一个解图中的一个解图中, n有有k个与个与后继节点后继节点n1, nk, 且且 h(n) C(n)+h(n1)+ +h(nk) 其中其中, C(n)为为k连接符的连接符的(总总)耗散值耗散值, 又若又若n为为终节点终节点, 则则h(n)=0, 则我们称则我们称h(n)满足单调满足单调限制限制. 可证可证, 对于所有节点有对于所有节点有h(n) h*(n), 即即h是是h*的下界的下界.n

17、举例说明举例说明nAO*算法算法n若若h(n)满足单调限制满足单调限制, 则下面的与或则下面的与或图搜索算法称为图搜索算法称为AO*算法算法(1)建立一个搜索图建立一个搜索图G, 使其仅包含起始节点使其仅包含起始节点S, 对应对应 于节点于节点S的费用为的费用为q(S)=h(S), 如如S为终节点为终节点, 则则标记标记S为为SOLVED(2)until S已标记为已标记为SOLVED do(3)begin(4)通过跟踪通过跟踪G中从中从S出发的有标记的连接符出发的有标记的连接符, 计算计算 G中的一个局部解图中的一个局部解图G(5)选择选择G的任一未标记为的任一未标记为SOLVED的叶节点的

18、叶节点n(6)扩展节点扩展节点n, 生成它的全部后继节点加入生成它的全部后继节点加入G中中. 对对 于未曾在于未曾在G中出现过的每一个后继节点中出现过的每一个后继节点nj, 相应的相应的 费用费用q(nj)=h(nj). 对其中的终节点对其中的终节点, 标记标记SOLVED, 相应的相应的q值为值为0(7)建立一个只包含节点建立一个只包含节点n的集合的集合M(8)until M为空为空 do(9)begin(10)从从M中移出后裔不在中移出后裔不在M中的节点中的节点m(即自下而上即自下而上)(11)根据以下步骤修改节点根据以下步骤修改节点m的费用的费用q(m):若若m有有j个或分枝个或分枝,

19、对于对于m的每个或分枝的每个或分枝 i 的与的与 后继节点集后继节点集n1i , n ki, 计算计算 qi(m)=Ci(m)+q(n1i)+ +q(nki)1 i j 令令 q(m)=min(qi(m)1 i j 并对这个具有最小值的分枝连接符加以标记并对这个具有最小值的分枝连接符加以标记, 如如 果以前标记在其他分枝连接符上果以前标记在其他分枝连接符上, 则删除以前的则删除以前的 标记标记; 如果该连接符的全部后继节点都已标记如果该连接符的全部后继节点都已标记 为为SOLVED, 则标记则标记m为为SOLVED(12)如果如果m已标记为已标记为SOLVED, 或或q(m)不同于以前不同于以

20、前计算的费用计算的费用, 则把通过有标记连接符连到则把通过有标记连接符连到m上的所上的所有祖先节点都添加到有祖先节点都添加到M中去中去(13)end (9)(14)end (3)AO*算法举例其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n8目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4绿色：3目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1

21、)n5(1)红色：4绿色：6n1n2(4)n3(4)5目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5绿色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5绿色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21n与与A*算法比较算法比较n估价函数只考虑估价函数只考虑h(n), 因为算法有自下因为算法有自下而上的修正费用的的操作而上的修正费用的的操作, 实际上局部实际上局部解图费用值的估计是在起始节点解图费用值的估计是在起始节点S比较比

22、较, 计算计算g既无必要也不可能既无必要也不可能.nK-连接符对父节点的可解性及费用值连接符对父节点的可解性及费用值的估计都产生影响的估计都产生影响, 因而不能象因而不能象A*算算法那样优先扩展具有最小费用的节点法那样优先扩展具有最小费用的节点.n没有没有OPEN表和表和CLOSED表表, 增加了局增加了局部解图部解图G, h(n)是最佳解图的费用估是最佳解图的费用估计计, 而不是最佳路径的估计而不是最佳路径的估计.4.3.4 博弈树的启发式搜索博弈树的启发式搜索n问题提出问题提出n博弈树的概念博弈树的概念n博弈树的搜索方法极大极小分析法博弈树的搜索方法极大极小分析法n 剪枝枝术剪枝枝术问题的

23、提出问题的提出n问题：分钱币游戏：有一堆数目为问题：分钱币游戏：有一堆数目为N的钱币，两的钱币，两个选手轮流将它一分为二，规则是无论哪个选手个选手轮流将它一分为二，规则是无论哪个选手分币时，一次只能挑选其中的一堆把它分为两小分币时，一次只能挑选其中的一堆把它分为两小堆，而且必须满足分堆后两小堆的钱数不能相等，堆，而且必须满足分堆后两小堆的钱数不能相等，直到哪个选手无法再分时，即碰到每堆钱币数为直到哪个选手无法再分时，即碰到每堆钱币数为1或或2的情况，他即为输家的情况，他即为输家.设设N=6,选手甲，乙，数选手甲，乙，数字序列字序列x1,x2xn为为n堆钱币不同的个数。堆钱币不同的个数。n例例

24、（6，甲，甲(MAX)）表示甲从一堆（）表示甲从一堆（6个）钱币开个）钱币开 始分始分 ,（5，1，乙，乙(MIN)）乙要分的状态）乙要分的状态n分钱币的搜索树S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN)MIN输MAX输博奕树博奕树n博弈树：以一方立场（我方）来看博弈博弈树：以一方立场（我方）来看博弈过程用图表示出来，得到的与或树过程用图表示出来，得到的与或树n初始节点为博弈的初始格局。初始节点为博弈的初始格局。n与或节点交替出现，

25、我方扩展节点之与或节点交替出现，我方扩展节点之间是间是“或或”的关系，敌方为的关系，敌方为“与与”节节点。点。n使我方获胜的终局都是本原问题，使使我方获胜的终局都是本原问题，使敌方获胜的终局都是不可解节点敌方获胜的终局都是不可解节点n博弈的特点：二人零和，全信息，非偶博弈的特点：二人零和，全信息，非偶然然n二人零和：结果必有一方获胜，或平二人零和：结果必有一方获胜，或平局。局。n全信息：参与者都了解对手当前和过全信息：参与者都了解对手当前和过去的走步，也可以推测出将要走的招去的走步，也可以推测出将要走的招术。术。n非偶然非偶然:根据当前情况（一般不能看到根据当前情况（一般不能看到终局），终局）

26、，选取对自己最为有利而对对选取对自己最为有利而对对方最为不利的对策方最为不利的对策n分钱币的搜索树（分钱币的搜索树（MAX必赢）必赢）S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN)MAX赢赢MAX输输n分钱币的搜索树（MIN可能赢）S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN

27、)MIN输MIN赢分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走我方必胜n如何找到博弈必胜的策略如何找到博弈必胜的策略n思路：尽选择对自己有利的方案，向前尽量多看几步思路：尽选择对自己有利的方案，向前尽量多看几步n基本概念基本概念n静态估值：每个结点的势态估计值。静态估值：每个结点的势态估计值。n 倒推值：由每个结点的静态估值倒推出父结点的估计值。倒推值：由每个结点的静态估值倒推出父结点的估计值。n 或节点或

28、节点(MAX节点节点)，其倒推值选，其倒推值选 取各分枝中最大值。取各分枝中最大值。n与节点与节点(MIN节点节点)，其倒推值选取各分枝中最小值。，其倒推值选取各分枝中最小值。n基本思想基本思想(极大极小法极大极小法)。n以一定深度生成博奕树以一定深度生成博奕树(扩展一级或二级扩展一级或二级),应用各节点的静应用各节点的静态估计值计算出态估计值计算出(倒推出倒推出)每个非端节点的倒退值。每个非端节点的倒退值。n选取选取”或或”节点节点(我方，我方，MAX)得分极大的棋步得分极大的棋步(对或节点来对或节点来说说)n 选取选取”与与”节点节点(敌方，敌方，MIN)得分极小的棋步得分极小的棋步(对与

29、节点来对与节点来说说)逐级搜索，求解博奕问题。逐级搜索，求解博奕问题。n例 计算倒推值（向前看两步）321-124 -2 6 4 364-56186 328562-12-243-51322343323中国象棋n一盘棋平均走50步，总状态数约为10的161次方。n假设1毫微秒走一步，约需10的145次方年。n结论：不可能穷举。极大极小分析法极大极小分析法1.设博弈的双方中一方为设博弈的双方中一方为A,另一方为另一方为B.极大极小分析法是为其极大极小分析法是为其中的一方中的一方(例如例如A)寻找一个最优行动方案的方法。寻找一个最优行动方案的方法。2.为找到当前的最优行动方案，需要对各个方案可能产生

30、的后为找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较。即要考虑每一方案实施后对方可能采取的所有果进行比较。即要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。行动，并计算可能的得分。3为计算得分，需要根据问题的特性信息定义一个估价函数，用为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分，此时估算出来的得分称为来估算当前博弈树端节点的得分，此时估算出来的得分称为静态估值。静态估值。4当端节点的估值计算出来后，再推算出其父节点的得分。当端节点的估值计算出来后，再推算出其父节点的得分。推算方法：推算方法：“或或”节点取其子节点中最大的得分作

31、为父节点的节点取其子节点中最大的得分作为父节点的得分。得分。 “与与”节点取其子节点中最小的得分作为父节点的得节点取其子节点中最小的得分作为父节点的得分。这样计算出的父节点的得分称为倒推值。分。这样计算出的父节点的得分称为倒推值。5如果一个方案能获得较大的倒推值，则它就是当前最好的行动如果一个方案能获得较大的倒推值，则它就是当前最好的行动方案。方案。n求解过程求解过程n搜索树搜索树n端节点的估计值端节点的估计值n- 表示表示MAX不可再分不可再分n+ 表示表示MIN不可再分不可再分n极大极小分析方法计算倒推值极大极小分析方法计算倒推值n选取对选取对MAX最有利的方案最有利的方案n分钱币的搜索树

32、（分钱币的搜索树（MAX必赢）必赢）S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN)MAX赢赢MAX输输- + - - + - + + 例例 极大极小法（向前看两步）极大极小法（向前看两步）321-124 -2 6 4 364-56186328562-12-243-51322343323极大极小搜索法举例极大极小搜索法举例:n一字棋一字棋n在博奕树中一般用方块表示轮到我方走棋的在博奕树中一般用方块表示轮到我方走棋的节点节点, 称为最大节

33、点称为最大节点; 用圆圈表示轮到对方用圆圈表示轮到对方走棋的节点走棋的节点, 称为最小节点称为最小节点. 棋局中, 我方(MAX)棋子用表示, 对方(MIN)棋子用表示. 开始由我方先走, 搜索深度为2. 估价函数: 我方获胜e(p)= - 对方获胜 空格视为时我方三连子数-其他情况 空格视为时对方三连子数1-1-211010-1-10-10-2 12 11213121010201112231221100 111212-101001122111-ABCD算法讨论算法讨论n存在问题n改进方法n 黑 红n车 18 18n马 0 8n炮 10 0n象 4 4n士 4 4n兵 4 2总和 40 364.3.5 剪枝枝术剪枝枝术n基本思想n值n剪枝枝术的一般规律n例n基本思想SABC=2D=7E=1F未定 值值与节点取当前子节点中最小倒推值作为其倒推值的与节点取当前子节点中最小倒推值作为其倒推值的上界上界- 值值或节点取当前子节点中最大倒推值作为其倒推值的或节点取当前子节点中最大倒推值作为其倒推值的下界下界- 值值n 剪枝枝术的一般规律剪枝枝术的一般规律n任何任何“或或”节点节