第五章状态空间搜索策略ppt课件

1、第五章 形状空间搜索战略S0Sg问题全形状空间问题的搜索空间解途径 主要内容：形状空间的搜索问题5.1 搜索的概念及种类5.2 盲目搜索5.3 启发式搜索5.1 搜索的概念及种类搜索的概念：找到从初始现实到问题最终答案的一条推理道路，找到的这条道路是时间和空间复杂度最小的求解道路搜索种类：“盲目搜索 ，即系统根据事先确定好的某种固定排序依次或随机调用规那么。“启发式搜索，即思索问题领域可运用的知识，根据详细情况动态地确定规那么的排序，优先调用较适宜的规那么运用。搜索例子：回溯搜索算法BACKTRACKDATADATA：当前形状。前往值： 胜利：前往从当前形状到目的形状的途径以规那么表的方式表示

2、 失败：前往FAIL。四皇后问题皇后问题 在一个4*4的国际象棋棋盘上，一次一个地摆布四枚棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击。四皇后问题续 综合数据库：DATA=L(表，L的元素属于ij，1i,j4。DATA非空，其表元素表示棋子所在的行和列 规那么集：if 1 i 4 且在i-1行上有一个皇后 then 在第ij位置放上皇后。搜索战略 固定次序：R11, R12, R13, , R21, R22,R44( )( )Q(1,1)( )QQ(1,1)(1,1) (2,3)( )Q(1,1)(1,1) (2,3)( )QQ(1,1)(1,1) (2,3)

3、(1,1) (2,4)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4)

4、(3.2)Q(1,2)Q(1,2) (2,4)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)Q(1,2) (2,4) (3,1) (4,3)5.1 搜索的概念及种类5.2 盲目搜索5.3 启发式搜索5.2.1 形状空间图的普通搜索算法5.2.2 宽度优先搜索战略5.2.3 深度优先搜索战略5.2.4 代价树的宽度

5、优先搜索战略5.2.5 代价树的深度优先搜索战略5.2 盲目搜索战略5.2.1 形状空间图的普通搜索算法形状空间表示法：用来表示问题及其搜索过程的一种方法。(P62)主要构成：1形状，描画问题求解过程中不同时辰情况的数据构造；2算符：使问题由一个形状变为另一个形状的操作。3形状空间：一个问题的全部形状及一切可用算符构成的集合。普通包括3部分初始形状集合S，算符集合F，目的形状集合G4问题的求解：从S出发经过一系列的算符运算，到达目的形状。由初始形状到目的形状所用算符的序列构成了问题的一个求解形状空间图： 把形状空间的问题求解过程用图的方式表示出来。 节点代表形状，弧代表算符5.2.1 形状空间

6、图的普通搜索算法几个概念：扩展：用适宜的算符对某个节点进展操作，生成一组后继节点，扩展过程就是求后继节点的过程。已扩展节点：曾经求出了其后继节点的节点。未扩展节点：尚未求出后继节点的节点。OPEN表：存放未扩展的节点，记录当前节点及其父节点。CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。图2.26的节点1，1能生成两个后继节点2，13，1形状空间的普通搜索算法普通搜索算法的描画：建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中建立CLOSED表，且置为空表判别OPEN表能否为空表，假设为空，那么问题无解，退出选择OPEN表中的第一个节点，把它从OPEN表移出，并放入

7、CLOSED表中，将此节点记为节点n调查节点n能否为目的节点，假设是，那么问题有解，胜利退出。问题的解就是沿着n到S0的途径得到。假设不是转扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点参与图G中对未在G中出现过的OPEN和CLOSED表中未出现过的集合M中的节点，设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定能否需求修正指向父节点的指针；对于已在G中出现过并已在closed表中的M中的节点，确定能否需求修正通向他们后继节点的指针。按某一恣意方式或某种战略重排OPEN表中节点的顺序转特例图的一些概念

8、：1节点深度： 根节点深度=0，其它节点深度=父节点深度+12途径 设一节点序列为(n0, n1,nk)，对于i=1,k，假设节点ni-1具有一个后继节点ni，那么该序列称为从n0到nk的途径。3途径的耗费值一条途径的耗费值等于衔接这条途径各节点间一切耗费值的总和。用C(ni, nj)表示从ni到nj的途径的耗费值。0123节点类型阐明.mkmjmln扩展点n，产生mk：没在OPEN和CLOSED表中出现过mj：在OPEN表中出现过ml：在CLOSED表中出现过S123645将要扩展节点6S126453修正4节点的前往指针S126453将要扩展节点1S12645修正2和4的前往指针5.2 无信

