搜索策略培训教材

《搜索策略培训教材》由会员分享，可在线阅读，更多相关《搜索策略培训教材（241页珍藏版）》请在金锄头文库上搜索。

1、第第3 3章章 搜索策略搜索策略o问题求解系统划分为两大类问题求解系统划分为两大类n知识贫乏系统知识贫乏系统 o依靠依靠搜索技术搜索技术o知识贫乏、缺乏针对性知识贫乏、缺乏针对性o效率低效率低 n知识丰富系统知识丰富系统 o依靠依靠推理技术推理技术o基于丰富知识的推理技术，直截了当基于丰富知识的推理技术，直截了当 o效率高效率高 2024/7/231第第3 3章章 搜索策略搜索策略o两大类两大类搜索技术搜索技术:n1、一般图搜索、启发式搜索、一般图搜索、启发式搜索n2、基于问题归约的与或图搜索、基于问题归约的与或图搜索 o两种典型的两种典型的推理技术推理技术:n1、基于归结的演绎推理、基于归结

2、的演绎推理o归结反演归结反演n2、基于规则的演绎推理、基于规则的演绎推理o正向演绎推理正向演绎推理o逆向演绎推理逆向演绎推理 2024/7/2323.1 引言引言 o对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。o基于给定的问题，问题求解的第一步是目标的表示。o搜索就是找到智能系统的动作序列的过程。 2024/7/233o搜索算法的输入是给定的问题，输出是表示为动作序列的方案。o一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）o因此，求解问题包括：n目标表示目标表示n搜索搜索n执行执行2024/7/234（1）初始状态集合：定

3、义了初始的环境。（2）操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。（3）目标检测函数：用来确定一个状态是不是目标。（4）路径费用函数：对每条路径赋予一定费用的函数。其中，初其中，初始状态集始状态集合和操作合和操作符集合定符集合定义了问题义了问题的搜索空的搜索空间。间。一般给定问题就是确定该问题的一一般给定问题就是确定该问题的一些基本信息，一个问题由些基本信息，一个问题由4 4部分组成部分组成: :2024/7/235o和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。 在人工智能中，搜索问题一般包括两个重要在人工智能中，搜索问题一般包括两个重要的

4、问题：的问题：v搜索什么搜索什么搜索什么通常指的就是目标。搜索什么通常指的就是目标。v在哪里搜索在哪里搜索在哪里搜索就是在哪里搜索就是“搜索空间搜索空间”。搜索空间通常。搜索空间通常是指一系列状态的汇集，因此称为是指一系列状态的汇集，因此称为状态空间状态空间。2024/7/236o所以，人工智能中的搜索可以分成两个阶段：n状态空间的生成阶段n在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分搜索可以根据是否使用启发式信息分为为v盲目搜索盲目搜索v启发式搜索启发式搜索 2024/7/237o盲目搜索盲目搜索 只是可以区分出哪个是目标状态。 一般是按预定的搜索策略进行搜索。 没有考

5、虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。 o启发式搜索启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。 2024/7/238o根据问题的表示方式分为n状态空间搜索n与或图搜索状态空间状态空间搜索是用搜索是用状态空间状态空间法来求解法来求解问题所进问题所进行的搜索行的搜索与与/ /或图搜或图搜索是指用问索是指用问题规约方法题规约方法来求解问题来求解问题时所进行的时所进行的搜索。搜索。2024/7/239o考虑一个问题的状态空间为一棵树的形式。o宽度优先搜索o深度优先搜索如果根节点首先如果根

6、节点首先扩展，然后是扩扩展，然后是扩展根节点生成的展根节点生成的所有节点，然后所有节点，然后是这些节点的后是这些节点的后继，如此反复下继，如此反复下去。去。在树的最深一层的节点在树的最深一层的节点中扩展一个节点。只有中扩展一个节点。只有当搜索遇到一个死亡节当搜索遇到一个死亡节点（非目标节点并且是点（非目标节点并且是无法扩展的节点）的时无法扩展的节点）的时候，才返回上一层选择候，才返回上一层选择其他的节点搜索。其他的节点搜索。2024/7/2310o无论是宽度优先搜索还是深度优先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为“确定性”的，也就是

7、盲目搜索。o对于启发式搜索，在计算每个节点的参数之前无法确定先选择哪个节点扩展，这种搜索一般也称为非确定的。 2024/7/2311o完备性：n如果存在一个解答，该策略是否保证能够找到？o时间复杂性：n需要多长时间可以找到解答？o空间复杂性：n执行搜索需要多少存储空间？o最优性：n如果存在不同的几个解答，该策略是否可以发现最高质量的解答？搜索策略评价标准搜索策略评价标准: :2024/7/2312有许多智力问题有许多智力问题( (如梵塔问题、旅行商问题、八皇如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等后问题、农夫过河问题等) )和实际问题（如路径规和实际问题（如路径规划、机器人行动规划等

8、）都可以归结为划、机器人行动规划等）都可以归结为状态空间搜状态空间搜索索。用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题的系统均定义一个状态状态空间空间，并通过适当的，并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。3.2 基于状态空间图的搜索技术基于状态空间图的搜索技术2024/7/2313状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(1)(1)状态空间的表示状态空间的表示状态空间的表示状态空间的表示oo状态空间记为状态空间记为状态空间记为状态空间记为SPSP，可表示为

9、二元组：，可表示为二元组：，可表示为二元组：，可表示为二元组：n nSP=(S,O)SP=(S,O)nS问题求解（即搜索）过程中所有问题求解（即搜索）过程中所有可能到达可能到达的的合法状态合法状态构成的集合；构成的集合；nO操作算子操作算子的集合，的集合，操作算子的执行会导致问题状态的操作算子的执行会导致问题状态的变迁变迁 ；n状态状态用于记载问题求解（即搜索）过程中用于记载问题求解（即搜索）过程中某一时刻问某一时刻问题现状的快照题现状的快照；o抽象为矢量形式抽象为矢量形式 Q=q0,q1,qnTo每个元素每个元素qi称为称为状态分量状态分量 o给定每个给定每个状态分量状态分量qi的值就得到一

10、个具体的状态的值就得到一个具体的状态 Qk=q0k,q1k,qnkT2024/7/2314状态状态表示状态的变迁表示状态的变迁操作算子操作算子问题的状态空间问题的状态空间是一个表示该问题的全部可能状态是一个表示该问题的全部可能状态及其变迁的及其变迁的有向图有向图。 o节点节点n状态状态o有向弧有向弧n状态的变迁状态的变迁 o弧上的标签弧上的标签n导致状态变迁的导致状态变迁的操作算子操作算子 用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题的系统均定义一个状态状态空间空间，并通过适当的，并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。2024/7/2

11、315例例例例1 1：走迷宫走迷宫走迷宫走迷宫是人们熟悉的一种游戏。是人们熟悉的一种游戏。是人们熟悉的一种游戏。是人们熟悉的一种游戏。状态空间搜索状态空间搜索2024/7/2316oo格子、入口和出口格子、入口和出口格子、入口和出口格子、入口和出口节点节点节点节点状态状态状态状态oo通道通道通道通道有向弧有向弧有向弧有向弧操作算子操作算子操作算子操作算子oo迷宫可以由一个迷宫可以由一个迷宫可以由一个迷宫可以由一个有向图有向图有向图有向图表示表示表示表示2024/7/2317 例例2:在在一一个个33的的方方格格棋棋盘盘上上放放置置着着1,2,3,4,5,6,7,8八八个个数数码码，每每个个数数

12、码码占占一一格格，且且有有一一个个空空格格。这这些些数数码码可可在在棋棋盘盘上上移移动动，其其移移动动规规则则是是：与与空空格格相相邻邻的数码方可移入空格。的数码方可移入空格。现现在在的的问问题题是是：对对于于指指定定的的初初始始棋棋局局和和目目标标棋棋局局，给出给出数码的移动序列数码的移动序列。该问题称为。该问题称为八数码问题八数码问题。 56741382初始棋局初始棋局56748321目标棋局目标棋局移动数码移动数码2024/7/23182 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47

13、 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 52024/7/23192024/7/2320状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示

14、(2)(2)状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子“ “传教士和野人问题传教士和野人问题传教士和野人问题传教士和野人问题” ”o问题的描述问题的描述问题的描述问题的描述：n nN N个传教士带领个传教士带领个传教士带领个传教士带领N N个野人划船过河；个野人划船过河；个野人划船过河；个野人划船过河；n n3 3个安全约束条件：个安全约束条件：个安全约束条件：个安全约束条件：o1)船上人数不得超过载重限量，设为船上人数不得超过载重限量，设为K个人；个人； o2)任何时刻（包括两岸、船上）野人数目不得任何时刻（包括两岸、船上）野人数目不得超过传教士

15、；超过传教士； o3)允许在河的某一岸或者在船上只有野人而没允许在河的某一岸或者在船上只有野人而没有传教士；有传教士；2024/7/2321状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(2)(2)状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子“ “传教士和野人问题传教士和野人问题传教士和野人问题传教士和野人问题” ”o 特例：特例：特例：特例：N=3N=3，K=2 K=2 n n状态分量状态分量状态分量状态分量mm传教士在左岸的实际人数传教士在左岸的实际人数传教士在左岸的实际人

16、数传教士在左岸的实际人数n n状态分量状态分量状态分量状态分量c c野人在左岸的实际人数野人在左岸的实际人数野人在左岸的实际人数野人在左岸的实际人数n n状态分量状态分量状态分量状态分量b b指示船是否在左岸指示船是否在左岸指示船是否在左岸指示船是否在左岸(1(1、0)0)n n3 3个安全约束条件个安全约束条件个安全约束条件个安全约束条件oom m c ( c (左岸安全左岸安全左岸安全左岸安全) )且且且且 N-m N-m N-c( N-c(右岸安全右岸安全右岸安全右岸安全); );oom=0m=0且且且且0c N (0c N (左岸没有传道士，右岸一定安全左岸没有传道士，右岸一定安全左岸

17、没有传道士，右岸一定安全左岸没有传道士，右岸一定安全); );ooN-m=0N-m=0且且且且0N-cN (0N-cN (右岸没有传道士，左岸一定安全右岸没有传道士，左岸一定安全右岸没有传道士，左岸一定安全右岸没有传道士，左岸一定安全); );2024/7/2322设设设设初始状态初始状态初始状态初始状态下传教士、野人和船都在左岸，下传教士、野人和船都在左岸，下传教士、野人和船都在左岸，下传教士、野人和船都在左岸，目标状态目标状态目标状态目标状态下下下下这三者均在右岸，这三者均在右岸，这三者均在右岸，这三者均在右岸，问题状态问题状态问题状态问题状态以以以以（m,c,bm,c,b）表示表示表示表

18、示。oo问题的求解任务可描述为：问题的求解任务可描述为：问题的求解任务可描述为：问题的求解任务可描述为：(3,3,1)(3,3,1) (0,0,0)(0,0,0)oo该简单问题该简单问题该简单问题该简单问题可能到达可能到达的的合法状态合法状态：n n可能状态可能状态可能状态可能状态总数总数总数总数：4 4 2=32n n根据条件得出根据条件得出根据条件得出根据条件得出合法状态合法状态合法状态合法状态：2020oom m c c 且且且且 N-m N-m N-c N-c ( (左岸安全且右岸安全左岸安全且右岸安全左岸安全且右岸安全左岸安全且右岸安全) )n nm=1,c=1m=1,c=1；m=2

19、,c=2m=2,c=2 oom=0m=0且且且且0c N(0c N(左岸没有传道士左岸没有传道士左岸没有传道士左岸没有传道士) )n nm=0,c=0,1,2,3m=0,c=0,1,2,3 ooN-m=0N-m=0且且且且0N-cN(0N-cN(右岸没有传道士右岸没有传道士右岸没有传道士右岸没有传道士) )n nm=3,c=0,1,2,3m=3,c=0,1,2,3n n不可能到达的合法状态不可能到达的合法状态不可能到达的合法状态不可能到达的合法状态：o(0,0,1),(0,3,0),(3,0,1),(3,3,0)n n可能到达可能到达可能到达可能到达的的的的合法状态合法状态合法状态合法状态共共

20、共共1616个个个个2024/7/2323状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(2)状态空间表示的经典例子状态空间表示的经典例子“传教士和野人问题传教士和野人问题”o定义定义2类类操作算子操作算子：nL(x,y)指示从指示从左岸左岸到到右岸右岸的划船操作的划船操作 nR(x,y)指示从指示从右岸右岸到到左岸左岸的划船操作的划船操作ox + y K=2(船的载重限制船的载重限制)；ox和和y取值的可能组合只有取值的可能组合只有5个个o10，20，11，01，02 o( 允许在船上只有野人而没有传教士允许在船上只有

21、野人而没有传教士 )n共有共有10个操作算子个操作算子2024/7/2324渡河问题的状态空间有向图渡河问题的状态空间有向图2024/7/2325状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示o由此例可以看出由此例可以看出n n用状态空间方法表示问题时，首先必须用状态空间方法表示问题时，首先必须用状态空间方法表示问题时，首先必须用状态空间方法表示问题时，首先必须定义状定义状定义状定义状态的描述形式态的描述形式态的描述形式态的描述形式，通过使用这种描述形式可把问，通过使用这种描述形式可把问，通过使用这种描述形式可把问，通过

22、使用这种描述形式可把问题的题的题的题的一切状态都表示出来一切状态都表示出来一切状态都表示出来一切状态都表示出来。另外，还要。另外，还要。另外，还要。另外，还要定义一定义一定义一定义一组操作组操作组操作组操作，通过使用这些操作可把问题，通过使用这些操作可把问题，通过使用这些操作可把问题，通过使用这些操作可把问题由一种状由一种状由一种状由一种状态转变为另一种状态态转变为另一种状态态转变为另一种状态态转变为另一种状态。 n n问题的求解过程是一个问题的求解过程是一个问题的求解过程是一个问题的求解过程是一个不断把操作作用于状态不断把操作作用于状态不断把操作作用于状态不断把操作作用于状态的过程的过程的过

