《第3章-搜索策略 丁世飞》由会员分享，可在线阅读，更多相关《第3章-搜索策略 丁世飞（217页珍藏版）》请在金锄头文库上搜索。
1、2017/8/5,1,第3章 搜索策略,问题求解系统划分为两大类知识贫乏系统 依靠搜索技术解决问题 知识贫乏、缺乏针对性效率低 知识丰富系统 依靠推理技术解决问题基于丰富知识的推理技术，直截了当 效率高,2017/8/5,2,3.1 引言,对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。基于给定的问题，问题求解的第一步是目标的表示。搜索就是找到智能系统的动作序列的过程。,2017/8/5,3,和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。,在人工智能中，搜索问题一般包括两个重要的问题：,搜索什么搜索什么
2、通常指的就是目标。在哪里搜索在哪里搜索就是“搜索空间”。搜索空间通常是指一系列状态的汇集，因此称为状态空间。,2017/8/5,4,所以，人工智能中的搜索可以分成两个阶段：状态空间的生成阶段在该状态空间中对所求问题状态的搜索,搜索可以根据是否使用启发式信息分为盲目搜索启发式搜索,2017/8/5,5,盲目搜索 只是可以区分出哪个是目标状态。 一般是按预定的搜索策略进行搜索。 没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。,启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。,2017/8/5
3、,6,根据问题的表示方式分为状态空间搜索与或树搜索,状态空间搜索是用状态空间法来求解问题所进行的搜索,与/或树搜索是指用问题规约方法来求解问题时所进行的搜索。,2017/8/5,7,考虑一个问题的状态空间为一棵树的形式。宽度优先搜索深度优先搜索,如果根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。,在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索。,2017/8/5,8,无论是宽度优先搜索还是深度优先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固
4、定了。这种类型的遍历称为“确定性”的，也就是盲目搜索。对于启发式搜索，在计算每个节点的参数之前无法确定先选择哪个节点扩展，这种搜索一般也称为非确定的。,2017/8/5,9,完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？,搜索策略评价标准:,2017/8/5,10,有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、机器人行动规划等）都可以归结为状态空间搜索。,用状态空间搜索来求解问题的系统均定义一个状态空间，
5、并通过适当的搜索算法在状态空间中搜索解答路径。,3.2 基于状态空间的搜索技术,2017/8/5,11,3.2.1 图搜索的基本概念,显式图与隐式图 显式图把问题有关的全部状态空间图，即相应的全部有关知识(叙述性知识、过程性知识和控制性知识)，都直接存入知识库 隐式图只存储与问题求解有关的部分知识(即部分状态空间)。这种存储方式称为隐式存储。,2017/8/5,12,图搜索的基本思想 图搜索-一种在图中寻找路径的方法 从图中的初始节点开始，至目标节点为止。初始节点和目标节点分别代表产生式系统的初始数据库和满足终止条件的数据库。方法：把问题的初始状态作为当前状态，选择适用的算符对其进行操作，生成
6、一组子状态，检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。,2017/8/5,13,3.2.2状态空间搜索1.什么是状态空间图,例：钱币翻转问题 设有3个钱币，其初始状态为(反、正、反),欲得的目标状态为(正、正、正)或(反、反、反)。问题是允许每次只能且必须翻转一个钱币，连翻三次。问能否达到目标状态。 引入一个三维变量将问题表示出来。设三维变量为：Q=q1,q2,q3，式中qi (i=1,2,3)=0表示钱币为正面，qi (i=1,2,3)
7、=1表示钱币为反面。三个钱币可能出现的状态有8种组合： Q0=(0,0,0),Q1=(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)。,2017/8/5,14,三枚钱币问题的状态空间图,2017/8/5,15,3.2.2状态空间搜索2.问题的状态空间表示法,(1)状态空间的表示状态空间记为SP，可表示为二元组：SP=(S,O)S问题求解（即搜索）过程中所有可能到达的合法状态构成的集合；O操作算子的集合，操作算子的执行会导致问题状态的变迁 ；状态用于记载问题求解（即搜索）过程中某一时刻问题现状的
8、快照；抽象为矢量形式 Q=q0,q1,qnT每个元素qi称为状态分量 给定每个状态分量qi的值就得到一个具体的状态 Qk=q0k,q1k,qnkT,2017/8/5,16,状态,表示状态的变迁,操作算子,问题的状态空间是一个表示该问题的全部可能状态及其变迁的有向图。,节点状态有向弧状态的变迁 弧上的标签导致状态变迁的操作算子,用状态空间搜索来求解问题的系统均定义一个状态空间，并通过适当的搜索算法在状态空间中搜索解答路径。,2017/8/5,17,3.2.2状态空间搜索2.问题的状态空间表示法,(2)状态空间表示的经典例子“传教士和野人问题”问题的描述：N个传教士带领N个野人划船过河；3个安全约
9、束条件：1)船上人数不得超过载重限量，设为K个人； 2)任何时刻（包括两岸、船上）野人数目不得超过传教士； 3)允许在河的某一岸或者在船上只有野人而没有传教士；,2017/8/5,18,3.2.2状态空间搜索2.问题的状态空间表示法,(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 (右岸没有传道士，左岸一定安全);,2017/8/5
10、,19,设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，问题状态以（m,c,b）表示。,问题的求解任务可描述为：(3,3,1) (0,0,0)该简单问题可能到达的合法状态：可能状态总数：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个,2017/8/5,20,3.2.2状态
11、空间搜索2.问题的状态空间表示法,(2)状态空间表示的经典例子“传教士和野人问题”定义2类操作算子：L(x,y)指示从左岸到右岸的划船操作 R(x,y)指示从右岸到左岸的划船操作x + y K=2(船的载重限制)；x和y取值的可能组合只有5个10，20，11，01，02 ( 允许在船上只有野人而没有传教士 )共有10个操作算子,2017/8/5,21,渡河问题的状态空间有向图,2017/8/5,22,3.2.2状态空间搜索 3.状态空间搜索的基本思想,由此例可以看出用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。另外，还要定义一组操作，通
12、过使用这些操作可把问题由一种状态转变为另一种状态。 问题的求解过程是一个不断把操作作用于状态的过程。如果在使用某个操作后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用操作构成的序列。,2017/8/5,23,3.2.2状态空间搜索 3.状态空间搜索的基本思想,由此例可以看出要使问题由一种状态转变到另一种状态时，就必须使用一次操作。这样，在从初始状态转变到目标状态时，就可能存在多个操作序列(即得到多个解)。那么，其中使用操作最少或较少的解才为最优解(因为只有在使用操作时所付出的代价为最小的解才是最优解)。 对其中的某一个状态，可能存在多个操作使该状态变到几个不同的
13、后继状态那么到底用哪个操作进行搜索呢?这就有赖于搜索策略了不同的搜索策略有不同的顺序，这就是本章后面要讨论的问题。,2017/8/5,24,例:在一个33的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称为八数码问题。,初始棋局,目标棋局,2017/8/5,25,2 31 8 47 6 5,2017/8/5,26,3.2.3 一般图的搜索算法,或图（一般图）一个状态可以有多个可供选择的操作算子；操作算子间的选择是一种“
14、或”的关系;这样的有向图称为或图。,2017/8/5,27,或图（一般图）一个状态可以有多个可供选择的操作算子；操作算子间的选择是一种“或”的关系，这样的有向图称为或图。状态空间一般都表示为或图（一般图）搜索图在搜索解答路径的过程中画出搜索时涉及到的节点和弧线，构成所谓的搜索图。,状态空间搜索,一般图搜索,2017/8/5,28,一般图搜索算法符号说明：s-初始状态节点G-搜索图OPEN-存放待扩展节点的表CLOSE-存放已被扩展的节点的表MOVE-FIRST(OPEN)-取OPEN表首的节点作为当前要被扩展的节点n，同时将节点n移至CLOSE表一般图搜索算法划分为二个阶段：1、初始化 2、搜
15、索循环,2017/8/5,29,一般图搜索算法算法划分为二个阶段：1、初始化 建立只包含初始状态节点s的搜索图G:=sOPEN:=sCLOSE:= 2、搜索循环MOVE-FIRST(OPEN)-取出OPEN表首的节点n作为扩展的节点，同时将其移到close表 扩展出n的子节点,插入搜索图G和OPEN表 适当的标记和修改指针排序OPEN表通过循环地执行该算法，搜索图G会因不断有新节点加入而逐步长大，直到搜索到目标节点。,2017/8/5,30,以下面的八数码为例，看一般图的搜索算法,初始布局,目标布局,2017/8/5,31,2017/8/5,32,2017/8/5,33,2017/8/5,34
16、,2017/8/5,35,2017/8/5,36,2017/8/5,37,2017/8/5,38,2017/8/5,39,2017/8/5,40,2017/8/5,41,2017/8/5,42,2017/8/5,43,2017/8/5,44,2017/8/5,45,2017/8/5,46,2017/8/5,47,2017/8/5,48,2017/8/5,49,2017/8/5,50,一般图搜索算法搜索过程中的指针修改节点n扩展后的子节点分为3类：(i)全新节点(ii)已出现在OPEN表中的节点(iii)已出现在CLOSE表中的节点指针标记和修改的方法：(i)类节点：加入OPEN表，建立从子节点到父节点n的指针(ii)类节点、 (iii)类节点比较经由老父节点、新父节点n到达初始状态节点的路径代价 经由节点n的代价比较小，则移动子节点指向老父节点的指针，改为指向新父节点n (iii)类节点还得从CLOSE表中移出，重新加入OPEN表。,
