多种方法解决八数码难题(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,#,八数码难题,汇报时间：,2018,年,10,月 汇报人：马玥,PPT,制作者：何帅帅 代码编辑调试者：尹迅、马玥,1,2025/4/9 周三,目,录,CONT,ENTS,01,问题重述,Problem Retelling,02,问题分析,Problem Analysis,03,宽度优先,Width First,04,深度优先,Depth First,0,启发式搜索,Heuristic Search,2,2025/4/9 周三,问题重述,Problem Retelling,1,八数码问题描述,33,九宫棋盘，放置数码为,1-8,的,8,个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。,要求：根据给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局，找到合法的走步序列。,八数码难题（,8-puzzle problem,）,1,2,3,8,4,7,6,5,2,8,3,1,6,4,7,5,（初始状态）,（目标状态）,4,2025/4/9 周三,宽度优先,Width First,宽度优先搜索算法解决八数码难题,它是从根节点（起始节点）开始，按层进行搜索，也就是按层来扩展节点。所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。,这种搜索方式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到目标节点的最短路径的解，但它的缺点是往往搜索过程很长。,2,3,1,8,4,7,6,5,s,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,3,1,8,4,7,6,5,1,2,3,4,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,4,7,6,5,5,6,7,1,2,3,8,4,7,6,5,2,3,4,1,8,7,6,5,9,8,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,4,5,7,6,2,8,1,4,3,7,6,5,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,1,2,3,7,8,4,6,5,1,2,3,8,4,7,6,5,10,11,12,13,14,15,16,17,目标,从图中得，解的路径是,S-3-8-17,宽度优先搜索,1,2,3,8,4,7,6,5,（目标状态）,7,2025/4/9 周三,宽度优先搜索算法代码演示,宽度优先搜索的性质,当问题有解时，一定能找到解,当问题为单位耗散值，且问题有解时，一定能找到最优解,方法与问题无关，具有通用性,效率较低,属于图搜索方法,9,2025/4/9 周三,深度优先,Depth First,深度优先搜索算法解决八数码难题,它是从根节点开始首先扩展最新产生的节点，即沿着搜索树的深度发展下去，一直到没有后继结点处时再返回，换一条路径走下去。就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。,由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。为了避免这种情况的出现，在实施这一方法时，定出一个深度界限，在搜索达到这一深度界限而且尚未找到目标时，即返回重找，所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解（最短路径）。,11,2025/4/9 周三,深度优先搜索算法解决八数码难题,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,4,7,6,5,1,2,3,8,4,7,6,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,6,4,1,7,5,1,2,3,7,8,4,6,5,1,2,3,8,4,7,6,5,目标,1,2,3,4,1,2,3,8,4,7,6,5,（目标状态）,12,2025/4/9 周三,2,31,8,4,7,6,5,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,4,7,6,5,1,2,3,8,4,7,6,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,2,8,1,4,3,7,6,5,2,8,3,1,4,5,7,6,1,2,3,7,8,4,6,5,1,2,3,8,4,7,6,5,目标,2,8,3,6,4,1,7,5,2,8,3,1,6,7,5,4,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,2,8,1,4,3,7,6,5,2,8,3,1,4,5,7,6,设深度界限,dm=4,1,2,12,3,6,9,13,4,5,7,8,10,11,1,2,3,8,4,7,6,5,（目标状态）,深度优先搜索算法代码演示,深度优先搜索的性质,一般不能保证找到最优解,当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制,最坏情况时，搜索空间等同于穷举,与回溯法的差别：图搜索,是一个通用的与问题无关的方法,15,2025/4/9 周三,启发式搜索,Heuristic Search,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,算法）,17,2025/4/9 周三,开始,把,S,放入,OPEN,表，计算估价函数,f,（,s,）,OPEN,表为空？,选取,OPEN,表中,f,值最小的节点,i,放入,CLOSE,表,否,i,为目标节点吗,扩展,i,，得后继结点,j,，计算,f,（,j,），提供返回节点,i,的指针，利用,f,（,j,）对,OPEN,表重新排序，调整亲子关系及指针,失败,是,失败,是,否,有序搜索算法框图,18,2025/4/9 周三,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,6,4,7,5,初始,S(4),1,A(6),B(4),C(6),2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,1,2,3,8,4,7,6,5,(,目标状态,),D(5),E(5),F(6),8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,2,3,1,8,4,7,6,5,2,3,1,8,4,7,6,5,G(6),H(7),I(5),J(7),1,2,3,8,4,7,6,5,K(5),1,2,3,8,4,7,6,5,1,2,3,7,8,4,6,5,L(5),M(7),目标,2,3,4,5,6,7,八数码难题的有序搜索树,黑色数字表示不在位的将牌数,19,2025/4/9 周三,启发式搜索算法解决八数码难题,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*,算法。,20,2025/4/9 周三,开始,读入棋局初始状态,是否可解？,在表中找到评价值最小的节点，作为当前节点,是目标节点,初始状态加入,OPEN,表,扩展新状态，把不重复的新状态加入表中,当前节点从表移除,输出结果,结束,否,是,否,是,算法框图,21,2025/4/9 周三,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,6,4,7,5,初始,S,1,A,B,C,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,1,2,3,8,4,7,6,5,(,目标状态,),D,E,F,2,3,1,8,4,7,6,5,2,3,1,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,7,8,4,6,5,目标,2,（）（）的搜索树,，,，,，,，,，,，,黑色数字表示不在位的将牌数,h*-,从节点,n,到目标节点,g,的最短路径耗散值。,g*-,从初始节点,s,到节点,n,的最短路径耗散值。,W,不在位将牌数之和。,P,每个不在位将牌移动到目标状态相应位置所需走步的总和。,22,2025/4/9 周三,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),24,2025/4/9 周三,谢谢观赏,25,2025/4/9 周三,