第三章搜索策略

2023/1/191第3章搜索策略问题求解系统划分为两大类知识贫乏系统

依靠搜索技术解决问题知识贫乏、缺乏针对性效率低知识丰富系统

依靠推理技术解决问题基于丰富知识的推理技术，直截了当效率高2023/1/192第3章搜索策略两大类搜索技术:1、一般图搜索、启发式搜索2、基于问题归约的与或图搜索两种典型的推理技术:1、基于归结的演绎推理归结反演2、基于规则的演绎推理正向演绎推理逆向演绎推理2023/1/1933.1引言

对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。基于给定的问题，问题求解的第一步是目标的表示。搜索就是找到智能系统的动作序列的过程。2023/1/194搜索算法的输入是给定的问题，输出是表示为动作序列的方案。一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）因此，求解问题包括：目标表示搜索执行2023/1/195（1）初始状态集合：定义了初始的环境。（2）操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。（3）目标检测函数：用来确定一个状态是不是目标。（4）路径费用函数：对每条路径赋予一定费用的函数。其中，初始状态集合和操作符集合定义了问题的搜索空间。一般给定问题就是确定该问题的一些基本信息，一个问题由4部分组成:2023/1/196和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。

在人工智能中，搜索问题一般包括两个重要的问题：搜索什么搜索什么通常指的就是目标。在哪里搜索在哪里搜索就是“搜索空间”。搜索空间通常是指一系列状态的汇集，因此称为状态空间。2023/1/197所以，人工智能中的搜索可以分成两个阶段：状态空间的生成阶段在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分为盲目搜索启发式搜索2023/1/198盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。

启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。

