第三章_搜索策略-1ppt课件

1、2022/7/171第3章 搜索战略问题求解系统划分为两大类知识贫乏系统 依托搜索技术处理问题 知识贫乏、缺乏针对性效率低 知识丰富系统 依托推理技术处理问题基于丰富知识的推理技术，直截了当 效率高 2022/7/172第3章 搜索战略两大类搜索技术:1、普通图搜索、启发式搜索2、基于问题归约的与或图搜索 两种典型的推理技术:1、基于归结的演绎推理归结反演2、基于规那么的演绎推理正向演绎推理逆向演绎推理 2022/7/1733.1 引言 对于给定的问题，智能系统的行为普通是找到可以到达所希望目的的动作序列，并使其所付出的代价最小、性能最好。基于给定的问题，问题求解的第一步是目的的表示。搜索就是

2、找到智能系统的动作序列的过程。 2022/7/174搜索算法的输入是给定的问题，输出时表示为动作序列的方案。一旦有了方案，就可以执行该方案所给出的动作了。执行阶段因此，求解问题包括：目的表示搜索执行2022/7/1751初始形状集合：定义了初始的环境。2操作符集合：把一个问题从一个形状变换为另一个形状的动作集合。3目的检测函数：用来确定一个形状是不是目的。4途径费用函数：对每条途径赋予一定费用的函数。其中，初始形状集合和操作符集合定义了问题的搜索空间。普通给定问题就是确定该问题的一些根本信息，一个问题由4部分组成:2022/7/176和通常的搜索空间不同，人工智能中大多数问题的形状空间在问题求

3、解之前不是全部知道的。 在人工智能中，搜索问题普通包括两个重要的问题：搜索什么搜索什么通常指的就是目的。在哪里搜索在哪里搜索就是“搜索空间。搜索空间通常是指一系列形状的聚集，因此称为形状空间。2022/7/177所以，人工智能中的搜索可以分成两个阶段：形状空间的生成阶段在该形状空间中对所求问题形状的搜索搜索可以根据能否运用启发式信息分为盲目搜索启发式搜索 2022/7/178盲目搜索 只是可以区分出哪个是目的形状。 普通是按预定的搜索战略进展搜索。 没有思索到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。 启发式搜索是在搜索过程中参与了与问题有关的启发式信息，用于指

4、点搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。 2022/7/179根据问题的表示方式分为形状空间搜索与或图搜索形状空间搜索是用形状空间法来求解问题所进展的搜索与/或图搜索是指用问题规约方法来求解问题时所进展的搜索。2022/7/1710思索一个问题的形状空间为一棵树的方式。宽度优先搜索深度优先搜索假设根节点首先扩展，然后是扩展根节点生成的一切节点，然后是这些节点的后继，如此反复下去。在树的最深一层的节点中扩展一个节点。只需当搜索遇到一个死亡节点非目的节点并且是无法扩展的节点的时候，才前往上一层选择其他的节点搜索。2022/7/1711无论是宽度优先搜索还是深度优先搜索，遍历节点的

5、顺序普通都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为“确定性的，也就是盲目搜索。对于启发式搜索，在计算每个节点的参数之前无法确定先选择哪个节点扩展，这种搜索普通也称为非确定的。 2022/7/1712完备性：假设存在一个解答，该战略能否保证可以找到？时间复杂性：需求多长时间可以找到解答？空间复杂性：执行搜索需求多少存储空间？最优性：假设存在不同的几个解答，该战略能否可以发现最高质量的解答？搜索战略评价规范:2022/7/1713有许多智力问题(如梵塔问题、游览商问题、八皇后问题、农夫过河问题等)和实践问题如途径规划、机器人行动规划等都可以归结为形状空间搜索。用形状

6、空间搜索来求解问题的系统均定义一个形状空间，并经过适当的搜索算法在形状空间中搜索解答途径。3.2 基于形状空间的搜索技术2022/7/1714形状空间搜索1.形状空间及其搜索的表示(1)形状空间的表示形状空间记为SP，可表示为二元组：SP=(S,O)S问题求解即搜索过程中一切能够到达的合法形状构成的集合；O操作算子的集合，操作算子的执行会导致问题形状的变化 ；形状用于记载问题求解即搜索过程中某一时辰问题现状的快照；笼统为矢量方式 Q=q0,q1,qnT每个元素qi称为形状分量 给定每个形状分量qi的值就得到一个详细的形状 Qk=q0k,q1k,qnkT2022/7/1715形状表示形状的变化操

7、作算子问题的形状空间是一个表示该问题的全部能够形状及其变化的有向图。 节点形状有向弧形状的变化 弧上的标签导致形状变化的操作算子 用形状空间搜索来求解问题的系统均定义一个形状空间，并经过适当的搜索算法在形状空间中搜索解答途径。2022/7/1716例1：走迷宫是人们熟习的一种游戏。形状空间搜索2022/7/1717格子、入口和出口节点形状通道有向弧操作算子迷宫可以由一个有向图表示2022/7/1718 例2:在一个33的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上挪动，其挪动规那么是：与空格相邻的数码方可移入空格。如今的问题是：对于指

