状态空间搜索策略课件

《状态空间搜索策略课件》由会员分享，可在线阅读，更多相关《状态空间搜索策略课件（53页珍藏版）》请在金锄头文库上搜索。

1、第5章 状态空间搜索策略,Searching,5.1 搜索概述,在解空间中寻找解的过程与策略 搜索问题的产生 （1）结构不良或非结构化的问题，无解析解 （2）理论上可解的问题，计算复杂度可能太高 基本搜索方式 （1）盲目搜索 按预定策略进行搜索，不考虑问题本身的特性 （2）启发式(Heuristic)搜索 利用与问题有关的启发式信息，加快搜索过程,启发式搜索,启发式信息与评价函数 反映问题特性，可用于确定搜索方向的信息 评价函数的作用是根据启发式信息，计算对应于特定搜索方向的评价值，作为选择搜索方向的依据。 局部(local)搜索 vs. 全局(global)搜索 确定搜索方向时考虑局部信息还

2、是全局信息？ 任一解 vs. 最优解,搜索方法,图搜索方法 宽度优先法(breadth-first)，深度优先法(depth-first)，有界深度优先法，启发式最优图搜索法(A*，AO*) 博弈搜索方法 极小极大法(MiniMax)，Alpha-Beta剪枝法 (pruning) 现代优化搜索方法 爬山法(hill climbing)，模拟退火法(simulated annealing)，遗传算法(genetic algorithms).,搜索策略的评价,完备性 如果问题有解，能否保证找到？ 最优性(optimization) 如果问题存在不同的解，能否找到最优解？ 时间复杂性-找到一个解需

3、要花费多少时间 空间复杂性-在搜索过程中需要占用多少内存,时空复杂性的量度,状态空间图的大小 分支因子 b 目标节点的深度 d 路径的最大长度 m 搜索深度限制 l,5.2 问题及其搜索过程的表示,状态空间表示法 通过“状态”表示问题，通过“操作符”求解问题 状态的改变表示了问题求解过程,状态空间,以“状态”和“操作符”为基础 状态： 问题求解过程中任意时刻的状况 操作符：使问题从一个状态变为另一个状态的操作 问题的全部状态(包含初始状态和目标状态)及一切可用操作符所构成的集合称为问题的状态空间。,初始状态,中间状态1,中间状态2,目标状态,状态空间例：二阶梵塔问题,设有三根钢针，它们的编号分

