人工智能第三章_搜索策略-2ppt课件

1、2022/7/171启发式搜索启发式知识指点OPEN表排序的普通图搜索：全局排序对OPEN表中的一切节点排序，使最有希望的节点排在表首。A算法， A*算法掌握！部分排序仅对新扩展出来的子节点排序，使这些新节点中最有希望者能优先取出调查和扩展；爬山法了解，对深度优先法的改良；2022/7/172 简单的搜索战略： g(n)0, f(n)= h(n), 部分排序只排序新扩展出来的子节点，即部分排序 简单易行，适用于不要求最优解答的问题求解义务。 1爬山法实现启发式搜索的最简一方法。 类似于人爬山只需好爬，总是选取最陡处，以求快速登顶。 求函数极大值问题非数值解法，依赖于启发式知识，试探性地逐渐向顶

2、峰逼近 适用于能逐渐求精的问题。 爬山法特点： 只能向上，不准后退，从而简化了搜索算法；表达在： * 从当前形状节点扩展出的子节点相当于找到上爬的途径中，将h(n)最小的子节点对应于到顶峰最近的上爬途径作为下一次调查和扩展的节点，其他子节点全部丢弃。 不需设置OPEN和CLOSE表，由于没有必要保管任何待扩展节点； 爬山法对于单一极值问题登单一山峰非常有效而又简便,对于具有多极值的问题无能为力会错登上次顶峰而失败：不能到达最顶峰。回溯战略和爬山法 2022/7/173 2回溯战略 可以有效地抑制爬山法面临的困难保管了每次扩展出的子节点，并按h(n)值从小到大陈列。 相当于爬山的过程中记住了途经

3、的岔路口途径搜索失败时回溯后退，向另一途径方向搜索 回溯战略和爬山法 2022/7/174 2回溯战略 递归过程实现回溯战略的有效方式 算法就取名为BACKTRACK(n),参数n为当前被扩展的节点， 初次调用时n即为初始形状节点s； 分二个部分：* 判别当前节点n的形状，* 作搜索任务扩展节点n，递归调用该算法，处置前往结果。回溯战略和爬山法 2022/7/175令PATH、SNL、n、n 为部分变量： PATH-节点列表，指示解答途径； SNL-当前节点扩展出的子节点列表； MOVE-FIRST(SNL)-把SNL表首的节点移出，作为下一次要加以扩展的节点； n、n-分别指示当前调查和下一

4、次调查的节点。 该递归过程的算法就取名为BACKTRACK(n),参数n为当前被扩展的节点，算法的初次调用式是BACKTRACK(s),s即为初始形状节点。算法的步骤如下：1 假设n是目的形状节点，那么算法的本次调用胜利终了，前往空表；2 假设n是失败形状，那么算法的本次调用失败终了，前往FAIL；3 扩展节点n，将生成的子节点置于列表SNL，并按评价函数f(k) = h(k)的值从小到大排序k指示子节点；4 假设SNL为空，那么算法的本次调用失败终了，前往FAIL；5 n= MOVE-FIRST(SNL)；6 PATH = BACKTRACK(n)；7 假设PATH =FAIL, 前往到语句

5、4；8 将n加到PATH表首，算法的本次调用胜利终了，前往PATH。2022/7/176 2回溯战略 三种失败形状： 不合法形状如传教士和野人问题中所述的那样 旧形状重现如八数码游戏中某一棋盘规划的重现，会导致搜索算法死循环， 形状节点深度超越预定限制例如八数码游戏中，指示解答途径不超越6步。 回溯条件 失败形状，由算法第2句指示； 搜索进入“死胡同，由该算法的第(4)句定义。回溯战略和爬山法 2022/7/177 2回溯战略 解答途径的生成从相应于目的形状节点的空表开场，递归前往PATH。 影响回溯算法效率的关键要素回溯次数。 回溯搜索到失败形状时的一种弥补行为， 准确选择下一步搜索调查的节

6、点大幅度减少甚至防止回溯。 设计好的启发式函数h(n)是至关重要的。回溯战略和爬山法 2022/7/178课堂练习:提高题在运用递归回溯算法处理四皇后的问题中，假设按行的序号从小到大试探性放置各列的皇后，请画出搜索图，并指出分别从算法第2步和第4步回溯的次数。2022/7/179 定义L，为表示明晰起见,L表中只记载皇后所在列,皇后所在行可由在L表中的先后位置指示,例如L=(1 3)指示两个皇后位置分别为第1行第1列和第2行第3列。搜索图(树)如右图所示:共回溯22次,其中算法第2步的回溯18次,算法第4次的回溯4次。2022/7/17103.4 问题归约和与或图启发式搜索问题归约是人求解问题

