多种方法解决八数码难题.ppt

八数码难题 汇报时间 2018年10月汇报人 马玥 PPT制作者 何帅帅代码编辑调试者 尹迅 马玥 目录 CONTENTS 问题重述ProblemRetelling 1 八数码问题描述 3 3九宫棋盘 放置数码为1 8的8个棋牌 剩下一个空格 只能通过棋牌向空格的移动来改变棋盘的布局 要求 根据给定初始布局 即初始状态 和目标布局 即目标状态 如何移动棋牌才能从初始布局到达目标布局 找到合法的走步序列 八数码难题 8 puzzleproblem 初始状态 目标状态 宽度优先WidthFirst 宽度优先搜索算法解决八数码难题 它是从根节点 起始节点 开始 按层进行搜索 也就是按层来扩展节点 所谓按层扩展 就是前一层的节点扩展完毕后才进行下一层节点的扩展 直到得到目标节点为止 这种搜索方式的优点是 只要存在有任何解答的话 它能保证最终找到由起始节点到目标节点的最短路径的解 但它的缺点是往往搜索过程很长 s 1 2 3 4 5 6 7 9 8 10 11 12 13 14 15 16 17 目标 从图中得 解的路径是S 3 8 17 宽度优先搜索 目标状态 宽度优先搜索算法代码演示 宽度优先搜索的性质 当问题有解时 一定能找到解当问题为单位耗散值 且问题有解时 一定能找到最优解方法与问题无关 具有通用性效率较低属于图搜索方法 深度优先DepthFirst 深度优先搜索算法解决八数码难题 它是从根节点开始 首先扩展最新产生的节点 即沿着搜索树的深度发展下去 一直到没有后继结点处时再返回 换一条路径走下去 就是在搜索树的每一层始终先只扩展一个子节点 不断地向纵深前进直到不能再前进 到达叶子节点或受到深度限制 时 才从当前节点返回到上一级节点 沿另一方向又继续前进 这种方法的搜索树是从树根开始一枝一枝逐渐形成的 由于一个有解的问题树可能含有无穷分枝 深度优先搜索如果误入无穷分枝 即深度无限 则不可能找到目标节点 为了避免这种情况的出现 在实施这一方法时 定出一个深度界限 在搜索达到这一深度界限而且尚未找到目标时 即返回重找 所以 深度优先搜索策略是不完备的 另外 应用此策略得到的解不一定是最佳解 最短路径 深度优先搜索算法解决八数码难题 目标 1 2 3 4 目标状态 目标 设深度界限dm 4 1 2 12 3 6 9 13 4 5 7 8 10 11 目标状态 深度优先搜索算法代码演示 深度优先搜索的性质 一般不能保证找到最优解当深度限制不合理时 可能找不到解 可以将算法改为可变深度限制最坏情况时 搜索空间等同于穷举与回溯法的差别 图搜索是一个通用的与问题无关的方法 启发式搜索HeuristicSearch 4 启发式搜索算法解决八数码难题 评价函数 f n g n h n 其中n是被评价的节点 g n 表示从初始节点s到节点n的最短路径的耗散值 h n 表示从节点n到目标节点g的最短路径的耗散值 f n g n h n 表示从初始节点s经过节点n到目标节点g的最短路径的耗散值 而f n g n 和h n 则分别表示是对f n g n 和h n 三个函数值的估计值 是一种预测 A算法就是利用这种预测 来达到有效搜索的目的 它每次按照f n 值的大小对OPEN表中的元素进行排序 f值小的节点放在前面 而f值的大的节点则被放在OPEN表的后面 这样每次扩展节点时 总是选择当前f值最小的节点来优先扩展 有序搜索 A算法 有序搜索算法框图 初始 S 4 1 A 6 B 4 C 6 目标状态 D 5 E 5 F 6 G 6 H 7 I 5 J 7 K 5 L 5 M 7 目标 2 3 4 5 6 7 八数码难题的有序搜索树 黑色数字表示不在位的将牌数 启发式搜索算法解决八数码难题 A 搜索算法 在图搜索过程中 如果第8步的重排OPEN表是依据f n g n h n 进行的 则称该过程为A算法 在A算法中 如果对所有的n存在h n h n 则称h n 为h n 的下界 它表示某种偏于保守的估计 采用h n 的下界h n 为启发函数的A算法 称为A 算法 当h 0时 A 算法就变为有序搜索算法 在A算法中 如果满足条件 1 g n 是对g n 的估计 且g n 0 2 h n 是h n 的下界 即对任意节点n均有0 h n h n 则A算法称为A 算法 算法框图 初始 S 1 A B C 目标状态 D E F 目标 2 的搜索树 黑色数字表示不在位的将牌数 h 从节点n到目标节点g的最短路径耗散值 g 从初始节点s到节点n的最短路径耗散值 W 不在位将牌数之和 P 每个不在位将牌移动到目标状态相应位置所需走步的总和 A 搜索算法代码演示 在八数码难题中 令估价函数f n d n p n 启发函数h n p n p n 为不在位的棋子与其目标位置的距离之和 则有p n h n 满足A 算法的限制条件 w n 表示不在位的棋子数 不够贴切 错误选用节点加以扩展 更接近于h n 的h n 其值是节点n与目标状态节点相比较 每个错位棋子在假设不受阻拦的情况下 移动到目标状态相应位置所需走步的总和 n 比w n 更接近于h n 因为p n 不仅考虑了错位因素 还考虑了错位的距离 移动次数 说明h值越大 启发功能越强 搜索效率越高 特别地 1 h n h n 搜索仅沿最佳路径进行 效率最高 2 h n 0无启发信息 盲目搜索 效率低 3 h n h n 谢谢观赏