状态空间搜索策略课件84181.pptx

《状态空间搜索策略课件84181.pptx》由会员分享，可在线阅读，更多相关《状态空间搜索策略课件84181.pptx（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、和3号。在初始情况下，l号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。l 用 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）1 2 3BABABA1 2 3S0=(1,1)S4=(2,2)S8=(3,3)二阶梵塔问题的初始与目标状态l 操作符：A(i,j)

5、表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第i号钢针移到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)l 根据状态和操作符，可构成二阶梵塔问题的状态图最短路径解l 八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样

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

7、点 编号 节点 父节点Open表：Closed表：算法步骤Step1把初始节点S0放入 Open表，建立仅包含S0的图 G；Step2从Open表中取出待扩展节点，放入Closed表；（不同搜索策略的区别主要体现于此）Step3对节点进行扩展，将扩展得到的、未在G中出现过的子节点放入Open表；根据需要修改G中节点的指针；Step4重复Step2-3直到 状态空间：待扩展节点为目标节点或Open表为空盲目搜索策略l 广度（宽度）优先搜索 先生成的节点先扩展l 深度优先搜索 后生成的节点先扩展l 有界深度优先搜索 在深度优先策略中增加深度限制，在广度优先与深度优先之间折衷完备最小路径解效率2 8 31 47 6 5S01 2 38 47 6 5Sg盲目搜索例（状态空间）:八数码难题在 3*3 的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0和目标状态Sg分别如图所示。可以使用的操作有：空格左移，空格上移，空格右移，空格下移寻找从初始状态到目标状态的解路径。