人工智能专家系统推理机的设计第六章搜索的策略课件

1、第六章 搜索策略基本概念状态空间的搜索策略 与/或树的搜索策略搜索的完备性和效率8/21/20221福州大学阳光学院计算机系第六章 搜索策略基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率8/21/20222福州大学阳光学院计算机系基本概念推理什么是推理：依据一定的规则（策略）从已知的事实推出新事实（结论）的过程称为推理。8/21/20223福州大学阳光学院计算机系基本概念推理推理方式及其分类 p.112 演绎推理、归纳推理、默认推理 确定推理、不确定推理 单调推理、非单调推理 启发式推理、非启发式推理 8/21/20224福州大学阳光学院计算机系基本概念 - 搜索什么叫搜索：根

2、据问题的实际情况不断寻找可用的知识，从而构造一条代价较小的推理线路，使问题得到解的过程称为搜索。盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用以指导搜索朝最有利的方向前进，加速求解过程并得到最优解。8/21/20225福州大学阳光学院计算机系基本概念 - 状态空间表示法状态：描述某一类事物中各不同事物之间的差异而引入的一组变量或多维数组。 Sk=(Sk0,Sk1,Skn)算符(算子) ：引起状态中某些分量发生变化，从而使问题从一个状态改变到另一个状态的操作，以F指示。状态空间：以SP指示，表示问题的全部

3、可能的状态及其相互关系，状态和算符的集合。一般用三元式表示： SP = ( S0 , F , Sg )8/21/20226福州大学阳光学院计算机系基本概念 - 状态空间表示法状态空间以SP指示，也可表示为一个二元组： SP = （S, F）S-在问题求解（即搜索）过程中所有可达的合法状态构成的集合；F-操作算子的集合，操作算子的执行导致状态的变迁。 所以，状态空间又可描述为一个有向图，其节点指示状态，节点间的有向弧表示状态变迁，弧上的标签则指示导致状态变迁的操作算子。状态可通过定义某种数据结构来描述，用于记载问题求解（即搜索）过程中某一时刻问题现状的快照。 8/21/20227福州大学阳光学院

4、计算机系状态空间表示法举例：八数码游戏 问题：一个33棋盘，有八张牌1，2， 8及一个空格，空格周围的牌可以向空格移动。 求解：给定一个初始状态S0 、一个目标状态Sg ，求从S0到Sg的走步序列。S0状态 Sg状态8/21/20228福州大学阳光学院计算机系状态空间表示法举例：八数码游戏解： 综合数据库（状态及状态空间描述） 定义：矩阵（Sij）表示任何状态，其中： Sij0,1, 8 1i,j3 Sij 互不相同 状态空间：9！=362,880 种状态8/21/20229福州大学阳光学院计算机系状态空间表示法举例：八数码游戏 规则集（算符F）设：空格移动代替数码移动。至多有四种移动的可能：

5、上、下、左、右。定义： Sij为矩阵第i行j列的数码; 其中：i0,j0表示空格所在的位置，则Si0j0=0 （0代表空格）空格左移规则： if j0-11 then j0j0-1; Si0j00解释：如果当前空格不在第一列，则空格左移一位，新的空格位置赋值为0。同理：右移规则：if j0+13 then j0j0+1; Si0j00 上移规则：if i0-11 then i0i0-1; Si0j00 下移规则：if i0+13 then i0i0+1; Si0j008/21/202210福州大学阳光学院计算机系状态空间表示法举例：八数码游戏 控制策略需要解决的问题： 在当前可用的规则中如何选

6、择其中之一来实现状态的转换 实时判断是否到达目标状态8/21/202211福州大学阳光学院计算机系状态空间表示法举例：传教士和野人问题传教士和野人问题 设N个传教士带领N个野人划船渡河，且为安全起见，渡河需遵从二个约束： 1）船上人数不得超过载重限量，设为K个人； 2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士。 8/21/202212福州大学阳光学院计算机系状态空间表示法举例：传教士和野人问题 为便于理解状态空间表示方法，我们简化该问题到一个特例：N=3，K=2；并以变量m和c分别指示传教士和野人在左岸或船上的实际人数，变量b指示船是否在左岸（值1指示船在左岸，否则为0