23、程的过程。如果在使用某个操作后得到的新状态。如果在使用某个操作后得到的新状态。如果在使用某个操作后得到的新状态。如果在使用某个操作后得到的新状态是目标状态，就得到了问题的一个解。这个解是目标状态，就得到了问题的一个解。这个解是目标状态，就得到了问题的一个解。这个解是目标状态，就得到了问题的一个解。这个解是从是从是从是从初始状态到目标状态所用操作构成的序列初始状态到目标状态所用操作构成的序列初始状态到目标状态所用操作构成的序列初始状态到目标状态所用操作构成的序列。 2024/7/2326状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其

24、搜索的表示o由此例可以看出由此例可以看出n n要使问题由一种状态转变到另一种状态时，就要使问题由一种状态转变到另一种状态时，就要使问题由一种状态转变到另一种状态时，就要使问题由一种状态转变到另一种状态时，就必须使用一次操作。这样，在从初始状态转变必须使用一次操作。这样，在从初始状态转变必须使用一次操作。这样，在从初始状态转变必须使用一次操作。这样，在从初始状态转变到目标状态时，就可能存在多个操作序列到目标状态时，就可能存在多个操作序列到目标状态时，就可能存在多个操作序列到目标状态时，就可能存在多个操作序列( (即得即得即得即得到多个解到多个解到多个解到多个解) )。那么，其中。那么，其中。那么

25、，其中。那么，其中使用操作最少或较少的使用操作最少或较少的使用操作最少或较少的使用操作最少或较少的解才为最优解解才为最优解解才为最优解解才为最优解( (因为只有在使用操作时所付出的因为只有在使用操作时所付出的因为只有在使用操作时所付出的因为只有在使用操作时所付出的代价为最小的解才是最优解代价为最小的解才是最优解代价为最小的解才是最优解代价为最小的解才是最优解) )。 n n对其中的某一个状态，可能存在多个操作使对其中的某一个状态，可能存在多个操作使对其中的某一个状态，可能存在多个操作使对其中的某一个状态，可能存在多个操作使该状态变到几个不同的后继状态那么到底用该状态变到几个不同的后继状态那么到

26、底用该状态变到几个不同的后继状态那么到底用该状态变到几个不同的后继状态那么到底用哪个操作进行搜索呢哪个操作进行搜索呢哪个操作进行搜索呢哪个操作进行搜索呢? ?这就有赖于这就有赖于这就有赖于这就有赖于搜索策略了搜索策略了搜索策略了搜索策略了不同的搜索策略有不同的顺序不同的搜索策略有不同的顺序不同的搜索策略有不同的顺序不同的搜索策略有不同的顺序，这就是本章后，这就是本章后，这就是本章后，这就是本章后面要讨论的问题。面要讨论的问题。面要讨论的问题。面要讨论的问题。 2024/7/2327课堂练习课堂练习o有一农夫带一只狐狸、一只小羊和一篮菜过河（从有一农夫带一只狐狸、一只小羊和一篮菜过河（从左岸到右

27、岸）。假设船太小，农夫每次只能带一样左岸到右岸）。假设船太小，农夫每次只能带一样东西过河；考虑到安全，无农夫看管时，狐狸和小东西过河；考虑到安全，无农夫看管时，狐狸和小羊不能在一起，小羊和那篮菜也不能在一起。请为羊不能在一起，小羊和那篮菜也不能在一起。请为该问题的解决设计状态空间，并画出状态空间图。该问题的解决设计状态空间，并画出状态空间图。2024/7/2328解析解析o以变量以变量m m、f f、s s、v v分别指示农夫、狐狸、小羊、菜分别指示农夫、狐狸、小羊、菜, ,且每个且每个变量只可取值变量只可取值1(1(表示在左岸表示在左岸) )或或0(0(表示在右岸表示在右岸) )。问题状态可

28、。问题状态可以四元组以四元组(m(m、f f、s s、v)v)描述描述, ,设初始状态下均在左岸设初始状态下均在左岸, ,目标状目标状态下都到达右岸。从而态下都到达右岸。从而, ,问题求解任务可描述为问题求解任务可描述为 (1, 1, 1, 1) -(0, 0, 0, 0)(1, 1, 1, 1) -(0, 0, 0, 0)o由于问题简单由于问题简单, ,状态空间中可能的状态总数为状态空间中可能的状态总数为2222 = 2222 = 16,16,由于要遵从安全限制由于要遵从安全限制, ,合法的状态只有合法的状态只有( (除初、目状态外除初、目状态外):): 1110 1110，11011101

29、，10111011，10101010，01010101，00010001，00100010，01000100；不合法状态有不合法状态有: 0111,1000,1100,0011,0110,1001: 0111,1000,1100,0011,0110,1001o设计二类操作算子设计二类操作算子:Lx:Lx、Rx,xRx,x为为m m、f f、s s、v v时分别指示农夫时分别指示农夫独自独自, ,带狐狸带狐狸, ,带小羊带小羊, ,带菜过河；状态空间图如下所示带菜过河；状态空间图如下所示. .由于由于LxLx和和RxRx是互逆操作是互逆操作, ,故而解答路径可有无数条故而解答路径可有无数条, ,

30、但最近的只有但最近的只有二条二条; ;都是都是7 7个操作步个操作步. . o思考：为什么不把船的状态放到状态空间中去？思考：为什么不把船的状态放到状态空间中去？2024/7/2329解析解析: :四元组四元组(m(m、f f、s s、v)v)2024/7/2330状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(3)状态空间的搜索状态空间的搜索o状态空间的搜索记为状态空间的搜索记为SE，可表示为五元组：，可表示为五元组：nSE=(S,O,E,I,G)；nE搜索引擎；搜索引擎；nI问题的初始状态，问题的初始状态，I S；n

31、G问题的目标状态集合，问题的目标状态集合，G S。o搜索引擎搜索引擎E可以设计为可以设计为实现任何搜索算法实现任何搜索算法的控制系统。的控制系统。o基本思想基本思想通过搜索引擎通过搜索引擎E寻找一个寻找一个操作算子的调用序操作算子的调用序列列，使问题从初始状态，使问题从初始状态I变迁到目标状态变迁到目标状态G之一。之一。o解答路径解答路径初初-目变迁过程中目变迁过程中的的状态序列状态序列或相应的或相应的操作算操作算子调用序列子调用序列。2024/7/2331状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示o或图（一般图）或

32、图（一般图）n一个状态一个状态可以可以有多个可供选择有多个可供选择的操作算子；的操作算子；n操作算子间的选择是一种操作算子间的选择是一种“或或”的关系的关系; ;n这样的有向图称为这样的有向图称为或图。或图。2024/7/2332状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(3)(3)状态空间的搜索状态空间的搜索o或图（一般图）或图（一般图）n一个状态可以有多个可供选择的操作算子；一个状态可以有多个可供选择的操作算子；n操操作作算算子子间间的的选选择择是是一一种种“或或”的的关关系系，这这样样的的有有向图称为向图称为或

33、图。或图。o状态空间状态空间一般都表示为一般都表示为或图（一般图）或图（一般图）o搜搜索索图图在在搜搜索索解解答答路路径径的的过过程程中中画画出出搜搜索索时时涉涉及及到到的节点和弧线，构成所谓的的节点和弧线，构成所谓的搜索图搜索图。状态空间搜索状态空间搜索一般图搜索一般图搜索2024/7/2333状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(3)状态空间的搜索状态空间的搜索o状态空间状态空间、搜索图搜索图和和解答路径解答路径之间的关系之间的关系S0Sg2024/7/2334状态空间搜索状态空间搜索1.1.状态空间及其搜

34、索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(4)(4)一般图搜索例子一般图搜索例子一般图搜索例子一般图搜索例子八数码游戏八数码游戏八数码游戏八数码游戏 oo求解的问题：求解的问题：求解的问题：求解的问题：n n给定初始布局给定初始布局给定初始布局给定初始布局( (即即即即初始状态初始状态初始状态初始状态) )和目标布局和目标布局和目标布局和目标布局( (即即即即目标状态目标状态目标状态目标状态) )，n n如何移动数码才能从初始布局到达目标布局？如何移动数码才能从初始布局到达目标布局？如何移动数码才能从初始布局到达目标布局？如何移动数码才能从初始布局到达目标布局

35、？oo解答解答解答解答n n就是一个合法的就是一个合法的就是一个合法的就是一个合法的棋牌走步序列棋牌走步序列棋牌走步序列棋牌走步序列。初始布局初始布局目标布局目标布局移动数码移动数码2024/7/2335状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(4)(4)一般图搜索例子一般图搜索例子一般图搜索例子一般图搜索例子八数码游戏八数码游戏八数码游戏八数码游戏 oo用一般图搜索方法解决该问题的步骤：用一般图搜索方法解决该问题的步骤：用一般图搜索方法解决该问题的步骤：用一般图搜索方法解决该问题的步骤：n n1 1、为、为、为、

36、为问题状态问题状态问题状态问题状态的表示建立数据结构的表示建立数据结构的表示建立数据结构的表示建立数据结构n n2 2、制定、制定、制定、制定操作算子操作算子操作算子操作算子集合集合集合集合n n3 3、设计、设计、设计、设计搜索引擎搜索引擎搜索引擎搜索引擎 oo第一步：为问题状态的表示建立数据结构第一步：为问题状态的表示建立数据结构第一步：为问题状态的表示建立数据结构第一步：为问题状态的表示建立数据结构n n3333的一个矩阵的一个矩阵的一个矩阵的一个矩阵S Sn n矩阵元素矩阵元素矩阵元素矩阵元素SijSij 0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,其中其中

37、其中其中1i,j3 1i,j3 n n数字数字数字数字0 0表示空格表示空格表示空格表示空格 n n数字数字数字数字1-81-8表示相应的棋牌表示相应的棋牌表示相应的棋牌表示相应的棋牌oo八数码问题就可表示为：八数码问题就可表示为：八数码问题就可表示为：八数码问题就可表示为：2024/7/2336状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示初始布局初始布局目标布局目标布局移动数码移动数码(4)(4)一般图搜索例子一般图搜索例子一般图搜索例子一般图搜索例子八数码游戏八数码游戏八数码游戏八数码游戏 2024/7/2337状

38、态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(4)一般图搜索例子一般图搜索例子八数码游戏八数码游戏 o第二步：制定操作算子集第二步：制定操作算子集n直观方法直观方法为每个棋牌制定一套可能的走步：左、上、右、为每个棋牌制定一套可能的走步：左、上、右、下四种移动。下四种移动。o需要需要32个操作算子个操作算子n简易方法简易方法仅为空格制定这仅为空格制定这4种走步。种走步。o仅需仅需4个操作算子个操作算子o第三步：设计搜索引擎第三步：设计搜索引擎 n问题状态空间的大小问题状态空间的大小与与问题涉及的元素问题涉及的元素个数是程个

39、数是程指数级指数级爆炸式增长爆炸式增长（即，（即，组合爆炸问题组合爆炸问题）o如，棋盘布局（问题状态）总共有如，棋盘布局（问题状态）总共有9!=362880个个 n研究焦点研究焦点是是解决组合爆炸问题解决组合爆炸问题，通过压缩搜索空间通过压缩搜索空间，提提高搜索效率高搜索效率。 2024/7/2338状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间状态空间、搜索图搜索图和和解答路径解答路径之间的关系之间的关系S0Sg2024/7/2339状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般

40、图搜索策略 （1）搜索术语）搜索术语o1、节点深度、节点深度n根节点根节点指示指示初始状态初始状态，令其深度为，令其深度为0；n搜索图中的其他节点的搜索图中的其他节点的深度深度dn就可以递归地定义为就可以递归地定义为其其父节点深度父节点深度dn-1加加1：dn= dn-1+1。 根节点深度根节点深度=0=0第第第第n-1n-1n-1n-1层节点层节点层节点层节点d d d dn-1n-1n-1n-1第第第第n n n n层节点层节点层节点层节点d d d dn n n n= = = = d d d dn-1n-1n-1n-1+1+1+1+1搜索图搜索图2024/7/2340状态空间搜索状态空间

41、搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略 （1）搜索术语）搜索术语o2、节点扩展、节点扩展n应用应用操作算子操作算子将将上一状态上一状态（节点（节点ni）变迁到）变迁到下一状态下一状态（节点（节点nj）n节点节点ni称为称为被扩展节点被扩展节点（父节点）（父节点）n节点节点nj称为称为ni的的子节点子节点节点节点节点节点n n n ni i i i节点节点节点节点n n n nj j j j2024/7/2341（1 1）搜索术语）搜索术语）搜索术语）搜索术语oo3 3、路径、路径、路径、路径 n n节点节点节点节点n ni i到到到到n nj j的路径是由相的路径

42、是由相的路径是由相的路径是由相邻节点间的邻节点间的邻节点间的邻节点间的弧线构成的弧线构成的弧线构成的弧线构成的折线折线折线折线n n要求路径是无环的要求路径是无环的要求路径是无环的要求路径是无环的o4、路径代价、路径代价相邻节点相邻节点ni和和ni+1间的间的路径代价路径代价记为记为C(ni, ni+1) n通常令通常令任意相邻节点间任意相邻节点间的路径代价相同的路径代价相同，并以，并以路径长度路径长度1 1指示。指示。n即即C(ni, ni+1)=1 。状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略节点节点n ni i节点节点ni+1节点节点nj20

43、24/7/2342状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略 （1 1）搜索术语）搜索术语）搜索术语）搜索术语oo4 4、路径代价、路径代价、路径代价、路径代价目标状态节点目标状态节点目标状态节点目标状态节点n n n ng g g g节点节点节点节点n n n ni i i i节点节点节点节点n n n nk k k kC(nk,ng) C(ni,nk) C(ni,ng) 2024/7/2343状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2 2）一般图搜索算法）一般图搜索算法）一般图搜索算法）一般图搜

44、索算法o符号说明：符号说明：ns-初始状态节点初始状态节点nG-搜索图搜索图nOPEN-存放存放待扩展节点待扩展节点的表的表nCLOSE-存放存放已被扩展的节点已被扩展的节点的表的表nMOVE-FIRST(OPEN)-取取OPEN表首的节点表首的节点作为作为当前要被扩展当前要被扩展的节点的节点n，同时，同时将节点将节点n移至移至CLOSE表表o一般图搜索算法划分为二个阶段：一般图搜索算法划分为二个阶段：n1、初始化、初始化 n2、搜索循环、搜索循环 2024/7/2344状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2 2）一般图搜索算法）一般图搜索