2023/1/199根据问题的表示方式分为状态空间搜索与或图搜索状态空间搜索是用状态空间法来求解问题所进行的搜索与/或图搜索是指用问题规约方法来求解问题时所进行的搜索。2023/1/1910考虑一个问题的状态空间为一棵树的形式。宽度优先搜索深度优先搜索如果根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索。2023/1/111无论是宽度度优先搜索索还是深度度优先搜索索，遍历节节点的顺序序一般都是是固定的，，即一旦搜搜索空间给给定，节点点遍历的顺顺序就固定定了。这种种类型的遍遍历称为“确定性”的，也就是是盲目搜索。对于启发式式搜索，在在计算每个个节点的参参数之前无法确定先先选择哪个个节点扩展展，这种搜索索一般也称2023/1/112完备性：如果存在一个个解答，该策策略是否保证证能够找到？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？搜索策略评价价标准:2023/1/113有许多智力力问题(如梵塔问题题、旅行商商问题、八八皇后问题题、农夫过过河问题等等)和实际问题题（如路径径规划、机机器人行动动规划等））都可以归归结为状态空间搜搜索。用状态空间搜搜索来求解问题题的系统均均定义一个个状态空间，并通过适适当的搜索算法在3.2基于状态空空间图的搜搜索技术2023/1/114状态空间搜搜索——1.状态空间及及其搜索的的表示(1)状态空间的的表示状态空间记记为SP，可表示为为二元组：：SP=(S,O)S——问题求解（（即搜索））过程中所所有可能到达的合法状态构成的集合合；O——操作算子的集合，操作算子的的执行会导导致问题状状态的变迁迁；状态——用于记载问问题求解（（即搜索））过程中某一时刻问问题现状的的快照；抽象为矢量量形式Q=[q0,q1,…,qn]T每个元素qi称为状态分量给定每个个状态分量量qi的值就得得到一个个具体的的状态Qk=[q0k,q1k,…,qnk]T2023/1/115状态表示状态态的变迁迁操作算子子问题的状状态空间间是一个表表示该问问题的全全部可能能状态及及其变迁迁的有向图。节点状态有向弧状态的变变迁弧上的标标签导致状态态变迁的的操作算子子用状态空间间搜索来求解2023/1/116例1：走迷宫是人们熟悉悉的一种游游戏。状态空间搜搜索2023/1/117格子、入口口和出口——节点——状态通道——有向弧——操作算子迷宫可以由由一个有向图表示2023/1/118例2:在一个3×3的方格棋盘盘上放置着着1,2,3,4,5,6,7,8八个数码，，每个数码码占一格，，且有一个个空格。这这些数码可可在棋盘上上移动，其其移动规则则是：与空空格相邻的的数码方可可移入空格格。现在的问题是：对于指指定的56741382初始棋局56748321目标棋局移动数码2023/1/119231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123847652023/1/1202023/1/121状态空间搜索索——1.状态空间及其其搜索的表示示(2)状态空间表示示的经典例子子“传教士和和野人问题””问题的描述：N个传教士带领领N个野人划船过过河；3个安全约束条条件：1)船上人数不得得超过载重限限量，设为K个人；2)任何时刻（包包括两岸、船船上）野人数数目不得超过过传教士；3)允许在河的某某一岸或者在在船上只有野野人而没有传传教士；22状态空间搜搜索——1.状态空间及及其搜索的的表示(2)状态空间表表示的经典典例子“传传教士和野野人问题””特例：N=3，K=2状态分量m——传教士在左左岸的实际际人数状态分量c——野人在左岸岸的实际人人数状态分量b——指示船是否否在左岸(1、0)3个安全约束束条件m≧c(左岸安全)且N-m≧≧N-c(右岸安全);m=0且0≤c≤≤N(左岸没有传传道士，右右岸一定安安全);N-m=0且0≤N-c≤N(右岸没有传传道士，左左岸一定安安全);2023/1/123设初始状态下传教士、、野人和船船都在左岸岸，目标状态下这三者均均在右岸，，问题状态以（m,c,b）表示。问题的求解解任务可描描述为：(3,3,1)→(0,0,0)该简单问题题可能到达的合法状态：可能状态总数：4×4×2=32根据条件得得出合法状态：20m≧c且N-m≧≧N-c(左岸安全且且右岸安全全)m=1,c=1；m=2,c=2m=0且0≤c≤≤N(左岸没有传传道士)m=0,c=0,1,2,3N-m=0且0≤N-c≤N(右岸没有传传道士)m=3,c=0,1,2,3不可能到达达的合法状状态：(0,0,1),(0,3,0),(3,0,1),(3,3,0)可能到达的合法状态共16个2023/1/124状态空间搜索索——1.状态空间及其其搜索的表示示(2)状态空间表示示的经典例子子“传教士和和野人问题””定义2类操作算子：L(x,y)——指示从左岸到右岸的划船操作R(x,y)——指示从右岸到左岸的划船操作x+y≤≤K=2(船的载重限制制)；x和y取值的可能组组合只有5个10，20，11，01，02(允许在船上只只有野人而没没有传教士)共有10个操作算子2023/1/125渡河问题的状状态空间有向向图2023/1/126状态空间搜搜索——1.状态空间及及其搜索的的表示由此例可以以看出用状态空间间方法表示示问题时，，首先必须须定义状态的的描述形式式，通过使用用这种描述述形式可把把问题的一切状态都都表示出来来。另外，还还要定义一组操操作，通过使用用这些操作作可把问题题由一种状态态转变为另另一种状态态。问题的求解解过程是一一个不断把操作作作用于状状态的过程程。如果在使使用某个操操作后得到到的新状态态是目标状状态，就得得到了问题题的一个解解。这个解解是从初始状态到到目标状态态所用操作作构成的序序列。2023/1/127状态空间搜搜索——1.状态空间及及其搜索的的表示由此例可以以看出要使问题由由一种状态态转变到另另一种状态态时，就必必须使用一一次操作。。这样，在在从初始状状态转变到到目标状态态时，就可可能存在多多个操作序序列(即得到多个解解)。那么，其中中使用操作最少少或较少的解解才为最优解解(因为只有在使使用操作时所所付出的代价价为最小的解解才是最优解解)。对其中的某一一个状态，可可能存在多个个操作．使该该状态变到几几个不同的后后继状态．那那么到底用哪哪个操作进行行搜索呢?这就有赖于搜索策略了．不同的搜索策策略有不同的的顺序，这就是本章章后面要讨论论的问题。2023/1/128课堂练练习有一农农夫带带一只只狐狸狸、一一只小小羊和和一篮篮菜过过河（（从左左岸到到右岸岸）。。假设设船太太小，，农夫夫每次次只能能带一一样东东西过过河；；考虑虑到安安全，，无农农夫看看管时时，狐狐狸和和小羊羊不能能在一一起，，小羊羊和那那篮菜菜也不不能在在一起起。请请为该该问题题的解解决设设计状状态空空间，，并画画出状状态空空间图图。2023/1/129解析以变量量m、f、s、v分别指指示农农夫、、狐狸狸、小小羊、、菜,且每个个变量量只可可取值值1(表示在在左岸岸)或0(表示在在右岸岸)。问题题状态态可以以四元元组(m、f、s、v)描述,设初始始状态态下均均在左左岸,目标状状态下下都到到达右右岸。。从而而,问题求求解任任务可可描述述为(1,1,1,1)->(0,0,0,0)由于问问题简简单,状态空空间中中可能能的状状态总总数为为2×2×2×2=16,由于要要遵从从安全全限制制,合法的的状态态只有有(除初、、目状状态外外):1110，1101，1011，1010，0101，0001，0010，0100；不不合法法状态态有:0111,1000,1100,0011,0110,1001设计二二类操操作算算子:Lx、Rx,x为m、f、s、v时分别别指示示农夫夫独自自,带狐狸狸,带小羊羊,带菜过过河；；状态态空间间图如如下所所示.由于Lx和Rx是互逆逆操作作,故而解解答路路径可可有无无数条条,但最近近的只只有二二条;都是7个操作作步.思考：：为什什么不不把船船的状状态放放到状状态空空间中中去？？2023/1/130解析:四元组组(m、f、s、v)2023/1/131状态空间搜索索——1.状态空间及其其搜索的表示示(3)状态空间的搜搜索状态空间的搜搜索记为SE，可表示为五五元组：SE=(S,O,E,I,G)；E——搜索引擎；I——问题的初始状状态，I∈S；G——问题的目标状状态集合，GS。搜索引擎E——可以设计为实现任何搜索索算法的控制系统。。基本思想——通过搜索引擎擎E寻找一个操作算子的调调用序列，使问题从初初始状态I变迁到目标状状态G之一。解答路径——初-目变迁过程中中的状态序列或相应的操作算子调用用序列。2023/1/132状态空间搜搜索——1.状态空间及及其搜索的的表示或图（一般般图）一个状态可以有多个可供供选择的操作算子子；操作算子间间的选择是是一种“或”的关系;这样的有向向图称为或图。2023/1/133状态空间搜搜索——1.状态空间及及其搜索的的表示(3)状态空间的的搜索或图（一般般图）一个状态可可以有多个个可供选择择的操作算算子；操作算子间间的选择是是一种“或”的关关系系，，这样样的的有有向向图图称称为为或图图。。状态态空空间间一般般都都表表示示为为或图图（（一一般般图图））搜索索图图———在搜索索解解答答路路径径的过过程程中中画画出出搜搜索索时时涉涉及及到到的的节节点点和和弧弧线线，，构构成成所所谓谓的的搜索索图图。状态态空空间间搜搜索索一般般图图搜搜索索2023/1/134状态空空间搜搜索——1.状态空空间及及其搜搜索的的表示示(3)状态空空间的的搜索索状态空空间、搜索图图和解答路路径之间的的关系系S0Sg2023/1/135状态空间搜索索——1.状态空间及其其搜索的表示示(4)一般图搜索例例子——八数码游戏求解的问题：：给定初始布局局(即初始状态)和目标布局(即目标状态)，如何移动数码码才能从初始始布局到达目目标布局？解答就是一个合法法的棋牌走步序列列。初始布局目标布局移动数码2023/1/136状态态空空间间搜搜索索———1.状态态空空间间及及其其搜搜索索的的表表示示(4)一般般图图搜搜索索例例子子———八数数码码游游戏戏用一一般般图图搜搜索索方方法法解解决决该该问问题题的的步步骤骤：：1、为为问题题状状态态的表表示示建建立立数数据据结结构构2、制制定定操作作算算子子集合合3、设设计计搜索索引引擎擎第一一步步：：为为问问题题状状态态的的表表示示建建立立数数据据结结构构3××3的一一个个矩矩阵阵S矩阵阵元元素素Sij∈∈{0,1,2,3,4,5,6,7,8},其中1≤i,j≤3数字0表示空格数字1-8表示相应的的棋牌八数码问题题就可表示示为：2023/1/137状态空间搜搜索——1.状态空间及及其搜索的的表示初始布局目标布局移动数码(4)一般图搜索索例子——八数码游戏戏2023/1/138状态空间搜搜索——1.状态空间及及其搜索的的表示(4)一般图搜索索例子——八数码游戏戏第二步：制制定操作算算子集直观方法——为每个棋牌牌制定一套套可能的走走步：左、、上、右、、下四种移移动。需要32个操作算子子简易方法——仅为空格制制定这4种走步。仅需4个操作算子子第三步：设设计搜索引引擎问题状态空空间的大小小与问题题涉涉及及的的元元素素个数数是是程程指数数级级爆爆炸炸式式增增长长（即即，，组合合爆爆炸炸问问题题）如，，棋棋盘盘布布局局（（问问题题状状态态））总总共共有有9!=362880个研究究焦焦点点是解决决组组合合爆爆炸炸问问题题，通过过压压缩缩搜搜索索空空间间，提高高搜搜索索效效率率。2023/1/139状态态空空间间搜搜索索———1.状态态空空间间及及其其搜搜索索的的表表示示状态态空空间间、搜索索图图和解答答路路径径之间间的的关关系系S0Sg2023/1/140状态空间间搜索——2.一般图搜搜索策略略（1）搜索术术语1、节点深深度根节点指示初始状态态，令其深深度为0；搜索图中中的其他他节点的的深度dn就可以递递归地定定义为其其父节点深深度dn-1加1：dn=dn-1+1。根节点深深度=0第n-1层节点dn-1第n层节点dn=dn-1+1搜索图2023/1/141状态空间间搜索——2.一般图搜搜索策略略（1）搜索术术语2、节点扩扩展应用操作算子子将上一状态态（节点ni）变迁到到下一状态态（节点nj）节点ni称为被扩展节节点（父节点点）节点nj称为ni的子节点节点ni节点nj2023/1/142（1）搜索术术语3、路径节点ni到nj的路径是是由相邻邻节点间间的弧线构成成的折线线要求路径径是无环环的4、路径代代价——相邻节点点ni和ni+1间的路径代价价记为C(ni,ni+1)通常令任意相邻邻节点间间的路径径代价相相同，并以路路径长度度1指示。即C(ni,ni+1)=1。状态空间间搜索——2.一般图搜搜索策略略节点ni节点ni+1节点nj2023/1/143状态态空空间间搜搜索索———2.一般般图图搜搜索索策策略略（1）搜搜索索术术语语4、路路径径代代价价目标标状状态态节节点点ng节点点ni节点点nkC(nk,ng)C(ni,nk)C(ni,ng)2023/1/144状态空空间搜搜索——2.一般图图搜索索策略略（2）一般般图搜搜索算算法符号说说明：：s-初始状状态节节点G-搜索图图OPEN-存放待扩展展节点点的表CLOSE-存放已被扩扩展的的节点点的表MOVE-FIRST(OPEN)-取OPEN表首的的节点点作为当前要要被扩扩展的的节点点n，同时时将节点点n移至CLOSE表一般图图搜索索算法法划分分为二二个阶阶段：：1、初始始化2、搜索索循环环2023/1/145状态空空间搜搜索——2.一般图图搜索索策略略（2）一般般图搜搜索算算法算法划划分为为二个个阶段段：1、初始始化建立只包含含初始始状态态节点点s的搜索索图G:={s}OPEN:={s}CLOSE:={}2、搜索索循环环MOVE-FIRST(OPEN)-取出OPEN表首的的节点点n作为扩扩展的的节点点，同同时将将其移移到close表扩展出出n的子节节点,插入搜索图图G和OPEN表适当的的标记记和修修改指指针排序OPEN表通过循循环地地执行行该算算法，，搜索图图G会因不不断有有新节节点加加入而而逐步步长大大，直直到搜搜索到到目标标节点点。2023/1/146以下面的八数数码为例，看看一般图的搜搜索算法初始布局目标布局移动数码状态空间搜索索——2.一般图搜索策策略2023/1/1472023/1/1482023/1/1492023/1/1502023/1/1512023/1/1522023/1/1532023/1/1542023/1/1552023/1/1562023/1/1572023/1/1582023/1/1592023/1/1602023/1/1612023/1/1622023/1/1632023/1/1642023/1/1652023/1/166状态态空空间间搜搜索索———2.一般般图图搜搜索索策策略略（2）一一般般图图搜搜索索算算法法———搜索索过过程程中中的的指指针针修修改改节点点n扩展展后后的子子节节点点分分为为3类：(i)全新新节节点点(ii)已出出现现在在OPEN表中的的节节点点(iii)已出现的CLOSE表中的节点指针标记和和修改的方方法：(i)类节点：加加入OPEN表，建立从从子节点到到父节点n的指针(ii)类节点、(iii)类节点比较经由老父节点、新父节点n到达初始状态节节点的路径代价经由新父节节点n的代价比较较小，则将将原子节点点指向老父父节点的指指针，修改改为指向新新父节点n(iii)类节点还得得从CLOSE表中移出，，重新加入入OPEN表。2023/1/167状态空间搜搜索——2.一般图搜索索策略Sn4ninjn1n2n3n31n32节点ni是当前扩展展的节点；；扩展出4个后续节点点；n1、n2是新节点，只需建立指指向父节点点的指针，，并加入OPEN表；2023/1/168状态空间搜索索——2.一般图搜索策策略Sn4ninjn1n2n3n31n32n4已经存在于OPEN表，并且已有有父节点njn4经nj的路径代价大大取消n4指向nj的指针改为建立n4指向新父节点点ni的指针n3已经存在于CLOSE表，并且已有有父节点nj需要做和n4同样的比较和和指针修改工工作。并且要要重新加入open表。2023/1/169状态空空间搜搜索——2.一般图图搜索索策略略（2）一般般图搜搜索算算法OPEN表中节节点简简单的的排序序方式式：深度优优先——扩展当当前节节点后后生成成的子子节点点总是是置于OPEN表的前前端，即OPEN表作为栈，后进先先出，使搜索优优先向向纵深深方向向发展展。2023/1/170深度优先实例例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123468911131416181912384765目标571012151720212023/1/171深度度优优先先搜搜索索在深深度度优优先先搜搜索索中中，，首首先先扩扩展展最最新新产产生生的的(最深深的的)节点点，，深深度度相相等等的的节节点点可可以以任任意意排排列列。。“最晚产产生的的节点点最先先扩展展”起始节节点深深度为为0任何其其他节节点的的深度度等于于其父父辈节节点深深度加加上1:dn=dn-1+12023/1/172深度优优先搜搜索很明显显这样样做，，不一定定找到最最佳解解，而而且由由于深深度的的限制制，可可能找找不到到解，，然而而，若若不加加深度度限制制，可可能沿沿着一一条路路线无无限制制地扩扩展下下去，，这当当然是是不允允许的的。为保证证找到到解，，应选选择适适当的的深度界界限，或者者采取取不断断加大大深度度界限限的办办法，，反复复搜索索，直直到找找到解解。这这种改改进的的方法法叫做做迭代加加深搜搜索。2023/1/173ProcedureDepthFirstSearchBegin把初始始节点点压入入栈，，并设设置栈栈顶指指针；；While栈不空空doBegin弹出栈栈顶元元素；；If栈顶元元素=goal，成功功返回回并结结束；；Else以任意意次序序把栈栈顶元元素的的子女女压入入栈中中；EndWhileEnd基于栈栈实现现的深深度优优先搜搜索算算法：：2023/1/174初始节点点放到栈栈中，栈栈指针指指向栈的的最上边边的元素素。为了对该该节点进进行检测测，需要要从栈中中弹出该该节点，，如果是是目标，，该算法法结束，，否则把把其子节节点以任任何顺序序压入栈栈中。该该过程直直到栈变变成为空空。遍历一棵树的的过程（（下图））。2023/1/175深度优先搜索索的性质一般不能保证证找到最优解解当深度限制不不合理时，可能找不到解解，可以将算法法改为可变深度限制制最坏情况时，，搜索空间等等同于穷举是一个通用的的与问题无关关的方法2023/1/176深度优先搜搜索的优点是比宽度优优先搜索算算法需要较较少的空间间，该算法法只需要保保存搜索树树的一部分分，它由当当前正在搜搜索的路径径和该路径径上还没有有完全展开开的节点标标志所组成成。深度优先搜搜索的存储储器要求是是深度约束束的线性函函数。深度优先搜搜索的优点点2023/1/177深度度优优先先搜搜索索的的缺缺点点既不不是是完完备备的的，，也也不不是是最最优优的的。。主要要问问题题是是可可能能搜搜索索到到了了错错误误的的路路径径上上。。很很多多问问题题可可能能具具有有很很深深甚甚至至是是无无限限的的搜搜索索树树，，如如果果不不幸幸选选择择了了一一个个错错误误的的路路径径，，则则深深度度优优先先搜搜索索会会一一直直搜搜索索下下去去，，而而不不会会回回到到正正确确的的路路径径上上。。这这样样一一来来对对于于这这些些问问题题，，深深度度优优先先搜搜索索要要么么陷陷入入无无限限的的循循环环而而不不能能给给出出一一个个答答案案，，要要么么最最后后找找到到一一个个答答案案，，但但路路径径很很长长而而且且不不是是最最优优的的答答案案。。2023/1/178状态空间搜索索——2.一般图搜索策策略（2）一般图搜索索算法OPEN表中节点简单单的排序方式式：深度优先——扩展当前节点点后生成的子子节点总是置于OPEN表的前端，即OPEN表作为栈，后进先出，使搜索优先向纵纵深方向发展展。宽度优先——扩展当前节点点后生成的子子节点总是置于OPEN表的后端，即OPEN表作为队列，先进先出，使搜索优先向横横向方向发展展。2023/1/179宽度优先实例例23184765283147652318476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654910111213141516172023/1/180宽度优优先搜搜索如果搜搜索是是以接接近起起始节节点的的程度度依次次扩展展节点点的，，那么么这种种搜索索就叫叫做宽度优优先搜搜索。。这种搜搜索是是逐层层进行行的，，在对对下一一层的的任意意节点点进行行搜索索之前前，必必须搜搜索完完本层层的所所有节节点。。“先产产生的的节点点先扩扩展””2023/1/181ProcedureBreadth-first-searchBegin把初始始节点点放入入队列列；Repeat取得队队列最最前面面的元元素为为current;Ifcurrent=goal成功返返回并并结束束；ElsedoBegin如果current有子女女，则则current的子女女以任意意次序序添加加到队队列的的尾部部；EndUntil队列为为空End采用队队列结结构，，宽度度优先先算法法可以以表示示如下下：2023/1/182宽度优先搜搜索算法原原理：如果当前的的节点不是是目标节点点，则把当当点节点的的子孙以任任意顺序增增加到队列列的后面，，并把队列列的前端元元素定义为为current。如果目标发发现，则算算法终止。。2023/1/183宽度优先搜搜索的性质质当问题有解解时，一定能找到解当问题为单单位代价时时，且问题题有解时，，一定能找到到最优解方法与问题题无关，具具有通用性性效率较低属于图搜索索方法2023/1/184宽度优先先搜索是一种盲盲目搜索索，时间间和空间间复杂度度都比较较高，当当目标节节点距离离初始节节点较远远时会产产生许多多无用的的节点，，搜索效效率低。。宽度优先先搜索中中，时间间需求是是一个很很大的问问题，特特别是当当搜索的的深度比比较大时时，尤为为严重，，但是空空间需求求是比执执行时间间更严重重的问题题。宽度优先先搜索优优点：目标节点点如果存存在，用用宽度优优先搜索索算法总总可以找找到该目目标节点点，而且且是最小小（即最最短路径径）的节节点。宽度优先先搜索的的优点和和缺点2023/1/185总结适用场场合深度优优先——当一个个问题题有多多个解解答或或多条条解答答路径径，且且只须须找到到其中中一个个时；；往往往应对对搜索索深度度加以以限制制。宽度优优先——确保搜搜索到到最短短的解解答路路径。。共同优优缺点点：可直接接应用用一般般图搜搜索算算法实实现，，不需需要设设计特特别的的节点点排序序方法法，从从而简简单易易行，，适合合于许许多复复杂度度不高高的问问题求求解任任务。。节点排排序的的盲目目性，，由于于不采采用领领域专专门知知识去去指导导排序序，往往往会会在白白白搜搜索了了大量量无关关的状状态节节点后后才碰碰到解解答，，所以以也称称为盲目搜搜索。2023/1/186有界深度搜搜索和迭代代加深搜索索有界深度优优先搜索过程总体上上按深度优优先算法方方法进行，，但对搜索索深度需要要给出一个个深度限制制dm，当深度达达到了dm的时候，如如果还没有有找到解答答，就停止止对该分支支的搜索，，换到另外外一个分支支进行搜索索。2023/1/187策略说明:（1）深度限制dm很重要。当问题有解，，且解的路径径长度小于或或等于dm时，则搜索过过程一定能够够找到解，但但是和深度优优先搜索一样样这并不能保保证最先找到到的是最优解解。但是当dm取得太小，解解的路径长度度大于dm时，则搜索过过程中就找不不到解，即这这时搜索过程程甚至是不完完备的。2023/1/188（2）深度限限制dm不能太太大。当dm太大时时，搜搜索过过程会会产生生过多多的无无用节节点，，既浪浪费了了计算算机资资源，，又降降低了了搜索索效率率。（3）有界界深度度搜索索的主主要问问题是是深度限限制值值dm的选取取。2023/1/189改进方法法：（迭迭代加深深搜索））先任意给给定一个个较小的的数作为为dm，然后按按有界深深度算法法搜索，，若在此此深度限限制内找找到了解解，则算算法结束束；如在在此限制制内没有有找到问问题的解解，则增增大深度度限制dm，继续搜搜索。2023/1/190迭代加深搜索索，试图尝试所所有可能的深深度限制：首先深度为0，然后深度为1，然后为2，等等。如果初始深度度为0，则该算法只只生成根节点点，并检测它它。如果根节点不不是目标，则则深度加1，通过典型的的深度优先算算法，生成深深度为1的树。当深度限制为为m时，树的深度度为m。2023/1/191迭代加深搜索索看起来会很很浪费，因为为很多节点都都可能扩展多多次。然而对于很多多问题，这种种多次的扩展展负担实际上上很小，直觉觉上可以想象象，如果一棵棵树的分支系系数很大，几几乎所有的节节点都在最底底层上，则对对于上面各层层节点扩展多多次对整个系系统来说影响响不是很大。。2023/1/192搜索最优策略略的比较表注：b是分支系数，，d是解答的深度度，m是搜索树的最最大深度，l是深度限制。。2023/1/193宽度优先搜索索、深度优先先搜索和迭代代加深搜索都都可以用于生生成和测试算算法。宽度度优优先先搜搜索索需要要指指数数数数量量的的空空间间，，深深度度优优先先搜搜索索的的空空间间复复杂杂度度和和最最大大搜搜索索深深度度呈呈线线性性关关系系。。2023/1/194迭代加深深搜索对一棵深深度受控控的树采采用深度度优先的的搜索。。它结合合了宽度度优先和和深度优优先搜索索的优点点。和宽度优优先搜索索一样，，它是最最优的，，也是完完备的。。但对空空间要求求和深度度优先搜搜索一样样是适中中的。2023/1/195一般图搜搜索算法法常用的简简单方式式：深度优先先宽度优先先【缺点：节节点排序序的盲目目性】在白白搜索了大大量无关关的状态态节点后才碰到到解答，，效率低提高一般图搜搜索效率的关键优化OPEN表中节点点的排序序方式盲目搜索索3.4启发式搜搜索★2023/1/196125634最理想情情况：每次排序序后OPEN表表首元素素n总在解答答路径上上2023/1/197启发式搜索索启发式知识识指导OPEN表排序的一般图搜索索：全局排序——对OPEN表中的所有节点排排序，使最有希望的节点排在在表首。A算法，A*算法（掌握握！）局部排序——仅对新扩展出来的的子节点排排序，使这些新节点中最有希望者能优先取取出考察和和扩展；爬山法（了了解，对深度优先法法的改进）；2023/1/198启发式搜索索——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，估计的最小路径径代价；2023/1/199启发式搜索索——1.A算法（掌握）Snng目标状态节节点ng初始状态节节点S节点n搜索图Gh(n):n-ng的估计最小小路径代价价g(n):s-n的实际路径径代价f(n):s-n-ng的估计最小路径代代价2023/1/1100启发发式式搜搜索索———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算法?（掌握！！）2023/1/1101启发式式搜索索——1.A算法（（掌握）A算法的设计计与一般图图搜索索相同，，划分分为二二个阶阶段：：1、初始始化建立只只包含含初始始状态态节点点s的搜索索图G:={s}OPEN:={s}CLOSE:={}2、搜索索循环环MOVE-FIRST(OPEN)-取出OPEN表首的节点点n⑥扩展出出n的子节节点,插入搜搜索图图G和OPEN表⑦适当的的标记记和修修改指指针（（子节点点父节节点）⑧排序OPEN表（评价函函数f(n)的值排排序））通过循循环地地执行行该算算法，，搜索索图会会因不不断有有新节节点加加入而而逐步步长大大，直直到搜搜索到到目标标节点点。2023/1/1102启发式搜搜索——1.A算法（掌握）算法A的设计与与一般图图搜索类类似，划划分为二二个阶段段：1、初始化化2、搜索循循环MOVE-FIRST(OPEN)-取出OPEN表首的节节点n⑥扩展出n的子节点点,插入搜索索图G和OPEN表对每个子子节点ni,计算f(n,ni)=g(n,ni)+h(ni)⑦适当的标标记和修修改指针针（子节点父节点点）⑧排序OPEN表（评价函函数f(n)的值排序序）2023/1/1103启发式搜搜索——1.A算法（掌握）⑥扩展出n的子节点点,插入搜索索图G和OPEN表对每个子子节点ni,计算f(n,ni)=g(n,ni)+h(ni)⑦适当的标标记和修修改指针针（子节点父节点点）(i)全新节点点：f(ni)=f(n,ni)(ii)已出现在在OPEN表中的节点点(iii)已出现的的CLOSE表中的节点点IFf(ni)>f(n,ni)THEN修改指针针指向新父结点nf(ni)=f(n,ni)⑧排序OPEN表（f(n)值从小到到大排序序）2023/1/11042.若OPEN表是空表表，则失失败退出出；算法A3.选择择OPEN表上上的的第第一一个个节节点点，，把把它它从从OPEN表移移出出并并放放进进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这条条路路径径而而得得到到的的；；2023/1/11056.对那那些些未未曾曾在在G中出出现现过过的的M成员员（（全全新新节节点点））设设置置一一个个通通向向n的指指针针。。把把M的这这些些成成员员加加进进OPEN表。。对对已已经经在在OPEN表上上的的每每一一个个M成员员，，比较较子子节节点点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(搜索树））。2023/1/1106启发式搜搜索——1.A算法（掌握）A算法实例例——八数码游游戏1)设计评价价函数f(n)f(n)=d(n)+w(n),其中d(n)-节点n在搜索图图中的节点深度度，对g(n)的度量；w(n)-代表启发发式函数数h(n),其值是节节点n与目标状状态节点点ng相比较，，不考虑虑空格，，错位的棋棋牌个数数；初始布局目标布局移动数码2023/1/1107启发式搜搜索——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)不考虑空空格2023/1/1108状态空间搜索索——2.一般图搜索策策略（1）搜索术语1、节点深度根节点指示初始状态，令其深度为为0；搜索图中的其其他节点的深度dn就可以递归地地定义为其父节点深度dn-1加1：dn=dn-1+1。根节点深度=0第n-1层节点dn-1第n层节点dn=dn-1+1搜索图G2023/1/1109启发式搜索——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的最最小小路路径径代代价价044注：：W(S)不考考虑虑空空格格2023/1/1110初始始化化OPEN:={s4}CLOSE:={}2023/1/1111循环1CLOSE:={s4}OPEN:={abc}OPEN:={a6b4c6}OPEN:={b4a6c6}2023/1/1112循环2CLOSE:={s4b4}OPEN:={a6c6dei}OPEN:={a6c6d5e5i6}OPEN:={d5e5a6c6i6}2023/1/1113循环3CLOSE:={s4b4d5}OPEN:={e5a6c6i6jk}OPEN:={e5a6c6i6j7k6}OPEN:={e5a6c6i6k6j7}2023/1/1114循环4CLOSE:={s4,b4,d5,e5}OPEN:={a6c6i6k6j7lm}OPEN:={a6c6i6k6j7l5m7}OPEN:={l5a6c6i6k6j7m7}2023/1/1115CLOSE:={s4,b4,d5,e5,l5}循环5OPEN:={a6c6i6k6j7m7n}OPEN:={a6c6i6k6j7m7n5}OPEN:={n5a6c6i6k6j7m7}2023/1/1116循环6CLOSE:={s4,b4,d5,e5,l5,n5}OPEN:={a6c6i6k6j7m7og}OPEN:={a6c6i6k6j7m7o7g5}OPEN:={g5a6c6i6k6j7m7o7}2023/1/1117循环7成功结结束2023/1/1118最理想想搜索索图G2023/1/1119判断失失误2023/1/1120例2给定4L和3L的水壶壶各一一个，，水壶壶上没没有刻刻度，，可以以向水水壶中中加水水。如何在在4L的壶中中准确确地得得到2L水？（x,y）——4L壶里的的水有有xL，3L壶里的的水有有yL，n表示搜搜索空空间中中的任任一节节点。。则给出出下面面的启启发式式函数数：2023/1/1121h(n)=2如果果0<x<4并且且0<y<3=4如果果0<x<4或者者0<y<3=8如果果x=0并且且y=3或者者x=4并且且y=0=10如果果x=0并且且y=0或者者x=4并且且y=3假定定g(n)表示示搜搜索索树树中中搜搜索索的的深深度度，，则则根根据据图图搜搜索索策策略略得得下下图图的的搜搜索索空空间间。。2023/1/1122水壶壶问问题题的的状状态态空空间间扩扩展展图图在第第0步，，由由节节点点O可以以得得到到g+h=10。在第第1步，，得得到到两两个个节节点点M和N，其其估估价价函函数数值值都都为为1+8=9，因因此此可可以以任任选选一一个个节节点点扩扩展展。。2023/1/1123水壶壶问问题题的的状状态态空空间间扩扩展展图图假定定选选择择了了节节点点M，在在第第2步扩扩展展M得到到了了两两个个后后继继点点P和R，对对于于P有2+4=6，对对于于R有2+10=12。现现在在，，在在节节点点P、R、N中，节节点P具有最最小的的估价价函数数值，，所以以选择择节点点P扩展。。在第3步，可可以得得到节节点S，其中中3+4=7。现在在，在在节点点S、R、N中，节节点S的估价价函数数值最最小，，所以以下一一步就就会选选择S节点扩扩展。。该过过程一一直进进行下下去，，直到到到达达目标标节点点。2023/1/1124启发式式搜索索——2.实现启启发式式搜索索的关关键因因素（（理解解）实现启启发式式搜索索应考考虑的的关键键因素素：（1）搜索索算法法的可采纳纳性(Admissibility);（2）启发式式函数数h(n)的强弱弱及其影影响；；2023/1/1125启发式式搜索索——2.实现启启发式式搜索索的关关键因因素（1）搜索索算法法的可可采纳纳性(Admissibility)1)定义在存在从初始状状态节点到到目标状状态节点解答路路径的情况况下，，若一一个搜搜索法法总能找找到最最短（（代价价最小小）的的解答答路径径，则称称该状态空空间中的搜索算算法具有可可采纳纳性，，也叫叫最优优性。如，宽度优优先的搜索索算法法是可采纳纳的，只是是搜索索效率不不高。2)A算法的的可采采纳性性——定义f*(n)=g*(n)+h*(n)n-搜索图图G中最短解解答路路径的节点点；f*(n)-s经节点点n到ng的最短解解答路路径的路径径代价价；g*(n)-该路径径前段（从s到n）的路路径代代价；；h*(n)-该路径径后段（从n到ng）的路路径代代价；；2023/1/1126启发式式搜索索——2.实现启启发式式搜索索的关关键因因素（1）搜索索算法法的可可采纳纳性(Admissibility)3)评价函函数f与f*的比较较f(n)、g(n)、h(n)分别是是f*(n)、g*(n)、h*(n)的近似值值（估估计值值）理想情情况下下：若g(n)=g*(n)、h(n)=h*(n)，则搜索索过程程中，，每次都都正确确选择择，不扩展展任何何无关关的节节点。实际情情况：：设计接接近f*的f是很困困难的的在算法执执行过程程中，g(n)容易从已已经生成成的搜索索树中计计算出来来Sn搜索图Gng2023/1/1127启发式搜搜索——2.实现启发发式搜索索的关键键因素（1）搜索算算法的可可采纳性性(Admissibility)3)评价函数数f与f*的比价理想情况况下：若g(n)=g*(n)、h(n)=h*(n)，不扩展无无关的节节点实际情况况：设计接近近f*的f是很困难难的在算法执执行过程程中，g(n)容易从已已经生成成的搜索索树中计计算出来来，比如如就以节节点深度度d(n)当做g(n),且有g(n)>=g*(n)h(n