7、）。从而上述约束条件转变为m + c = c。 考虑到在这个渡河问题中，左岸的状态描述（m、c和b）可以决定右岸的状态，所以整个问题状态就可以左岸的状态来描述，以简化问题的表示。 8/21/202213福州大学阳光学院计算机系状态空间表示法举例：传教士和野人问题 设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，问题状态以三元组（m,c,b）表示，则问题求解任务可描述为： (3，3，1） （0，0，0） 在这个简单问题中，状态空间可能的状态总数为442 = 32 ，但由于要遵守安全约束，只有20个状态是合法的。下面是几个不合法状态的例子： (1，0，1）， （1，2，1）， （2

8、，3，1） 鉴于存在不合法状态，还会导致某些合法状态不可达，例如状态（0，0，1），（0，3，0）。结果，这个问题总共只有16个可达的合法状态。8/21/202214福州大学阳光学院计算机系状态空间表示法举例：传教士和野人问题 渡河问题中的操作算子可以定义2类：L(m,c)、R(m,c)，分别指示从左岸到右岸的划船操作和从右岸回到左岸的划船操作。由于m和c取值的可能组合只有5个：10，20，11，01，02，故而总共有10个操作算子。 渡河问题状态空间的有向图8/21/202215福州大学阳光学院计算机系状态空间表示法举例：传教士和野人问题8/21/202216福州大学阳光学院计算机系基本概念

9、 - 与/或树表示法与/或树又称问题归约。问题归约是人们求解问题常用的策略，就是把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。只有当这些子问题全部解决时，问题才算解决，问题的解答就由子问题的解答联合构成。8/21/202217福州大学阳光学院计算机系基本概念 - 与/或树表示法与/或图：应用问题归约策略得到的状态空间图。与节点：用圆弧将几条节点间关联弧连接在一起去指示问题分解为若干子问题，只有这些子问题全部解决才会导致问题的解决。 或节点：问题（子问题）也可能激活多条重写规则（等价变换）；显然，只要有一条激活的重写规则能导致最终的解答成功即可。 8/21/202218福

10、州大学阳光学院计算机系基本概念 - 与/或树表示法本原问题：不可或不需再通过变换，可以直接得到问题的解的子问题。 端节点与终止节点：没有子节点的节点称为端节点（叶节点）。本原问题对应的节点称为终止节点。8/21/202219福州大学阳光学院计算机系基本概念 - 与/或树表示法可解节点： 终止节点是可解节点。 如果非终止节点有“或”子节点，当且仅当其子节点至少有一个能解，则该非终止节点是可解节点。 如果非终止节点有“与”子节点，当且仅当其子节点都能解，则该非终止节点是可解节点。8/21/202220福州大学阳光学院计算机系基本概念 - 与/或树表示法不可解节点： 没有后裔的非终止节点是不可解节点

11、（该节点是叶节点但不是本原问题）。 如果非终止节点有“或”子节点，当且仅当所有子节点都不能解，则该非终止节是不可解节点。 如果非终止节点有“与”子节点，至少有一个子节点不能解，则该非终止节点是不可解节点。解树：由可解节点构成，并且由这些可解节点可推出初始节点为可解节点的子树。8/21/202221福州大学阳光学院计算机系与/或树表示法举例：梵塔问题（1 1 1） （3 3 3） （1 2 2） （3 2 2） （3 2 2） （3 3 3） （1 1 1） （1 2 2） （1 1 1） （1 1 3） （3 2 2） （3 2 1） （3 2 1） （3 3 1） （3 3 1） （3 3

12、3） （1 2 3） （1 2 2） （1 1 3） （1 2 3） ( c b a )P.261 图6-78/21/202222福州大学阳光学院计算机系与/或树表示法举例：符号积分问题符号积分是求不定积分原函数的问题，通过应用各种代数和三角变换以及不定积分性质（如函数和积分、分部积分等）可以把复杂的积分问题逐步归约为若干个本原积分问题（可利用积分表直接求出原函数）。六十年代开发的SAINT系统。就是一个应用问题归约的符号积分系统。 8/21/202223福州大学阳光学院计算机系第六章 搜索策略基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率8/21/202224福州大学阳光学院

13、计算机系第六章 搜索策略基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率8/21/202225福州大学阳光学院计算机系状态空间的搜索策略状态空间的搜索以SE指示，可表示为一个五元组：SE = (S,F,E,S0,Sg)E -搜索引擎；S0 -问题的初始状态， S0 S;Sg -问题的目标状态集， Sg S。 状态空间搜索的基本思想就是通过搜索引擎寻找一个操作算子的调用序列，使问题从初始状态变迁到目标状态之一，而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的 解答路径。搜索引擎可以设计为任意实现搜索算法的控制系统。 8/21/202226福州大学阳光学院计算

14、机系状态空间的搜索策略通常，状态空间的解答路径有多条，但最短的只有1条或少数几条。上述渡河问题就有无数条解答路径（因为划船操作可逆），但只有4条是最短的，都包含11个操作算子的调用。由于一个状态可以有多个可供选择的操作算子，导致了多个待搜索的解答路径。除了少数像渡河这样的简单问题外，描述状态空间的一般图都很大，无法直观地画出，只能将其视为隐含图，在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的 搜索图。 8/21/202227福州大学阳光学院计算机系状态空间的搜索策略八数码问题的搜索图。对于八数码游戏，可能的棋盘布局（问题状态）总共9!=362880个，由于棋盘的对称性，实

15、际只有这个总数的一半。显然，我们无法直观地画出整个状态空间的一般图，但搜索图则小得多，可以图示。状态空间、搜索图和解答路径之间的关系 8/21/202228福州大学阳光学院计算机系状态空间的搜索策略尽管状态空间可以很大（例如国际象棋），但只要确保搜索空间足够小，就能在合理的时间范围内搜索到问题解答。搜索空间的压缩程度主要取决于搜索引擎采用的搜索算法。换言之，当问题有解时，使用不同的搜索策略，找到解答路径时，搜索图的大小是有区别的。 8/21/202229福州大学阳光学院计算机系状态空间的一般搜索过程一般图搜索算法为建立该算法，令： s -指示初始状态节点；G -指示搜索图；OPEN -作为存放

16、待扩展节点的表；CLOSE -作为存放已被扩展节点的表；MOVE-FIRST(OPEN) -指示取OPEN表首的节点作为当前要被扩展的节点n，同时将节点n移至CLOSE表；SNS -子节点集合； 8/21/202230福州大学阳光学院计算机系状态空间的一般搜索过程该算法的一般过程如下：1） G := s； / 即算法开始时搜索图只包括初始状态节点； OPEN := (s), CLOSE := ()； / 即此时仅有作为待扩展节点，而CLOSE表为空； 2）若OPEN是空表，则算法以失败结束； / 因为此时未搜索到解答（目标状态），又无法继续搜索； 3） n := MOVE-FIRST(OPEN

17、)； 4）若n是目标状态节点，则搜索成功结束，并给出解答路径； 5）扩展节点n，将非节点n祖先的子节点置于子节点集合SNS中，并插入搜索图G中； 8/21/202231福州大学阳光学院计算机系状态空间的一般搜索过程 6） 标记和修改指针： 把SNS中的子节点分为三类：（1）全新节点，（2）已出现于OPEN表的节点，（3）已出现于CLOSE表的节点； / 后二类子节点实际上意味着具有新老二个父节点； 加第1类子节点于OPEN表，并建立从子节点到父节点n的指针； 比较第2类子节点经由新、老父节点到达初始状态节点s的路径代价，若经由新父节点的代价较小， 则移动子节点指向老父节点的指针，改为指向新父节

18、点n； 对于第3类子节点作与第2类同样的处理，并把这些子节点从CLOSE表中移出，重新加入OPEN表；7） 按某种原则重新排序OPEN表中的节点；8） 返回语句2）； 8/21/202232福州大学阳光学院计算机系状态空间的一般搜索过程8/21/202233福州大学阳光学院计算机系状态空间的一般搜索过程讨论：1 OPEN中的节点是尚未扩充的节点2 CLOSED的节点是已经扩充过的节点 3 G中的每个节点都唯一地指向一个父节点4 mi mj mk ml其中： mi是当前被扩充的全部节点 mj是新扩充的节点 mk是已经在OPEN中的节点 ml是已经在CLOSED中的节点5 n是当前被选中的节点，它

19、是OPEN表中排列在最前面的一个节点。6 该算法对于连通图及树都适用。8/21/202234福州大学阳光学院计算机系状态空间的一般搜索过程例：n=1S23456当前节点ml节点表示图本身的连接关系搜索路径8/21/202235福州大学阳光学院计算机系状态空间的一般搜索过程讨论： 空心节点是已经在OPEN中的节点，如：1，4，5 实心节点是已经在CLOSED中的节点，如：S，2，3 扩充节点2后，对其原来搜索路径进行修改，由原来指向节点3改为指向节点1 对后继节点4的搜索路径进行修改，由原来指向节点6改为指向节点28/21/202236福州大学阳光学院计算机系状态空间的一般搜索过程修改后的搜索图

20、如下：n=1S234568/21/202237福州大学阳光学院计算机系状态空间的一般搜索过程下面给出两种对OPEN表中节点按照某种规则排列的算法： 深度优先算法 宽度优先算法8/21/202238福州大学阳光学院计算机系状态空间的一般搜索过程一般图搜索算法中，提高搜索效率的关键在于优化OPEN表中节点的排序方式，若每次排在表首的节点都在最终搜索到的解答路径上，则算法不会扩展任何多余的节点就可快速结束搜索。所以排序方式成为研究搜索算法的焦点，并由此形成了多种搜索策略。一种简单的排序策略就是按预先确定的顺序或随机地排序新加入到OPEN表中的节点，常用的方式是深度优先和宽度优先。 8/21/2022

21、39福州大学阳光学院计算机系状态空间的一般搜索过程8/21/202240福州大学阳光学院计算机系广（宽）度优先搜索 宽度优先-扩展当前节点后生成的子节点总是置于OPEN表的后端（未部），即OPEN表作为排队表使用，先进先出，使搜索优先向横广方向发展。 先进先出排序策略使宽度优先法能确保搜索到最短的解答路径。8/21/202241福州大学阳光学院计算机系深度优先搜索 深度优先-扩展当前节点后生成的子节点总是置于OPEN表的前端（首部），即OPEN表作为栈表使用，后进先出，使搜索优先向纵深方向发展。 当一个问题有多个解答或多条解答路径，且只须找到其中一个时，深度优先法十分适用。例如8数码游戏，若不

22、限定从初始布局转变到目标布局所需移动的棋牌个数（即移动步数），则存在多条解答路径，应用深度优先法可随机地找到其中一条。8/21/202242福州大学阳光学院计算机系深度优先搜索 不过有些问题的状态空间搜索或许会无限延伸，而又存在较短的解答路径，则可以对搜索深度加以限制，以求提高搜索效率并确保寻找到较短的解答路径。 有界深度优先如果当前节点的深度不超过限定的界限，则扩展当前节点后生成的子节点总是置于OPEN表的前端（首部） ，后进先出，使搜索优先向纵深方向发展。 8/21/202243福州大学阳光学院计算机系状态空间搜索上述二种搜索方法可直接应用一般图搜索算法实现，且只要问题有解就一定能搜索到解

23、答。由于不需要设计特别的节点排序方法，从而简单易行，适合于许多复杂度不高的问题求解任务。 这两种搜索方法的共同缺点是节点排序的盲目性，由于不采用领域专门知识去指导排序，往往会在白白搜索了大量无关的状态节点后才碰到解答，所以也称为盲目搜索。8/21/202244福州大学阳光学院计算机系状态空间搜索 只要引入与应用领域相关的启发式知识来指导OPEN表中节点的排序，使最有希望出现在较短解答路径上的节点优先考察，就能显著提高搜索的有效性。用启发式知识指导排序可划分为二种方式: 局部排序-这是对上述深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展。如：代价树深度优

24、先。 全局排序-对OPEN表中的所有节点排序，使最有希望的节点排在表首。如：代价树广度优先。 8/21/202245福州大学阳光学院计算机系代价树的广度优先搜索代价树广度优先-对OPEN表中的所有节点按代价大小排序，使最有希望的节点排在表首。是一种全局排序方法。代价树：边上标有代价（费用）的树。代价：若用g(x)表示从初始节点S0到节点x的代价，用 c(x1,x2)表示从父节点x1到子节点x2的代价，则有： g(x2) = g(x1) + c(x1,x2)最有希望的节点：代价最小的节点。8/21/202246福州大学阳光学院计算机系代价树的广度优先搜索例：巡回推销员问题，从A出发并返回。 A

25、(75 )E (100)B (100)D (125)C(125 ) B (125 ) C (75 ) D (75 ) B (100 ) C (5 0) C (125 ) AABCDE75100125125757510050125100A-E-D-B-C-A : 3758/21/202247福州大学阳光学院计算机系代价树的深度优先搜索代价树深度优先-这是对上述深度优先法的改进，仅对新扩展出来的子节点按代价大小排序，使这些节点中最有希望者能优先取出考察和扩展。是一种局部排序方法。8/21/202248福州大学阳光学院计算机系启发式搜索搜索是一种试探性的查寻过程，引入启发式知识可以减少搜索的盲目性，

26、增加试探的准确性，为此就称应用启发式知识的搜索是启发式搜索。 启发式知识对于搜索的指导作用可归纳为三方面： 选择下一个要被扩展的节点，排序OPEN表中的待扩展节点是一种常用的方法。在扩展一个节点时，仅仅有选择性地生成部分有用的节点，而非所有可能的子节点。修剪掉某些估计不可能导致成功的子节点。 本节只讨论如何应用第一方面的启发式知识于一般图搜索。8/21/202249福州大学阳光学院计算机系启发式搜索启发式信息用于解决OPEN表中节点的排列次序问题，方法是利用一个评(估)价函数计算OPEN表中节点的评价函数值，按照函数值从大到小（或从小到大）排列所有节点。 一种有效的方法就是设计体现启发式知识的

27、所谓评价函数来计算每个节点的得分，以便用于排列它们在OPEN表中的位置。 应用这种评价函数来实现启发式搜索的典型是算法A，其将评价函数f设计为：8/21/202250福州大学阳光学院计算机系启发式搜索 -算法A算法A，其将评价函数f设计为： f(n) = g(n) + h(n) n-搜索图中的某个当前被扩展的节点； f(n)-从初始状态节点s0, 经由节点n到达目标状节点sg，估计的最小路径代价； g(n)-从s0到n ,估计的最小路径代价； h(n)-从n到sg,估计的最小路径代价； 通常我们可以用至今已发现的自s0到n的最短路径作为g(n)值，但h(n)则要依赖于启发式知识来加以估算，故h

28、(n)称为启发式函数。8/21/202251福州大学阳光学院计算机系启发式搜索 -算法A算法A的设计与前述一般图算法类同，主要的不同是在算法第（5）步中增加了子节点函数f的计算，在第（6）步中依赖于f值确定子节点指向父节点指针的修改，并在第（7）步中按f值从小到大排序OPEN表中的节点。算法A第（5）和第（6）步的修改如下：8/21/202252福州大学阳光学院计算机系启发式搜索 -算法A(5) 扩展节点n,将非节点n祖先的子节点置于子节点集合SNS中， 并插入搜索图G中，对于SNS中每个子节点ni,计算f(n,ni) = g(n,ni) + h(ni);(6) 标记和修改指针把SNS中的子节

29、点分为三类（同一般图搜索算法）；加第1类子节点于OPEN表（同一般图搜索算法）；比较第2类子节点ni经由新、老父节点的评价函数值f(n,ni)、f(ni);若f(n,ni) 8/21/202263福州大学阳光学院计算机系启发式搜索 - A*算法性质1.算法可采纳性： 给定任意图，设存在从初始节点s到目标节点t的路径。如果算法能够结束在从s到t的最佳解路径上，则称该算法是可采纳的。 A*算法是可纳的，即它能在有限步内终止并找到最优解。（证明略）8/21/202264福州大学阳光学院计算机系启发式搜索 - A*算法性质 对于八数码游戏，从当前被扩展节点n到目标状态节点的最短路径-棋牌移动的最少次数

30、必定不少于错位棋牌的个数w(n) （因为有些棋牌可能需移动多于一次才能到达目标状态的相应位置）， 即w(n) h*(n) 也必定不会少于错位棋牌不受阻挡情况下移动到目标状态相应位置的移动次数总和p(n) （因为有些棋牌的移动可能受阻挡），即p(n) h*(n) 从而采用w(n)和p(n)作为评价函数时，算法A都是可纳的。 8/21/202265福州大学阳光学院计算机系启发式搜索 - A*算法性质思考1: 传教士和野人问题(m,c,b) 1) h(n)=0； 2) h(n)=m+c 3) h(n)=m+c-2b哪个是A*算法？思考2: 只有A*算法才能找到最优解？ 对于八数码游戏，令h(n)=

