第2讲 问题求解与搜索方法.ppt

《第2讲 问题求解与搜索方法.ppt》由会员分享，可在线阅读，更多相关《第2讲 问题求解与搜索方法.ppt（83页珍藏版）》请在麦多课文档分享上搜索。

1、第2讲 问题求解与搜索方法,知识回顾,什么是人工智能 人工智能的产生及主要学派 人工智能的技术特征 人工智能应用系统,(一).从拟人思维角度的定义： (二).从理性思维角度的定义 (三).从拟人行为角度的定义 (四).从理性行为角度的定义,知识回顾,什么是人工智能 人工智能的产生及主要学派 人工智能的技术特征 人工智能应用系统,(一).符号主义学派 (二).联结主义学派 (三).行为主义学派,知识回顾,什么是人工智能 人工智能的产生及主要学派 人工智能的技术特征 人工智能应用系统,(一).利用搜索 (二).利用知识 (三).利用推理 (四).遵循有限合理原则 (五).利用抽象,知识回顾,什么是

2、人工智能 人工智能的产生及主要学派 人工智能的技术特征 人工智能应用系统,(一).问题求解系统 (二).自然语言理解和处理系统 (三).专家系统 (四).智能软件Agent (五).数据挖掘和知识发现,主要内容,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,一、问题的状态和状态空间,(一). 如何定义状态空间及其搜索 人工智能中的搜索技术的应用 （如机器人足球赛 对弈） 解空间：所求问题的解构成的状态集。 状态(State)：在人工智能中，状态是为了描述某些不同事物间的差别而引入的一组最小变量q0,q1,qn的有序集合。 其形式表示为：Q=(q0,q1,qn)。其中，

3、每个qi称为状态变量。给定每个分量的一组值，就得到一个具体的状态。(如对弈中的状态),一、问题的状态和状态空间,(一). 如何定义状态空间及其搜索 操作符或算子：,Q1,Q2,状态1,状态2,operator,使问题从一种状态变化为另一种状态的手段如五子棋游戏,一、问题的状态和状态空间,(一). 如何定义状态空间及其搜索 问题的状态空间(State Space)。是一个表示该问题全部可能状态及其关系的集合。 它包括问题初始状态集合S、操作符集合F和目标状态集合G。 状态空间可表示为三元组(S,F,G),其中S属于Q,G属于Q。,一、问题的状态和状态空间,(一). 如何定义状态空间及其搜索 问题

4、状态空间法：是基于解空间的问题表示和求解方法。 问题状态空间法的基本思想:（1）将问题的已知条件看成状态空间的初始状态(S)；将问题中要求达到的目标看成状态空间中的目标状态(G)；将问题中其他可能发生的情况看成状态空间的任一状态。（2）设法在状态空间寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。,一、问题的状态和状态空间,(一). 如何定义状态空间及其搜索 问题状态空间法的基本算法：(1)、根据问题定义相应的状态空间，确定出状态的一般表示，它含有相关对象各种可能的排列。(2)、规定一组操作(算子)，能够作用于一个状态后过渡到另一种状态。(3)、决定一组搜索策略，使得能够从初始状态

5、出发，沿某个路径到达目标状态。,如 水壶问题,一、问题的状态和状态空间,(二). 问题的特征分析为了选择最适合于某一特定问题的搜索方法，需要对问题的几个关键指标或特征加以分析。,一、问题的状态和状态空间,(二). 问题的特征分析 问题是否可分解如果问题能分解成若干子问题，则将子问题解出后，原问题的解也就求出了。这种求解问题的方法称为问题的归约。,一、问题的状态和状态空间,(二). 问题的特征分析 问题求解步骤是否可撤回 (1).忽略。 (2).可撤回。如走迷宫。 (3).不可撤回 ，如下棋，决策等问题，要提前分析每步走一步后会导致的结果，不可回头重来，这需要使用规划技术。,一、问题的状态和状态