7、常用的战略：把复杂的问题变换为假设干需求同时处置的较为简单的子问题后再加以分别求解只需子问题全部处理时，问题才算处理；问题的解答由子问题的解答结合构成。本节主要内容：问题归约的描画了解与或图搜索的根本过程了解与或图的启发式搜索掌握2022/7/1711问题归约法Problem Reduction Representation子问题1子问题n原始问题子问题集本原问题2022/7/1712问题归约可以用三元组表示：S0，O，P，其中S0是初始问题，即要求解的问题；P是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、知现实等，或已证明过的问题；O是操作算子集，它是一组变换规那么，经过一

8、个操作算子把一个问题化成假设干个子问题。2022/7/1713问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样不断进展到产生的问题均为本原问题，那么问题得解。 2022/7/1714看如下符号积分问题：初始问题f ( x ) dx变换规那么积分规那么本原问题可直接求原函数和积分，如sin ( x ) dx，cos ( x ) dx等。一切问题归约的最终目的是产生本原问题。2022/7/1715符号积分问题sin3x + x4/(x2 + 1)dx=sin3xdx + (x4/(x2 + 1)dx=-(1 - cos2x)dcosx

9、+ (x2 - 1 + 1/(1 + x2)dx=(-dcosx + cos2xdcosx) + (x2dx - dx + (1/(1 + x2)dx= -cosx + cos3x/3 + x3/3 - x + arctgx2022/7/1716分子构造识别问题 如何区分分子式一样但分子构造不同的有机化合物成为重要而又困难的问题。著名的专家系统 DENDRAL能用于有效地识别分子构造，该系统建立了一套重写规那么去把分子式重写为原子数较少的分子式和原子间结合关系的混合构造 2022/7/1717问题归约的本质： 从目的(要处理的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题

10、归约为一个平凡的本原问题集合。2022/7/1718运用问题归约战略得到的形状空间图，也称为“与或图逻辑“与关系用圆弧将几条节点间关联弧衔接在一同表示问题分解为子问题；子问题的形状结合起来构成问题形状。子问题全部处理才会导致问题的处理；逻辑“或关系：问题可以有多种分解方式；问题子问题能够激活多个形状变化操作；只需一种分解方式或形状变化操作能导致最终的解答胜利即可；导致多个能够的解答。与或图2022/7/1719用AND-OR图把问题归约为子问题交换集合。如，假设问题A既可经过问题C1与C2，也可经过问题C3、C4和C5，或者由单独求解问题C6来处理，如以下图所示。图中各节点表示要求解的问题或子

11、问题。与或图2022/7/1720梵塔问题问题描画：初始形状下三个盘按A、B、C顺序堆放在1号柱子上；目的形状下三个盘以同样次序顺序堆放在3号柱子上；盘子的搬移规那么：每次只能搬一个盘子；较大盘不能压放在较小盘之上；CAB初始形状(1 1 1)目的形状(3 3 3)CAB132132与或图2022/7/1721梵塔问题形状空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(2,2,1)132CAB(2,2,3)123ABC目的形状(3 3 3)CAB1322022/7/1722梵塔问题形状空间图(1,1,1)(3,3,3)(1

12、,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)2022/7/1723梵塔问题(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)123456789子问题间有交互作用，问题

13、分解留意正确的顺序2022/7/1724与或图搜索与或图视为对普通图(或图)的扩展； 引入K-衔接父子节点间可以存在“与关系结果解图。解答途径往往不复存在，代之以广义的解途径解图。问题归约求解问题的过程表示为与或图搜索2022/7/1725与或图搜索1)与或图搜索的根本概念1、K-衔接从父节点到K个子节点的衔接，子节点间有“与关系；以圆弧指示这些子节点间的“与关系；一个父节点可以有多个K-衔接K-衔接间或关系当一切的K都等于1时，与或图蜕化为普通图或图。3个子节点2个子节点2022/7/1726与或图搜索1)与或图搜索的根本概念2、根、叶、终节点根节点无父节点的节点用于指示问题初始形状和普通图

14、一样叶节点无子节点的节点终节点能用于结合表示目的形状的节点终节点必定是叶节点，反之不然；目的形状终结点的集合。2022/7/1727一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点终节点2022/7/1728与或图搜索1)与或图搜索的根本概念3、解图的生成解图纯粹是一种“与图解图中，节点或节点组间不存在“或关系；一切叶节点都是终节点2022/7/1729与或图搜索1)与或图搜索的根本概念3、解图的生成自根节点开场选K-衔接;从该K-衔接指向的每个子节点出发，再选一K-衔接;如此反复进展，直到一切K-衔接都指向终节点为止.2022/7/17302022/7/1731与或图搜索

15、1)与或图搜索的根本概念3、解图的生成解图纯粹是一种“与图解图中，节点或节点组间不存在“或关系；一切叶节点都是终节点与或图中存在“或关系，搜索到多个解图；2022/7/1732与或图搜索2) 解图、解图代价、能解节点和不能解节点的定义 (1)解图与或图记为G任一节点记为n到终节点集合的解图记为G是G的子图。(1)假设n是终节点，那么G就由单一节点n构成；(2)假设n有一K-衔接指向子节点n1，n2，nk,且每个子节点都有到终节点集合的解图，那么G由该k-衔接和一切这些相应于子节点的解图构成;(3)否那么不存在n到终节点集合的解图。 2022/7/1733与或图搜索2) 解图、解图代价、能解节点