31、p(n) + 3 s(n) ,其中s(n)为所有棋子得分总和，计算方法：中心方格棋子得1分，非中心方格棋子后继棋子与目标顺序不同得2分，否则0分。8/21/202266福州大学阳光学院计算机系启发式搜索 - A*算法性质2.算法最优性： （启发式函数的强弱及其影响 ） 用h(n)接近h* (n)的程度去衡量启发式函数的强弱。当h(n) h* (n)且两者差距较大时，h(n)过弱，从而导致OPEN表中节点排序的误差较大，易于产生较大的搜索图；反之，当h(n) h* (n),则h(n)过强，使算法A失去可采纳性，从而不能确保找到最短解答路径。 设计接近、又总是 h* (n)的h(n)成为应用A*算

32、法搜索问题解答的关键，以压缩搜索图，提高搜索效率。 8/21/202267福州大学阳光学院计算机系启发式搜索 - A*算法性质算法最优性： （启发式函数的强弱及其影响 ）定理： 给定两个A*算法A1、A2，如果A2的启发信息比A1多，则在任何存在从节点s到目标节点t 路径的图上，搜索结束时由A2扩充的每一个节点必定被A1扩充。（ A1扩充的节点数至少与A2 扩充的节点数一样多)。 （证明略）8/21/202268福州大学阳光学院计算机系启发式搜索 - A*算法性质算法最优性： （启发式函数的强弱及其影响 ） 可以证明，对于解决同一问题的两个算法A1和A2，若有h1(n) h2(n) h* (n

33、)，则t(A1) t(A2) 其中，h1、h2分别是算法A1、A2 的启发式函数，t指示相应算法达到目标状态时搜索图含的节点总数。 8/21/202269福州大学阳光学院计算机系启发式搜索 - A*算法性质算法最优性： （启发式函数的强弱及其影响 ）再以八数码游戏为例，正因为w(n) p(n) h* (n),所以采用p(n)扩展出的节点总数不会比采用w(n)时多。更明显的例子是采用宽度优先法解决八数码问题，其相当于h(n)0，则搜索树会变得比采用w(n)时庞大得多。 8/21/202270福州大学阳光学院计算机系启发式搜索 - A*算法性质算法最优性： （启发式函数的强弱及其影响 ） 三种算法

