人工智能第三章_搜索策略-1

《人工智能第三章_搜索策略-1》由会员分享，可在线阅读，更多相关《人工智能第三章_搜索策略-1（160页珍藏版）》请在装配图网上搜索。

1、2022-9-141第第3 3章章 搜索策略搜索策略o 问题求解系统划分为两大类问题求解系统划分为两大类n 知识贫乏系统知识贫乏系统 o 依靠依靠搜索技术搜索技术解决问题解决问题 o 知识贫乏、缺乏针对性知识贫乏、缺乏针对性o 效率低效率低 n 知识丰富系统知识丰富系统 o 依靠依靠推理技术推理技术解决问题解决问题o 基于丰富知识的推理技术，直截了当基于丰富知识的推理技术，直截了当 o 效率高效率高 2022-9-142第第3 3章章 搜索策略搜索策略o 两大类两大类搜索搜索技术技术:n 1、一般图搜索、启发式搜索、一般图搜索、启发式搜索n 2、基于问题归约的与或图搜索、基于问题归约的与或图搜

2、索 o 两种典型的两种典型的推理技术推理技术:n 1、基于归结的演绎推理、基于归结的演绎推理o 归结反演归结反演n 2、基于规则的演绎推理、基于规则的演绎推理o 正向演绎推理正向演绎推理o 逆向演绎推理逆向演绎推理 2022-9-143 o对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。o基于给定的问题，问题求解的第一步是目标的表示。o搜索就是找到智能系统的动作序列的过程。2022-9-144o 搜索算法的输入是给定的问题，输出时表示为动作序列的方案。o 一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）o 因此，求解问题包括：n

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

4、间在问题求解之前不是全部知道的。在人工智能中，搜索问题一般包括两个重在人工智能中，搜索问题一般包括两个重要的问题：要的问题：v搜索什么搜索什么搜索什么通常指的就是目标。搜索什么通常指的就是目标。v在哪里搜索在哪里搜索在哪里搜索就是在哪里搜索就是“搜索空间搜索空间”。搜索空间通常。搜索空间通常是指一系列状态的汇集，因此称为是指一系列状态的汇集，因此称为状态空间状态空间。2022-9-147o所以，人工智能中的搜索可以分成两个阶段：n 状态空间的生成阶段n 在该状态空间中对所求问题状态的搜索搜索可以根据是否使用搜索可以根据是否使用启发式信息启发式信息分分为为v盲目搜索盲目搜索v启发式搜索启发式搜索

5、 2022-9-148o 盲目搜索盲目搜索 只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。o启发式搜索启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。2022-9-149o 根据问题的表示方式分为n 状态空间搜索n 与或图搜索状态空间状态空间搜索是用搜索是用状态空间状态空间法来求解法来求解问题所进问题所进行的搜索行的搜索与与/或图搜或图搜索是指用问索是指用问题规约方法题规约方法来求解问题来求解问题时所进行的时所进行的搜索。搜索

6、。2022-9-1410o 考虑一个问题的状态空间为一棵树的形式。o 宽度优先搜索o 深度优先搜索如果根节点首先如果根节点首先扩展，然后是扩扩展，然后是扩展根节点生成的展根节点生成的所有节点，然后所有节点，然后是这些节点的后是这些节点的后继，如此反复下继，如此反复下去。去。在树的最深一层的节在树的最深一层的节点中扩展一个节点。点中扩展一个节点。只有当搜索遇到一个只有当搜索遇到一个死亡节点（非目标节死亡节点（非目标节点并且是无法扩展的点并且是无法扩展的节点）的时候，才返节点）的时候，才返回上一层选择其他的回上一层选择其他的节点搜索。节点搜索。2022-9-1411o 无论是宽度优先搜索还是深度优

7、先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为“确定性”的，也就是盲目搜索。o 对于启发式搜索，在计算每个节点的参数之前无法确定先选择哪个节点扩展，这种搜索一般也称为非确定的。2022-9-1412o 完备性：n 如果存在一个解答，该策略是否保证能够找到？o 时间复杂性：n 需要多长时间可以找到解答？o 空间复杂性：n 执行搜索需要多少存储空间？o 最优性：n 如果存在不同的几个解答，该策略是否可以发现最高质量的解答？搜索策略评价标准搜索策略评价标准:2022-9-1413有许多智力问题有许多智力问题(如梵塔问题、旅行商问题、八皇如梵塔问题

8、、旅行商问题、八皇后问题、农夫过河问题等后问题、农夫过河问题等)和实际问题（如路径规和实际问题（如路径规划、机器人行动规划等）都可以归结为划、机器人行动规划等）都可以归结为状态空间搜状态空间搜索索。用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题的系统均定义一个状态状态空间空间，并通过适当的，并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。2022-9-1414nS问题求解（即搜索）过程中所有问题求解（即搜索）过程中所有可能到达可能到达的的合法状态合法状态构成的集合；构成的集合；nO操作算子操作算子的集合，的集合，操作算子的执行会导致问题状态的操作