16、和不能解节点的定义 (2)解图代价 以C(n)指示节点n到终节点集合解图的代价，并令K-衔接的代价就为K, 那么 (1)假设n是终节点，那么C(n) = 0；(2)假设n有一K-衔接指向子节点n1，n2，nk,且这些子节点每个都有到终节点集合的解图,那么C(n) = K + C(n1) + C(n2) + + C(nk) 352022/7/1734与或图搜索2) 解图、解图代价、能解节点和不能解节点的定义 (3)能解节点 (1) 终节点是能解节点；(2) 假设节点n有一K-衔接指向子节点n1，n2，nk,且这些子节点都是能解节点，那么n是能解节点； 能解节点能解节点能解节点能解节点2022/7

17、/1735与或图搜索2) 解图、解图代价、能解节点和不能解节点的定义 (4)不能解节点(1)非终节点的叶节点是不能解节点；(2)假设节点n的每一个K-衔接都至少指向一个不能解节点，那么n是不能解节点。 能解节点不能解节点能解节点不能解节点不能解节点2022/7/1736与或图的启发式搜索与或图中搜索的是解图，不是解答途径；评价函数f(n)=h(n)h(n)是对n到终节点集合解图最小解图代价的估计；与或图中存在“或关系，会有多个候选的部分解图；选择部分解图中能够代价最小的用于下一步搜索。1)部分解图代价f(n0) n0初始形状节点递归地计算出f(n0),比直接用h(n0)估算更为准确。父节点n的

18、K-衔接指向的子节点：n1，n2，nkf(n) = K + h(n1) + h(n2) + + h(nk)，替代h(n)2022/7/1737与或图的启发式搜索2) AO*算法符号阐明：G-搜索图；G-被选中的待扩展部分解图；LGS-待扩展部分解图集；n0-根节点，即初始形状节点；n-被选中的待扩展节点；fi(n0)-第i个待扩展部分解图的能够代价。2022/7/1738与或图的启发式搜索2) AO*算法算法划分二个阶段：1、初始化 建立只包含初始形状节点n0的搜索图G:=n0；待扩展部分解图集LGS:=；2、搜索循环选择和扩展LGS中的部分解图；精化新部分解图代价的估计；传送节点的能解性。2

19、022/7/1739与或图的启发式搜索2、搜索循环选择和扩展LGS中的部分解图；选择LGS中fi(n0)最小的待扩展解图G；随机选择G中一个非终节点的叶节点作为n；扩展n建立K-衔接，子节点ni并参与G；计算子节点ni的f(ni)=h(ni)假设n存在j个K-衔接LGS中删除G将j个新的部分解图参与LGS;2022/7/1740与或图的启发式搜索2、搜索循环选择和扩展LGS中的部分解图；精化新部分解图代价的估计用公式f(n) = K + h(n1) + h(n2) + + h(nk)取代原先的f(n);递归地作用到初始节点n0；传送新部分解图中节点的能解性标志作为终节点的子节点为能解节点；递归

20、地传送节点的能解性到初始节点n0 。f(n)=h(n)2022/7/17412022/7/1742与或图的启发式搜索2) AO*算法AO*算法运用例搜索过程中，启发式函数h(ni)的 估算如下：h(n0)=3h(n1)=2h(n2)=1h(n3)=1h(n4)=4h(n5)=2h(n6)=2h(n7)=1h(n8)=1h(n13)=3012354678910111213141516171819202022/7/1743初始化候选的待扩展部分解图集LGS:0302022/7/1744012354循环1候选的待扩展部分解图集LGS:32114202022/7/1745012354循环1候选的待扩展