34、的搜索代价,其中IDS为宽度搜索,h1采用的启发式函数为w(n), h2采用的启发式函数为p(n),d为解的长度.随机产生1200个八数码问题统计: d=12 IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes8/21/202271福州大学阳光学院计算机系启发式搜索 - A*算法性质3.h(x)的单调性限制：单调性定义：给定一个启发函数h，如果对于所有节点ni 、 nj （ nj是ni的子节点

35、）满足 h(ni) h(nj) c(ni, nj) 且 h(t) 0 ，则称h 满足单调性限制。上式可以写成 h(ni) c(ni, nj) h(nj) 可以理解为三角形边长和不等式。 单调性限制的作用是：避免重复计算某些节点的f值（主要针对连通图而言）以便减少搜索代价。tninjh(ni)h(nj)c(ni, nj)8/21/202272福州大学阳光学院计算机系启发式搜索 - A*算法性质h(x)的单调性限制：结论1 如果h(n)满足单调性限制条件，则A*算法扩充了节点n之后，就已经找到了到达节点n的最佳路径，即：如果A*选中节点n，在单调性限制条件下，有 g(n) g*(n) 结论2 如果

36、h 满足单调性限制，则由A*扩充的节点序列的f 值是非递减的。8/21/202273福州大学阳光学院计算机系第六章 搜索策略基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率8/21/202274福州大学阳光学院计算机系第六章 搜索策略基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率8/21/202275福州大学阳光学院计算机系与/或树的一般搜索过程 可以把 与/或图（树）视为对一般图的扩展；或反之，把一般图视为与/或图的特例，即一般图不允许节点间具有“与”关系，所以又可把一般图称为或图。与一般图类似，与/或图也有根节点，用于指示初始状态。由于同父子节点间可以存在“与