4、别是1号、2号和3号。在初始情况下，l号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。,用 Sk=Sk0， Sk1表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种： SO=(1，l) S1=（1，2） S2=（1，3） S3=(2，1） S4=（2，2） S5=（2，3） S6=(3，1） S7=（3，2） S8=（3，3）,操作符：A(i,j)表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第i号钢针移

5、到j号钢针上。共有12种操作，分别是： A(1，3) A(2，1) A(2，3) A(3，1) A(3，2) B(1，3) B(2，1) B(2，3) B(3，1) B(3，2),(1,1),(2,1),(2,3),(3,3),(1,3),(1,2),(2,2),(3,2),(3,1),A(1,3),B(1,2),A(3,2),根据状态和操作符，可构成二阶梵塔问题的状态图,最短路径解,八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局

6、。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。,5.3 一般图搜索算法,无论是状态空间，还是与或图的问题表示，问题求解过程都可看作是在“图”中进行搜索。 基本思想 不存储全部搜索图，而是逐步展开问题求解所需的搜索子图 具体方法 从初始状态开始，不断扩展当前节点，即生成子节点，直到目标状态出现在这些子节点中，或者没有可供扩展的节点为止。,数据结构,Open表（未扩展节点表） 存放未进行过扩展的节点 Closed表（已扩展节点表） 存放已经扩展过的节点,Open表：,Closed表：,算法步骤,St

7、ep1 把初始节点S0放入 Open表，建立仅包含S0的图 G； Step2 从Open表中取出待扩展节点，放入Closed表； （不同搜索策略的区别主要体现于此） Step3 对节点进行扩展，将扩展得到的、未在G中出现过的子节点放入Open表；根据需要修改G中节点的指针； Step4 重复Step2-3直到 状态空间：待扩展节点为目标节点或Open表为空,盲目搜索策略,广度（宽度）优先搜索 先生成的节点先扩展 深度优先搜索 后生成的节点先扩展 有界深度优先搜索 在深度优先策略中增加深度限制，在广度优先与深度优先之间折衷,完备,最小路径解,效率,盲目搜索例（状态空间）: 八数码难题,在 3*3

8、 的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0和目标状态Sg分别如图所示。可以使用的操作有： 空格左移，空格上移，空格右移，空格下移 寻找从初始状态到目标状态的解路径。,广度优先搜索算法如下： (1)把初始结点放入Open表中； (2)如果Open表为空，则问题无解，失败退出； (3)把Open表的第一个结点取出，放入Closed表，并记该结点为n； (4)扩展节点n，如果没有后继节点，则转向第(2)步； (5)把n的所有后继结点放入Open表的末尾，并提供从这些后继结点回到父结点(编号值为n)的指针; (6)如果刚产生的这些后继结点中存在一个目标结点，

9、则找到一个解。解可从目标结点开始直到初始结点的返回指针中得到，算法成功退出。否则转(2)继续。,S,L,O,M,F,P,Q,N,F,F,F,起始结点,起始,把S0放入Open表,Open表 是否为空,失败,把第1个结点n，从Open表 移出并把它放入Closed表中,扩展n,把它的后继结点放入 Open表的末端,提供回到n的 指针,是否有 任何后继结点为目标 结点？,成 功,否,是,否,是,示意图,算法框图,Sg,解的路径是： S0 3 8 16 26(Sg),八数码难题的广度优先搜索,广度优先搜索是一种完备策略，即只要问题有解,它就一定可以找到解。并且广度优先搜索找到的解，还一定是路径最短的

10、解。 深度优先搜索 深度优先搜索是一种后生成的结点先扩展的策略。其搜索过程是：从初始结点S0开始，在其子结点中选择一个最新生成的结点进行考察，如果该子结点不是目标结点且可以扩展，则扩展该子结点，依此向下搜索，直到某个子结点既不是目标结点，又不能继续扩展时，才选择其兄弟结点进行考察。图示如下：,S0,1,2,3,7,6,8,4,5,9,起始结点,起始,把S0放入Open表,S0是否为 目标结点,是否Open 为空表,把Open表中的第一个结 点n移入Closed表,结点n 的深度是否等于深度 界限,扩展结点n，把其后代放入 Open表的前端,是否有 任何后继结点为目标 结点,成功,失败,成功,是

11、,否,是,是,是,否,否,否,示意图,算法框图,深度优先搜索算法如下： (1)把初始结点S0放入Open表中； (2)如果Open表空，则问题无解，失败退出； (3)把Open表的第一个结点取出放入Close表，并记该结点为n; (4)考察结点n是否为目标结点，若是，则得到问题的解，成功退出； (5) 若结点n不可扩展，则转(2)； (6)扩展结点n，将其子结点放入Open表的首部，并为每一个子结点设置指向父结点的指针，然后转(2)。,八数码难题的深度优先搜索,从深度优先搜索的算法可以看出,搜索一旦进入某个分支，就将沿这个分支一直进行下去，如果目标恰好在这个分支上,则它可以很快找到解.但是,如

12、果目标不在这个分支上，且分支是一个无穷分支，则搜索过程就不可能找到解。因此，深度优先搜索是一种不完备策略，即使问题有解，它也不一定能够找到解。,解路径为: So：l 11 12 13 14：Sg,Sg,八数码难题的有界深度优先搜索,2 8 3 4 7 6 5,S0,1,2 8 3 1 4 7 6 5,2,2 3 8 4 7 6 5,11,2 8 3 4 7 6 5,2 8 3 6 4 7 5,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,2 3 8 4 7 6 5,2 3 8 4 7 6 5,2 8 4 3 7 6 5,2 8 3 4 5 7 6,2 8 3 6 4 7 5,

13、2 8 3 6 4 7 5,3,7,13,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,1 2 3 8 4 7 6 5,2 3 4 8 7 6 5,2 8 4 3 7 6 5,2 8 3 4 5 7 6,2 8 3 6 4 1 7 5,2 8 3 6 7 5 4,4,8,8 3 2 1 4 7 6 5,8 1 3 2 4 7 6 5,5,6,2 8 3 7 4 6 1 5,2 8 3 7 1 4 6 5,9,10,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,14,12,深度限制为4,上面讨论的搜索方法都没有用到问题本身的特性信息，只是按事先设定的线路进行搜

14、索，具有较大的盲目性。事实上，如果能利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是非常有益的。这种利用问题自身的特性来引导搜索过程，提高搜索效率的搜索策略称为启发式搜索或有信息搜索。 启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数而作用于搜索过程的。,5.4启发式搜索,启发式算法 利用问题的特殊性，选择待扩展的节点，以缩小搜索范围，提高搜索速度。 启发信息 可指导搜索过程，且与具体问题求解过程有关的控制性信息。一般有以下三种： 帮助确定扩展节点的信息； 帮助决定哪些后继节点应被生成的信息； 在扩展一个节点时决定哪些节点应被删除的信息,估价函数

15、f(n)：用于估计节点代价的函数 定义为从初始节点S0出发，经过节点n约束后，到达目标节点Sg的所有路径中最优路径的代价估计值。 一般形式为 f(n)=g(n)h(n) g(n)是从初始节点S0到节点n的实际代价。可以从节点n反向跟踪到初始节点S0,得到一条当前最小代价路径，把这条路径上所有有向边的代价相加，就得到g(n)的值。 ； h(n)是从节点n到目标节点S0的最优路径的估计代价。需要根据问题自身的特性来确定，体现了问题自身的启发性信息，因此也称为启发函数。,估价函数例：,f(n) = d(n) + W(n),节点n在搜索树中的深度,n中“不在位”的数码个数,f(S0) = ?,= 0 + 3 = 3,根据搜索过程中选择扩展节点的范围，分为全局择优搜索和局部择优搜索。 1. 全局择优 在Open表的所有节点中选择一个估价函数值最小的节点进行扩展 2. 局部择优 在刚生成的子节点中选择一个估价函数值最小的节点进行扩展。,局部最佳优先搜索算法,对OPEN表中所有节点的f(n)进行比较，按从小到大的顺序重排OPEN表。 其算法效率类似于纵向搜索算法，但使用了与问题特性相关的估价函数来确定