9、算子的执行会导致问题状态的变迁变迁；n状态状态用于记载问题求解（即搜索）过程中用于记载问题求解（即搜索）过程中某一时刻问某一时刻问题现状的快照题现状的快照；o 抽象为矢量形式抽象为矢量形式 Q=q0,q1,qnTo 每个元素每个元素qi称为称为状态分量状态分量 o 给定每个给定每个状态分量状态分量qi的值就得到一个具体的状态的值就得到一个具体的状态 Qk=q0k,q1k,qnkT2022-9-1415状态状态表示状态的变迁表示状态的变迁操作算子操作算子问题的状态空间问题的状态空间是一个表示该问题的全部可能状态是一个表示该问题的全部可能状态及其变迁的及其变迁的有向图有向图。o 节点节点n 状态状

10、态o 有向弧有向弧n 状态的变迁状态的变迁 o 弧上的标签弧上的标签n 导致状态变迁的导致状态变迁的操作算子操作算子 用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题的系统均定义一个状态状态空间空间，并通过适当的，并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。2022-9-1416S1S2S3S4S5S6S7S8S9S0Sg2022-9-14172022-9-1418 例例2:在一个在一个33的方格棋盘上放置着的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些八个数码，每个数码占一格，且有一个空格。这些数

11、码可在棋盘上移动，其移动规则是：与空格相邻数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。的数码方可移入空格。现在的现在的问题问题是：对于指定的是：对于指定的初始棋局初始棋局和和目标棋局目标棋局，给出给出数码的移动序列数码的移动序列。该问题称为。该问题称为八数码问题八数码问题。56741382初始棋局初始棋局56748321目标棋局目标棋局移动数码移动数码2022-9-14192 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

12、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 52022-9-14202022-9-1421 例例3:钱币翻转问题。设有钱币翻转问题。设有3个钱币，其初始状态个钱币，其初始状态为为(正、反、正正、反、正),欲得的目标状态为欲得的目标状态为(正、正、正正、正、正)

13、或或(反、反、反反、反、反)。问题是允许每次只能且必须翻。问题是允许每次只能且必须翻转一个钱币，连翻三次。问能否达到目标状态。转一个钱币，连翻三次。问能否达到目标状态。分析：通过引入一个分析：通过引入一个三维变量三维变量将问题表示出来。设将问题表示出来。设三维变量为：三维变量为：Q=qQ=q1 1,q,q2 2,q,q3 3，式中，式中q qi i(i=1,2,3)=1(i=1,2,3)=1表表示钱币为正面，示钱币为正面，q qi i(i=1,2,3)=0(i=1,2,3)=0表示钱币为反面。表示钱币为反面。则三个钱币可能出现的状态有则三个钱币可能出现的状态有8 8种组合：种组合：Q Q0 0

14、=(0,0,0),Q=(0,0,0),Q1 1=(0,0,1),Q=(0,0,1),Q2 2=(0,1,0),Q=(0,1,0),Q3 3=(0,1,1),Q=(0,1,1),Q4 4=(1,0,0),Q(1,0,0),Q5 5=(1,0,1),Q=(1,0,1),Q6 6=(1,1,0),Q=(1,1,0),Q7 7=(1,1,1)=(1,1,1)。即初始状态为即初始状态为Q Q5 5，目标状态为目标状态为Q Q0 0或或Q Q7 7，要求步数为要求步数为3 3。2022-9-1422钱币问题的状态空间图钱币问题的状态空间图2022-9-1423：o 1)船上人数不得超过载重限量，设为船上人

15、数不得超过载重限量，设为K个人；个人；o 2)任何时刻（包括两岸、船上）野人数目不得超任何时刻（包括两岸、船上）野人数目不得超过传教士；过传教士；o 3)允许在河的某一岸或者在船上只有野人而没有允许在河的某一岸或者在船上只有野人而没有传教士；传教士；2022-9-14242022-9-1425可能到达可能到达的的合法状态合法状态：442=32 o(0,0,1),(0,3,0),(3,0,1),(3,3,0)2022-9-1426(2)状态空间表示的经典例子状态空间表示的经典例子“传教士和野人问题传教士和野人问题”o 定义定义2类类操作算子操作算子：n L(x,y)指示从指示从左岸左岸到到右岸右

16、岸的划船操作的划船操作 n R(x,y)指示从指示从右岸右岸到到左岸左岸的划船操作的划船操作o x+y K=2(船的载重限制船的载重限制)；o x和和y取值的可能组合只有取值的可能组合只有5个个o 10，20，11，01，02 o(允许在船上只有野人而没有传教士允许在船上只有野人而没有传教士)n 共有共有10个操作算子个操作算子2022-9-14272022-9-1428 2022-9-1429 2022-9-1430课堂练习课堂练习o 有一农夫带一只狐狸、一只小羊和一篮菜过河（从有一农夫带一只狐狸、一只小羊和一篮菜过河（从左岸到右岸）。假设船太小，农夫每次只能带一样左岸到右岸）。假设船太小，

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

18、设初始状态下均在左岸设初始状态下均在左岸,目标状目标状态下都到达右岸。从而态下都到达右岸。从而,问题求解任务可描述为问题求解任务可描述为 (1,1,1,1)-(0,0,0,0)(1,1,1,1)-(0,0,0,0)o 思考：为什么不把船的状态放到状态空间中去？思考：为什么不把船的状态放到状态空间中去？o 由于问题简单由于问题简单,状态空间中可能的状态总数为状态空间中可能的状态总数为2 22 22 22=2=16,16,由于要遵从安全限制由于要遵从安全限制,合法的状态只有合法的状态只有(除初、目状态外除初、目状态外):):1110 1110，11011101，10111011，10101010，