6、空间,(二). 问题的特征分析 问题全域是否可预测有些问题的全域可预测，即该问题空间有哪些状态是可以预计的。如水壶问题有些问题的全域不可预测，如变化环境下机器人的控制。,一、问题的状态和状态空间,(二). 问题的特征分析 问题要求的是最优解还是较满意解，解得要求不同，采用的策略也不同。一般说来，最佳路径问题的计算比次优路径问题的计算要困难。,问题的状态和状态空间盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,主要内容,二、盲目的搜索方法,盲目搜索是按预定的控制策略进行，在搜索过程中获得的中间信息不用来改进控制策略,二、盲目的搜索方法,(一). 宽度优先搜索(Breadth-first Sea

7、rch)宽度优先搜索，又称为广度优先搜索，是一种逐层次搜索的方法。在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。,用宽度优先搜索解决八数码难题,优点：若问题有解，则可找到最优解 缺点：效率低，组合爆炸问题难以解决,宽度优先搜索算法描述 1 把初始状态节点So放入OPEN表中； 2 若OPEN表为空，则搜索失败，退出。 3 取OPEN表中前面第一个节点放在CLOSED表中，令该节点为x并以顺序编号n; 4 若目标状态节点Sg=x，则搜索成功，结束。 5 若x不可扩展，则转至步骤2； 6 扩展x将其所有字节点配上指向x的指针依次放入OPEN表的尾部转至步骤2。,OPNE表用于

8、存放刚生成的节点。,CLOSED表用于存放将要扩展或以被扩展的节点。,二、盲目的搜索方法,(二). 深度优先搜索(Depth-first-Search),如用深度优先搜索解决八数码难题,优点：节省大量的时间和空间。 缺点：不一定能找到解。因为在深度无限搜索树的情况下，最坏的情况可能是不能停机。,深度优先搜索算法描述 1 把初始状态节点So放入OPEN表中； 2 若OPEN表为空，则搜索失败，退出。 3 取OPEN表中前面第一个节点放入CLOSD表中，令该节点为x并以顺序编号n; 4 若目标状态节点Sg=x，则搜索成功，结束。 5 若x不可扩展，则转至步骤2； 6 扩展x，将其所有子节点配上指向

9、x的返回指针依次放入OPEN表的首部，转至步骤2。,二、盲目的搜索方法,(三). 分支有界搜索(Branch-and-Bound Search) 也是一种深度优先搜索，但是每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续按深度优先搜索。,分支有界搜索算法描述 1 把So放入OPEN表中，置So的深度d(So)=0; 2 若OPEN表为空，则搜索失败，退出。 3 取OPEN表中前面第一个节点放入CLOSD表中，令该节点为x并以顺序编号n; 4 若目标状态节点Sg=x，则搜索成功，结束。 5 若x的深度d(x)=dm,或x无子节点，则转至步骤2； 6

10、扩展x，将所有子节点xi配上指向x的返回指针后依次放入OPEN表中前部，置d(xi)=d(x)+1,转至步骤2。,二、盲目的搜索方法,(四). 迭代加深搜索(IterativeDeepening Search) 是在分支有界搜索的基础上，对dmax进行迭代，即逐步加深。这是一种同时兼顾深度和宽度的搜索方法。在限定的深度内，保证了对宽度节点的搜索，如果没有找到解，再加深深度。,迭代加深搜索,迭代加深搜索算法描述（P67),主要内容,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,三、启发式搜索方法,前面讨论的方法都是盲目的搜索方法,即都没有利用问题本身的特性信息。 启发式

11、搜索要用到问题自身的某些特性信息,以指导搜索朝着最有希望的方向前进,三、启发式搜索方法,(一). 启发式信息的表示 为什么要使用启发式搜索 (1).人们善于利用一些线索来帮助自己选择搜索方向，这些线索被称为启发式(Heuristic)信息。(如案件侦探)。 (2).现实问题往往只需一个解，而不是求最优解或全部解。 (3).启发式信息可以避免某些领域里的组合爆炸问题。 如：计算机下棋问题,三、启发式搜索方法,(一). 启发式信息的表示 启发式函数的表示方法估价函数用来估计节点重要性的函数。,三、启发式搜索方法,(一). 启发式信息的表示 启发式函数的表示方法 例：八数码问题，评价函数 f(n)