8、定的初始棋局和目的棋局，给出数码的挪动序列。该问题称为八数码问题。 56741382初始棋局56748321目的棋局挪动数码2022/7/17192 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 5

9、 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/7/17202022/7/1721 例3:钱币翻转问题。设有3个钱币，其初始形状为(正、反、正),欲得的目的形状为(正、正、正)或(反、反、反)。问题是允许每次只能且必需翻转一个钱币，连翻三次。问能否到达目的形状。 分析：经过引入一个三维变量将问题表示出来。设三维变量为：Q=q1,q2,q3，式中qi (i=1,2,3)=1表示钱币为正面，qi (i=1,2,3)=0表示钱币为反面。那么三个钱币能够出现的形状有8种组合：Q0=(0,0,0),Q1=(

10、0,0,1),Q2=(0,1,0),Q3=(0,1,1),Q4=(1,0,0),Q5=(1,0,1), Q6=(1,1,0), Q7=(1,1,1)。即初始形状为Q5，目的形状为Q0或Q7，要求步数为3。2022/7/1722钱币问题的形状空间图2022/7/1723形状空间搜索1.形状空间及其搜索的表示(2)形状空间表示的经典例子“传教士和野人问题 问题的描画：N个传教士带着N个野人划船过河；3个平安约束条件：1)船上人数不得超越载重限量，设为K个人； 2)任何时辰包括两岸、船上野人数目不得超越传教士； 3)允许在河的某一岸或者在船上只需野人而没有传教士；2022/7/1724形状空间搜索1

11、.形状空间及其搜索的表示(2)形状空间表示的经典例子“传教士和野人问题 特例：N=3，K=2 形状分量m传教士在左岸的实践人数形状分量c野人在左岸的实践人数形状分量b指示船能否在左岸(1、0)3个平安约束条件m c (左岸平安)且 N-m N-c(右岸平安);(想一想，为什么不思索船平安？)m=0且0c N (左岸没有传道士，右岸一定平安);N-m=0且0N-cN (右岸没有传道士，左岸一定平安);2022/7/1725设初始形状下传教士、野人和船都在左岸，目的形状下这三者均在右岸，问题形状以m,c,b表示。问题的求解义务可描画为：(3,3,1) (0,0,0)该简单问题能够到达的合法形状：能

12、够形状总数：442=32根据条件得出合法形状：20m c 且 N-m N-c (左岸平安且右岸平安)m=1,c=1；m=2,c=2 m=0且0c N(左岸没有传道士)m=0,c=0,1,2,3 N-m=0且0N-cN(右岸没有传道士)m=3,c=0,1,2,3不能够到达的合法形状：(0,0,1),(0,3,0),(3,0,1),(3,3,0)能够到达的合法形状共16个2022/7/1726形状空间搜索1.形状空间及其搜索的表示(2)形状空间表示的经典例子“传教士和野人问题定义2类操作算子：L(x,y)指示从左岸到右岸的划船操作 R(x,y)指示从右岸到左岸的划船操作x + y K=2(船的载重

13、限制)；x和y取值的能够组合只需5个10，20，11，01，02 ( 允许在船上只需野人而没有传教士 )共有10个操作算子2022/7/1727渡河问题的形状空间有向图2022/7/1728形状空间搜索1.形状空间及其搜索的表示总结形状空间表示方法： 用形状空间方法表示问题时，首先必需定义形状的描画方式，经过运用这种描画方式可把问题的一切形状都表示出来。另外，还要定义一组操作，经过运用这些操作可把问题由一种形状转变为另一种形状。 问题的求解过程是一个不断把操作作用于形状的过程。假设在运用某个操作后得到的新形状是目的形状，就得到了问题的一个解。这个解是从初始形状到目的形状所用操作构成的序列。 2

14、022/7/1729形状空间搜索1.形状空间及其搜索的表示总结形状空间表示方法： 要使问题由一种形状转变到另一种形状时，就必需运用一次操作。这样，在从初始形状转变到目的形状时，就能够存在多个操作序列(即得到多个解)。那么，其中运用操作最少或较少的解才为最优解(由于只需在运用操作时所付出的代价为最小的解才是最优解)。 对其中的某一个形状，能够存在多个操作使该形状变到几个不同的后继形状那么究竟用哪个操作进展搜索呢?这就有赖于搜索战略了不同的搜索战略有不同的顺序，这就是本章后面要讨论的问题。 2022/7/1730课堂练习有一农夫带一只狐狸、一只小羊和一篮菜过河从左岸到右岸。假设船太小，农夫每次只能

15、带一样东西过河；思索到平安，无农夫看管时，狐狸和小羊不能在一同，小羊和那篮菜也不能在一同。请为该问题的处理设计形状空间，并画出形状空间图。2022/7/1731解析以变量m、f、s、v分别指示农夫、狐狸、小羊、菜,且每个变量只可取值1(表示在左岸)或0(表示在右岸)。问题形状可以四元组(m、f、s、v)描画,设初始形状下均在左岸,目的形状下都到达右岸。从而,问题求解义务可描画为 (1, 1, 1, 1) -(0, 0, 0, 0)思索：为什么不把船的形状放到形状空间中去？由于问题简单,形状空间中能够的形状总数为2222 = 16,由于要服从平安限制,合法的形状只需(除初、目形状外): 1110