19、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是互逆操作是互逆操作,故而解答路径可有无数条故而解答路径可有无数条,但最近的只有但最近的只有二条二条;都是都是7 7个操作步个操作步

20、.2022-9-1432解析解析:四元组四元组(m(m、f f、s s、v)v)代表（农夫、狐狸、小羊、菜）代表（农夫、狐狸、小羊、菜）2022-9-1433(3)状态空间的搜索状态空间的搜索o 状态空间的搜索记为状态空间的搜索记为SE，可表示为五元组：，可表示为五元组：n SE=(S,O,E,I,G)；n E搜索引擎；搜索引擎；n I问题的初始状态，问题的初始状态，I S；n G问题的目标状态集合，问题的目标状态集合，G S。o 搜索引擎搜索引擎E可以设计为可以设计为实现任何搜索算法实现任何搜索算法的控制系统。的控制系统。o 基本思想基本思想通过搜索引擎通过搜索引擎E寻找一个寻找一个操作算子

21、的调用序操作算子的调用序列列，使问题从初始状态，使问题从初始状态I变迁到目标状态变迁到目标状态G之一。之一。o 解答路径解答路径初初-目变迁过程中目变迁过程中的的状态序列状态序列或相应的或相应的操作算操作算子调用序列子调用序列。2022-9-1434o 或图（一般图）或图（一般图）n 一个状态一个状态可以可以有多个可供选择有多个可供选择的操作算子；的操作算子；n 操作算子间的选择是一种操作算子间的选择是一种“或或”的关系的关系;n 这样的有向图称为这样的有向图称为或图。或图。2022-9-1435(3)(3)状态空间的搜索状态空间的搜索o 或图（一般图）或图（一般图）n 一个状态可以有多个可供

22、选择的操作算子；一个状态可以有多个可供选择的操作算子；n 操作算子间的选择是一种操作算子间的选择是一种“或或”的关系，的关系，这样的有这样的有向图称为向图称为或图。或图。o 状态空间状态空间一般都表示为一般都表示为或图（一般图）或图（一般图）o 搜索图搜索图在在搜索解答路径搜索解答路径的过程中画出搜索时涉及到的过程中画出搜索时涉及到的节点和弧线，构成所谓的的节点和弧线，构成所谓的搜索图搜索图。状态空间搜索状态空间搜索一般图搜索一般图搜索2022-9-1436(3)状态空间的搜索状态空间的搜索o 状态空间状态空间、搜索图搜索图和和解答路径解答路径之间的关系之间的关系S0Sg2022-9-1437

23、 初始布局初始布局目标布局目标布局移动数码移动数码2022-9-1438 2022-9-1439初始布局初始布局目标布局目标布局移动数码移动数码586427301567408321 2022-9-1440(4)一般图搜索例子一般图搜索例子八数码游戏八数码游戏 o 第二步：制定操作算子集第二步：制定操作算子集n直观方法直观方法为每个棋牌制定一套可能的走步：左、上、右、为每个棋牌制定一套可能的走步：左、上、右、下四种移动。下四种移动。o 需要需要32个操作算子个操作算子n简易方法简易方法仅为空格制定这仅为空格制定这4种走步。种走步。o 仅需仅需4个操作算子个操作算子o 第三步：设计搜索引擎第三步：

24、设计搜索引擎 n问题状态空间的大小问题状态空间的大小与与问题涉及的元素问题涉及的元素个数是程个数是程指数级指数级爆炸式增长爆炸式增长（即，（即，组合爆炸问题组合爆炸问题）o 如，棋盘布局（问题状态）总共有如，棋盘布局（问题状态）总共有9!=362880个个 n研究焦点研究焦点是是解决组合爆炸问题解决组合爆炸问题，通过压缩搜索空间通过压缩搜索空间，提提高搜索效率高搜索效率。2022-9-1441状态空间状态空间、搜索图搜索图和和解答路径解答路径之间的关系之间的关系S0Sg2022-9-1442（1）搜索术语）搜索术语o 1、节点深度、节点深度n 根节点根节点指示指示初始状态初始状态，令其深度为，

25、令其深度为0；n 搜索图中的其他节点的搜索图中的其他节点的深度深度dn就可以递归地定义为就可以递归地定义为其其父节点深度父节点深度dn-1加加1：dn=dn-1+1。根节点深度根节点深度=0=0搜索图搜索图2022-9-1443（1）搜索术语）搜索术语o 2、节点扩展、节点扩展n应用应用操作算子操作算子将将上一状态上一状态（节点（节点ni）变迁到）变迁到下一状态下一状态（节点（节点nj）n节点节点ni称为称为被扩展节点被扩展节点（父节点）（父节点）n节点节点nj称为称为ni的的子节点子节点2022-9-1444o4、路径代价、路径代价相邻节点相邻节点ni和和ni+1间的间的路径代价路径代价记为