12、= d(n) + W(n) d(n): 节点n的深度; W(n):与目标相比, 错位的数字数目;,初始状态,目标状态,八数码问题估计函数,三、启发式搜索方法,(一). 启发式信息的表示 搜索方向的选择正向搜索：从初始状态向目标状态搜索。逆向搜索：从目始状态向初标状态搜索。双向搜索：正向搜索与逆向搜索结合的搜索。,如图示,三、启发式搜索方法,(二). 几种最基本的搜索策略 生成测试法(Generate-and-test) 基本步骤： (1).生成一个可能解，此解是状态空间中的一个点，或一条使始于So的一条路径。 (2).用生成的“解”与目标比较。 (3).达到目标，则停止，否则转(1).,三、启

13、发式搜索方法,(二). 几种最基本的搜索策略 生成测试法(Generate-and-test)该方法几乎接近耗尽式搜索，因而效率低。于是人们考虑能否利用反馈信息以帮助决定生成什么样的“解”，这就是爬山算法。,三、启发式搜索方法,(二). 几种最基本的搜索策略 爬山法(Hill-climbing) 基本步骤： (1) 生成第一个可能的解。若是目标，则停止；否则转下一步。 (2) 从当前可能的解出发，生成新的可能的解集。(2.1) 用测试函数测试新的可能解集中的元素，若是解，则停止；若不是解，转下一步。(2.2) 将它与至今已测试过的解比较。若它最接近解，则保留作为最佳元素；若它不是接近解，则舍弃

14、。 (3) 以当前最佳元素为起点，转(2).,三、启发式搜索方法,(二). 几种最基本的搜索策略 最佳优先搜索(Best-first-Search) 基本步骤：(由爬山法改造而来) (1) 生成第一个可能的解。若是目标，则停止；否则转下一步。 (2) 从该可能的解出发，生成新的可能的解集。(2.1) 用测试函数测试新的可能解集中的元素，若是解，则停止；若不是解，转下一步。(2.2) 将新生成的解集加入到原可能解集中。 (3) 从解集中挑选最好的元素作为起点，再转(2.2)。,小结,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,(一). 如何定义状态空间及其搜索 (二)

15、. 问题的特征分析,小结,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,(一).宽度优先搜索 (二).深度优先搜索 (三).分支有界搜索 (四).迭代加深搜索,小结,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,(一).启发式信息的表示 (二).几种最基本的搜索策略,修道士(Missionaries)和野人(Cannibals)问题(简称M-C问题)。设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一岸，如果野人数目超过修道士

16、数，修道士会被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。,思 考 题,修道士与野人,作业,3.1阐述广度优先搜索、深度优先搜索、有界深度优先搜索和迭代加深搜索各自的特点及复杂度。（P94）,第2讲 问题求解与搜索方法,郭建方,4课时,主要内容,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,四、图搜索策略,(一). 一个通用的图搜索算法 1、问题的分解与等价变换基本思想：当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。,四、图搜索

17、策略,(一). 一个通用的图搜索算法 1、问题的分解与等价变换 分解： 如果一个问题P可以归约为一组子问题P1,P2,Pn，并且只有当所有子问题Pi都有解时原问题P才有解，任何一个子问题Pi无解都会导致原问题P无解，则称此种归约为问题的分解。即分解所得到的子问题的“与”与原问题P等价。,四、图搜索策略,(一). 一个通用的图搜索算法 1、问题的分解与等价变换 等价变换：如果一个问题P可以归约为一组子问题P1,P2,Pn，并且子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的“或”与原问题P等价。,

18、四、图搜索策略,(一). 一个通用的图搜索算法 2. 问题的与/或树表示,(1)与树 分解,(2) 或树 等价变换,(3) 与/或树,四、图搜索策略,(一). 一个通用的图搜索算法 3.一般图搜索过程 基本思想：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。,四、图搜