45、算法）一般图搜索算法）一般图搜索算法o算法划分为二个阶段：算法划分为二个阶段：n1、初始化、初始化 o建立建立只包含初始状态节点只包含初始状态节点s的搜索图的搜索图G:=soOPEN:=soCLOSE:= n2、搜索循环、搜索循环oMOVE-FIRST(OPEN)-取出取出OPEN表首的节点表首的节点n作为扩展的节作为扩展的节点，同时将其移到点，同时将其移到close表表 o扩展出扩展出n的子节点的子节点,插入插入搜索图搜索图G和和OPEN表表 o适当的标记和修改指针适当的标记和修改指针o排序排序OPEN表表n通过循环地执行该算法，通过循环地执行该算法，搜索图搜索图G会因不断有新节点加入而逐会

46、因不断有新节点加入而逐步长大，直到搜索到目标节点。步长大，直到搜索到目标节点。 2024/7/2345以下面的八数码为例，看一般图的搜索算法以下面的八数码为例，看一般图的搜索算法以下面的八数码为例，看一般图的搜索算法以下面的八数码为例，看一般图的搜索算法初始布局初始布局目标布局目标布局移动数码移动数码状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略2024/7/23462024/7/23472024/7/23482024/7/23492024/7/23502024/7/23512024/7/23522024/7/23532024/7/23542024/7

47、/23552024/7/23562024/7/23572024/7/23582024/7/23592024/7/23602024/7/23612024/7/23622024/7/23632024/7/23642024/7/2365状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2 2）一般图搜索算法）一般图搜索算法）一般图搜索算法）一般图搜索算法搜索过程中的指针修改搜索过程中的指针修改o节点节点n扩展后扩展后的子节点分为的子节点分为3类类：n(i)全新节点全新节点n(ii)已出现在已出现在OPEN表表中的节点中的节点n(iii)已出现的已出现的CLOS

48、E表表中的节点中的节点o指针标记和修改的方法：指针标记和修改的方法：n(i)类节点：加入类节点：加入OPEN表，建立从子节点到父节点表，建立从子节点到父节点n的指针的指针n(ii)类节点、类节点、 (iii)类节点类节点o比较比较经由经由老父节点老父节点、新父节点新父节点n到达到达初始状态节点初始状态节点的的路径代路径代价价 o经由新父节点经由新父节点n的代价比较小，则将原子节点指向老父节点的代价比较小，则将原子节点指向老父节点的指针，修改为指向新父节点的指针，修改为指向新父节点no (iii)类节点还得从类节点还得从CLOSE表中移出，重新加入表中移出，重新加入OPEN表。表。2024/7/

49、2366状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略Sn4ninjn1n2n3n31n32o节点节点ni是当前扩展的节点；是当前扩展的节点；o扩展出扩展出4个后续节点；个后续节点；on1、n2是新节点是新节点，只需建立只需建立指向父节点的指针，并加入指向父节点的指针，并加入OPEN表表；2024/7/2367状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略Sn4ninjn1n2n3n31n32on4已经存在于已经存在于OPEN表，并表，并且已有父节点且已有父节点njnn4经经nj的路径代价大的路径代价大n取消取

50、消n4指向指向nj的指针的指针n改为建立改为建立n4指向新父节点指向新父节点ni的的指针指针on3已经存在于已经存在于CLOSE表，表，并且已有父节点并且已有父节点njn需要做和需要做和n4同样的比较和指同样的比较和指针修改工作。并且要重新加入针修改工作。并且要重新加入open表。表。2024/7/2368状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2）一般图搜索算法）一般图搜索算法oOPEN表中节点简单的排序方式表中节点简单的排序方式：n深度优先深度优先扩展当前节点后生成的子节点总是扩展当前节点后生成的子节点总是置于置于OPEN表的前端表的前端，

51、即，即OPEN表表作为作为栈栈，后进先出后进先出，使，使搜索搜索优先向纵深方向发展优先向纵深方向发展。2024/7/2369深度优先深度优先实例实例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67

52、5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 612346891113141618191 2 3 8 47 6 5目标目标571012151720212024/7/2370深度优先搜索深度优先搜索o在深度优先搜索中，首先扩展最新产生的在深度优先搜索中，首先扩展最新产生的( (最最深的深的) )节点，深度节点，深度 相等的节点可以任意排列。相等的节点可以任意排列。o“最晚产生的节点最先扩展最晚产生的节点最先扩展”起始节点深度为0 任何其他节点的深度等于其父辈节点深度加上1 :dn=dn-1+12024/7/2371深度优先搜索深度优先

53、搜索很明显这样做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿着一条路线无限制地扩展下去，这当然是不允许的。为保证找到解，应选择适当的深度界限，或者采取不断加大深度界限的办法，反复搜索，直到找到解。这种改进的方法叫做迭代加深搜索。2024/7/2372Procedure Depth First SearchBegin把初始节点压入栈，并设置栈顶指针；把初始节点压入栈，并设置栈顶指针；While 栈不空栈不空 do Begin弹出栈顶元素；弹出栈顶元素； If 栈顶元素栈顶元素=goal=goal，成功返回并结束；，成功返回并结束； Else 以任意次序把栈顶

54、元素的子女压入栈中；以任意次序把栈顶元素的子女压入栈中；End WhileEnd基于栈实现的深度优先搜索算法： 2024/7/2373o初始节点放到栈中，栈指针指向栈的最上边的元素。初始节点放到栈中，栈指针指向栈的最上边的元素。o为了对该节点进行检测，需要从栈中弹出该节点，如果是目标，该为了对该节点进行检测，需要从栈中弹出该节点，如果是目标，该算法结束，否则把其子节点以任何顺序压入栈中。该过程直到栈变算法结束，否则把其子节点以任何顺序压入栈中。该过程直到栈变成为空。成为空。o遍历遍历遍历遍历一棵树的过程（下图）。一棵树的过程（下图）。 2024/7/2374深度优先搜索的性质深度优先搜索的性质

55、深度优先搜索的性质深度优先搜索的性质o一般不能保证找到最优解一般不能保证找到最优解o当深度限制不合理时，当深度限制不合理时，可能找不到解可能找不到解，可以，可以将算法改为将算法改为可变深度限制可变深度限制o最坏情况时，搜索空间等同于穷举最坏情况时，搜索空间等同于穷举o是一个通用的与问题无关的方法是一个通用的与问题无关的方法2024/7/2375o深度优先搜索深度优先搜索的的优点优点是比宽度优先搜索算是比宽度优先搜索算法需要较少的空间，该算法只需要保存搜法需要较少的空间，该算法只需要保存搜索树的一部分，它由当前正在搜索的路径索树的一部分，它由当前正在搜索的路径和该路径上还没有完全展开的节点标志所

56、和该路径上还没有完全展开的节点标志所组成。组成。o深度优先搜索的存储器要求是深度约束的深度优先搜索的存储器要求是深度约束的线性函数。线性函数。 深度优先搜索的优点深度优先搜索的优点深度优先搜索的优点深度优先搜索的优点2024/7/2376深度优先搜索的缺点深度优先搜索的缺点深度优先搜索的缺点深度优先搜索的缺点 既不是完备的，也不是最优的。既不是完备的，也不是最优的。 主要问题是可能搜索到了错误的路径上。很多主要问题是可能搜索到了错误的路径上。很多问题可能具有很深甚至是无限的搜索树，如果不幸问题可能具有很深甚至是无限的搜索树，如果不幸选择了一个错误的路径，则深度优先搜索会一直搜选择了一个错误的路

57、径，则深度优先搜索会一直搜索下去，而不会回到正确的路径上。这样一来对于索下去，而不会回到正确的路径上。这样一来对于这些问题，深度优先搜索要么陷入无限的循环而不这些问题，深度优先搜索要么陷入无限的循环而不能给出一个答案，要么最后找到一个答案，但路径能给出一个答案，要么最后找到一个答案，但路径很长而且不是最优的答案。很长而且不是最优的答案。2024/7/2377状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2）一般图搜索算法）一般图搜索算法oOPEN表中节点简单的排序方式表中节点简单的排序方式：n深度优先深度优先扩展当前节点后生成的子节点总是扩展当前节点

58、后生成的子节点总是置于置于OPEN表的前端表的前端，即，即OPEN表表作为作为栈栈，后进先出后进先出，使，使搜索搜索优先向纵深方向发展优先向纵深方向发展。n宽度优先宽度优先扩展当前节点后生成的子节点总是扩展当前节点后生成的子节点总是置于置于OPEN表的后端表的后端，即，即OPEN表表作为作为队列队列，先进先出先进先出，使，使搜搜索优先向横向方向发展索优先向横向方向发展。2024/7/2378宽度优先实宽度优先实例例2 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6

59、 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标目标82 3 41 8 7 6 54910111213141516172024/7/2379宽度优先搜索宽度优先搜索 如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”2024/7/2380Proced

60、ure Breadth-first-searchProcedure Breadth-first-searchBeginBegin把初始节点放入队列；把初始节点放入队列； RepeatRepeat取得队列最前面的元素为取得队列最前面的元素为current;current; If current=goal If current=goal 成功返回并结束；成功返回并结束； Else doElse do Begin Begin 如果如果currentcurrent有子女，则有子女，则currentcurrent的子女的子女 以任意次序添加到队列的尾部；以任意次序添加到队列的尾部； EndEnd Unt

61、il Until 队列为空队列为空 EndEnd采用队列结构，宽度优先算法可以表示如下：2024/7/2381o宽度优先搜索算法原理：宽度优先搜索算法原理：o如果当前的节点不是目标节点，则把当点如果当前的节点不是目标节点，则把当点节点的子孙以任意顺序增加到队列的后面，节点的子孙以任意顺序增加到队列的后面，并把队列的前端元素定义为并把队列的前端元素定义为currentcurrent。o如果目标发现，则算法终止。如果目标发现，则算法终止。 2024/7/2382宽度优先搜索的性质宽度优先搜索的性质o当问题有解时，当问题有解时，一定一定能找到解能找到解o当问题为单位代价时，且问题有解时，当问题为单位

62、代价时，且问题有解时，一定一定能找到最优解能找到最优解o方法与问题无关，具有通用性方法与问题无关，具有通用性o效率较低效率较低o属于图搜索方法属于图搜索方法2024/7/2383o宽度优先搜索宽度优先搜索是一种盲目搜索，是一种盲目搜索，时间和空间复杂度都比较高，当时间和空间复杂度都比较高，当目标节点距离初始节点较远时会目标节点距离初始节点较远时会产生许多无用的节点，搜索效率产生许多无用的节点，搜索效率低。低。o宽度优先搜索中，时间需求是一宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的个很大的问题，特别是当搜索的深度比较大时，尤为严重，但是深度比较大时，尤为严重，但是空间需求是比执行时

63、间更严重的空间需求是比执行时间更严重的问题。问题。 宽度优先搜索优点：目标节点如果存在，用宽度优先搜索算法总可以找到该目标节点，而且是最小（即最短路径）的节点。宽度优先搜索的优点和缺点宽度优先搜索的优点和缺点2024/7/2384总结总结 o适用场合适用场合 深深度度优优先先当当一一个个问问题题有有多多个个解解答答或或多多条条解解答答路路径径，且只须找到其中一个时；往往应对搜索深度加以限制。且只须找到其中一个时；往往应对搜索深度加以限制。 宽度优先宽度优先确保搜索到最短的解答路径。确保搜索到最短的解答路径。o共同优缺点：共同优缺点： 可可直直接接应应用用一一般般图图搜搜索索算算法法实实现现，不

64、不需需要要设设计计特特别别的的节节点点排排序序方方法法，从从而而简简单单易易行行，适适合合于于许许多多复复杂杂度度不不高高的的问问题求解任务。题求解任务。 节节点点排排序序的的盲盲目目性性，由由于于不不采采用用领领域域专专门门知知识识去去指指导导排排序序，往往往往会会在在白白白白搜搜索索了了大大量量无无关关的的状状态态节节点点后后才才碰碰到到解解答，所以也称为答，所以也称为盲目搜索盲目搜索。 2024/7/2385有界深度搜索和迭代加深搜索有界深度搜索和迭代加深搜索 有界深度优先搜索有界深度优先搜索过程总体上按深度优先算过程总体上按深度优先算法方法进行，但对搜索深度需要给出一个深法方法进行，但

65、对搜索深度需要给出一个深度限制度限制dmdm，当深度达到了，当深度达到了dmdm的时候，如果还的时候，如果还没有找到解答，就停止对该分支的搜索，换没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。到另外一个分支进行搜索。2024/7/2386策略说明策略说明: : o（1 1）深度限制深度限制dmdm很重要很重要。当问题有解，且当问题有解，且解的路径长度小于或等于解的路径长度小于或等于dmdm时，则搜索过时，则搜索过程一定能够找到解，但是和深度优先搜索程一定能够找到解，但是和深度优先搜索一样这并不能保证最先找到的是最优解。一样这并不能保证最先找到的是最优解。o但是当但是当dmdm取

66、得太小，解的路径长度大于取得太小，解的路径长度大于dmdm时，则搜索过程中就找不到解，即这时搜时，则搜索过程中就找不到解，即这时搜索过程甚至是不完备的。索过程甚至是不完备的。2024/7/2387（2 2）深度限制深度限制dmdm不能太大不能太大。当。当dmdm太大时，搜索太大时，搜索过程会产生过多的无用节点，既浪费了计算过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。机资源，又降低了搜索效率。（3 3）有界深度搜索的主要问题是）有界深度搜索的主要问题是深度限制值深度限制值dmdm的选取的选取。 2024/7/2388改进方法改进方法： （迭代加深搜索）（迭代加深搜索） 先任意

67、给定一个较小的数作为先任意给定一个较小的数作为dmdm，然后，然后按有界深度算法搜索，若在此深度限制按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制内没有找到问题的解，则增大深度限制dmdm，继续搜索。，继续搜索。2024/7/2389o迭代加深搜索迭代加深搜索，试图尝试所有可能的深度限制：，试图尝试所有可能的深度限制：n首先深度为首先深度为0 0，n然后深度为然后深度为1 1，n然后为然后为2 2，等等。，等等。o如果初始深度为如果初始深度为0 0，则该算法只生成根节点，并，则该算法只生成根节点，并检测它