26、记为C(ni,ni+1)n通常令通常令任意相邻节点任意相邻节点间的路径代价相同间的路径代价相同，并以路径长度并以路径长度1 1指示。指示。n即即C(ni,ni+1)=1。节点节点n ni i节点节点ni+1节点节点nj2022-9-1445 C(nk,ng)C(ni,nk)C(ni,ng)2022-9-1446o 符号说明：符号说明：ns-初始状态节点初始状态节点nG-搜索图搜索图nOPEN-存放存放待扩展节点待扩展节点的表的表nCLOSE-存放存放已被扩展的节点已被扩展的节点的表的表nMOVE-FIRST(OPEN)-取取OPEN表首的节点表首的节点作为作为当前要被扩展的节当前要被扩展的节点

27、点n，同时，同时将节点将节点n移至移至CLOSE表表o 一般图搜索算法划分为二个阶段：一般图搜索算法划分为二个阶段：n1、初始化、初始化 n2、搜索循环、搜索循环 2022-9-1447o算法划分为二个阶段：算法划分为二个阶段：n1、初始化、初始化 o 建立建立只包含初始状态节点只包含初始状态节点s的搜索图的搜索图G:=so OPEN:=so CLOSE:=n2、搜索循环、搜索循环o MOVE-FIRST(OPEN)-取出取出OPEN表首的节点表首的节点n作为扩展的节点，作为扩展的节点，同时将其移到同时将其移到close表表 o 扩展出扩展出n的子节点的子节点,插入插入搜索图搜索图G和和OPE

28、N表表 o 适当的标记和修改指针适当的标记和修改指针o 排序排序OPEN表表n通过循环地执行该算法，通过循环地执行该算法，搜索图搜索图G会因不断有新节点加入而逐会因不断有新节点加入而逐步长大，直到搜索到目标节点。步长大，直到搜索到目标节点。2022-9-1448初始布局初始布局目标布局目标布局移动数码移动数码2022-9-14495864273012022-9-14505864273012022-9-14515864273015864270315864073215864273102022-9-14525864273015864270315864073215864273102022-9-1453

29、5864273015864270315864073215864273102022-9-14545864273015864270315864073215864273105064873215864703215860473212022-9-14555864273015864270315864073215864273105064873215864703215860473212022-9-14565864273015864270315864073215864273105064873215864703215860473215864273102022-9-14575864273015864270315864

30、073215864273105064873215864703215860473215604873210564873212022-9-14585864273015864270315864073215864273105064873215864703215860473215604873210564873212022-9-14595864273015864270315864073215864273105064873215864703215860473215604873210564873212022-9-14605864273015864270315864073215864273105064873215

31、864703215860473215604873210564873215674803212022-9-14615864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-9-14625864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-9-14635864273015864270315864073215864273105064873

32、215864703215860473215604873210564873215674803215674813205674083212022-9-14645864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-9-1465586427301586427031586407321586427310506487321586470321586047321560487321056487321567480321567481320567408

33、3212022-9-14665864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-9-14675864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-9-1468搜索过程中的指针修改搜索过程中的指针修改o 节点节点n扩展后扩展后的子节点分为的子节点分为3类类

34、：n(i)全新节点全新节点n(ii)已出现在已出现在OPEN表表中的节点中的节点n(iii)已出现的已出现的CLOSE表表中的节点中的节点o 指针标记和修改的方法：指针标记和修改的方法：n(i)类节点：加入类节点：加入OPEN表，建立从子节点到父节点表，建立从子节点到父节点n的指针的指针n(ii)类节点、类节点、(iii)类节点类节点o 比较比较经由经由老父节点老父节点、新父节点新父节点n到达到达初始状态节点初始状态节点的的路径代价路径代价 o 经由节点经由节点n的代价比较小，则移动子节点指向老父节的代价比较小，则移动子节点指向老父节点的指针，改为指向新父节点点的指针，改为指向新父节点no (

35、iii)类节点还得从类节点还得从CLOSE表中移出，重新加入表中移出，重新加入OPEN表表。2022-9-1469Sn4ninjn1n2n3n31n32o 节点节点ni是当前扩展的节点；是当前扩展的节点；o 扩展出扩展出4个后续节点；个后续节点；o n1、n2是新节点是新节点，只需建只需建立指向父节点的指针，并加立指向父节点的指针，并加入入OPEN表表；2022-9-1470Sn4ninjn1n2n3n31n32o n4已经存在于已经存在于OPEN表，并表，并且已有父节点且已有父节点njnn4经经nj的路径代价大的路径代价大n取消取消n4指向指向nj的指针的指针n改为建立改为建立n4指向新父节

36、点指向新父节点ni的指针的指针o n3已经存在于已经存在于CLOSE表，表，并且已有父节点并且已有父节点njn需要做和需要做和n4同样的比较和指同样的比较和指针修改工作。并且要重新加入针修改工作。并且要重新加入open表。表。2022-9-1471 o 提高搜索效率的关键提高搜索效率的关键优化优化OPENOPEN表中节点的排序表中节点的排序方式方式。o 简单的排序策略简单的排序策略按预先确定的顺序或随机地排按预先确定的顺序或随机地排序新加入到序新加入到OPENOPEN表中的节点。表中的节点。o 常用的简单方式：常用的简单方式：宽度优先宽度优先扩展当前节点后生成的子节点总是置于扩展当前节点后生成