37、”关系，父、子节点间不能简单地以弧线关联，需要引入超连接概念。同样原因，在典型的与/或图中，解答路径往往不复存在，代之以广义的解路径-解图。 8/21/202276福州大学阳光学院计算机系与/或树的一般搜索过程8/21/202277福州大学阳光学院计算机系与/或树的一般搜索过程 解图的生成-自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止。 解图是遵从问题归约策略而搜索到的，解图中不存在节点或节点组之间的“或”关系；换言之，解图纯粹是一种“与”图。另外，正因为与或图中存在“或”关系，所以往往会搜索到多个解图，本例中就有4个

38、。 8/21/202278福州大学阳光学院计算机系与/或树的一般搜索过程8/21/202279福州大学阳光学院计算机系与/或树的一般搜索过程初始节点S0对应原始问题的描述。用可适用的分解或等价变换算符求得S0的后继节点集合。从每个后裔设置指向父辈节点的指针（用于标示可解或不可解，并指出一个到终叶节点的解图），删去没有意义的节点。继续扩展节点和设置指针的过程，直至S0被标示为可解或不可解为止。 8/21/202280福州大学阳光学院计算机系与/或树的广度优先搜索基本思想：把新生成的子节点放入OPEN表的尾部。算法：1）把初始节点S0放入OPEN表。2）把OPEN表中首节点（记为n）取出放入CLO