68、。检测它。o如果根节点不是目标，则深度加如果根节点不是目标，则深度加1 1，通过典型的，通过典型的深度优先算法，生成深度为深度优先算法，生成深度为1 1的树。的树。o当深度限制为当深度限制为m m时，树的深度为时，树的深度为m m。 2024/7/2390o迭代加深搜索看起来会很浪费，因为很多节点迭代加深搜索看起来会很浪费，因为很多节点都可能扩展多次。都可能扩展多次。o然而对于很多问题，这种多次的扩展负担实际然而对于很多问题，这种多次的扩展负担实际上很小，直觉上可以想象，如果一棵树的分支上很小，直觉上可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则系数很大，几乎所有的节点都在

69、最底层上，则对于上面各层节点扩展多次对整个系统来说影对于上面各层节点扩展多次对整个系统来说影响不是很大。响不是很大。 2024/7/2391搜索最优策略的比较搜索最优策略的比较 o表注：表注：b是分支系数，是分支系数，d是解答的深度，是解答的深度，m是搜索树的最是搜索树的最大深度，大深度，l是深度限制。是深度限制。2024/7/2392o宽度优先搜索、深度优先搜索和迭代加深搜宽度优先搜索、深度优先搜索和迭代加深搜索都可以用于生成和测试算法。索都可以用于生成和测试算法。o宽度优先搜索宽度优先搜索需要指数数量的空间，深度优需要指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性先搜索的空间

70、复杂度和最大搜索深度呈线性关系。关系。 2024/7/2393o迭代加深搜索迭代加深搜索对一棵深度受控的树采用深度对一棵深度受控的树采用深度优先的搜索。它结合了宽度优先和深度优先优先的搜索。它结合了宽度优先和深度优先搜索的优点。搜索的优点。o和宽度优先搜索一样，它是最优的，也是完和宽度优先搜索一样，它是最优的，也是完备的。但对空间要求和深度优先搜索一样是备的。但对空间要求和深度优先搜索一样是适中的。适中的。 2024/7/2394状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2）一般图搜索算法）一般图搜索算法o常用的简单方式：常用的简单方式：n深度优

71、先深度优先n宽度优先宽度优先n【缺点：节点排序的盲目性缺点：节点排序的盲目性】o在白白在白白搜索了大量无关的状态节点搜索了大量无关的状态节点后才碰到解后才碰到解答，答，效率低效率低o提高提高一般图搜索一般图搜索效率效率的关键的关键n优化优化OPEN表中节点的排序方式表中节点的排序方式盲目搜索盲目搜索2024/7/2395125634最理想情况：最理想情况：每次排序后每次排序后OPEN表表表首元素表首元素n n总在解答路径上总在解答路径上2024/7/2396启发式搜索启发式搜索o启发式知识启发式知识指导指导OPEN表排序表排序的的一般图搜索一般图搜索：n全局排序全局排序对对OPEN表中的表中的

72、所有节点排序所有节点排序，使使最有希望最有希望的节点排在表首。的节点排在表首。oA算法，算法， A*算法（掌握！）算法（掌握！）n局部排序局部排序仅对仅对新新扩展出来的子节点排序扩展出来的子节点排序，使这些使这些新新节点中节点中最有希望最有希望者能优先取出考察者能优先取出考察和扩展；和扩展；o爬山法（了解，爬山法（了解，对对深度优先法深度优先法的改进的改进）；）；2024/7/2397启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌握）o【基本思想基本思想】n设计体现启发式知识的设计体现启发式知识的评价函数评价函数f(n)；n指导指导一般图搜索一般图搜索中中OPEN表待扩

73、展节点的排序表待扩展节点的排序：o【评价函数评价函数f(n)=g(n)+h(n) （掌握）（掌握） 】nn-搜索图搜索图G中中的节点的节点；nf(n)- G中从初始状态节点中从初始状态节点s，经由节点，经由节点n到达目到达目标节点标节点ng，估计估计的的最小路径代价最小路径代价；ng(n)- G中从中从s到到n，目前实际目前实际的路径代价；的路径代价；nh(n)-从从n到到ng，估计估计的最小路径代价；的最小路径代价；2024/7/2398启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌握）Snng目标状态节点目标状态节点目标状态节点目标状态节点n n n ng g g

74、g初始状态节点初始状态节点初始状态节点初始状态节点S S S S节点节点节点节点n n n n搜索图搜索图G Gh(n): n-ng的估计最小路径代价的估计最小路径代价 g(n):s-n的实际路径代价的实际路径代价 f(n):s-n-ng的的估计估计最小路径代价最小路径代价 2024/7/2399启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌握）o【评价函数评价函数f(n)=g(n)+h(n) （掌握）（掌握） 】nn-搜索图搜索图G中中的节点的节点；nf(n)- G中从中从s经经n到到ng，估计估计的的最小路径代价最小路径代价；ng(n)- G中从中从s到到n，目前实

75、际目前实际的路径代价；的路径代价；nh(n)-从从n到到ng，估计估计的的最小路径代价最小路径代价； oh(n)值值-依赖于依赖于启发式知识启发式知识加以计算；加以计算；oh(n)称为称为启发式函数启发式函数（掌握意义！掌握意义！）。o如何用评价函数来实现如何用评价函数来实现A算法算法? （ 掌握！掌握！） 2024/7/23100启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌握）oA算法算法的设计与的设计与一般图搜索一般图搜索相同，划分为二个阶段：相同，划分为二个阶段：n1、初始化、初始化 o建立只包含初始状态节点建立只包含初始状态节点s的搜索图的搜索图G:=soOP

76、EN:=soCLOSE:= n2、搜索循环、搜索循环oMOVE-FIRST(OPEN)-取出取出OPEN表首表首的节点的节点n o扩展出扩展出n的子节点的子节点,插入搜索图插入搜索图G和和OPEN表表 o适当的标记和修改指针（适当的标记和修改指针（子节点子节点父节点父节点）o排序排序OPEN表（表（评价函数评价函数f(n)的值排序）的值排序）n通过循环地执行该算法，搜索图会因不断有新节点加入而逐步通过循环地执行该算法，搜索图会因不断有新节点加入而逐步长大，直到搜索到目标节点。长大，直到搜索到目标节点。2024/7/23101启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌

77、握）o算法算法A的设计与一般图搜索类似，划分为二个阶段：的设计与一般图搜索类似，划分为二个阶段：n1、初始化、初始化 n2、搜索循环、搜索循环oMOVE-FIRST(OPEN)-取出取出OPEN表首的节点表首的节点n o扩展出扩展出n的子节点的子节点,插入搜索图插入搜索图G和和OPEN表表 n对每个子节点对每个子节点ni,计算计算f(n,ni)=g(n,ni)+h(ni)o适当的标记和修改指针适当的标记和修改指针（子节点子节点父节点父节点）o排序排序OPEN表表（评价函数（评价函数f(n)的值排序）的值排序）2024/7/23102启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌

78、握掌握掌握）o扩展出扩展出n的子节点的子节点,插入搜索图插入搜索图G和和OPEN表表 n对每个子节点对每个子节点ni,计算计算f(n,ni)=g(n,ni)+h(ni)o适当的标记和修改指针适当的标记和修改指针（子节点子节点父节点父节点）n(i)全新节点：全新节点：f(ni)=f(n,ni)n(ii)已出现在已出现在OPEN表表中的节点中的节点n(iii)已出现的已出现的CLOSE表表中的节点中的节点oIF f(ni)f(n,ni) THENo 修改指针指向修改指针指向新新父结点父结点no f(ni)=f(n,ni)o排序排序OPEN表表（f(n)值从小到大排序）值从小到大排序）2024/7/

79、231032.若OPEN表是空表，则失败退出；算法A3.3.选择选择OPENOPEN表上的第一个表上的第一个节点，把它从节点，把它从OPENOPEN表移出表移出并放进并放进CLOSECLOSE表中，称此表中，称此节点为节点节点为节点n n； 1.建立一个只包含起始只包含起始节点节点S S的搜索图G,把S放到一个叫OPEN的未扩展节点表中；建立一个叫做CLOSE的已扩展节点表，其初始为空表；5.扩展节点n，同时生成不是n的祖先的那些子节点的集合M,把M的这些成员作为n的后继节点添入图G中；对于对于M M中每个子中每个子节点节点n ni i, ,计算计算f(n,f(n,n ni i) = ) =

80、g(n,ng(n,ni i) + h(n) + h(ni i););4.若n为一目标节点，则有解成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；2024/7/231046.6.对那些未曾在对那些未曾在G G中出现过的中出现过的M M成员（全新节点）设置一个通成员（全新节点）设置一个通向向n n的指针。把的指针。把M M的这些成员加的这些成员加进进OPENOPEN表。对已经在表。对已经在OPENOPEN表上表上的每一个的每一个M M成员，成员，比较子节点比较子节点n ni i经由新、老父节点的评价函经由新、老父节点的评价函数值数值f(n,nf(n,ni i) )、f(nf(ni i)

81、;);若若f(n,nf(n,ni i) f(n) f(ni i) )点点, ,则令则令f(nf(ni i) ) = f(n,n= f(n,ni i),),并移动子节点指向并移动子节点指向老父节点的指针，改为指向新老父节点的指针，改为指向新父节点。父节点。对已在对已在CLOSECLOSE表上的表上的每个每个M M成员，作与第成员，作与第2 2类同样的类同样的处理，并把这些子结点从处理，并把这些子结点从CLOSECLOSE表移出，重新加入表移出，重新加入OPENOPEN表。表。7.按按f(n)排序排序OPEN表中的表中的节点，节点，f(n)值最小者排在首值最小者排在首位位，重排，重排OPEN表；表

82、；8.转转2。此过程生成一个明确的此过程生成一个明确的图图G(G(搜索图）和一个搜索图）和一个G G的子集的子集T(T(搜索树）。搜索树）。2024/7/23105启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌握）A A算法实例算法实例算法实例算法实例八数码游戏八数码游戏八数码游戏八数码游戏o1)设计评价函数设计评价函数f(n)nf(n)=d(n)+w(n),其中其中nd(n)-节点节点n在搜索图中的在搜索图中的节点深度节点深度，对，对g(n)的度量的度量；nw(n)-代表启发式函数代表启发式函数h(n),其值是节点其值是节点n与目标状态节点与目标状态节点ng相比较，不

83、考虑空格，相比较，不考虑空格，错位的棋牌个数错位的棋牌个数；初始布局初始布局目标布局目标布局移动数码移动数码2024/7/23106启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌握）启发式算法启发式算法启发式算法启发式算法A A实例实例实例实例八数码游戏八数码游戏八数码游戏八数码游戏o1)设计评价函数设计评价函数f(n)nf(n)计算实例计算实例初始布局初始布局s目标布局目标布局ngw(s):错位的棋牌个数错位的棋牌个数d(s):当前节点深度当前节点深度 f(s)h(n): n-ng的最小路径代价的最小路径代价 g(n):s-n的最小路径代价的最小路径代价 f(n):s

84、-n-ng的最小路径代价的最小路径代价 注：注：W(S)不考虑空格不考虑空格2024/7/23107状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略 （1）搜索术语）搜索术语o1、节点深度、节点深度n根节点根节点指示指示初始状态初始状态，令其深度为，令其深度为0；n搜索图中的其他节点的搜索图中的其他节点的深度深度dn就可以递归地定义为就可以递归地定义为其其父节点深度父节点深度dn-1加加1：dn= dn-1+1。 根节点深度根节点深度=0=0第第第第n-1n-1n-1n-1层节点层节点层节点层节点d d d dn-1n-1n-1n-1第第第第n n n

85、n层节点层节点层节点层节点d d d dn n n n= = = = d d d dn-1n-1n-1n-1+1+1+1+1搜索图搜索图G G2024/7/23108启发式搜索启发式搜索1.A1.A算法（算法（算法（算法（掌握掌握掌握掌握）启发式算法启发式算法启发式算法启发式算法A A实例实例实例实例八数码游戏八数码游戏八数码游戏八数码游戏o1)设计评价函数设计评价函数f(n)nf(n)计算实例计算实例初始布局初始布局s目标布局目标布局ngw(s):错位的棋牌个数错位的棋牌个数d(s):当前节点深度当前节点深度 f(s)h(n): n-ng的最小路径代价的最小路径代价 g(n):s-n的最小路

86、径代价的最小路径代价 f(n):s-n-ng的最小路径代价的最小路径代价 0 4 4 注：注：W(S)不考虑空格不考虑空格2024/7/23109初始化初始化OPEN:=s4 CLOSE:= 2024/7/23110循环循环1CLOSE:=s4 OPEN:=a b c OPEN:=a6 b4 c6 OPEN:=b4 a6 c6 2024/7/23111循环循环2CLOSE:=s4 b4 OPEN:=a6 c6 d e i OPEN:=a6 c6 d5 e5 i6 OPEN:=d5 e5 a6 c6 i6 2024/7/23112循环循环3CLOSE:=s4 b4 d5 OPEN:=e5 a6

87、c6 i6 j k OPEN:=e5 a6 c6 i6 j7 k6 OPEN:=e5 a6 c6 i6 k6 j7 2024/7/23113循环循环4CLOSE:=s4,b4,d5,e5 OPEN:=a6 c6 i6 k6 j7 l m OPEN:=a6 c6 i6 k6 j7 l5 m7 OPEN:=l5 a6 c6 i6 k6 j7 m7 2024/7/23114CLOSE:=s4,b4,d5,e5,l5 循环循环5OPEN:=a6 c6 i6 k6 j7 m7 n OPEN:=a6 c6 i6 k6 j7 m7 n5 OPEN:=n5 a6 c6 i6 k6 j7 m7 2024/7/2

88、3115循环循环6CLOSE:=s4,b4,d5,e5,l5,n5 OPEN:=a6 c6 i6 k6 j7 m7 o g OPEN:=a6 c6 i6 k6 j7 m7 o7 g5 OPEN:=g5 a6 c6 i6 k6 j7 m7 o7 2024/7/23116循环循环7成功结束成功结束2024/7/23117最理想搜索图最理想搜索图G2024/7/23118判断失误判断失误2024/7/23119o 例例 2 2 给定给定4L4L和和3L3L的水壶各一个，水壶上的水壶各一个，水壶上没有刻度，可以向水壶中加水。没有刻度，可以向水壶中加水。o如何在如何在4L4L的壶中准确地得到的壶中准确地

89、得到2L2L水？水？ o（x,yx,y）4L4L壶里的水有壶里的水有x xL L，3L3L壶里的水壶里的水有有y yL L，on n表示搜索空间中的任一节点。表示搜索空间中的任一节点。o则给出下面的启发式函数：则给出下面的启发式函数： 2024/7/23120o h h( (n n) ) = = 2 2 如果如果0 0 x x 4 4并且并且0 0 y y 3 3 = = 4 4 如果如果0 0 x x 4 4或者或者0 0 y y 3 =g*(n)oh(n)尽可能尽可能靠近靠近h*(n) A算法的关键算法的关键。2024/7/23127启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现

90、启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素（1 1）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性(Admissibility)(Admissibility)o4)改进启发式函数改进启发式函数八数码游戏八数码游戏nf(n)=d(n)+w(n),其中其中nw(n)-表示表示错位的棋牌个数错位的棋牌个数，不够贴切，错误的，不够贴切，错误的扩展了节点扩展了节点d；np(n)-节点节点n与目标状态节点比较，与目标状态节点比较，错位棋牌在不错位棋牌在不受阻拦的情况下，移动到目标状态相应位置所受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数

