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

八数码难题汇报时间：2018年10月 汇报人：马玥PPT制作者：何帅帅 代码编辑调试者：尹迅、马玥目 录CONTENTS01问题重述 Problem Retelling02问题分析 Problem Analysis03宽度优先 Width First04深度优先 Depth First0启发式搜索 Heuristic Search问题重述Problem Retelling1八数码问题描述 33九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。要求：根据给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局，找到合法的走步序列。八数码难题（8-puzzle problem）1238476528316475（初始状态）（目标状态）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去宽度优先Width First宽度优先搜索算法解决八数码难题 它是从根节点（起始节点）开始，按层进行搜索，也就是按层来扩展节点。所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。这种搜索方式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到目标节点的最短路径的解，但它的缺点是往往搜索过程很长。231 8 47 6 5s2 8 3147 6 52 31 8 47 6 52 31 8 47 6 512342 8 31 6 4752 8 31 47 6 52 8 31 47 6 55671 2 38 47 6 52 3 41 87 6 5982 8 31 6 47 52 8 31 6 47 52 8 31 4 57 62 81 4 37 6 58 32 1 47 6 52 8 37 1 46 51 2 37 8 46 51 2 3847 6 51011121314151617目标从图中得，解的路径是S-3-8-17宽度优先搜索1 2 3847 6 5（目标状态）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去宽度优先搜索算法代码演示火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去宽度优先搜索的性质 当问题有解时，一定能找到解 当问题为单位耗散值，且问题有解时，一定能找到最优解 方法与问题无关，具有通用性 效率较低 属于图搜索方法火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去深度优先Depth First火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去深度优先搜索算法解决八数码难题 它是从根节点开始，首先扩展最新产生的节点，即沿着搜索树的深度发展下去，一直到没有后继结点处时再返回，换一条路径走下去。就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。为了避免这种情况的出现，在实施这一方法时，定出一个深度界限，在搜索达到这一深度界限而且尚未找到目标时，即返回重找，所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解（最短路径）。深度优先搜索算法解决八数码难题231 8 47 6 52 8 3147 6 52 31 8 47 6 52 31 8 47 6 52 8 31 6 4752 8 31 47 6 52 8 31 47 6 51 2 38 47 6 52 8 31 6 47 52 8 31 6 47 52 8 36 41 7 51 2 37 8 46 51 2 3847 6 5目标123412384765（目标状态）231 8 47 6 52 8 3147 6 52 31 8 47 6 52 31 8 47 6 52 8 31 6 4752 8 31 47 6 52 8 31 47 6 51 2 38 47 6 52 8 31 6 47 52 8 31 6 47 58 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 37 8 46 51 2 3847 6 5目标2 8 36 41 7 52 8 31 67 5 4832 1 47 6 52 8 37 1 465281 4 37 6 52 8 31 4 576设深度界限dm=4121236913457810111 2 3847 6 5（目标状态）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去深度优先搜索算法代码演示火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去深度优先搜索的性质 一般不能保证找到最优解 当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制 最坏情况时，搜索空间等同于穷举 与回溯法的差别：图搜索 是一个通用的与问题无关的方法火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去启发式搜索Heuristic Search4启发式搜索算法解决八数码难题 评价函数：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放入OPEN表，计算估价函数f（s）OPEN表为空？选取OPEN表中f值最小的节点i放入CLOSE表否i为目标节点吗扩展i，得后继结点j，计算f（j），提供返回节点i的指针，利用f（j）对OPEN表重新排序，调整亲子关系及指针失败是失败是否有序搜索算法框图2 8 31 6 4752 8 31 6 47 52 8 3147 6 52 8 31 6 47 5初始S(4)1A(6)B(4)C(6)2 8 31 47 6 5231 8 47 6 52 8 31 47 6 51 2 3847 6 5(目标状态)D(5)E(5)F(6)8 32 1 47 6 52 8 37 1 46 52 31 8 47 6 52 31 8 47 6 5G(6)H(7)I(5)J(7)1 2 38 47 6 5K(5)1 2 3847 6 51 2 37 8 46 5L(5)M(7)目标234567八数码难题的有序搜索树黑色数字表示不在位的将牌数启发式搜索算法解决八数码难题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均有0h(n)h*(n)，则A算法称为A*算法。开始读入棋局初始状态是否可解？在表中找到评价值最小的节点，作为当前节点是目标节点初始状态加入OPEN表扩展新状态，把不重复的新状态加入表中当前节点从表移除输出结果结束否是否是算法框图2 8 31 6 4752 8 31 6 47 52 8 3147 6 52 8 31 6 47 5初始S1ABC2 8 31 47 6 5231 8 47 6 52 8 31 47 6 51 2 3847 6 5(目标状态)DEF2 31 8 47 6 52 31 8 47 6 51 2 38 47 6 51 2 3847 6 51 2 37 8 46 5目标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)谢谢观赏