16、，1101，1011，1010，0101，0001，0010，0100；不合法形状有: 0111,1000,1100,0011,0110,1001设计二类操作算子:Lx、Rx,x为m、f、s、v时分别指示农夫单独,带狐狸,带小羊,带菜过河；形状空间图如下所示.由于Lx和Rx是互逆操作,故而解答途径可有无数条,但最近的只需二条;都是7个操作步. 2022/7/1732解析:四元组(m、f、s、v)代表农夫、狐狸、小羊、菜2022/7/1733形状空间搜索1.形状空间及其搜索的表示(3)形状空间的搜索形状空间的搜索记为SE，可表示为五元组：SE=(S,O,E,I,G)；E搜索引擎；I问题的初始形状

17、，I S；G问题的目的形状集合，G S。搜索引擎E可以设计为实现任何搜索算法的控制系统。根本思想经过搜索引擎E寻觅一个操作算子的调用序列，使问题从初始形状I变化到目的形状G之一。解答途径初-目变化过程中的形状序列或相应的操作算子调用序列。2022/7/1734形状空间搜索1.形状空间及其搜索的表示或图普通图一个形状可以有多个可供选择的操作算子；操作算子间的选择是一种“或的关系;这样的有向图称为或图。2022/7/1735形状空间搜索1.形状空间及其搜索的表示(3)形状空间的搜索或图普通图一个形状可以有多个可供选择的操作算子；操作算子间的选择是一种“或的关系，这样的有向图称为或图。形状空间普通都

18、表示为或图普通图搜索图在搜索解答途径的过程中画出搜索时涉及到的节点和弧线，构成所谓的搜索图。形状空间搜索普通图搜索2022/7/1736形状空间搜索1.形状空间及其搜索的表示(3)形状空间的搜索形状空间、搜索图和解答途径之间的关系S0Sg2022/7/1737形状空间搜索1.形状空间及其搜索的表示(4)普通图搜索例子八数码游戏 求解的问题：给定初始规划(即初始形状)和目的规划(即目的形状)，如何挪动数码才干从初始规划到达目的规划？解答就是一个合法的棋牌走步序列。初始规划目的规划挪动数码2022/7/1738形状空间搜索1.形状空间及其搜索的表示(4)普通图搜索例子八数码游戏 用普通图搜索方法处

19、理该问题的步骤：1、为问题形状的表示建立数据构造2、制定操作算子集合3、设计搜索引擎 第一步：为问题形状的表示建立数据构造33的一个矩阵S矩阵元素Sij0,1,2,3,4,5,6,7,8,其中1i,j3 数字0表示空格 数字1-8表示相应的棋牌八数码问题就可表示为：2022/7/1739形状空间搜索1.形状空间及其搜索的表示初始规划目的规划挪动数码(4)普通图搜索例子八数码游戏 2022/7/1740形状空间搜索1.形状空间及其搜索的表示(4)普通图搜索例子八数码游戏 第二步：制定操作算子集直观方法为每个棋牌制定一套能够的走步：左、上、右、下四种挪动。需求32个操作算子简易方法仅为空格制定这4

20、种走步。仅需4个操作算子第三步：设计搜索引擎 问题形状空间的大小与问题涉及的元素个数是程指数级爆炸式增长即，组合爆炸问题如，棋盘规划问题形状总共有9!=362880个 研讨焦点是处理组合爆炸问题，经过紧缩搜索空间，提高搜索效率。 2022/7/1741形状空间搜索1.形状空间及其搜索的表示形状空间、搜索图和解答途径之间的关系S0Sg2022/7/1742形状空间搜索2.普通图搜索战略 1搜索术语1、节点深度根节点指示初始形状，令其深度为0；搜索图中的其他节点的深度dn就可以递归地定义为其父节点深度dn-1加1：dn= dn-1+1。 根节点深度=0第n-1层节点dn-1第n层节点dn= dn-

21、1+1搜索图2022/7/1743形状空间搜索2.普通图搜索战略 1搜索术语2、节点扩展运用操作算子将上一形状节点ni变化到下一形状节点nj节点ni称为被扩展节点父节点节点nj称为ni的子节点节点ni节点nj2022/7/17441搜索术语3、途径 节点ni到nj的途径是由相邻节点间的弧线构成的折线要求途径是无环的4、途径代价相邻节点ni和ni+1间的途径代价记为C(ni, ni+1) 通常令恣意相邻节点间的途径代价一样，并以途径长度1指示。即C(ni, ni+1)=1 。形状空间搜索2.普通图搜索战略节点ni节点ni+1节点nj2022/7/1745形状空间搜索2.普通图搜索战略 1搜索术语

