3第三章搜索策略

2019/9/81第3章搜索策略问题求解系统划分为两大类知识贫乏系统依靠搜索技术解决问题知识贫乏、缺乏针对性效率低知识丰富系统依靠推理技术解决问题基于丰富知识的推理技术，直截了当效率高2019/9/82第3章搜索策略两大类搜索技术:1、一般图搜索、启发式搜索2、基于问题归约的与或图搜索两种典型的推理技术:1、基于归结的演绎推理归结反演2、基于规则的演绎推理正向演绎推理逆向演绎推理2019/9/833.1引言对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。基于给定的问题，问题求解的第一步是目标的表示。搜索就是找到智能系统的动作序列的过程。2019/9/84搜索算法的输入是给定的问题，输出是表示为动作序列的方案。一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）因此，求解问题包括：目标表示搜索执行2019/9/85（1）初始状态集合：定义了初始的环境。（2）操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。（3）目标检测函数：用来确定一个状态是不是目标。（4）路径费用函数：对每条路径赋予一定费用的函数。其中，初始状态集合和操作符集合定义了问题的搜索空间。一般给定问题就是确定该问题的一些基本信息，一个问题由4部分组成:2019/9/86和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。在人工智能中，搜索问题一般包括两个重要的问题：搜索什么搜索什么通常指的就是目标。在哪里搜索在哪里搜索就是“搜索空间”。搜索空间通常是指一系列状态的汇集，因此称为状态空间。2019/9/87所以，人工智能中的搜索可以分成两个阶段：状态空间的生成阶段在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分为盲目搜索启发式搜索2019/9/88盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。2019/9/89根据问题的表示方式分为状态空间搜索与或图搜索状态空间搜索是用状态空间法来求解问题所进行的搜索与/或图搜索是指用问题规约方法来求解问题时所进行的搜索。2019/9/810考虑一个问题的状态空间为一棵树的形式。宽度优先搜索深度优先搜索如果根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索。2019/9/811无论是宽度优先搜索还是深度优先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为“确定性”的，也就是盲目搜索。对于启发式搜索，在计算每个节点的参数之前无法确定先选择哪个节点扩展，这种搜索一般也称为非确定的。2019/9/812完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？搜索策略评价标准:2019/9/813有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、机器人行动规划等）都可以归结为状态空间搜索。用状态空间搜索来求解问题的系统均定义一个状态空间，并通过适当的搜索算法在状态空间中搜索解答路径。3.2基于状态空间图的搜索技术2019/9/814状态空间搜索——1.状态空间及其搜索的表示(1)状态空间的表示状态空间记为SP，可表示为二元组：SP=(S,O)S——问题求解（即搜索）过程中所有可能到达的合法状态构成的集合；O——操作算子的集合，操作算子的执行会导致问题状态的变迁；状态——用于记载问题求解（即搜索）过程中某一时刻问题现状的快照；抽象为矢量形式Q=[q0,q1,…,qn]T每个元素qi称为状态分量给定每个状态分量qi的值就得到一个具体的状态Qk=[q0k,q1k,…,qnk]T2019/9/815状态表示状态的变迁操作算子问题的状态空间是一个表示该问题的全部可能状态及其变迁的有向图。节点状态有向弧状态的变迁弧上的标签导致状态变迁的操作算子用状态空间搜索来求解问题的系统均定义一个状态空间，并通过适当的搜索算法在状态空间中搜索解答路径。2019/9/816例1：走迷宫是人们熟悉的一种游戏。状态空间搜索S1S2S3S4S5S6S7S8S9S0Sg2019/9/817S1S2S3S4S5S6S7S8S9S0Sg格子、入口和出口——节点——状态通道——有向弧——操作算子迷宫可以由一个有向图表示S1S2S3S4S5S6S7S8S9S0Sg2019/9/818例2:在一个3×3的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称为八数码问题。56741382初始棋局56748321目标棋局移动数码2019/9/819231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123847652019/9/8202019/9/821状态空间搜索——1.状态空间及其搜索的表示(2)状态空间表示的经典例子“传教士和野人问题”问题的描述：N个传教士带领N个野人划船过河；3个安全约束条件：1)船上人数不得超过载重限量，设为K个人；2)任何时刻（包括两岸、船上）野人数目不得超过传教士；3)允许在河的某一岸或者在船上只有野人而没有传教士；2019/9/822状态空间搜索——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(右岸没有传道士，左岸一定安全);2019/9/823设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，问题状态以（m,c,b）表示。问题的求解任务可描述为：(3,3,1)→(0,0,0)该简单问题可能到达的合法状态：可能状态总数：4×4×2=32根据条件得出合法状态：20m≧c且N-m≧N-c(左岸安全且右岸安全)m=1,c=1；m=2,c=2m=0且0≤c≤N(左岸没有传道士)m=0,c=0,1,2,3N-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个2019/9/824状态空间搜索——1.状态空间及其搜索的表示(2)状态空间表示的经典例子“传教士和野人问题”定义2类操作算子：L(x,y)——指示从左岸到右岸的划船操作R(x,y)——指示从右岸到左岸的划船操作x+y≤K=2(船的载重限制)；x和y取值的可能组合只有5个10，20，11，01，02(允许在船上只有野人而没有传教士)共有10个操作算子2019/9/825渡河问题的状态空间有向图2019/9/826状态空间搜索——1.状态空间及其搜索的表示由此例可以看出用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。另外，还要定义一组操作，通过使用这些操作可把问题由一种状态转变为另一种状态。问题的求解过程是一个不断把操作作用于状态的过程。如果在使用某个操作后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用操作构成的序列。2019/9/827状态空间搜索——1.状态空间及其搜索的表示由此例可以看出要使问题由一种状态转变到另一种状态时，就必须使用一次操作。这样，在从初始状态转变到目标状态时，就可能存在多个操作序列(即得到多个解)。那么，其中使用操作最少或较少的解才为最优解(因为只有在使用操作时所付出的代价为最小的解才是最优解)。对其中的某一个状态，可能存在多个操作．使该状态变到几个不同的后继状态．那么到底用哪个操作进行搜索呢?这就有赖于搜索策略了．不同的搜索策略有不同的顺序，这就是本章后面要讨论的问题。2019/9/828课堂练习有一农夫带一只狐狸、一只小羊和一篮菜过河（从左岸到右岸）。假设船太小，农夫每次只能带一样东西过河；考虑到安全，无农夫看管时，狐狸和小羊不能在一起，小羊和那篮菜也不能在一起。请为该问题的解决设计状态空间，并画出状态空间图。2019/9/829解析以变量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个操作步.思考：为什么不把船的状态放到状态空间中去？2019/9/830解析:四元组(m、f、s、v)2019/9/831状态空间搜索——1.状态空间及其搜索的表示(3)状态空间的搜索状态空间的搜索记为SE，可表示为五元组：SE=(S,O,E,I,G)；E——搜索引擎；I——问题的初始状态，I∈S；G——问题的目标状态集合，GS。搜索引擎E——可以设计为实现任何搜索算法的控制系统。基本思想——通过搜索引擎E寻找一个操作算子的调用序列，使问题从初始状态I变迁到目标状态G之一。解答路径——初-目变迁过程中的状态序列或相应的操作算子调用序列。2019/9/832状态空间搜索——1.状态空间及其搜索的表示或图（一般图）一个状态可以有多个可供选择的操作算子；操作算子间的选择是一种“或”的关系;这样的有向图称为或图。2019/9/833状态空间搜索——1.状态空间及其搜索的表示(3)状态空间的搜索或图（一般图）一个状态可以有多个可供选择的操作算子；操作算子间的选择是一种“或”的关系，这样的有向图称为或图。状态空间一般都表示为或图（一般图）搜索图——在搜索解答路径的过程中画出搜索时涉及到的节点和弧线，构成所谓的搜索图。状态空间搜索一般图搜索2019/9/834状态空间搜索——1.状态空间及其搜索的表示(3)状态空间的搜索状态空间、搜索图和解答路径之间的关系S0Sg2019/9/835状态空间搜索——1.状态空间及其搜索的表示(4)一般图搜索例子——八数码游戏求解的问题：给定初始布局(