37、的子节点总是置于OPENOPEN表的后端，即表的后端，即OPENOPEN表作为表作为队列队列使用，使用，先进先出先进先出，使搜索优先向，使搜索优先向横横广广方向发展。方向发展。深度优先深度优先扩展当前节点后生成的子节点总是置于扩展当前节点后生成的子节点总是置于OPENOPEN表的前端，即表的前端，即OPENOPEN表作为表作为栈栈使用，使用，后进先出后进先出，使搜索优先向，使搜索优先向纵深纵深方向发展。方向发展。2022-9-1472o 宽度优先宽度优先扩展当前节点后生成的子节点总是扩展当前节点后生成的子节点总是置置于于OPEN表的后端表的后端，即，即OPEN表表作为作为队列队列，先进先出先进

38、先出，使使搜索优先向横向方向发展搜索优先向横向方向发展。o 过程：指从初始节点过程：指从初始节点S0开始，向下逐层搜索，在开始，向下逐层搜索，在n层节层节点未搜索完之前，不进入点未搜索完之前，不进入n+1层搜索。层搜索。同层节点的搜索同层节点的搜索次序可以任意次序可以任意。即先按生成规则生成第一层节点，在该。即先按生成规则生成第一层节点，在该层全部节点中沿宽层全部节点中沿宽(广广)度进行横向扫描，检查目标节点度进行横向扫描，检查目标节点Sg是否在这些子节点中。若没有是否在这些子节点中。若没有,则再将所有笫一层节则再将所有笫一层节点逐一扩展，得到第二层节点。并逐一检查第二层节点点逐一扩展，得到第

39、二层节点。并逐一检查第二层节点中是否包含有中是否包含有Sg，如此依次按照先生成、先检查、先扩，如此依次按照先生成、先检查、先扩展的原则进行下去，直到发现展的原则进行下去，直到发现Sg为止为止 2022-9-1473宽度优先宽度优先实例实例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 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

40、 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标目标82 3 41 8 7 6 54910111213141516172022-9-1474宽度优先搜索宽度优先搜索 如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”2022-9-1475(1)把初始节点把初始节点S0，放入，放入OPEN表。表。(2)如果如果OPEN表为空。则问题无解，失败并退出。表为空。则问题无解，失败并退出。(3)把把OPEN表中的第一个节点取出放入表中的