22、4、途径代价目的形状节点ng节点ni节点nkC(nk,ng) C(ni,nk) C(ni,ng) 2022/7/1746形状空间搜索2.普通图搜索战略2普通图搜索算法符号阐明：s-初始形状节点G-搜索图OPEN-存放待扩展节点的表CLOSE-存放已被扩展的节点的表MOVE-FIRST(OPEN)-取OPEN表首的节点作为当前要被扩展的节点n，同时将节点n移至CLOSE表普通图搜索算法划分为二个阶段：1、初始化 2、搜索循环 2022/7/1747形状空间搜索2.普通图搜索战略2普通图搜索算法算法划分为二个阶段：1、初始化 建立只包含初始形状节点s的搜索图G:=sOPEN:=sCLOSE:= 2

23、、搜索循环MOVE-FIRST(OPEN)-取出OPEN表首的节点n作为扩展的节点，同时将其移到close表 扩展出n的子节点,插入搜索图G和OPEN表 适当的标志和修正指针排序OPEN表经过循环地执行该算法，搜索图G会因不断有新节点参与而逐渐长大，直到搜索到目的节点。 2022/7/1748以下面的八数码为例，看普通图的搜索算法初始规划目的规划挪动数码形状空间搜索2.普通图搜索战略2022/7/17492022/7/17502022/7/17512022/7/17522022/7/17532022/7/17542022/7/17552022/7/17562022/7/17572022/7/1

24、7582022/7/17592022/7/17602022/7/17612022/7/17622022/7/17632022/7/17642022/7/17652022/7/17662022/7/17672022/7/1768形状空间搜索2.普通图搜索战略2普通图搜索算法搜索过程中的指针修正节点n扩展后的子节点分为3类：(i)全新节点(ii)已出如今OPEN表中的节点(iii)已出现的CLOSE表中的节点指针标志和修正的方法：(i)类节点：参与OPEN表，建立从子节点到父节点n的指针(ii)类节点、 (iii)类节点比较经由老父节点、新父节点n到达初始形状节点的途径代价 经由节点n的代价比较小

25、，那么挪动子节点指向老父节点的指针，改为指向新父节点n (iii)类节点还得从CLOSE表中移出，重新参与OPEN表。2022/7/1769形状空间搜索2.普通图搜索战略Sn4ninjn1n2n3n31n32节点ni是当前扩展的节点；扩展出4个后续节点；n1、n2是新节点，只需建立指向父节点的指针，并参与OPEN表；2022/7/1770形状空间搜索2.普通图搜索战略Sn4ninjn1n2n3n31n32n4曾经存在于OPEN表，并且已有父节点njn4经nj的途径代价大取消n4指向nj的指针改为建立n4指向新父节点ni的指针n3曾经存在于CLOSE表，并且已有父节点nj需求做和n4同样的比较和

26、指针修正任务。并且要重新参与open表。2022/7/17713.3 盲目搜索 提高搜索效率的关键优化OPEN表中节点的排序方式。简单的排序战略按预先确定的顺序或随机地排序新参与到OPEN表中的节点。 常用的简一方式： 宽度优先扩展当前节点后生成的子节点总是置于OPEN表的后端，即OPEN表作为队列运用，先进先出，使搜索优先向横广方向开展。 深度优先扩展当前节点后生成的子节点总是置于OPEN表的前端，即OPEN表作为栈运用，后进先出，使搜索优先向纵深方向开展。2022/7/1772宽度优先宽度优先扩展当前节点后生成的子节点总是置于OPEN表的后端，即OPEN表作为队列，先进先出，使搜索优先向横

27、向方向开展。过程：指从初始节点S0开场，向下逐层搜索，在n层节点未搜索完之前，不进入n+1层搜索。同层节点的搜索次序可以恣意。即先按生成规那么生成第一层节点，在该层全部节点中沿宽(广)度进展横向扫描，检查目的节点Sg能否在这些子节点中。假设没有,那么再将一切笫一层节点逐一扩展，得到第二层节点。并逐一检查第二层节点中能否包含有Sg，如此依次按照先生成、先检查、先扩展的原那么进展下去，直到发现Sg为止 2022/7/1773宽度优先实例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

28、 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 51256731 2 3 8 47 6 5目的82 3 41 8 7 6 54910111213141516172022/7/1774宽度优先搜索 假设搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进展的，在对下一层的恣意节点进展搜索之前，必需搜索完本层的一切节点。“先产生的节点先扩展2022/7/1775 (1)把初

29、始节点S0，放入OPEN表。 (2)假设OPEN表为空。那么问题无解，失败并退出。 (3)把OPEN表中的第一个节点取出放入CLOSE表中，并按顺序冠以编号n； (4)调查节点n能否为目的节点。假设是，那么求得了问题的解，胜利并退出。 (5)假设节点n不可扩展，那么转第(2)步； (6)扩展节点n，将其子节点放到OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第(2)步。采用队列构造，宽度优先算法可以表示如下：2022/7/1776 例 经过挪动积木块，希望从初始形状到达一个目的形状，即三块积木堆叠在一同。积木A在顶部，积木B在顶中间，积木C在底部。请画出按照宽度优先搜索战略所