91、）的总和需走步（移动次数）的总和；np(n)比比w(n)更接近于更接近于h*(n)-p(n)不仅考虑了棋牌不仅考虑了棋牌的错位因素，还考虑了错位的距离（移动距离）的错位因素，还考虑了错位的距离（移动距离）2024/7/23128启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素4)改进启发式函数改进启发式函数八数码游戏八数码游戏nf(s)计算实例计算实例初始布局初始布局s目标布局目标布局ngw(s):错位的棋牌个数错位的棋牌个数d(s):当前节点深度当前节点深度 f(s)0 4 4 p(s):错位棋牌移动距离错位棋牌移动

92、距离d(s):当前节点深度当前节点深度 f(s)0 5 5 1 1 1 2 2024/7/23129初始化初始化OPEN:=s5 CLOSE:= 2024/7/23130循环循环1CLOSE:=s5 OPEN:=a b c OPEN:=a7 b5 c7 OPEN:=b5 a7 c7 2024/7/23131循环循环2CLOSE:=s5 b5 OPEN:=a7 c7 d e i OPEN:=a7 c7 d7 e5 i7 OPEN:=e5 a7 c7 d7 i7 2024/7/23132循环循环3CLOSE:=s5 b5 e5 OPEN:=a7 c7 d7 i7 l m OPEN:=a7 c7 d

93、7 i7 l5 m7 OPEN:=l5 a7 c7 d7 i7 m7 2024/7/23133CLOSE:=s5,b5,e5,l5 循环循环4OPEN:=a7 c7 d7 i7 m7 n OPEN:=a7 c7 d7 i7 m7 n5 OPEN:=n5 a7 c7 d7 i7 m7 2024/7/23134CLOSE:=s5,b5,e5,l5,n5 循环循环5OPEN:=a7 c7 d7 i7 m7 o g OPEN:=a7 c7 d7 i7 m7 o7 g5 OPEN:=g5 a7 c7 d7 i7 m7 o7 2024/7/23135循环循环6成功结束成功结束最理想搜索图最理想搜索图G20

94、24/7/23136避免了错误选择避免了错误选择2024/7/23137启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素（1 1）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性(Admissibility)(Admissibility)o5) A*算法算法定义：定义：o1、在、在A算法算法中，规定中，规定h(n)h*(n);o2、经如此限制以后的、经如此限制以后的A算法算法就是就是A*算法算法。nA*算法是算法是可采纳的可采纳的，即总能搜索到即总能搜索到最短解答路径最短解答路径n【回顾：

95、回顾：八数码游戏的八数码游戏的h(n)】ow(n)-错位的棋牌个数错位的棋牌个数op(n)-错位棋牌在不受阻拦的情况下，移动到目标状错位棋牌在不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和态相应位置所需走步（移动次数）的总和；2024/7/23138启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素（1 1）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性(Admissibility)(Admissibility)o5) A*算法算法定义：定义：o1、在、在A算法算法中，

96、规定中，规定h(n)h*(n);o2、经如此限制以后的、经如此限制以后的A算法算法就是就是A*算法算法。nA*算法是算法是可采纳的可采纳的，即总能搜索到即总能搜索到最短解答路径最短解答路径n证明：证明：【人工智能人工智能 上册上册陆汝陆汝钤钤钤钤P248】o1）如果存在一条从初始状态到目标状态的解答路径，则）如果存在一条从初始状态到目标状态的解答路径，则一定一定存在一条最短解答通路存在一条最短解答通路；o2）设）设状态状态n是最短解答路径上的一个状态是最短解答路径上的一个状态，那么经过有限步，那么经过有限步后，后，n必然会成为必然会成为OPEN表的第一个节点；表的第一个节点；o3）因为）因为最

97、短解答路径只有有限个节点最短解答路径只有有限个节点n，所以有限步后算法，所以有限步后算法必然因到达目标状态必然因到达目标状态ng。这就是最优解。这就是最优解。o证明完毕。证明完毕。2024/7/23139启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素（1 1）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性(Admissibility)(Admissibility)o5)满足可采纳性条件的算法满足可采纳性条件的算法A*算法算法n证明：证明：o2）设）设状态状态n是最短解答路径上的一个状态

98、是最短解答路径上的一个状态，那么经过有限步后，那么经过有限步后，n必然会成为必然会成为OPEN表的第一个节点；表的第一个节点；of(n)=g(n)+h(n)o 根据假设，根据假设，n在最短解答路径上在最短解答路径上o 经过有限步骤后，经过有限步骤后，g(n)= g*(n)o f(n)=g*(n)+h(n)o h(n)h*(n)o f(n)=g*(n)+h(n) g*(n)+h*(n)=f*(n)o f*(n)= f*(ng)o f(n) f*(ng)2024/7/23140启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因

99、素（1 1）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性）搜索算法的可采纳性(Admissibility)(Admissibility)o5)满足可采纳性条件的算法满足可采纳性条件的算法A*算法算法n证明：证明：o2）设）设状态状态n是最短解答路径上的一个状态是最短解答路径上的一个状态，那么经过有限，那么经过有限步后，步后，n必然会成为必然会成为OPEN表的第一个节点；表的第一个节点；o设设OPEN表中表中n之前的节点只有有限个，设为之前的节点只有有限个，设为N个，其中估个，其中估计值最小者为计值最小者为a1，并称之为，并称之为第一代节点第一代节点；由第一代节点生；由第一代节点生

100、成的节点称为成的节点称为第二代节点第二代节点，其中估计值最小者为，其中估计值最小者为a2；oa2a1+e(其中，其中，e0，表示每扩展一次起码的代价，表示每扩展一次起码的代价)o扩展扩展j代后，代后， aj a1+(j-1)eo当当j足够大时一定有足够大时一定有aj f*(ng)o f(n) f*(ng)且且OPEN表中表中n之前的节点经过之前的节点经过j次扩展后的次扩展后的最小估计值最小估计值aj f*(ng) f(n) o 经过有限步后，经过有限步后，n必然会成为必然会成为OPEN表的第一个节点表的第一个节点2024/7/23141启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现启

101、发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素（2）启发式函数的强弱及其影响）启发式函数的强弱及其影响oh(n)接近接近h*(n)的程度的程度衡量启发式函数的强弱衡量启发式函数的强弱nh(n)h*(n)，h(n)过强过强，A算法失去可采纳性算法失去可采纳性，不能确保找，不能确保找到最短解答路径；到最短解答路径；nh(n)=h*(n)是最理想是最理想的，的， OPEN表中节点排序没有误差表中节点排序没有误差，可可以确保产生最小的搜索图，搜索到最短解答路径；以确保产生最小的搜索图，搜索到最短解答路径；o无法设计无法设计nA*算法搜索问题解答的关键算法搜索问题解答的关键oh(n)

102、在满足在满足h(n) h*(n)的条件下，越大越好！的条件下，越大越好！2024/7/23142启发式搜索启发式搜索2.2.实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素实现启发式搜索的关键因素（2）启发式函数的强弱及其影响）启发式函数的强弱及其影响o定理：解决同一问题的两个定理：解决同一问题的两个A*算法算法A1和和A2，n若若h1(n) h2(n) h*(n)且且g1(n)=g2(n)n则则t(A1) t(A2)n其中，其中，h1、h2分别是算法分别是算法A1、A2的启发式函数，的启发式函数，t指示相应算法到达目标状态时指示相应算法到达目标状态时搜索图含的节点总数