21、部分解图集LGS:321142031201235432114202022/7/1746012354循环1候选的待扩展部分解图集LGS:10211420512f(n) = K + h(n1) + h(n2) + + h(nk)取代原先的f(n);f1(n0) = 2 + h(n1) + h(n2)=5f2(n0) = 3 + h(n3) + h(n4)+h(n5)=102022/7/1747012354循环2候选的待扩展部分解图集LGS:102114205678211122022/7/1748012354循环2候选的待扩展部分解图集LGS:1021142057811012215623422022

22、/7/1749012354循环2候选的待扩展部分解图集LGS:10411420778110123166234225252022/7/1750012354候选的待扩展部分解图集LGS:104114207781101231662342131430循环32022/7/1751012354候选的待扩展部分解图集LGS:104114207781101261965342131430循环33622022/7/1752012354循环4候选的待扩展部分解图集LGS:1041142077811012619653421314301402022/7/1753012354循环5候选的待扩展部分解图集LGS:10411

23、42077811012619653421314301401502022/7/1754012354循环5候选的待扩展部分解图集LGS:1051142087812012619653421314301401504712022/7/1755012354循环6候选的待扩展部分解图集LGS:105114208781201261965342131430140150902022/7/1756012354搜索胜利！候选的待扩展部分解图集LGS:105114208781201261965342131430140150902022/7/1757与或图的启发式搜索4算法运用的假设干问题1、从部分解图G中选择加以扩展的

24、节点n与或图搜索的是解图而非解途径；选择f(n) = h(n)的值最小的节点n加以扩展并不一定会加速搜索过程；应选择导致解图代价发生较大变化的节点n优先加以扩展；使搜索的留意力快速地聚焦到实践代价较小的候选解图上；简单情况下，可随机选择加以扩展的节点。2022/7/1758与或图的启发式搜索4算法运用的假设干问题2、算法AO*与A*的比较解图解答途径，估计代价最小的部分解图加以优先扩展OPEN表中f(n)最小的节点；只思索评价函数f(n)=h(n)同时计算分量g(n)和h(n)，运用LGS存放待扩展部分解图，并根据fi(n0)值排序运用OPEN表和CLOSE表分别存放待扩展节点和已扩展节点，并

25、根据f(n)值排序OPEN表。2022/7/1759与或图的启发式搜索4算法运用的假设干问题3、解图代价的反复计算某些子节点能够会有多个父节点；这种子节点到终节点集合的解图代价在计算自根节点n0出发的解图时被反复累计。1781781415125178142216241182022/7/1760博弈 博弈提供了一个可构造的义务领域，在这个领域中，具有明确的胜利和失败；博弈问题对人工智能研讨提出了严峻的挑战。例如，如何表示博弈问题的形状、博弈过程和博弈知识等。 这里讲的博弈是二人博弈，二人零和、全信息、非偶尔博弈，博弈双方的利益是完全对立的。 2022/7/1761所谓“二人零和，是指在博弈中只需

26、“敌、我二方。且双方的利益完全对立，其博得函数之和为零，即 1+2=0 式中，1为我方博得(利益)；2为敌方博得(利益)。 即：博弈的双方有三种结局： (1)我胜：10；敌负：2= -10。 (2)我负：1= -20。 (3)平局：1=0，2=0。 博弈问题对人工智能研讨提出了严峻的挑战。例如，如何表示博弈问题的形状、博弈过程和博弈知识等。 2022/7/1762所谓“全信息，是指博弈双方都了解当前的格局及过去的历史。 所谓“非偶尔，是指博弈双方都可根据得失大小进展分析，选取我方博得最大，敌方博得最小的对策，而不是偶尔的随机对策。 2022/7/17631对垒的双方MAX和MIN轮番采取行动，

27、博弈的结果只能有3种情况：MAX胜、MIN败；MAX败，MIN胜；和局。2在对垒过程中，任何一方都了解当前的格局和过去的历史。3任何一方在采取行动前都要根据当前的实践情况，进展得失分析，选择对本人最为有利而对对方最不利的对策，在不存在“碰运气的偶尔要素，即双方都很明智地决议本人的行动。这类博弈如一字棋、象棋、围棋等。博弈的特点 2022/7/1764另外一种博弈是机遇性博弈，是指不可预测性的博弈，如掷硬币游戏等。 2022/7/1765例：假设有七枚钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮番进展，直到每一堆都只需一个或两个钱币，不能再分为止，哪个选手遇到不能再分的