19、索策略,(一). 一个通用的图搜索算法 3.一般图搜索过程 算法的数据结构和符号约定：Open表：用于存放刚生成的节点，作用是当Open表为空且未找到目标节点时搜索失败。Closed表：用于存放已经扩展或将要扩展的节点，作用是在搜索成功时为回溯求解路径提供依据。S0：用表示问题的初始状态G：表示搜索过程所得到的搜索图M：表示当前扩展节点新生成的且不为自己先辈的子节点集。,四、图搜索策略,(一). 一个通用的图搜索算法 4.一般图搜索算法 (1) 把初始节点S0放入Open表，并建立目前仅包含S0的图G； (2) 检查Open表是否为空，若为空，则问题无解，失败推出； (3) 把Open表的第一

20、个节点取出放入Closed表，并记该节点为节点n； (4)考察节点n是否为目标节点。若是则得到了问题的解，成功退出； (5) 扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中。,四、图搜索策略,(一). 一个通用的图搜索算法 4.一般图搜索算法 (6)针对M中子节点的不同情况，分别作如下处理： 对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入Open表。（新生成的） 对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的） 对于那些先前已在

21、G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的） (7)按某种策略对Open表中的节点进行排序。 (8)转第(2)步。,四、图搜索策略,(一). 一个通用的图搜索算法 4.一般图搜索算法,实心圆点在Closed表中，代表已扩展的节点； 空心圆点在Open表中，代表未扩展的节点； 假设每条边的代价为1； 分析节点2和节点4.,四、图搜索策略,(一). 一个通用的图搜索算法 5. 算法的几点说明 (1) 上述过程是状态空间的一般图搜索算法，它具有通用性，所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对Open表中节

22、点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。,四、图搜索策略,(一). 一个通用的图搜索算法 5. 算法的几点说明 (2)在第(5)步对节点n扩展后，生成并记入M的子节点有以下三种情况： 该子节点来从未被任何节点生成过，由n第一次生成； 该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成； 该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被n再次生成。,四、图搜索策略,(一). 一个通用的图搜索算法 5. 算法的几点说明以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其状态空间是树状结构，因此不会出现后

23、两种情况，每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。,四、图搜索策略,(一). 一个通用的图搜索算法 5. 算法的几点说明 (3) 在第(6)步针对M中子节点的不同情况进行处理时，如果发生当第种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。,四、图搜索策略,(一). 一个通用的图搜索算法 5. 算法的几点说明如果发生第种情况，除了需要确定该子节点指向父节点的指针外，

24、还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。,四、图搜索策略,(一). 一个通用的图搜索算法 5. 算法的几点说明 (4)在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。 (5)在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第(6)步所形成的指向父节点的指针来确定。 (6)如果搜索过程终止在第(2)步，即没有达到目标，且Open表中已无可供扩展的节点，则失败结束。,四

25、、图搜索策略,(二). A算法和A*算法 1、 A算法 概念：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。 由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。,四、图搜索策略,(二). A算法和A*算法 1、 A算法 类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。全局择优： 从Open表的所有节点中选择一个估价函数值最小的一个进行扩展。局部择优：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。,四、图搜索策略,(二). A

26、算法和A*算法 1、 A算法 全局择优搜索A算法描述： (1)把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)； (2)如果Open表为空，则问题无解 ，失败退出； (3)把Open表的第一个节点取出放入Closed表，并记该节点为n； (4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出； (5)若节点n不可扩展，则转第(2)步；,四、图搜索策略,(二). A算法和A*算法 1、 A算法 全局择优搜索A算法描述： (6)扩展节点n，生成其子节点ni(i=1, 2, )，计算每一个子节点的估价值f(ni)(i=1, 2, )，并为每一个子节点设置指向父节点的指针，

27、然后将这些子节点放入Open表中； (7)根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序； (8)转第(2)步。,四、图搜索策略,(二). A算法和A* 算法 2、 A*算法A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制得到的一种启发式搜索算法假设f*(n)是从初始节点出发，约束经过节点n达到目标节点的最小代价，估价函数f(n)是对f*(n)的估计值。且f*(n)=g*(n)+h*(n),四、图搜索策略,(二). A算法和A* 算法 2、 A*算法,四、图搜索策略,(二). A算法和A* 算法 2、 A*算法A*算法对A算法（全局择优的启发式

28、搜索算法）中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)0；第二，h(n)是最小代价h*(n)的下界，即对任意节点n均有h(n)h*(n)。即满足上述两条限制的A算法称为A*算法。,例4.10 八数码难题。,2 8 3 1 4 7 6 5,2 8 31 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 46 5,1 2 38 4 7 6 5,S0,f=6 g*=1h*=3