39、SE表。3）如果节点n可扩展，则 i)扩展n，将其子节点配置指针，放入OPEN表尾部。 ii)这些子节点是否有终止节点，若是，应用可解标示过程。若S0被标示可解，则得到解树搜索成功；否则从OPEN表中删除具有可解先辈的节点。 iii)转2）8/21/202281福州大学阳光学院计算机系与/或树的广度优先搜索算法： （续）4）如果节点n不可扩展，则 i)应用不可解标示过程。若S0被标示为不可解，则搜索失败；否则从OPEN表中删除具有不可解先辈的节点。 ii)转2）流程图： P.281举例：8/21/202282福州大学阳光学院计算机系与/或树的深度优先搜索基本思想：把新生成的子节点放入OPEN表

40、的首部。算法： P.282 （与广度优先类似）流程图：举例：8/21/202283福州大学阳光学院计算机系与/或树的有序搜索基本思想：考虑付出的代价，选择扩展节点时，先走几步，选择代价最小的节点进行扩展。解树的代价：从起始节点为根的最优解树的代价，记为h*(s)。任一节点x为根的解树的最小代价h(x)定义：1）若x为终止节点，则h(x)=0；2）若x为或节点，则h(x)=minc(x,yi)+h(yi)3）若x为与节点，则h(x)= maxc(x,yi)+h(yi)或h(x)= c(x,yi)+h(yi)8/21/202284福州大学阳光学院计算机系8/21/202285福州大学阳光学院计算机