41、第一个节点取出放入CLOSE表中，表中，并按顺序冠以编号并按顺序冠以编号n；(4)考察节点考察节点n是否为目标节点。若是，则求得了问是否为目标节点。若是，则求得了问题的解，成功并退出。题的解，成功并退出。(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，将其子节点放到，将其子节点放到OPEN表的表的尾部尾部，并，并为每一个子节点都配置指向父节点的指针，然后为每一个子节点都配置指向父节点的指针，然后转第转第(2)步。步。采用队列结构，宽度优先算法可以表示如下：采用队列结构，宽度优先算法可以表示如下：2022-9-1476 例例 通过挪动积木块，希望从初始

42、状态达到一个目的状通过挪动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。积木态，即三块积木堆叠在一起。积木A在顶部，积木在顶部，积木B在在顶中间，积木顶中间，积木C在底部。请画出按照宽度优先搜索策在底部。请画出按照宽度优先搜索策略所产生的搜索树。略所产生的搜索树。这个问题的唯一操作算子为这个问题的唯一操作算子为MOVE(X,Y)MOVE(X,Y)，即积木，即积木X X搬到搬到Y Y（积木（积木或桌面）上面。如或桌面）上面。如“挪动积木挪动积木A A到桌面上表示为到桌面上表示为MOVE(A,Table)MOVE(A,Table)。该操作算子可运用的先决条件是：该操作算子可运用的先

43、决条件是：（1 1）被挪动积木的顶部必须为空。）被挪动积木的顶部必须为空。（2 2）如）如Y Y是积木（不是桌面），则积木是积木（不是桌面），则积木Y Y的顶部也必须为空。的顶部也必须为空。（3 3）同一状态下，运用操作算子的次数不得多于一次。）同一状态下，运用操作算子的次数不得多于一次。2022-9-1477积木问题的宽度优先搜索树积木问题的宽度优先搜索树 2022-9-1478宽度优先搜索的性质宽度优先搜索的性质o 当问题有解时，当问题有解时，一定一定能找到解能找到解(完备性完备性)o 当问题为单位代价时，且问题有解时，当问题为单位代价时，且问题有解时，一定一定能找到最优解（最优性）能找到

44、最优解（最优性）o 方法与问题无关，具有通用性方法与问题无关，具有通用性o 效率较低效率较低o 属于图搜索方法属于图搜索方法2022-9-1479o 宽度优先搜索宽度优先搜索是一种盲目搜索，是一种盲目搜索，时间和空间复杂度都比较高，当时间和空间复杂度都比较高，当目标节点距离初始节点较远时会目标节点距离初始节点较远时会产生许多无用的节点，搜索效率产生许多无用的节点，搜索效率低。低。o 宽度优先搜索中，时间需求是一宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的个很大的问题，特别是当搜索的深度比较大时，尤为严重，但是深度比较大时，尤为严重，但是空间需求是比执行时间更严重的空间需求是比执行时

45、间更严重的问题。问题。宽度优先搜索优宽度优先搜索优点：点：目标节点如果存目标节点如果存在，用宽度优先在，用宽度优先搜索算法总可以搜索算法总可以找到该目标节点，找到该目标节点，而且而且是最小（即是最小（即最短路径）的节最短路径）的节点。点。宽度优先搜索的优点和缺点宽度优先搜索的优点和缺点2022-9-1480o 深度优先深度优先扩展当前节点后生成的子节点总是扩展当前节点后生成的子节点总是置置于于OPEN表的前端表的前端，即，即OPEN表表作为作为栈栈，后进先出后进先出，使使搜索优先向纵深方向发展搜索优先向纵深方向发展。o 过程：从初始节点过程：从初始节点S0开始，按生成规则生成下一级各子开始，按

46、生成规则生成下一级各子节点，检查是否出现目标节点节点，检查是否出现目标节点Sg；若未出现，则按；若未出现，则按“最最晚生成的子节点优先扩展晚生成的子节点优先扩展”的原则，再用生成规则生成的原则，再用生成规则生成再下一级的子节点，再检查是否出现再下一级的子节点，再检查是否出现Sg；若仍未出现，；若仍未出现，则再扩展最晚生成的子节点。如此下去，沿着最晚生成则再扩展最晚生成的子节点。如此下去，沿着最晚生成的子节点分枝，逐级的子节点分枝，逐级“纵向纵向”深入搜索。深入搜索。2022-9-1481深度优先深度优先实例实例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52

47、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 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目标目标571012151720212022-9-148

48、2深度优先搜索深度优先搜索o 在深度优先搜索中，首先扩展最新产生的在深度优先搜索中，首先扩展最新产生的(最最深的深的)节点，深度节点，深度 相等的节点可以任意排列。相等的节点可以任意排列。o“最晚产生的节点最先扩展最晚产生的节点最先扩展”起始节点深度为0 任何其他节点的深度等于其父辈节点深度加上1:dn=dn-1+12022-9-1483深度优先搜索深度优先搜索很明显这样做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿着一条路线无限制地扩展下去，这当然是不允许的。为保证找到解，应选择适当的深度界限，或者采取不断加大深度界限的办法，反复搜索，直到找到解。这种改

49、进的方法叫做迭代加深搜索。2022-9-1484(1)把初始节点S0放入OPEN表；(2)如果OPEN表为空，则问题无解，失败并退出。(3)把OPEN表中的第一个节点取出放入CLOSE表中，并按顺序冠以编号n；(4)考察节点n是否为目标节点。若是，则求得了问题的解，成功并退出。(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其子节点放到OPEN表的首部，并为其配置指向父节点的指针，然后转第(2)步。基于栈实现的深度优先搜索算法：2022-9-1485 例例 卒子穿阵问题卒子穿阵问题:要求一卒子从顶部通过图所示的列阵到达要求一卒子从顶部通过图所示的列阵到达底部。要求卒子行进中不可进入

50、到代表敌兵驻守的区域内底部。要求卒子行进中不可进入到代表敌兵驻守的区域内（标注（标注1），并不准后退。），并不准后退。假定限制值为假定限制值为5。请画出按照深。请画出按照深度优先搜索策略所产生的搜索树度优先搜索策略所产生的搜索树 2022-9-1486卒子穿阵的深度优先搜索树卒子穿阵的深度优先搜索树 2022-9-1487o 一般不能保证找到最优解一般不能保证找到最优解o 当深度限制不合理时，当深度限制不合理时，可能找不到解可能找不到解，可以，可以将算法改为将算法改为可变深度限制可变深度限制o 最坏情况时，搜索空间等同于穷举最坏情况时，搜索空间等同于穷举o 是一个通用的与问题无关的方法是一个通

51、用的与问题无关的方法2022-9-1488o 深度优先搜索深度优先搜索的的优点优点是是比宽度优先搜索算比宽度优先搜索算法需要较少的空间法需要较少的空间，该算法只需要保存搜，该算法只需要保存搜索树的一部分，它由索树的一部分，它由当前正在搜索的路径当前正在搜索的路径和该路径上还没有完全展开的节点标志所和该路径上还没有完全展开的节点标志所组成组成。o 深度优先搜索的存储器要求是深度约束的深度优先搜索的存储器要求是深度约束的线性函数。线性函数。2022-9-1489 既不是完备的，也不是最优的。既不是完备的，也不是最优的。主要问题是可能主要问题是可能搜索到了错误的路径上搜索到了错误的路径上。很多。很多

52、问题可能具有很深甚至是无限的搜索树，如果不幸问题可能具有很深甚至是无限的搜索树，如果不幸选择了一个错误的路径，则深度优先搜索会一直搜选择了一个错误的路径，则深度优先搜索会一直搜索下去，而不会回到正确的路径上。这样一来对于索下去，而不会回到正确的路径上。这样一来对于这些问题，深度优先搜索要么陷入无限的循环而不这些问题，深度优先搜索要么陷入无限的循环而不能给出一个答案，要么最后找到一个答案，但路径能给出一个答案，要么最后找到一个答案，但路径很长而且不是最优的答案。很长而且不是最优的答案。2022-9-1490比较比较 o 适用场合适用场合 深度优先深度优先当一个问题有多个解答或多条解答路径，当一个

53、问题有多个解答或多条解答路径，且只须找到其中一个时；且只须找到其中一个时；往往应对搜索深度加以限制往往应对搜索深度加以限制。宽度优先宽度优先确保搜索到确保搜索到最短的解答路径最短的解答路径。o 共同优缺点：共同优缺点：可直接应用一般图搜索算法实现，不需要设计特别的可直接应用一般图搜索算法实现，不需要设计特别的节点排序方法，从而简单易行，适合于许多复杂度不高的问节点排序方法，从而简单易行，适合于许多复杂度不高的问题求解任务。题求解任务。节点排序的盲目性，由于不采用领域专门知识去指导节点排序的盲目性，由于不采用领域专门知识去指导排序，往往会在白白搜索了大量无关的状态节点后才碰到解排序，往往会在白白

54、搜索了大量无关的状态节点后才碰到解答，所以也称为答，所以也称为盲目搜索盲目搜索。2022-9-1491有界深度搜索和迭代加深搜索有界深度搜索和迭代加深搜索 有界深度优先搜索有界深度优先搜索过程总体上按深度优先算过程总体上按深度优先算法方法进行，但对搜索深度需要给出一个深法方法进行，但对搜索深度需要给出一个深度限制度限制dmdm，当深度达到了，当深度达到了dmdm的时候，如果还的时候，如果还没有找到解答，就停止对该分支的搜索，换没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。到另外一个分支进行搜索。2022-9-1492(1)把初始节点把初始节点S0放入放入OPEN表中，置表中，置

55、S0的深度的深度d(S0)=0。(2)如果如果OPEN表为空，则问题无解，失败并退出。表为空，则问题无解，失败并退出。(3)把把OPEN表中的第一个节点取出放入表中的第一个节点取出放入CLOSE表中。并按顺序表中。并按顺序冠以编号冠以编号n。(4)考察节点考察节点n是否为目标节点。若是，则求得了问题的解，成是否为目标节点。若是，则求得了问题的解，成功并退出。功并退出。(5)如果节点如果节点n的深度的深度d(n)=dm，则转第，则转第(2)步步。(6)如果节点如果节点n不可扩展，则转第不可扩展，则转第(2)步。步。(7)扩展节点扩展节点n。将其子节点放入。将其子节点放入OPEN表的表的首部首部，

56、并为其配置，并为其配置指向父节点的指针。然后转第指向父节点的指针。然后转第(2)步。步。有界深度搜索算法有界深度搜索算法2022-9-1493策略说明策略说明:o（1 1）深度限制深度限制dmdm很重要很重要。当问题有解，且当问题有解，且解的路径长度小于或等于解的路径长度小于或等于dmdm时，则搜索过时，则搜索过程一定能够找到解，但是和深度优先搜索程一定能够找到解，但是和深度优先搜索一样这并不能保证最先找到的是最优解。一样这并不能保证最先找到的是最优解。o 但是当但是当dmdm取得太小，解的路径长度大于取得太小，解的路径长度大于dmdm时，则搜索过程中就找不到解，即这时搜时，则搜索过程中就找不

57、到解，即这时搜索过程甚至是不完备的。索过程甚至是不完备的。2022-9-1494（2 2）深度限制深度限制dmdm不能太大不能太大。当。当dmdm太大时，搜太大时，搜索过程会产生过多的无用节点，既浪费了计索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。算机资源，又降低了搜索效率。（3 3）有界深度搜索的主要问题是）有界深度搜索的主要问题是深度限制值深度限制值dmdm的选取的选取。2022-9-1495改进方法改进方法：（迭代加深搜索）（迭代加深搜索）先任意给定一个较小的数作为先任意给定一个较小的数作为dmdm，然后，然后按有界深度算法搜索，若在此深度限制按有界深度算法搜索，若

58、在此深度限制内找到了解，则算法结束；如在此限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制内没有找到问题的解，则增大深度限制dmdm，继续搜索。，继续搜索。2022-9-1496o 迭代加深搜索迭代加深搜索，试图尝试所有可能的深度限制：，试图尝试所有可能的深度限制：n首先深度为首先深度为0 0，n然后深度为然后深度为1 1，n然后为然后为2 2，等等。，等等。o 如果初始深度为如果初始深度为0 0，则该算法只生成根节点，并，则该算法只生成根节点，并检测它。检测它。o 如果根节点不是目标，则深度加如果根节点不是目标，则深度加1 1，通过典型的，通过典型的深度优先算法，生成

59、深度为深度优先算法，生成深度为1 1的树。的树。o 当深度限制为当深度限制为m m时，树的深度为时，树的深度为m m。2022-9-1497o 迭代加深搜索看起来会很浪费，因为很多节点迭代加深搜索看起来会很浪费，因为很多节点都可能扩展多次。都可能扩展多次。o 然而对于很多问题，然而对于很多问题，这种多次的扩展负担实际这种多次的扩展负担实际上很小上很小，直觉上可以想象，如果一棵树的分支，直觉上可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则系数很大，几乎所有的节点都在最底层上，则对于上面各层节点扩展多次对整个系统来说影对于上面各层节点扩展多次对整个系统来说影响不是很大。响不是很

60、大。2022-9-1498 Procedure Iterative-deepeningBegin(1)设置当前深度限制设置当前深度限制=1;(2)把初始节点压入栈把初始节点压入栈,并设置栈顶指针并设置栈顶指针;(3)While栈不空并且深度在给定的深度限制之内栈不空并且深度在给定的深度限制之内do Begin 弹出栈顶元素；弹出栈顶元素；If栈顶元素栈顶元素=goal,返回并结束返回并结束;Else以任意的顺序把栈顶元素的子女压入栈中以任意的顺序把栈顶元素的子女压入栈中;End End whild (4)深度限制加深度限制加1,并返回并返回2;End.迭代加深搜索算法迭代加深搜索算法2022-

61、9-1499总结总结o 宽度优先搜索、深度优先搜索和迭代加深搜宽度优先搜索、深度优先搜索和迭代加深搜索都可以用于生成和测试算法。索都可以用于生成和测试算法。o 宽度优先搜索宽度优先搜索需要指数数量的空间，深度优需要指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性先搜索的空间复杂度和最大搜索深度呈线性关系。关系。2022-9-14100o 迭代加深搜索迭代加深搜索对一棵深度受控的树采用深度对一棵深度受控的树采用深度优先的搜索。它结合了宽度优先和深度优先优先的搜索。它结合了宽度优先和深度优先搜索的优点。搜索的优点。o 和宽度优先搜索一样，它是最优的，也是完和宽度优先搜索一样，它是最优的

62、，也是完备的。但对空间要求和深度优先搜索一样是备的。但对空间要求和深度优先搜索一样是适中的。适中的。2022-9-14101搜索最优策略的比较搜索最优策略的比较 o 表注：表注：b是分支系数，是分支系数，d是解答的深度，是解答的深度，m是搜索树的最是搜索树的最大深度，大深度，l是深度限制。是深度限制。2022-9-14102一般图搜索算法一般图搜索算法o 常用的简单方式：常用的简单方式：n 深度优先深度优先n 宽度优先宽度优先n【缺点：节点排序的盲目性缺点：节点排序的盲目性】o 在白白在白白搜索了大量无关的状态节点搜索了大量无关的状态节点后才碰到解后才碰到解答，答，效率低效率低o 提高提高一般

63、图搜索一般图搜索效率效率的关键的关键n 优化优化OPEN表中节点的排序方式表中节点的排序方式盲目搜索盲目搜索2022-9-14103586427031586407321586427310506487321586470321586047321560487321056487321567480321567481320567408321586427301125634最理想情况：最理想情况：每次排序后每次排序后OPEN表表表首元素表首元素n n总在解答路径上总在解答路径上2022-9-14104o 启发式知识启发式知识指导指导OPEN表排序表排序的的一般图搜索一般图搜索：n 全局排序全局排序对对OPEN

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

65、评价函数f(n)=g(n)+h(n)】n n-搜索图搜索图G中中的节点的节点；n f(n)-G中从初始状态节点中从初始状态节点s，经由节点，经由节点n到达目标到达目标节点节点ng，估计估计的的最小路径代价最小路径代价；n g(n)-G中从中从s到到n，目前实际目前实际的路径代价；的路径代价；n h(n)-从从n到到ng，估计估计的最小路径代价；的最小路径代价；2022-9-14106Snng搜索图搜索图G Gh(n):n-ng的的估计估计最小路径代价最小路径代价 g(n):s-n的实际路径代价的实际路径代价 f(n):s-n-ng的的估计估计最小路径代价最小路径代价 2022-9-14107o

66、【评价函数评价函数f(n)=g(n)+h(n)】n n-搜索图搜索图G中中的节点的节点；n f(n)-G中从中从s经经n到到ng，估计估计的的最小路径代价最小路径代价；n g(n)-G中从中从s到到n，目前实际目前实际的路径代价；的路径代价；n h(n)-从从n到到ng，估计估计的的最小路径代价最小路径代价；o h(n)值值-依赖于依赖于启发式知识启发式知识加以计算；加以计算；o h(n)称为称为启发式函数启发式函数。o 如何用评价函数来实现如何用评价函数来实现A算法算法?（掌握！掌握！）2022-9-14108oA算法算法的设计与的设计与一般图搜索一般图搜索相同，划分为二个阶段相同，划分为二个阶段：n1、初始化、初始化 o 建立只包含初始状态节点建立只包含初始状态节点s的搜索图的搜索图G:=so OPEN:=so CLOSE:=n2、搜索循环、搜索循环o MOVE-FIRST(OPEN)-取出取出OPEN表首表首的节点的节点n o 扩展出扩展出n的子节点的子节点,插入搜索图插入搜索图G和和OPEN表表 o 适当的标记和修改指针（适当的标记和修改指针（子节点子节点父节点父节点）o 排序