103、搜索图含的节点总数。n【证明：证明： 人工智能人工智能 上册上册陆汝钤陆汝钤 P250）】o八数码游戏：八数码游戏：w(n)p(n) h*(n)op(n)扩展出的节点总数扩展出的节点总数t(w(n)2024/7/23143迭代加深迭代加深迭代加深迭代加深A*A*算法算法算法算法 o由于由于A*A*算法把所有生成的节点保存在内存中，所算法把所有生成的节点保存在内存中，所以以A*A*算法在耗尽计算时间之前一般早已经把空间算法在耗尽计算时间之前一般早已经把空间耗尽了。耗尽了。o目前开发了一些新的算法，它们的目的是为了克目前开发了一些新的算法，它们的目的是为了克服空间问题。服空间问题。o但一般不满足最

104、优性或完备性，如迭代加深但一般不满足最优性或完备性，如迭代加深A*A*算算法法IDA*IDA*、简化内存受限、简化内存受限A*A*算法算法SMA*SMA*等。等。o下面简单介绍下面简单介绍IDA*IDA*算法。算法。 2024/7/23144o迭代加深搜索算法，它以深度优先的方式在有限制迭代加深搜索算法，它以深度优先的方式在有限制的深度内搜索目标节点。的深度内搜索目标节点。o在每个深度上，该算法在每个深度上检查目标节点在每个深度上，该算法在每个深度上检查目标节点是否出现，如果出现则停止，否则深度加是否出现，如果出现则停止，否则深度加1 1继续搜继续搜索。索。o而而A*A*算法是选择具有最小估价

105、函数值的节点扩展。算法是选择具有最小估价函数值的节点扩展。2024/7/23145o迭代加深迭代加深A* A* 搜索算法搜索算法IDA*IDA*是上述两种算法是上述两种算法的结合的结合。o这里启发式函数用做深度的限制，而不是选这里启发式函数用做深度的限制，而不是选择扩展节点的排序。择扩展节点的排序。2024/7/23146迭代加深迭代加深A*算法算法Procedure IDA*算法算法Begin (1) 初始化当前的深度限制初始化当前的深度限制c=1 (2) 把初始节点压入栈把初始节点压入栈; 并假定并假定 (3) While 栈不空桥栈不空桥do Begin 弹出栈顶元素弹出栈顶元素n If

106、 n=goal, Then 结束结束, 返回返回n以及从初始节点到以及从初始节点到n的路径的路径 Else do Begin For n 的每个子节点的每个子节点 If , Then 把把 压入栈压入栈 Else End for End End While (4) If 栈为空并且栈为空并且 , Then 停止并退出停止并退出 (5) If 栈为空并且栈为空并且 , Then , 并返回并返回2 End 2024/7/23147oIDA*算法和A*算法相比，主要优点是对于内存的需求。A*算法需要指数级数量的存储空间，因为没有深度方面的限制。而IDA*算法只有当节点n的所有子节点 的 小于限制值

107、c时才扩展它,这样就可以节省大量的内存。o另一问题是当启发式函数是最优的时候，IDA*算法和A*算法扩展相同的节点，并且可以找到最优路径。特点特点2024/7/23148启发式搜索启发式搜索o启发式知识启发式知识指导指导OPEN表排序表排序的的一般图搜索一般图搜索：n全局排序全局排序对对OPEN表中的表中的所有节点排序所有节点排序，使使最有希望最有希望的节点排在表首。的节点排在表首。oA算法，算法， A*算法（掌握！）算法（掌握！）n局部排序局部排序仅对仅对新新扩展出来的子节点排序扩展出来的子节点排序，使这些使这些新新节点中节点中最有希望最有希望者能优先取出考察者能优先取出考察和扩展；和扩展；

108、o爬山法（了解，爬山法（了解，对对深度优先法深度优先法的改进的改进）；）；2024/7/23149 简单的搜索策略：简单的搜索策略： g(n)0, f(n)= h(n),g(n)0, f(n)= h(n), 局部排序局部排序只排序新扩展出来的子节点，即局部排序只排序新扩展出来的子节点，即局部排序 简单易行，适用于不要求最优解答的问题求解任务。简单易行，适用于不要求最优解答的问题求解任务。 1 1）爬山法）爬山法实现启发式搜索的最简单方法。实现启发式搜索的最简单方法。 类似于人爬山类似于人爬山只要好爬，总是选取最陡处，以求快速登顶。只要好爬，总是选取最陡处，以求快速登顶。 求求函函数数极极大大值

109、值问问题题非非数数值值解解法法，依依赖赖于于启启发发式式知知识识，试试探探性性地地逐逐步步向向顶顶峰峰逼近逼近 适用于能逐步求精的问题。适用于能逐步求精的问题。 爬山法特点：爬山法特点： 只能向上，不准后退，从而简化了搜索算法；体现在：只能向上，不准后退，从而简化了搜索算法；体现在： * * 从从当当前前状状态态节节点点扩扩展展出出的的子子节节点点（相相当当于于找找到到上上爬爬的的路路径径）中中，将将h(n)h(n)最最小小的的子子节节点点（对对应应于于到到顶顶峰峰最最近近的的上上爬爬路路径径）作作为为下下一一次次考考察察和和扩扩展展的的节节点点，其其余余子子节点全部丢弃。节点全部丢弃。 不需

110、设置不需设置OPENOPEN和和CLOSECLOSE表，因为没有必要保存任何待扩展节点；表，因为没有必要保存任何待扩展节点； 爬爬山山法法对对于于单单一一极极值值问问题题（登登单单一一山山峰峰）十十分分有有效效而而又又简简便便, ,对对于于具具有有多多极极值值的问题无能为力的问题无能为力会错登上次高峰而失败：不能到达最高峰。会错登上次高峰而失败：不能到达最高峰。回溯策略和爬山法回溯策略和爬山法 2024/7/2315010J(0,1)用梯度下降算法用梯度下降算法最小化代价函数最小化代价函数J(0,1)2024/7/2315101J(0,1)2024/7/231522024/7/23153 2

111、2）回溯策略）回溯策略 可可以以有有效效地地克克服服爬爬山山法法面面临临的的困困难难保保存存了了每每次次扩扩展展出出的的子子节节点点，并并按按h(n)h(n)值值从从小到大排列。小到大排列。 相相当当于于爬爬山山的的过过程程中中记记住住了了途途经经的的岔岔路路口口路路径径搜搜索索失失败败时时回回溯溯（后后退退），向向另一路径方向搜索另一路径方向搜索 回溯策略和爬山法回溯策略和爬山法 2024/7/23154 2 2）回溯策略）回溯策略 递归过程递归过程实现回溯策略的有效方式实现回溯策略的有效方式 算法名为算法名为BACKTRACK(n),BACKTRACK(n),参数参数n n为当前被扩展的节

112、点，为当前被扩展的节点， 初次调用时初次调用时n n即为初始状态节点即为初始状态节点s s； 分两个部分：分两个部分：* * 判断当前节点判断当前节点n n的状态，的状态，* * 作作搜搜索索工工作作扩扩展展节节点点n n，递递归归调调用用该该算算法法，处处理理返返回结果。回结果。回溯策略和爬山法回溯策略和爬山法 2024/7/23155令令PATHPATH、SNLSNL、n n、n n 为局部变量：为局部变量： PATH- PATH-节点列表，指示解答路径；节点列表，指示解答路径； SNL- SNL-当前节点扩展出的子节点列表；当前节点扩展出的子节点列表； MOVE-FIRST(SNL)-M

113、OVE-FIRST(SNL)-把把SNLSNL表表首首的的节节点点移移出出，作作为为下下一一次次要要加加以以扩扩展展的的节点；节点； n n、n n-分别指示当前考察和下一次考察的节点。分别指示当前考察和下一次考察的节点。 该该递递归归过过程程的的算算法法就就取取名名为为BACKTRACK(n),BACKTRACK(n),参参数数n n为为当当前前被被扩扩展展的的节节点点，算算法法的的初初次调用式是次调用式是BACKTRACK(s),sBACKTRACK(s),s即为初始状态节点。算法的步骤如下：即为初始状态节点。算法的步骤如下：（1 1） 若若n n是目标状态节点，则算法的本次调用成功结束，

114、返回空表；是目标状态节点，则算法的本次调用成功结束，返回空表；（2 2） 若若n n是失败状态，则算法的本次调用失败结束，返回是失败状态，则算法的本次调用失败结束，返回FAILFAIL；（3 3） 扩扩展展节节点点n n，将将生生成成的的子子节节点点置置于于列列表表SNLSNL，并并按按评评价价函函数数f(k) f(k) = = h(k)h(k)的的值从小到大排序（值从小到大排序（k k指示子节点）；指示子节点）；（4 4） 若若SNLSNL为空，则算法的本次调用失败结束，返回为空，则算法的本次调用失败结束，返回FAILFAIL；（5 5） n= MOVE-FIRST(SNL)n= MOVE-

115、FIRST(SNL)；（6 6） PATH = BACKTRACK(n)PATH = BACKTRACK(n)；（7 7） 若若PATH =FAIL, PATH =FAIL, 返回到语句（返回到语句（4 4）；）；（8 8） 将将nn加到加到PATHPATH表首，算法的本次调用成功结束，返回表首，算法的本次调用成功结束，返回PATHPATH。2024/7/23156 2 2）回溯策略）回溯策略 三种失败状态：三种失败状态： 不合法状态（如传教士和野人问题中所述的那样）不合法状态（如传教士和野人问题中所述的那样） 旧旧状状态态重重现现（如如八八数数码码游游戏戏中中某某一一棋棋盘盘布布局局的的重重

116、现现，会会导导致搜索算法死循环），致搜索算法死循环）， 状状态态节节点点深深度度超超过过预预定定限限度度（例例如如八八数数码码游游戏戏中中，指指示示解解答路径不超过答路径不超过6 6步）。步）。 回溯条件回溯条件 失败状态，由算法第（失败状态，由算法第（2 2）句指示；）句指示； 搜索进入搜索进入“死胡同死胡同”，由该算法的第，由该算法的第(4)(4)句定义。句定义。回溯策略和爬山法回溯策略和爬山法 2024/7/23157 2 2）回溯策略）回溯策略 解解答答路路径径的的生生成成从从相相应应于于目目标标状状态态节节点点的的空空表表开开始始，递递归归返返回回PATHPATH。 影响回溯算法效率

117、的关键因素影响回溯算法效率的关键因素回溯次数回溯次数。 回溯回溯搜索到失败状态时的一种弥补行为，搜索到失败状态时的一种弥补行为， 准准确确选选择择下下一一步步搜搜索索考考察察的的节节点点大大幅幅度度减减少少甚甚至至避避免免回回溯。溯。 设计好的启发式函数设计好的启发式函数h(n)h(n)是至关重要的。是至关重要的。回溯策略和爬山法回溯策略和爬山法 2024/7/23158问题归约问题归约o问题归约问题归约是人求解问题常用的策略：是人求解问题常用的策略：n把把复杂的问题复杂的问题变换为若干需要变换为若干需要同时同时处理的较为处理的较为简单的子问题简单的子问题后再加以分别求解后再加以分别求解n只有

118、子问题全部解决时只有子问题全部解决时，问题才算解决问题才算解决；n问题的解答问题的解答由子问题的解答联合由子问题的解答联合构成。构成。o本节主要内容：本节主要内容：n问题归约的描述（理解）问题归约的描述（理解）n与或图搜索的基本过程（理解）与或图搜索的基本过程（理解）n与或图的启发式搜索（与或图的启发式搜索（掌握掌握）2024/7/23159问题归约法问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题2024/7/23160o问题归约可以用三元组表示：（问题归约可以用三元组表示：（S S0 0，O

119、O，P P），其中），其中nS S0 0是初始问题，即要求解的问题；是初始问题，即要求解的问题；nP P是本原问题集，其中的每一个问题是不用证是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或明的，自然成立的，如公理、已知事实等，或已证明过的问题；已证明过的问题；nO O是操作算子集，它是一组变换规则，通过一是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。个操作算子把一个问题化成若干个子问题。2024/7/23161o问题归约表示方法就是由初始问题出发，运问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算

120、子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直用操作算子产生子问题的子问题，这样一直进行到进行到产生的问题均为本原问题产生的问题均为本原问题，则问题得，则问题得解。解。 2024/7/23162o看如下符号积分问题：看如下符号积分问题：o初始问题初始问题f f ( ( x x ) d ) dx xo变换规则变换规则积分规则积分规则o本原问题本原问题可直接求原函数和积分，可直接求原函数和积分，如如sin ( sin ( x x ) d ) dx x，coscos ( ( x x ) d ) dx x等。等。o所有问题归约的最终目的是产生本原问所有问题归约的最终目的是产生本原

121、问题。题。2024/7/23163符号积分问题符号积分问题（sin3x + x4/(x2 + 1)）dx=sin3xdx + (x4/(x2 + 1)dx=-(1 - cos2x)dcosx + (x2 - 1 + 1/(1 + x2)dx=(-dcosx + cos2xdcosx) + (x2dx - dx + (1/(1 + x2)dx）= -cosx + cos3x/3 + x3/3 - x + arctgx2024/7/23164分子结构识别问题分子结构识别问题 如何区分分子式相同但分子结构不同的有机化合物成为如何区分分子式相同但分子结构不同的有机化合物成为重要而又困难的问题。著名的专

122、家系统重要而又困难的问题。著名的专家系统 DENDRAL能用能用于有效地识别分子结构，该系统建立了一套重写规则去于有效地识别分子结构，该系统建立了一套重写规则去把分子式重写为原子数较少的分子式和原子间结合关系把分子式重写为原子数较少的分子式和原子间结合关系的混合结构的混合结构 2024/7/23165o问题归约的实质：问题归约的实质： 从目标从目标( (要解决的问题要解决的问题) )出发逆向推理，出发逆向推理，建立子问题以及子问题的子问题，直至建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原最后把初始问题归约为一个平凡的本原问题集合。问题集合。2024/7/23166n应用

123、应用问题归约策略问题归约策略得到的得到的状态空间图状态空间图，也称为，也称为“与或图与或图”n逻辑逻辑“与与”关系关系用用圆弧圆弧将几条将几条节点间关联弧节点间关联弧连接在一起连接在一起o表示问题分解为子问题表示问题分解为子问题；o子问题的状态子问题的状态联合起来构成联合起来构成问题状态问题状态。o子问题全部解决才会导致问题的解决子问题全部解决才会导致问题的解决；n逻辑逻辑“或或”关系关系：o问题可以有问题可以有多种分解方式多种分解方式；o问题（子问题）可能激活问题（子问题）可能激活多个状态变迁操作多个状态变迁操作；o只要一种只要一种分解方式分解方式或或状态变迁操作状态变迁操作能导致最终的解答

124、成功能导致最终的解答成功即可；即可；o导致多个可能的解答。导致多个可能的解答。与或图与或图2024/7/23167o用用AND-ORAND-OR图图把问题归约为子问题替换集合。把问题归约为子问题替换集合。o如，假设问题如，假设问题A A既可通过问题既可通过问题C C1 1与与C C2 2，也可通过问题，也可通过问题C C3 3、C C4 4和和C C5 5，或者由单独求解问题，或者由单独求解问题C C6 6来解决，如下图所示。图中各节来解决，如下图所示。图中各节点表示要求解的问题或子问题。点表示要求解的问题或子问题。与或图与或图2024/7/23168梵塔问题梵塔问题n问题描述：问题描述：n初

125、始状态下三个盘按初始状态下三个盘按A、B、C顺序堆放在顺序堆放在1号柱子上；号柱子上；n目标状态下三个盘以同样次序顺序堆放在目标状态下三个盘以同样次序顺序堆放在3号柱子上；号柱子上；n盘子的盘子的搬移规则搬移规则：o每次只能搬一个盘子；每次只能搬一个盘子；o较大盘不能压放在较小盘之上；较大盘不能压放在较小盘之上；CAB初始状态初始状态(1 1 1)目标目标状态状态(3 3 3)CAB132132与或图与或图2024/7/23169梵塔问题梵塔问题状态空间图状态空间图(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)13

126、2CAB(2,2,3)123ABC目标目标状态状态(3 3 3)CAB1322024/7/23170梵塔问题梵塔问题状态空间图状态空间图(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)2024/7/23171梵塔问题梵塔问题(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

127、,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子问题间有子问题间有交互作用交互作用，问题分解问题分解注意注意正确的顺序正确的顺序2024/7/23172与或图搜索与或图搜索o与或图与或图视为对视为对一般图一般图(或图或图)的扩展；的扩展；n引入引入K-连接连接o父子节点父子节点间可以存在间可以存在“与与”关系关系n结果结果解图解图。o解答路径往往不复存在，代之以广义的解路径解答路径往往不复存在，代之以广义的解路径解图解图。问题归约求解问题的过程问题归约求解问题的过程表示为与或图搜索表示为

128、与或图搜索2024/7/23173与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n1、K-连接连接o从从父节点父节点到到K个个子节点子节点的连接，的连接，子节点子节点间间有有“与与”关系关系；o以以圆弧圆弧指示指示这些子节点这些子节点间间的的“与与”关系关系；o一个父节点可以一个父节点可以有多个有多个K-连接连接nK-连接间连接间”或或”关系关系o当当所有的所有的K都等于都等于1时，时，与或图与或图蜕化为蜕化为一般图（或图）一般图（或图）。3个子节点个子节点2个子节点个子节点2024/7/23174与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n2、根、

129、叶、根、叶、终节点终节点o根节点根节点无父节点的节点无父节点的节点n用于指示用于指示问题初始状态（和一般图一样）问题初始状态（和一般图一样）o叶节点叶节点无子节点的节点无子节点的节点o终节点终节点能用于能用于联合表示目标状态的节点联合表示目标状态的节点n终节点必定是叶节点终节点必定是叶节点，反之不然；，反之不然；n目标状态目标状态终结点的集合终结点的集合。2024/7/23175一些关于与或图的术语一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点终节点2024/7/23176与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成o解图纯

130、粹是一种解图纯粹是一种“与与”图图o解图解图中，中，节点节点或或节点组间节点组间不存在不存在“或或”关系；关系；o所有叶节点都是终节点所有叶节点都是终节点2024/7/23177与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成n自自根节点根节点开始选开始选K-连连接接;n从该从该K-连接连接指向的指向的每每个子节点个子节点出发，再选出发，再选一一K-连接连接;n如此反复进行，直到如此反复进行，直到所有所有K-连接连接都指向都指向终终节点节点为止为止.2024/7/231782024/7/23179与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜

131、索的基本概念n3、解图的生成解图的生成o解图纯粹是一种解图纯粹是一种“与与”图图n解图解图中，中，节点节点或或节点组间节点组间不存在不存在“或或”关系；关系；n所有所有叶节点叶节点都是都是终节点终节点o与或图与或图中存在中存在“或或”关系，关系，搜索到多个解图搜索到多个解图；2024/7/23180与或图搜索与或图搜索o2) 解图解图、解图代价、能解节点和不能解节点的定义、解图代价、能解节点和不能解节点的定义n (1)解图解图与或图与或图（记为（记为G）任一节点（记为）任一节点（记为n）到）到终终节点集合节点集合的的解图解图（记为（记为G）是）是G的的子图子图。o(1)若若n是是终节点终节点，

132、则，则G就就由单一节点由单一节点n构成构成；o(2)若若n有一有一K-连接连接指向子节点指向子节点n1，n2，nk,且每且每个子节点都有到终节点集合的个子节点都有到终节点集合的解图解图，则，则G由该由该k-连连接接和所有这些和所有这些相应于子节点的解图相应于子节点的解图构成构成;o(3)否则不存在否则不存在n到到终节点集合终节点集合的的解图解图。 2024/7/23181与或图搜索与或图搜索o2) 解图、解图、解图代价解图代价、能解节点和不能解节点的定义、能解节点和不能解节点的定义n (2)解图代价解图代价 以以C(n)指示节点指示节点n到到终节点集合终节点集合解图解图的的代价，并令代价，并令

133、K-连接的代价就为连接的代价就为K, 则则 o(1)若若n是终节点，则是终节点，则C(n) = 0；o(2)若若n有一有一K-连接连接指向子节点指向子节点n1，n2，nk,且这且这些子节点每个都有到终节点集合的解图些子节点每个都有到终节点集合的解图,则则C(n) = K + C(n1) + C(n2) + + C(nk) 352024/7/23182与或图搜索与或图搜索o2) 解图、解图代价、解图、解图代价、能解节点能解节点和和不能解节点不能解节点的定义的定义n (3)能解节点能解节点 o(1) 终节点是能解节点终节点是能解节点；o(2) 若节点若节点n有有一一K-连接连接指向子节点指向子节点

134、n1，n2，nk,且这些且这些子节点都是能解节点子节点都是能解节点，则，则n是能解节点；是能解节点； 能解节点能解节点能解节点能解节点能解节点能解节点能解节点能解节点2024/7/23183与或图搜索与或图搜索o2) 解图、解图代价、解图、解图代价、能解节点能解节点和和不能解节点不能解节点的定义的定义n (4)不能解节点不能解节点o(1)非终节点的叶节点是不能解节点非终节点的叶节点是不能解节点；o(2)若节点若节点n的的每一个每一个K-连接连接都都至少至少指向一个不能解指向一个不能解节点节点，则，则n是不能解节点。是不能解节点。 能解节点能解节点不能解节点不能解节点能解节点能解节点不能解节点不

135、能解节点不能解节点不能解节点2024/7/23184与或图的启发式搜索与或图的启发式搜索o与或图中搜索的是与或图中搜索的是解图解图，不是解答路径；，不是解答路径；n评价函数评价函数f(n)=h(n)nh(n)是对是对n到到终节点集合终节点集合最小解图代价最小解图代价的估计；的估计；o与或图中存在与或图中存在“或或”关系关系，会有会有多个候选的局部解图多个候选的局部解图；n选择选择局部解图中可能代价最小局部解图中可能代价最小的用于下一步搜索。的用于下一步搜索。o1)（局部）解图代价（局部）解图代价f(n0)nn0初始状态节点初始状态节点n递归地计算出递归地计算出f(n0),比直接用比直接用h(n

136、0)估算估算更为准确。更为准确。n父节点父节点n的的K-连接连接指向的子节点：指向的子节点：n1，n2，nknf(n) = K + h(n1) + h(n2) + + h(nk)，代替，代替h(n)2024/7/23185与或图的启发式搜索与或图的启发式搜索o2) AO*算法算法o符号说明：符号说明：nG-搜索图；搜索图；nG-被选中的被选中的待扩展局部解图待扩展局部解图；nLGS-待扩展局部解图集待扩展局部解图集；nn0-根节点根节点，即初始状态节点；，即初始状态节点；nn-被选中的被选中的待扩展节点待扩展节点；nfi(n0)-第第i个候选的个候选的待扩展局部解图待扩展局部解图的的可能代价可