30、产生的搜索树。 这个问题的独一操作算子为MOVE(X,Y)，即积木X搬到Y积木或桌面上面。如“挪动积木A到桌面上表示为MOVE(A,Table)。该操作算子可运用的先决条件是：1被挪动积木的顶部必需为空。2如Y是积木不是桌面，那么积木Y的顶部也必需为空。3同一形状下，运用操作算子的次数不得多于一次。2022/7/1777积木问题的宽度优先搜索树 2022/7/1778宽度优先搜索的性质当问题有解时，一定能找到解(完备性)当问题为单位代价时，且问题有解时，一定能找到最优解最优性方法与问题无关，具有通用性效率较低属于图搜索方法2022/7/1779宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较

31、高，当目的节点间隔初始节点较远时会产生许多无用的节点，搜索效率低。宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时，尤为严重，但是空间需求是比执行时间更严重的问题。 宽度优先搜索优点：目的节点假设存在，用宽度优先搜索算法总可以找到该目的节点，而且是最小即最短途径的节点。宽度优先搜索的优点和缺陷2022/7/1780深度优先深度优先扩展当前节点后生成的子节点总是置于OPEN表的前端，即OPEN表作为栈，后进先出，使搜索优先向纵深方向开展。过程：从初始节点S0开场，按生成规那么生成下一级各子节点，检查能否出现目的节点Sg；假设未出现，那么按“最晚生成的子节点优先扩展的原那么，再

32、用生成规那么生成再下一级的子节点，再检查能否出现Sg；假设仍未出现，那么再扩展最晚生成的子节点。如此下去，沿着最晚生成的子节点分枝，逐级“纵向深化搜索。 2022/7/1781深度优先实例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

33、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/7/1782深度优先搜索在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度 相等的节点可以恣意陈列。“最晚产生的节点最先扩展起始节点深度为0 任何其他节点的深度等于其父辈节点深度加上1 :dn=dn-1+12022/7/1783深度优先搜索很明显这样做，不一定找到最正确解，而且由于深度的限制，能够找不到解，然而，假设不加深度限制，能够

34、沿着一条道路无限制地扩展下去，这当然是不允许的。为保证找到解，应选择适当的深度界限，或者采取不断加大深度界限的方法，反复搜索，直到找到解。这种改良的方法叫做迭代加深搜索。2022/7/1784(1)把初始节点S0放入OPEN表； (2)假设OPEN表为空，那么问题无解，失败并退出。 (3)把OPEN表中的第一个节点取出放入CLOSE表中，并按顺序冠以编号n； (4)调查节点n能否为目的节点。假设是，那么求得了问题的解，胜利并退出。 (5)假设节点n不可扩展，那么转第(2)步； (6)扩展节点n，将其子节点放到OPEN表的首部，并为其配置指向父节点的指针，然后转第(2)步。基于栈实现的深度优先搜

35、索算法： 2022/7/1785 例 卒子穿阵问题: 要求一卒子从顶部经过图所示的列阵到达底部。要求卒子行进中不可进入到代表敌兵驻守的区域内标注1，并不准后退。假定限制值为5。请画出按照深度优先搜索战略所产生的搜索树 2022/7/1786卒子穿阵的深度优先搜索树 2022/7/1787深度优先搜索的性质普通不能保证找到最优解当深度限制不合理时，能够找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法2022/7/1788深度优先搜索的优点是比宽度优先搜索算法需求较少的空间，该算法只需求保管搜索树的一部分，它由当前正在搜索的途径和该途径上还没有完全展开

36、的节点标志所组成。深度优先搜索的存储器要求是深度约束的线性函数。 深度优先搜索的优点2022/7/1789深度优先搜索的缺陷 既不是完备的，也不是最优的。 主要问题是能够搜索到了错误的途径上。很多问题能够具有很深甚至是无限的搜索树，假设不幸选择了一个错误的途径，那么深度优先搜索会不断搜索下去，而不会回到正确的途径上。这样一来对于这些问题，深度优先搜索要么堕入无限的循环而不能给出一个答案，要么最后找到一个答案，但途径很长而且不是最优的答案。2022/7/1790比较 适用场所 深度优先当一个问题有多个解答或多条解答途径，且只须找到其中一个时；往往应对搜索深度加以限制。 宽度优先确保搜索到最短的解

37、答途径。共同优缺陷： 可直接运用普通图搜索算法实现，不需求设计特别的节点排序方法，从而简单易行，适宜于许多复杂度不高的问题求解义务。 节点排序的盲目性，由于不采用领域专门知识去指点排序，往往会在白白搜索了大量无关的形状节点后才碰到解答，所以也称为盲目搜索。 2022/7/1791有界深度搜索和迭代加深搜索 有界深度优先搜索过程总体上按深度优先算法方法进展，但对搜索深度需求给出一个深度限制dm，当深度到达了dm的时候，假设还没有找到解答，就停顿对该分支的搜索，换到另外一个分支进展搜索。2022/7/1792(1)把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。 (2)假设OPEN表为