28、情况，那么为输。 2022/7/1766用数字序列加上一个阐明表示一个形状，其中数字表示不同堆中钱币的个数，阐明表示下一步由谁来分，如7，MIN表示只需一个由七枚钱币组成的堆，由MIN走，MIN有3种可供选择的分法，即6，1，MAX，5，2，MAX，4，3，MAX，其中MAX表示另一选手，不论哪一种方法，MAX在它的根底上再作符合要求的划分。2022/7/1767以下图已将双方能够的方案完全表示出来了，无论MIN开场时怎样走法，MAX总可以获胜，取胜的战略用双线箭头表示。2022/7/1768实践的情况没有这么简单，任何一种棋都不能够将一切情况列尽，因此，只能模拟人“向前看几步，然后做出决策，

29、决议本人走哪一步最有利。只能给出几层走法，然后按照一定的估算方法，决议走哪一步棋。在双人完备信息博弈过程中，双方都希望本人可以获胜。因此当一方走步时，都是选择对本人最有利，而对对方最不利的走法。2022/7/1769假设博弈双方为MAX和MIN。在博弈的每一步，可供他们选择的方案都有很多种。从MAX的观念看，可供本人选择的方案之间是“或的关系，缘由是自动权在本人手里，选择哪个方案完全由本人决议，可供本人选择的方案之间是“或的关系，而对那些可供MIN选择的方案之间是“与的关系，这是由于自动权在MIN手中，任何一个方案都能够被MIN选中，MAX必需防止那种对本人最不利的情况出现。 2022/7/1

30、770以下图是把双人博弈过程用图的方式表示出来，这样就可以得到一棵AND-OR树，这种AND-OR树称为博弈树。在博弈树中，那些下一步该MAX走的节点称为MAX节点，而下一步该MIN走的节点称为MIN节点。2022/7/1771以下图 所示是向前看两步，共四层的博弈树，用表示MAX，用表示MIN，端节点上的数字表示它对应的估价函数的值。在MIN处用圆弧衔接，用0表示其子节点取估值最小的格局。 图中节点处的数字，在端节点是估价函数的值，称它为静态值，在MIN处取最小值，在MAX处取最大值，最后MAX选择箭头方向的走步。 2022/7/1772博弈树特点：(1)博弈的初始形状是初始节点；(2)博弈

31、树的“与节点和“或节点是逐层交替出现的；(3)整个博弈过程一直站在某一方的立场上，所以能使本人一方获胜的结局都是本原问题，相应的节点也是可解节点，一切使对方获胜的节点都是不可解节点。 2022/7/1773在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈中两中最根本的搜索方法。 2022/7/1774极大极小过程 极大极小过程是思索双方对弈假设干步之后，从能够的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进展求解。需求定义一个静态估价函数f,以便对棋局的态势做出评价。 2022/7/1775这个函数可以根据棋局的态势特征进展定义。假定对弈双方分别为MAX和MIN，规定：

32、有利于MAX方的态势：f(p)取正值 有利于MIN方的态势：f(p)取负值 态势平衡的时候：f(p)取零其中p代表棋局。2022/7/1776MINMAX根本思想：(1)当轮到MIN走步的节点时取与时，MAX应思索最坏的情况即f(p)取极小值。(2)当轮到MAX走步的节点时取或时，MAX应思索最好的情况即f(p)取极大值。(3)评价往回倒推时，相应于两位棋手的对抗战略，交替运用1和2两种方法传送倒推值。所以这种方法称为极大极小过程。 2022/7/1777用一字棋阐明极大极小过程，设只进展两层，即每方只走一步。一字棋游戏规那么如下：设有一个三行三列的棋盘，如下图，两个棋手轮番走步，每个棋手走步

33、时往空格上摆一个本人的棋子，谁先使本人的棋子成三子一线为赢。设MAX方的棋子用标志，MIN方的棋子用标志，并规定MAX方先走步。2022/7/1778 为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下： 设棋局为P，估价函数为e(P)。(1)假设格局p对任何一方都不是获胜的，那么 e(p) = (一切空格都放上 MAX 的棋子之后三子成一线的总数) 一切空格都放上 MIN 的棋子后三子成一线的总数(2)假设p是MAX获胜，那么 e(p) = +3 假设p是MIN获胜，那么 e(p) = - 2022/7/1779假设p为以下图所示，且 e(P)=e(+P)-e(-P)=5-4=