137、能代价。2024/7/23186与或图的启发式搜索与或图的启发式搜索o2) AO*算法算法o算法划分二个阶段：算法划分二个阶段：n1、初始化、初始化 o建立只包含建立只包含初始状态节点初始状态节点n0的搜索图的搜索图G:=n0；o待扩展局部解图集待扩展局部解图集LGS:=；n2、搜索循环、搜索循环o选择选择和和扩展扩展LGS中的中的局部解图局部解图；o精化精化新局部解图新局部解图代价的估计代价的估计；o传递传递节点的节点的能解性能解性。2024/7/23187与或图的启发式搜索与或图的启发式搜索o2、搜索循环、搜索循环n选择选择和和扩展扩展LGS中的中的局部解图局部解图；o选择选择LGS中中f

138、i(n0)最小的待扩展解图最小的待扩展解图G；o随机随机选择选择G中一个中一个非终节点非终节点的的叶节点叶节点作为作为n；o扩展扩展nn建立建立K-连接连接，子节点，子节点ni并加入并加入G；n计算计算子节点子节点ni的的f(ni)=h(ni)o若若n存在存在j个个K-连接连接nLGS中删除中删除Gn将将j个个新的局部解图新的局部解图加入加入LGS;2024/7/23188与或图的启发式搜索与或图的启发式搜索o2、搜索循环、搜索循环n选择选择和和扩展扩展LGS中的中的局部解图局部解图；n精化精化新新局部解图局部解图代价的估计代价的估计o用公式用公式f(f(n n) = K + h(n1) +

139、h(n2) + + ) = K + h(n1) + h(n2) + + h(nk)h(nk)取代原先的取代原先的f(n);f(n);o递归地递归地作用到作用到初始节点初始节点n n0 0；n传递传递新局部解图中新局部解图中节点的节点的能解性能解性o标记标记作为作为终节点终节点的子节点为的子节点为能解节点能解节点；o递归地递归地传递节点的传递节点的能解性能解性到到初始节点初始节点n n0 0 。f(n)=h(n)2024/7/231892024/7/23190与或图的启发式搜索与或图的启发式搜索o2) AO*算法算法oAO*算法应用例算法应用例o启发式函数启发式函数h(ni)的估算如下：的估算如

140、下：oh(n0)=3oh(n1)=2oh(n2)=1oh(n3)=1oh(n4)=4oh(n5)=2oh(n6)=2oh(n7)=1oh(n8)=1oh(n13)=30123546 7 891011 121314 15161718 19 202024/7/23191初始化初始化候选的待扩展局部解图集候选的待扩展局部解图集LGS:0302024/7/23192012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:32114202024/7/23193012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:321142031201235432114202024

141、/7/23194012354循环循环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)=102024/7/23195012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:1021142056 7 8211122024/7/23196012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:1021142057 8110

142、12215623422024/7/23197012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 8110123166234225252024/7/23198012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 81101231662342131430循环循环32024/7/23199012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 81101261965342131430循环循环33622024/7/23200012354循环循环4候选的待扩展局部解图集候选的待扩展局部解图集LGS:

143、1041142077 811012619653421314301402024/7/23201012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 811012619653421314301401502024/7/23202012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 812012619653421314301401504712024/7/23203012354循环循环6候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 8120126196534213143014015090202

144、4/7/23204012354搜索成功！搜索成功！候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 81201261965342131430140150902024/7/23205与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o1、从局部解图、从局部解图G中选择加以扩展的节点中选择加以扩展的节点nn与或图搜索的是与或图搜索的是解图解图而而非解路径非解路径；n选择选择f(n) = h(n)的值最小的值最小的节点的节点n加以扩展并不加以扩展并不一定会加速搜索过程；一定会加速搜索过程；n应选择导致解图代价发生较大变化应选择导致解图代价发生较大

145、变化的节点的节点n优先优先加以扩展；加以扩展；o使搜索的注意力快速地聚焦到实际代价较小的候选使搜索的注意力快速地聚焦到实际代价较小的候选解图上；解图上；n简单情况下，可简单情况下，可随机选择随机选择加以扩展的节点。加以扩展的节点。2024/7/23206与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o2、算法算法AO*与与A*的比较的比较n解图解图解答路径解答路径，n估计估计代价最小的局部解图代价最小的局部解图加以优先扩展加以优先扩展估计估计代代价最小的路径价最小的路径加以优先扩展；加以优先扩展；n只考虑只考虑评价函数评价函数f(n)=h(n)，只需对新扩展出

146、的节，只需对新扩展出的节点点n计算计算h(n)，用于修正，用于修正fi(n0) 同时计算分量同时计算分量g(n)和和h(n)，以评价节点，以评价节点n是否在代价最小的路径是否在代价最小的路径上。上。n应用应用LGS存放存放待扩展局部解图待扩展局部解图，并依据，并依据fi(n0)值排值排序序应用应用OPEN表和表和CLOSE表分别存放表分别存放待扩展待扩展节点节点和和已扩展节点已扩展节点，并依据，并依据f(n)值值排序排序OPEN表。表。2024/7/23207与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o3、解图代价的重复计算、解图代价的重复计算n某些某些子

147、节点子节点可能会有可能会有多个父节点多个父节点；n这种这种子节点子节点到终节点集合的到终节点集合的解图代价解图代价在计算自在计算自根节点根节点n0出发的解图时被出发的解图时被重复累计重复累计。17 817 814 1512517 8142216241182024/7/23208博弈博弈 n博弈提供了一个可构造的任务领域，在这个领博弈提供了一个可构造的任务领域，在这个领域中，具有明确的胜利和失败；域中，具有明确的胜利和失败；n博弈问题对人工智能研究提出了严峻的挑战。博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和例如，如何表示博弈问题的状态、博弈过程和博弈知识等。

148、博弈知识等。 o这里讲的博弈是这里讲的博弈是二人博弈二人博弈，二人零和二人零和、全信息全信息、非偶然博弈非偶然博弈，博弈双方的利益是，博弈双方的利益是完全对立完全对立的。的。 2024/7/23209n所谓所谓“二人零和二人零和”，是指在博弈中只有，是指在博弈中只有“敌、我敌、我”二方。二方。且双方的利益完全对立，其赢得函数之和为零，即且双方的利益完全对立，其赢得函数之和为零，即 1+2=0 式中，式中，1为我方赢得为我方赢得(利益利益)；2为敌方赢得为敌方赢得(利益利益)。 即：博弈的双方有三种结局：即：博弈的双方有三种结局： (1)我胜：我胜：10；敌负：；敌负：2= -10。 (2)我负

149、：我负：1= -20。 (3)平局：平局：1=0，2=0。 博弈问题对人工智能研究提出了严峻的挑战。例如，如博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和博弈知识等。何表示博弈问题的状态、博弈过程和博弈知识等。 2024/7/23210n所谓所谓“全信息全信息”，是指博弈双方都了解当前的，是指博弈双方都了解当前的格局及过去的历史。格局及过去的历史。 n所谓所谓“非偶然非偶然，是指博弈双方都可根据得失大，是指博弈双方都可根据得失大小进行分析，选取我方赢得最大，敌方赢得最小进行分析，选取我方赢得最大，敌方赢得最小的对策，而不是偶然的随机对策。小的对策，而不是偶然的

150、随机对策。 2024/7/23211（1 1）对垒的双方）对垒的双方MAXMAX和和MINMIN轮流采取行动，博轮流采取行动，博弈的结果只能有弈的结果只能有3 3种情况：种情况：MAXMAX胜、胜、MINMIN败；败；MAXMAX败，败，MINMIN胜；和局。胜；和局。（2 2）在对垒过程中，任何一方都了解当前的）在对垒过程中，任何一方都了解当前的格局和过去的历史。格局和过去的历史。（3 3）任何一方在采取行动前都要根据当前的）任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选择对自己最实际情况，进行得失分析，选择对自己最为有利而对对方最不利的对策，且不存在为有利而对对方最不利的对策

151、，且不存在“碰运气碰运气”的偶然因素，即双方都很理智的偶然因素，即双方都很理智地决定自己的行动。地决定自己的行动。这类博弈如一字棋、象棋、围棋等。博弈的特点博弈的特点博弈的特点博弈的特点 2024/7/23212o另外一种博弈是随机性博弈，是指不可预测另外一种博弈是随机性博弈，是指不可预测性的博弈，如掷硬币游戏等。性的博弈，如掷硬币游戏等。 2024/7/23213例：例：o假设有七枚钱币，任一选手只能将已分好的假设有七枚钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个手轮流进行，直到每一堆都只有一个

152、或两个钱币，不能再分为止，哪个选手遇到不能再钱币，不能再分为止，哪个选手遇到不能再分的情况，则为输。分的情况，则为输。 2024/7/23214o用数字序列加上一个说明表示一个状态，其中数字用数字序列加上一个说明表示一个状态，其中数字表示不同堆中钱币的个数，说明表示下一步由谁来表示不同堆中钱币的个数，说明表示下一步由谁来分，分，o如如（7 7，MINMIN）表示只有一个由七枚钱币组成的堆，表示只有一个由七枚钱币组成的堆，由由MINMIN走，走，MINMIN有有3 3种可供选择的分法，即种可供选择的分法，即n（6 6，1 1，MAXMAX），（），（5 5，2 2，MAXMAX），（），（4 4

153、，3 3，MAXMAX），），o其中其中MAXMAX表示另一选手，不论哪一种方法，表示另一选手，不论哪一种方法，MAXMAX在它在它的基础上再作符合要求的划分。的基础上再作符合要求的划分。2024/7/23215o下图已将双方可能的方案完全表示出来了，无下图已将双方可能的方案完全表示出来了，无论论MINMIN开始时怎么走法，开始时怎么走法，MAXMAX总可以获胜，取胜总可以获胜，取胜的策略用双线箭头表示。的策略用双线箭头表示。2024/7/23216o实际的情况没有这么简单，任何一种棋都不可能实际的情况没有这么简单，任何一种棋都不可能将所有情况列尽，因此，只能模拟人将所有情况列尽，因此，只能模

154、拟人“向前看几向前看几步步”，然后做出决策，决定自己走哪一步最有利。，然后做出决策，决定自己走哪一步最有利。o只能给出几层走法，然后按照一定的估算方法，只能给出几层走法，然后按照一定的估算方法，决定走哪一步棋。决定走哪一步棋。o在双人全信息博弈过程中，双方都希望自己能够在双人全信息博弈过程中，双方都希望自己能够获胜。因此当一方走棋时，都是选择对自己最有获胜。因此当一方走棋时，都是选择对自己最有利，而对对方最不利的走法。利，而对对方最不利的走法。2024/7/23217o假设博弈双方为假设博弈双方为MAXMAX和和MINMIN。在博弈的每一步，可。在博弈的每一步，可供他们选择的方案都有很多种。供