38、空，那么问题无解，失败并退出。 (3)把OPEN表中的第一个节点取出放入CLOSE表中。并按顺序冠以编号n。(4)调查节点n能否为目的节点。假设是，那么求得了问题的解，胜利并退出。 (5)假设节点n的深度d(n)= dm，那么转第(2)步。 (6)假设节点n不可扩展，那么转第(2)步。 (7)扩展节点n。将其子节点放入OPEN表的首部，并为其配置指向父节点的指针。然后转第(2)步。 有界深度搜索算法2022/7/1793战略阐明: 1深度限制dm很重要。当问题有解，且解的途径长度小于或等于dm时，那么搜索过程一定可以找到解，但是和深度优先搜索一样这并不能保证最先找到的是最优解。但是当dm获得太

39、小，解的途径长度大于dm时，那么搜索过程中就找不到解，即这时搜索过程甚至是不完备的。2022/7/17942深度限制dm不能太大。当dm太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。3有界深度搜索的主要问题是深度限制值dm的选取。 2022/7/1795改良方法： 迭代加深搜索 先恣意给定一个较小的数作为dm，然后按有界深度算法搜索，假设在此深度限制内找到了解，那么算法终了；如在此限制内没有找到问题的解，那么增大深度限制dm，继续搜索。2022/7/1796迭代加深搜索，试图尝试一切能够的深度限制：首先深度为0，然后深度为1，然后为2，等等。假设初始深度为0，那么

40、该算法只生成根节点，并检测它。假设根节点不是目的，那么深度加1，经过典型的深度优先算法，生成深度为1的树。当深度限制为m时，树的深度为m。 2022/7/1797迭代加深搜索看起来会很浪费，由于很多节点都能够扩展多次。然而对于很多问题，这种多次的扩展负担实践上很小，直觉上可以想象，假设一棵树的分支系数很大，几乎一切的节点都在最底层上，那么对于上面各层节点扩展多次对整个系统来说影响不是很大。 2022/7/1798 Procedure Iterative-deepeningBegin(1)设置当前深度限制=1; (2)把初始节点压入栈,并设置栈顶指针; (3)While栈不空并且深度在给定的深度

41、限制之内do Begin 弹出栈顶元素； If栈顶元素=goal,前往并终了; Else以恣意的顺序把栈顶元素的子女压入栈中; End End whild (4)深度限制加1,并前往2;End.迭代加深搜索算法2022/7/1799总结宽度优先搜索、深度优先搜索和迭代加深搜索都可以用于生成和测试算法。宽度优先搜索需求指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性关系。 2022/7/17100迭代加深搜索对一棵深度受控的树采用深度优先的搜索。它结合了宽度优先和深度优先搜索的优点。和宽度优先搜索一样，它是最优的，也是完备的。但对空间要求和深度优先搜索一样是适中的。 2022/7/1

42、7101搜索最优战略的比较 表注：b是分支系数，d是解答的深度，m是搜索树的最大深度，l是深度限制。2022/7/171023.4 启发式搜索普通图搜索算法常用的简一方式：深度优先宽度优先【缺陷：节点排序的盲目性】在白白搜索了大量无关的形状节点后才碰到解答，效率低提高普通图搜索效率的关键优化OPEN表中节点的排序方式盲目搜索2022/7理想情况：每次排序后OPEN表表首元素n总在解答途径上2022/7/17104启发式搜索启发式知识指点OPEN表排序的普通图搜索：全局排序对OPEN表中的一切节点排序，使最有希望的节点排在表首。A算法， A*算法重点掌握！部分排序仅对新

43、扩展出来的子节点排序，使这些新节点中最有希望者能优先取出调查和扩展；爬山法了解，对深度优先法的改良；2022/7/17105启发式搜索1.A算法掌握【根本思想】设计表达启发式知识的评价函数f(n)；指点普通图搜索中OPEN表待扩展节点的排序：【评价函数f(n)=g(n)+h(n) 】 n-搜索图G中的节点；f(n)- G中从初始形状节点s，经由节点n到达目的节点ng，估计的最小途径代价；g(n)- G中从s到n，目前实践的途径代价；h(n)-从n到ng，估计的最小途径代价；2022/7/17106启发式搜索1.A算法掌握Snng目的形状节点ng初始形状节点S节点n搜索图Gh(n): n-ng的

44、估计最小途径代价 g(n):s-n的实践途径代价 f(n):s-n-ng的估计最小途径代价 2022/7/17107启发式搜索1.A算法掌握【评价函数f(n)=g(n)+h(n) 】n-搜索图G中的节点；f(n)- G中从s经n到ng，估计的最小途径代价；g(n)- G中从s到n，目前实践的途径代价；h(n)-从n到ng，估计的最小途径代价； h(n)值-依赖于启发式知识加以计算；h(n)称为启发式函数 。如何用评价函数来实现A算法? 掌握！ 2022/7/17108启发式搜索1.A算法掌握A算法的设计与普通图搜索一样，划分为二个阶段 ：1、初始化 建立只包含初始形状节点s的搜索图G:=sOP