29、 f=6 f=6,g*=2 h*=2 f=6f=4,g*=3 h*=1f=4,g*=4 h*=0 f=4,f=6,Sg,八数码难题h(n)=P(n)的搜索树,f(n)=d(n)+P(n) d(n) 深度 P(n)表示每个数码与目标位置之间的距离总和。节点n至少要移动P(n)步才能到达目标。显然满足P(n) h*(n), 即f*=g*+h*,f=4,A*算法应用举例,h*=4 f=4,主要内容,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,五、博弈,博弈的概念博弈是一类具有智能行为的竞争活动，如下棋、战争等。 博弈的类型双人完备信息博弈：两位选手（例如MAX和MIN ）

30、对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。机遇性博弈：存在不可预测性的博弈，例如掷币等。,五、博弈,博弈树若把双人完备信息博弈过程用图表示出来，就得到一棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的节点称为MAX节点，下一步该MIN走步的节点称为MIN 节点。,例4.13 设有下图所示的与/或树，节点按标注顺序进行扩展，其中表有t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点。,1,2 3,A 4 t1 5,t2 B t3 C,与/或树的广度优先搜索,搜索过程为：(1) 先扩展1号节点，生成2号节点和3号节点。(2)

31、 扩展2号节点，生成A节点和4号节点。(3) 扩展3号节点，生成t1节点和5号节点。由于t1为终止节点，则标记它为可解节点，并应用可解标记过程，不能确定3号节点是否可解。,(6) 扩展5号节点，生成t3节点和C节点。由于t3为终止节点，则标记它为可解节点，并应用可解标记过程，可标记1号节点为可解节点。,(7) 搜索成功，得到由1、2、3、4、5号节点即t1、t2、t3节点构成的解树。,(4) 扩展节点A，由于A是端节点，因此不可扩展。调用不可解标记过程。(5) 扩展4号节点，生成t2节点和B节点。由于t2为终止节点，则标记它为可解节点，并应用可解标记过程，可标记2号节点为可解，但不能标记1号节

32、点为可解。,五、博弈,博弈树的特点(1) 博弈的初始状态是初始节点； (2) 博弈树中的“或”节点和“与”节点是逐层交替出现的；(3) 整个博弈过程始终站在某一方的立场上，例如MAX方。所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。,五、博弈,博弈中两种最基本的搜索方法 ： 极大极小过程 -过程,五、博弈,极大极小(MAXMIN)过程 对简单的博弈问题，可生成整个博弈树，找到必胜的策略。 对于复杂的博弈问题，不可能生成整个搜索树，如国际象棋，大约有10的120次幂个节点。 一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，并利用估价函数

33、f(n)对叶节点进行静态估值。,五、博弈,极大极小(MAXMIN)过程 对叶节点的估值方法是：那些对MAX有利的节点，其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。,五、博弈,极大极小(MAXMIN)过程 为非叶节点的值，必须从叶节点开始向上倒退。其倒退方法是： 对于MAX节点，由于MAX 方总是选择估值最大的走步，因此，MAX节点的倒退值应该取其后继节点估值的最大值。 对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的最小值。 这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。这

34、一过程称为极大极小过程。,如：一字棋游戏,五、博弈,-过程 剪枝的概念 极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为-剪枝。,五、博弈,-过程 剪枝方法 (1) MAX节点（或节点）的值为当前子节点的最大倒推值； (2) MIN节点（与节点）的值为当前子节点的最小倒推值；,五、博弈,-过程 剪枝方法 (3) -剪枝的规则如下： 若任何MAX节点n的值大于或等于它先辈节点的值，则n 以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。若任何MIN节点n的值小于或等于它先辈节点的值，则n 以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。,五、博弈,-过程,一个-剪枝的具体例子,小结,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,一个通用的图搜索算法 A算法和A*算法,小结,问题的状态和状态空间 盲目的搜索方法 启发式搜索方法 图搜索策略 博弈,极大极小(MAXMIN)过程 -过程,作业题,作业题,