155、他们选择的方案都有很多种。o从从MAXMAX的观点看，可供自己选择的方案之间是的观点看，可供自己选择的方案之间是“或或”的关系，原因是主动权在自己手里，选择哪个的关系，原因是主动权在自己手里，选择哪个方案完全由自己决定，可供自己选择的方案之间方案完全由自己决定，可供自己选择的方案之间是是“或或”的关系，而对那些可供的关系，而对那些可供MINMIN选择的方案之选择的方案之间是间是“与与”的关系，这是因为主动权在的关系，这是因为主动权在MINMIN手中，手中，任何一个方案都可能被任何一个方案都可能被MINMIN选中，选中，MAXMAX必须防止那必须防止那种对自己最不利的情况出现。种对自己最不利的情

156、况出现。 2024/7/23218o下图是把双人博弈过程用图的形式表示出来，下图是把双人博弈过程用图的形式表示出来，这样就可以得到一棵这样就可以得到一棵AND-ORAND-OR树，这种树，这种AND-ORAND-OR树称为博弈树。树称为博弈树。o在博弈树中，那些下一步该在博弈树中，那些下一步该MAXMAX走的节点称走的节点称为为MAXMAX节点，而下一步该节点，而下一步该MINMIN走的节点称为走的节点称为MINMIN节点。节点。2024/7/23219o下图下图 所示是向前看两步，共四层的博弈树，用所示是向前看两步，共四层的博弈树，用表示表示MAXMAX，用用表示表示MINMIN，端节点上的

157、数字表示它对应的估价函数的值。，端节点上的数字表示它对应的估价函数的值。在在MINMIN处用圆弧连接，用处用圆弧连接，用0 0表示其子节点取估值最小的格局。表示其子节点取估值最小的格局。 图中节点处的数字，在端节点是估价函数的值，称它为静态值，在MIN处取最小值，在MAX处取最大值，最后MAX选择箭头方向的走步。 2024/7/23220博弈树特点：博弈树特点：(1)(1)博弈的初始状态是初始节点；博弈的初始状态是初始节点；(2)(2)博弈树的博弈树的“与与”节点和节点和“或或”节点是逐层交替节点是逐层交替出现的；出现的；(3)(3)整个博弈过程始终站在某一方的立场上，所以整个博弈过程始终站在

158、某一方的立场上，所以能使自己一方获胜的终局都是本原问题，相应能使自己一方获胜的终局都是本原问题，相应的节点也是可解节点，所有使对方获胜的节点的节点也是可解节点，所有使对方获胜的节点都是不可解节点。都是不可解节点。 2024/7/23221在人工智能中可以采用搜索方法来求解在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论博弈中两种最博弈问题，下面就来讨论博弈中两种最基本的搜索方法。基本的搜索方法。 2024/7/23222极大极小过程极大极小过程 o极大极小过程是考虑双方对弈若干步之后，极大极小过程是考虑双方对弈若干步之后，从可能的走法中选一步相对好的走法来走，从可能的走法中选一步相对好

159、的走法来走，即在即在有限的搜索深度有限的搜索深度范围内进行求解。范围内进行求解。o需要定义一个需要定义一个静态估价函数静态估价函数f f, ,以便对棋局的以便对棋局的态势做出评估。态势做出评估。 2024/7/23223o这个函数可以根据棋局的态势特征进行定义。这个函数可以根据棋局的态势特征进行定义。假定对弈双方分别为假定对弈双方分别为MAXMAX和和MINMIN，规定：，规定： 有利于有利于MAXMAX方的态势：方的态势：f(p)f(p)取正值取正值 有利于有利于MINMIN方的态势：方的态势：f(p)f(p)取负值取负值 态势均衡的时候：态势均衡的时候：f(p)f(p)取零取零其中其中p

160、p代表棋局。代表棋局。2024/7/23224oMINMAXMINMAX基本思想：基本思想：(1)(1)当轮到当轮到MINMIN走步的节点时（取与时），走步的节点时（取与时），MAXMAX应考虑应考虑最坏的情况（即最坏的情况（即f(p)f(p)取极小值）。取极小值）。(2)(2)当轮到当轮到MAXMAX走步的节点时（取或时），走步的节点时（取或时），MAXMAX应考虑应考虑最好的情况（即最好的情况（即f(p)f(p)取极大值）。取极大值）。(3)(3)评价往回倒推时，相应于两位棋手的对抗策略，评价往回倒推时，相应于两位棋手的对抗策略，交替使用（交替使用（1 1）和（）和（2 2）两种方法传递倒

161、推值。）两种方法传递倒推值。o所以这种方法称为极大极小过程。所以这种方法称为极大极小过程。 2024/7/23225o用用一字棋一字棋说明极大极小过程，设只进行两层，即每方只说明极大极小过程，设只进行两层，即每方只走一步。走一步。o一字棋游戏规则如下：设有一个三行三列的棋盘，如图一字棋游戏规则如下：设有一个三行三列的棋盘，如图所示，两个棋手轮流走步，每个棋手走步时往空格上摆所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。一个自己的棋子，谁先使自己的棋子成三子一线为赢。设设MAX方的棋子用方的棋子用标记，标记，MIN方的棋子用方的棋子用标记，并规标

162、记，并规定定MAX方先走步。方先走步。2024/7/23226 为了不致于生成太大的博弈树，假设每次仅扩展两层。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：估价函数定义如下： 设棋局为设棋局为P，估价函数为，估价函数为e(P)。o(1)(1)若格局若格局p p对任何一方都不是获胜的，则对任何一方都不是获胜的，则 e(p) = (e(p) = (棋局棋局P P上有可能使上有可能使MAXMAX成为三子成一成为三子成一线的状态的数目线的状态的数目) ) （棋局（棋局P P上有可能使上有可能使MINMIN成为三子成为三子成一线的状态的数目）成一线的状态的数目）= e(+p)-e(

163、-p)= e(+p)-e(-p)o(2)(2)若若p p是是MAXMAX获胜，则获胜，则 e(p) = +e(p) = +o（3 3） 若若p p是是MINMIN获胜，则获胜，则 e(p) = - e(p) = - 2024/7/23227o若若p p为下图所示，且为下图所示，且 oe(P)=e(+P)-e(-P)=5-4=12024/7/23228o假设由假设由MAX先走棋，且我们站在先走棋，且我们站在MAX立场上。下图给出了立场上。下图给出了MAX的第一着走棋生的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可成的博弈树。图中节点旁的数字分别表示相应节点的

164、静态估值或倒推值。由图可以看出，对于以看出，对于MAX来说最好的一着棋是来说最好的一着棋是S3，因为，因为S3比比S1和和S2有较大的估值。有较大的估值。2024/7/23229-过程过程 o上面讨论的极大极小过程先生成一棵博弈搜索树，上面讨论的极大极小过程先生成一棵博弈搜索树，而且会生成规定深度内的所有节点，然后再进行而且会生成规定深度内的所有节点，然后再进行估值的倒推计算，这样使得估值的倒推计算，这样使得生成博弈树和估计值生成博弈树和估计值的倒推计算两个过程完全分离的倒推计算两个过程完全分离，因此，因此搜索效率较搜索效率较低低。o如果能边生成博弈树，边进行估值的计算，则可如果能边生成博弈树

165、，边进行估值的计算，则可能不必生成规定深度内的所有节点，以减少搜索能不必生成规定深度内的所有节点，以减少搜索的次数，这就是下面要讨论的的次数，这就是下面要讨论的-过程过程。 2024/7/23230o-过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此来提高算法的效率。来提高算法的效率。o下面仍然用一字棋进行说明。现将原图左边所示的一部分重画在图中。下面仍然用一字棋进行说明。现将原图左边所示的一部分重画在图中。2024/7/23231o极大极小过程极大极小过程实际上类似于实际上类似于宽度优先搜索宽度优先搜索，将每

166、层格局均生成，现在用将每层格局均生成，现在用深度优先搜索深度优先搜索来来处理。处理。o比如在节点比如在节点A A（与节点与节点）处，若已生成）处，若已生成5 5个子个子节点，并且估出了节点，并且估出了A A处的倒推值等于处的倒推值等于-1-1，即，即节点节点A A的的值为值为-1-1，由此可推出节点，由此可推出节点S S的倒推的倒推值值-1-1，即，即S S的倒推值的下确界为的倒推值的下确界为-1-1，不可，不可能再比能再比-1-1小，所以小，所以S S的的值为值为-1-1。我们将此。我们将此下确界叫做下确界叫做MAXMAX节点节点S S的的值，即值，即-1-1。 2024/7/23232o现

167、在轮到节点现在轮到节点B B，产生它的第一后继节点，产生它的第一后继节点C C，C C的静态值为的静态值为-1-1，可知，可知B B处的倒推值处的倒推值-1-1，此，此为上确界为上确界MINMIN节点的节点的值，即值，即B B处处-1-1，这，这样样B B节点最终的倒推值可能小于节点最终的倒推值可能小于-1-1，但绝不，但绝不可能大于可能大于-1-1，o因此，因此，B B节点的其他后继节点的静态值不必节点的其他后继节点的静态值不必计算，自然不必再生成，反正计算，自然不必再生成，反正B B决不会比决不会比A A好，好，所以通过倒推值的比较，就可以减少搜索的所以通过倒推值的比较，就可以减少搜索的工

168、作量工作量2024/7/23233o上图表示了上图表示了值小于等于父节点的值小于等于父节点的值（值（）时的情况，实际上当某个时的情况，实际上当某个MINMIN节点的节点的值不大于它的值不大于它的先辈的先辈的MAXMAX节点（不一定是父节点）的节点（不一定是父节点）的值时，则值时，则MINMIN节点就可以终止向下搜索。节点就可以终止向下搜索。 o同样，当某个同样，当某个MAXMAX节点的节点的值大于等于它的先辈值大于等于它的先辈MINMIN节节点的点的值值（）时，则该时，则该MAXMAX节点就可以终止向节点就可以终止向下搜索。下搜索。2024/7/23234 再看一个例子，再看一个例子，如下图所

169、示。其中最下面一层端节点旁如下图所示。其中最下面一层端节点旁边的数字是假设的估值。边的数字是假设的估值。 2024/7/23235o通过上面的讨论可以看出，通过上面的讨论可以看出，-过程首先使搜索过程首先使搜索树的某一部分达到最大深度，这时计算出某些树的某一部分达到最大深度，这时计算出某些MAXMAX节点的节点的值，或者是某些值，或者是某些MINMIN节点的节点的值。值。o随着搜索的继续，不断修改个别节点的随着搜索的继续，不断修改个别节点的或或值。值。对任一节点，当其某一后继节点的最终值给定时，对任一节点，当其某一后继节点的最终值给定时，就可以确定该节点的就可以确定该节点的或或值。值。2024

170、/7/23236o当该节点的其他后继节点的最终值给定时，当该节点的其他后继节点的最终值给定时，就可以对该节点的就可以对该节点的或或值进行修正。值进行修正。o注意注意、值修改有如下规律：值修改有如下规律：( (1)MAX1)MAX节点节点的的值永不下降；值永不下降；(2)(2)MINMIN节点的节点的值永不增值永不增加加。2024/7/23237 因此可以利用上述规律进行剪枝，一般可以停止对某因此可以利用上述规律进行剪枝，一般可以停止对某个节点搜索，即剪枝的规则表述如下：个节点搜索，即剪枝的规则表述如下： o(1)(1)若任何若任何MINMIN节点的节点的值小于或等于任何它的先值小于或等于任何它

171、的先辈辈MAXMAX节点的节点的值，则可停止该值，则可停止该MINMIN节点以下的搜节点以下的搜索，然后这个索，然后这个MINMIN节点的最终倒推值即为它已得到节点的最终倒推值即为它已得到的的值。值。 该值与真正的极大极小值的搜索结果的该值与真正的极大极小值的搜索结果的倒推值可能不相同，但是对开始节点而言，倒推倒推值可能不相同，但是对开始节点而言，倒推值是相同的，使用它选择的走步也是相同的。值是相同的，使用它选择的走步也是相同的。o(2)(2)若任何若任何MAXMAX节点的节点的值大于或等于它的值大于或等于它的MINMIN先辈先辈节点的节点的值，则可以停止该值，则可以停止该MAXMAX节点以下

172、的搜索，节点以下的搜索，然后这个然后这个MAXMAX节点处的倒推值即为它已得到的节点处的倒推值即为它已得到的值。值。2024/7/23238o当满足规则当满足规则1 1而减少了搜索时，进行了而减少了搜索时，进行了剪枝剪枝；而当满足规则而当满足规则2 2而减少了搜索时，进行了而减少了搜索时，进行了剪剪枝枝。o保存保存和和值，并且一旦可能就进行剪枝的整值，并且一旦可能就进行剪枝的整个过程通常称为个过程通常称为-过程，当初始节点的全过程，当初始节点的全体后继节点的最终倒推值全部给出时，上述过体后继节点的最终倒推值全部给出时，上述过程便结束。程便结束。o在搜索深度相同的条件下，采用这个过程所获在搜索深

173、度相同的条件下，采用这个过程所获得的走步总跟简单的极大极小过程的结果是相得的走步总跟简单的极大极小过程的结果是相同的，区别只在于同的，区别只在于-过程通常只用少得多过程通常只用少得多的搜索便可以找到一个理想的走步。的搜索便可以找到一个理想的走步。 2024/7/23239小结小结o搜索的基本概念和分类搜索的基本概念和分类o状态空间的概念和表示方法。状态空间的概念和表示方法。o一般图的搜索算法一般图的搜索算法o启发式搜索的概念，启发式搜索算法启发式搜索的概念，启发式搜索算法A A，f(x),g(x),h(x)f(x),g(x),h(x)定义定义o盲目搜索及其代表：深度优先和宽度优先。盲目搜索及其代表：深度优先和宽度优先。o深度优先的变形：有界深度和迭代加深搜索深度优先的变形：有界深度和迭代加深搜索oA*A*算法，算法， f*(x),g*(x),h*(x)f*(x),g*(x),h*(x)定义定义o与或图的搜索和与或图的搜索和AO*AO*算法。算法。oA*A*和和AO*AO*的比较的比较o博弈问题，看作是一种特殊的与或搜索问题。博弈问题，看作是一种特殊的与或搜索问题。o极大极小方法和极大极小方法和-剪枝技术。剪枝技术。2024/7/232402024/7/23241