45、EN:=sCLOSE:= 2、搜索循环MOVE-FIRST(OPEN)-取出OPEN表首的节点n 扩展出n的子节点,插入搜索图G和OPEN表 适当的标志和修正指针子节点父节点排序OPEN表评价函数f(n)的值排序经过循环地执行该算法，搜索图会因不断有新节点参与而逐渐长大，直到搜索到目的节点。2022/7/17109启发式搜索1.A算法掌握算法A的设计与普通图搜索类似，划分为二个阶段 ：1、初始化 2、搜索循环MOVE-FIRST(OPEN)-取出OPEN表首的节点n 扩展出n的子节点,插入搜索图G和OPEN表 对每个子节点ni,计算f(n,ni)=g(n,ni)+h(ni)适当的标志和修正指针

46、子节点父节点排序OPEN表评价函数f(n)的值排序2022/7/17110启发式搜索1.A算法掌握扩展出n的子节点,插入搜索图G和OPEN表 对每个子节点ni,计算f(n,ni)=g(n,ni)+h(ni)适当的标志和修正指针子节点父节点(i)全新节点：f(ni)=f(n,ni)(ii)已出如今OPEN表中的节点(iii)已出现的CLOSE表中的节点IF f(ni)f(n,ni) THEN 修正指针指向新父结点n f(ni)=f(n,ni)排序OPEN表f(n)值从小到大排序2022/7/171112.假设OPEN表是空表，那么失败退出；算法A3.选择OPEN表上的第一个节点，把它从OPEN表

47、移出并放进CLOSE表中，称此节点为节点n； 1.建立一个只包含起始节点S的搜索图G,把S放到一个叫OPEN的未扩展节点表中；建立一个叫做CLOSE的已扩展节点表，其初始为空表；5.扩展节点n，同时生成不是n的祖先的那些子节点的集合M,把M的这些成员作为n的后继节点添入图G中；对于M中每个子节点ni,计算f(n,ni) = g(n,ni) + h(ni);4.假设n为一目的节点，那么有解胜利退出，此解是追踪图G中沿着指针从n到S这条途径而得到的；2022/7/171126.对那些未曾在G中出现过的M成员全新结点设置一个通向n的指针。把M的这些成员加进OPEN表。对曾经在OPEN表上的每一个M成

48、员，比较子节点ni经由新、老父节点的评价函数值f(n,ni)、f(ni);假设f(n,ni) f(ni)点,那么令f(ni) = f(n,ni),并挪动子节点指向老父节点的指针，改为指向新父节点。对已在CLOSE表上的每个M成员，作与第2类同样的处置，并把这些子结点从CLOSE表移出，重新参与OPEN表。7.按f(n)排序OPEN表中的节点，f(n)值最小者排在首位，重排OPEN表；8.转2。此过程生成一个明确的图G(搜索图和一个G的子集T(搜索树。2022/7/17113启发式搜索1.A算法掌握A算法实例八数码游戏1)设计评价函数f(n)f(n)=d(n)+w(n),其中d(n)-节点n在搜

49、索图中的节点深度，对g(n)的度量；w(n)-代表启发式函数h(n),其值是节点n与目的形状节点ng相比较，不思索空格，错位的棋牌个数；初始规划目的规划挪动数码2022/7/17114启发式搜索1.A算法掌握启发式算法A实例八数码游戏1)设计评价函数f(n)f(n)计算实例初始规划s目的规划ngw(s):错位的棋牌个数d(s):当前节点深度 f(s)h(n): n-ng的最小途径代价 g(n):s-n的最小途径代价 f(n):s-n-ng的最小途径代价 注：W(S)不思索空格2022/7/17115形状空间搜索2.普通图搜索战略 1搜索术语1、节点深度根节点指示初始形状，令其深度为0；搜索图中

50、的其他节点的深度dn就可以递归地定义为其父节点深度dn-1加1：dn= dn-1+1。 根节点深度=0第n-1层节点dn-1第n层节点dn= dn-1+1搜索图G2022/7/17116启发式搜索1.A算法掌握启发式算法A实例八数码游戏1)设计评价函数f(n)f(n)计算实例初始规划s目的规划ngw(s):错位的棋牌个数d(s):当前节点深度 f(s)h(n): n-ng的最小途径代价 g(n):s-n的最小途径代价 f(n):s-n-ng的最小途径代价 0 4 4 注：W(S)不思索空格2022/7/17117初始化OPEN:=s4 CLOSE:= 目的规划ng2022/7/17118循环1

51、CLOSE:=s4 OPEN:=a b c OPEN:=a6 b4 c6 OPEN:=b4 a6 c6 目的规划ng2022/7/17119循环2CLOSE:=s4 b4 OPEN:=a6 c6 d e i OPEN:=a6 c6 d5 e5 i6 OPEN:=d5 e5 a6 c6 i6 目的规划ng2022/7/17120循环3CLOSE:=s4 b4 d5 OPEN:=e5 a6 c6 i6 j k OPEN:=e5 a6 c6 i6 j7 k6 OPEN:=e5 a6 c6 i6 k6 j7 目的规划ng2022/7/17121循环4CLOSE:=s4,b4,d5,e5 OPEN:=a