41、系与/或树的有序搜索-希望树希望树：可能构成最优解树的一部分的树。希望树T的定义：1）初始节点S0在T中。2）如果节点x在T中，则一定有 i）x是一个或节点，则具有minc(x,yi)+h(yi)值的那个子节点yl也应该在T中。 ii）x是一个与节点，则它的所有子节点都应该在T中。8/21/202286福州大学阳光学院计算机系与/或树的有序搜索_希望树算法：1）把初始节点S0放入OPEN表。2）根据当前搜索树中节点的代价h，求希望树T。3）把OPEN表中T的端节点（记为n）取出放入CLOSE表。4）如果节点n为可解节点，则应用可解标示过程。若S0被标示可解，则得到最优解树T，搜索成功；否则从O

42、PEN表中删除具有可解先辈的所有节点。 8/21/202287福州大学阳光学院计算机系与/或树的有序搜索_希望树算法： （续）5）如果节点n为不可解节点，则应用不可解标示过程。若S0被标示为不可解，则搜索失败退出；否则从OPEN表中删除具有不可解先辈的所有节点。6）如果节点n可扩展，则 i)扩展n，将其子节点配置指针，放入OPEN表。 ii)计算这些子节点的h值及其先辈节点的h值。7） 转第2）步。流程图：P.2868/21/202288福州大学阳光学院计算机系与/或树的有序搜索举例： 假定在搜索过程中扩展出来的某些节点的启发式函数h(ni)的估算如下：h(n0)=3, h(n1)=2, h(

43、n2)=1, h(n3)=1, h(n4)=4,h(n5)=2, h(n6)=2, h(n7)=1, h(n8)=1，h(n13)=3。 8/21/202289福州大学阳光学院计算机系与/或树的有序搜索h(n0)=3, h(n1)=2, h(n2)=1, h(n3)=1, h(n4)=4,h(n5)=2, h(n6)=2, h(n7)=1, h(n8)=1,h(n13)=3。8/21/202290福州大学阳光学院计算机系博弈树的启发式搜索概念：MINMINMAXMAXMAX8/21/202291福州大学阳光学院计算机系博弈树的启发式搜索概念：MINMINMINMAXMAXMAX8/21/202292福州大学阳光学院计算机系博弈树的启发式搜索概念（博奕树特点）：1）初始格局为初始节点S0。2）或节点和与节点逐层交替出现。3）己方获胜格局为可解节点，对方获胜为不可解节点。 可以用类似于求解与/或树搜索技术来处理许多简单博弈以及若干复杂的博弈残局。8/21/202293福州大学阳光学院计算机系博弈树的启发式搜索极大极小分析法 基本思想：