9、息图搜索过程盲目搜索战略5.2.2 宽度优先搜索5.2.3 深度优先搜索5.2.4 代价树的宽度优先5.2.5 代价树的深度优先1、定义假设搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。2、特点这种搜索是逐层进展的；在对下一层的任一节点进展搜索之前，必需搜索完本层的一切节点。5.2.2 宽度优先搜索战略3、宽度优先搜索算法(1) 把起始节点放到OPEN表中(假设该起始节点为一目的节点，那么求得一个解答)。(2) 假设OPEN是个空表，那么没有解，失败退出；否那么继续。(3) 把第一个节点(节点n)从OPEN表移出，并把它放

10、入CLOSED的扩展节点表中。 (4) 扩展节点n。假设没有后继节点，那么转向上述第(2)步。 (5) 把n的一切后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。 (6) 假设n的任一个后继节点是个目的节点，那么找到一个解答，胜利退出；否那么转向第(2)步。例：把宽度优先搜索运用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目的棋局的问题： 1 2 3 8 4 7 6 55.2.2 宽度优先搜索战略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

11、 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 54宽度优先搜索的性质当问题有解时，一定能找到解。当问题为单位耗费值，且问题有解时，一定能找到最优解。算法与问题无关，具有通用性。时间效率和空间效率都比较低。1、定义 在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以恣意陈列。 这种盲目(无信息)搜索叫做深度优先搜索(dep

12、th-first search)。2、特点 首先，扩展最深的节点的结果使得搜索沿着形状空间某条单一的途径从起始节点向下进展下去；只需当搜索到达一个没有后裔的形状时，它才思索另一条替代的途径。3、深度界限 为了防止思索太长的途径(防止搜索过程沿着无益的途径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点假设到达了深度界限，那么都将把它们作为没有后继节点处置。 5.2.3 深度优先搜索战略3、深度优先搜索算法(1) 把起始节点放到OPEN表中(假设该起始节点为一目的节点，那么求得一个解答)。(2) 假设OPEN是个空表，那么没有解，失败退出；否那么继续。(3) 把第一个节点(节点n)从OP

13、EN表移出，并把它放入CLOSED的扩展节点表中。 (4) 调查节点n能否为目的节点，假设是，那么找到问题的解，用回溯法求解途径，退出 5假设没有后继节点，那么转向上述第(2)步。 (6) 扩展节点n，把n的一切后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第(2)步。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

14、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 6123456789101112131 2 3 8 47 6 5目的深度优先搜索的性质普通不能保证找到最优解。当深度限制不合理时，能够找不到解。最坏情况时，搜索空间等同于穷举。1、定义 形状空间图中各节点之间有向边的代价是不同的，有向边上标有代价的搜索树成为代价搜索树。2、特点 每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。3、C(

15、i,j):从节点i到其后继节点j的连线代价； gx:从初始节点到恣意节点x的途径代价； g(j)=g(i)+C(i,j).5.2.4 代价树的宽度优先搜索4、代价树的宽度优先搜索算法(1) 把起始节点放到OPEN表中，令g(S0)=0。(2) 假设OPEN是个空表，那么没有解，失败退出；否那么继续。(3) 把OPEN表中代价最小的节点即排在最前端的节点n，移入CLOSED的扩展节点表中。 (4) 假设n是目的节点，问题得解，退出。否那么继续。 (5) 判别节点n能否可扩展。假设否那么转向第(2)步，假设是那么转向(6)。 (6) 对节点n进展扩展，将他们的一切后继节点放到OPEN表中，并对每个

16、后继节点j计算其总代价g(j)=g(j)+C(i,j),为每个后继节点指向n节点的指针，然后根据节点的代价大小对OPEN表中的一切节点进展从小到大的排序。 (7) 转向第(2)步。例子：推销员游览问题P193ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n父节点A66BA71175CDABACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E道路：A-C-E代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表进展扩

17、展或判别。代价树的深度优先搜索从刚刚扩展的节点的后继节点中选择一个代价最小的节点移入CLOSED表中，并进展扩展或判别。5.2.5 代价树的深度优先搜索4、代价树的深度优先搜索算法(1) 把起始节点放到OPEN表中，令g(S0)=0。(2) 假设OPEN是个空表，那么没有解，失败退出；否那么继续。(3) 把OPEN表中的第一个节点代价最小的节点n，移入CLOSED表。 (4) 假设n是目的节点，问题得解，退出。否那么继续。 (5) 判别节点n能否可扩展。假设否那么转向第(2)步，假设是那么转向(6)。 (6) 对节点n进展扩展，并将其后继节点按有向边代价C(i,j)从小到大排序后放到OPEN表

18、前端，并为每个后继节点设置指向n节点的指针。 (7) 转向第(2)步。ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n父节点A66BA71175CDABACBDE768765gC节点n父节点A66BA71117187578CDECABDD节点扩展顺序：A，B，C，D，E道路：A-B-D-EACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E道路：A-C-E5.1 搜索的概念及种类5.2 盲目搜索5.3 启发式搜索5.3.1 启发信息与估价函数5.

19、3.2 最正确优先搜索5.3.3 A*搜索算法5.3 启发式图搜索 5.3.1启发信息与估价函数定义利用与问题有关的知识即：启发信息来引导搜索，到达减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索方法。中心问题：启发信息运用，启发才干度量和如何获得启发信息。启发信息的强度强：降低搜索任务量，但能够导致找不到最优解。弱：普通导致任务量加大，极限情况下变为盲目搜索，但能够可以找到最优解。希望：引入启发知识，在保证找到最正确解的前提下，尽能够减少搜索范围，提高搜索效率。搜索算法的效果：可以用启发才干的强弱来度量。思索解途径的耗费值和求得途径所需搜索的耗费值两者的某种组合最小。思索搜索方法对求解一

20、切能够遇见的问题，其平均的组合耗费最小。问题的关键如何寻觅最有希望的节点 启发搜索过程中，要对OPEN表进展排序，这就需求有一种方法来计算待扩展节点有希望通向目的节点的不同程度。 我们总希望能找到最有希望通向目的节点的待扩展节点优先扩展。根本思想定义一个估价函数fEvaluation Function，对当前的搜索形状进展评价，找出一个“最有希望的节点来扩展。估价函数的格式：f(n) = g(n) + h(n)f(n)：估价函数g(n)：代价函数， 初始节点到节点n已实践付出的代价 h(n)：启发函数， 从节点n到目的节点的最优途径的估计代价5.3.2 最正确优先搜索部分最正确优先搜索全局最正

21、确优先搜索部分最正确优先搜索：(1) 把起始节点放到OPEN表中，并计算估价函数f(S0)。(2) 假设OPEN是个空表，那么没有解，失败退出；否那么继续。(3) 把OPEN表中的第一个节点股价函数最小的节点n，移入CLOSED表。(4) 假设n是目的节点，问题得解，退出。否那么继续。(5) 判别节点n能否可扩展。假设否那么转向第(2)步，假设是那么转向(6)。(6) 对节点n进展扩展，并对其一切后继节点计算估价函数fn的值，并按其值从小到大排序后放到OPEN表前端，并为每个后继节点设置指向n节点的指针。(7) 转向第(2)步。全局最正确优先搜索：(1) 把起始节点放到OPEN表中，并计算估价

22、函数f(S0)。(2) 假设OPEN是个空表，那么没有解，失败退出；否那么继续。(3) 把OPEN表中的第一个节点股价函数最小的节点n，移入CLOSED表。(4) 假设n是目的节点，问题得解，退出。否那么继续。(5) 判别节点n能否可扩展。假设否那么转向第(2)步，假设是那么转向(6)。(6) 对节点n进展扩展，并对其一切后继节点计算估价函数fn的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价函数值从小到大的顺序排序。(7) 转向第(2)步。例子定义评价函数：f(n) = g(n) + h(n)= d(n)+h(n)；d(n)：代表节点的深度，表示从初始节点到当前节点的耗费值；h(n)：为当前节点“不在位的牌数。2 8 31 6 47 51 2 38 47 6 5h计算举例h(n) =4 2 8 31 6 47 51 2 3457 6 82 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 3