34、12022/7/1780假设由MAX先走棋，且我们站在MAX立场上。以下图给出了MAX的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出，对于MAX来说最好的一着棋是S3，由于S3比S1和S2有较大的估值。2022/7/1781以下图 所示是向前看两步，共四层的博弈树，用表示MAX，用表示MIN，端节点上的数字表示它对应的估价函数的值。在MIN处用圆弧衔接，用0表示其子节点取估值最小的格局。 图中节点处的数字，在端节点是估价函数的值，称它为静态值，在MIN处取最小值，在MAX处取最大值，最后MAX选择箭头方向的走步。 2022/7/1782-过程 上面讨

35、论的极大极小过程先生成一棵博弈搜索树，而且会生成规定深度内的一切节点，然后再进展估值的倒推计算，这样使得生成博弈树和估计值的倒推计算两个过程完全分别，因此搜索效率较低。假设能边生成博弈树，边进展估值的计算，那么能够不用生成规定深度内的一切节点，以减少搜索的次数，这就是下面要讨论的-过程。 2022/7/1783思索：假设边生成博弈树，边进展估值的计算会带来什么益处。2022/7/1784-过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此来提高算法的效率。下面依然用一字棋进展阐明。现将原图左边所示的一部分重画在中。2022/7/1785前面的过程实践上类似于宽度优先搜索，将每层

36、格局均生成，如今用深度优先搜索来处置。比如在节点A处，假设已生成5个子节点，并且A处的倒推值等于-1，我们将此下界叫做MAX节点的值，即-1。 2022/7/1786如今轮到节点B，产生它的第一后继节点C，C的静态值为-1，可知B处的倒推值-1，此为上界MIN节点的值，即B处-1，这样B节点最终的倒推值能够小于-1，但绝不能够大于-1，因此，B节点的其他后继节点的静态值不用计算，自然不用再生成，反正B决不会比A好，所以经过倒推值的比较，就可以减少搜索的任务量2022/7/1787上图表示了值小于等于父节点的值时的情况，实践上当某个MIN节点的值不大于它的先辈的MAX节点不一定是父节点的值时，那

37、么MIN节点就可以终止向下搜索。 同样，当某个节点的值大于等于它的先辈MIN节点的值时，那么该MAX节点就可以终止向下搜索。2022/7/1788 再看一个例子，如以下图所示。其中最下面一层端节点旁边的数字是假设的估值。 2022/7/1789经过上面的讨论可以看出，-过程首先使搜索树的某一部分到达最大深度，这时计算出某些MAX节点的值，或者是某些MIN节点的值。随着搜索的继续，不断修正个别节点的或值。对任一节点，当其某一后继节点的最终值给定时，就可以确定该节点的或值。2022/7/1790当该节点的其他后继节点的最终值给定时，就可以对该节点的或值进展修正。留意、值修正有如下规律：(1)MAX

38、节点的值永不下降；(2)MIN节点的值永不添加。2022/7/1791 因此可以利用上述规律进展剪枝，普通可以停顿对某个节点搜索，即剪枝的规那么表述如下： (1)假设任何MIN节点的值小于或等于任何它的先辈MAX节点的值，那么可停顿该MIN节点以下的搜索，然后这个MIN节点的最终倒推值即为它已得到的值。 该值与真正的极大极小值的搜索结果的倒推值能够不一样，但是对开场节点而言，倒推值是一样的，运用它选择的走步也是一样的。(2)假设任何MAX节点的值大于或等于它的MIN先辈节点的值，那么可以停顿该MAX节点以下的搜索，然后这个MAX节点处的倒推值即为它已得到的值。2022/7/1792当满足规那么1而减少了搜索时，进展了剪枝；而当满足规那么2而减少了搜索时，进展了剪枝。保管和值，并且一旦能够就进展剪枝的整个过程通常称为-过程，当初始节点的全体后继节点的最终倒推值全部给出时，上述过程便终了。在搜索深度一样的条件下，采用这个过程所获得的走步总跟简单的极大极小过程的结果是一样的，区别只在于-过程通常只用少得多的搜索便可以找到一个理想的走步。 2022/7/1793约束满足搜索 约束满足问题CSP就是为一组变量寻觅满足约束的赋值。如，N-皇后问题就是一个约束满足问题。这里的问题就是为