52、6 c6 i6 k6 j7 l m OPEN:=a6 c6 i6 k6 j7 l5 m7 OPEN:=l5 a6 c6 i6 k6 j7 m7 目的规划ng2022/7/17122CLOSE:=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 目的规划ng2022/7/17123循环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 O

53、PEN:=g5 a6 c6 i6 k6 j7 m7 o7 目的规划ng2022/7/17124循环7胜利终了目的规划ng2022/7/17125最理想搜索图G2022/7/17126判别失误2022/7/17127 例 2 给定4L和3L的水壶各一个，水壶上没有刻度，可以向水壶中加水。如何在4L的壶中准确地得到2L水？ x,y4L壶里的水有xL，3L壶里的水有yL，n表示搜索空间中的任一节点。那么给出下面的启发式函数： 2022/7/17128 h(n) = 2 假设0 x 4并且0 y 3 = 4 假设0 x 4或者0 y =g*(n)h(n)尽能够接近h*(n) A算法的关键。2022/7

54、/17135启发式搜索2.实现启发式搜索的关键要素1搜索算法的可采用性(Admissibility)4)改良启发式函数八数码游戏f(n)=d(n)+w(n),其中w(n)-表示错位的棋牌个数，不够贴切，错误的扩展了节点d；p(n)-节点n与目的形状节点比较，错位棋牌在不受阻拦的情况下，挪动到目的形状相应位置所需走步挪动次数的总和；p(n)比w(n)更接近于h*(n)-p(n)不仅思索了棋牌的错位要素，还思索了错位的间隔挪动间隔2022/7/17136启发式搜索2.实现启发式搜索的关键要素4)改良启发式函数八数码游戏f(s)计算实例初始规划s目的规划ngw(s):错位的棋牌个数d(s):当前节点

55、深度 f(s)0 4 4 p(s):错位棋牌挪动间隔d(s):当前节点深度 f(s)0 5 5 1 1 1 2 2022/7/17137初始化OPEN:=s5 CLOSE:= 目的规划ng2022/7/17138循环1CLOSE:=s5 OPEN:=a b c OPEN:=a7 b5 c7 OPEN:=b5 a7 c7 目的规划ng2022/7/17139循环2CLOSE:=s5 b5 OPEN:=a7 c7 d e i OPEN:=a7 c7 d7 e5 i7 OPEN:=e5 a7 c7 d7 i7 目的规划ng2022/7/17140循环3CLOSE:=s5 b5 e5 OPEN:=a7

56、 c7 d7 i7 l m OPEN:=a7 c7 d7 i7 l5 m7 OPEN:=l5 a7 c7 d7 i7 m7 目的规划ng2022/7/17141CLOSE:=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 目的规划ng2022/7/17142CLOSE:=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 目的规划n

57、g2022/7/17143循环6胜利终了最理想搜索图G目的规划ng2022/7/17144防止了错误选择2022/7/17145启发式搜索2.实现启发式搜索的关键要素1搜索算法的可采用性(Admissibility)5) A*算法定义 ：1、在A算法中，规定h(n)h*(n);2、经如此限制以后的A算法就是A*算法。A*算法是可采用的，即总能搜索到最短解答途径【回想：八数码游戏的h(n)】w(n)-错位的棋牌个数p(n)-错位棋牌在不受阻拦的情况下，挪动到目的形状相应位置所需走步挪动次数的总和；上述两者均是可采用的。(想想为什么)2022/7/17146启发式搜索2.实现启发式搜索的关键要素1

58、搜索算法的可采用性(Admissibility)5) A*算法定义：1、在A算法中，规定h(n)h*(n);2、经如此限制以后的A算法就是A*算法。A*算法是可采用的，即总能搜索到最短解答途径证明：【陆汝钤P248】1假设存在一条从初始形状到目的形状的解答途径，那么一定存在一条最短解答通路；2设形状n是最短解答途径上的一个形状，那么经过有限步后，n必然会成为OPEN表的第一个节点；3由于最短解答途径只需有限个节点n，所以有限步后算法必然因到达目的形状ng。这就是最优解。证明终了。2022/7/17147启发式搜索2.实现启发式搜索的关键要素1搜索算法的可采用性(Admissibility)5)满足可采用性条件的算法A*算法证明：2设形状n是最短解答途径上的一个形状，那么经过有限步后，n必然会成为OPEN表的第一个节点；f(n)=g(n)+h(n)根据假设，n在最短解答途径上 经过有限步骤后，g(n)= g*(n)f(n)=g*(n)+h(n) h(n)h*(n)f(n)=g*(n)+h(n) g*(n)+h*(n)=f*(n) f*(n)= f*(ng) f(n) f*(ng)2022/7/17148启发式搜索2.实现启发式搜索的关键要素1搜索算法的可采用性(Admissibility)5)满足可采用性条件的算法A*算法证明：2设形状n是最短解答途径上的一个形状，那么经过有限步后