八数码问题算法文献综述

1、八数码问题算法文献综述报告摘要：随着计算机和网络的大范围普及，电脑游戏也普遍存在于人们的生活 中，但是大部分的人都只是看重游戏的娱乐价值（启发思维，培养观察能力、耐 心等），而不在乎其本质，比如说它有着什么样的数据结构，它的核心算法是什 么等等这些问题。本文就目前一个很经典的算法问题一一八数码问题来分析其核 心的算法，并且借助前人得出的研究，进一步分析和设计算法。关键词：八数码；拼图游戏；广度优先搜索；深度优先搜索；A*搜索1引言从古至今，“游戏”这个词对于人们来说都不陌生，从古代的斗禽，蹴鞠等 到现在的一系列的电脑游戏。尤其是如今的电脑游戏，不胜其数，种类繁多，不 亦乐乎，拼图游戏就是其中的

2、一种。所谓的拼图游戏就是把一副完整的图片通过 规则的或者不规则的切割后打乱成零片，玩家只需把零片拼凑回原形即可。在这 个过程中，要发生无数次的状态改变，在电脑上也如此。不同的是，电脑上的拼 图游戏需要一个“看不见”的存储空间来存储这一个个不同的状态。这就必须涉 及到数据的存贮方式。尤其是算法，它是拼图游戏的核心，它决定了计算机怎样 解决这个问题，同时还影响着这个游戏程序的存储方式。但是，并不是一个能玩 的游戏都具有理想的算法和数据结构。因此，对一个游戏的算法进行分析优化并 设计出一个理想的算法显得更加重要。此拼图游戏是建立在一个3*3的方格棋 盘上，把棋盘上的打散的八块图片分别用数字1-8标识

3、，棋盘上空的那块标识为 0，那么拼图游戏就可以转化成我们算法中极为极为经典的八数码问题。2八数码问题的研究现状2.1八数码问题的概念八数码问题也称为九宫问题。在3X3的棋盘，摆有八个棋子，每个棋子上 标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与 空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个 目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所 谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改 变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间 过渡状态。2.2八数码问题的状态空间法表

4、示2.2.1状态描述八数码问题的一个状态就是八个数字在棋盘上的一种放法。每个棋子用它上 面所标的数字表示，并用0表示空格，这样就可以将棋盘上棋子的一个状态存储 在一个一维数组p9中，存储的顺序是从左上角开始，自左至右，从上到下。把标识的八块图片抽象成一个数字序列，构成一个数组，表示其摆放的位置。例如:假设初始状态为：218 ，目标状态为:6 518732 0465，那么此八数码问题就可以转换为从开始系列为2,8,3,1,0,6,7,4,5向目标系列为1,2,3,8,0,4,7,6,5 转化的 问题。也可以用一个二维数组来存放。2.3八数码问题的搜索算法2.3.1深度优先搜索耿国华在研究中指出了

5、深度优先搜索（Depth_First Search，DFS）的概念： 是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。它 的算法思想中有递归算法：首先访问出发点A，然后依次以A的未被访问的邻 接点为出发点，深度优先搜索图，直至图中所有与A有路径相同的顶点都被访 问。若是非连通图，那么图中一定还会有未被访问的顶点，则需要从图中另选一 个还未被访问过得顶点作为起始点，重复上述搜索过程，直到图中所有顶点都被 访问过为止。除了递归算法外，还用邻接表作为存储结构实现深度优先搜索，其 查找邻接点的时间复杂度为O（e），其中e是无向图中的边数或有向图中的弧数， 则深度优先搜索图的时间复杂度

6、为O（n+e）。用深度优先搜索求解八数码问题的搜索过程：（1） 把起始节点S放到未扩展节点的OPEN表（此时OPEN表是一个堆 栈，后进先出）中。如果此节点为一目标节点，则得到解。（2）如果OPEN为一空表则无解，失败退出。（3）把第一个节点（记作节点n ）从OPEN表移到CLOSED表。（4）如果节点n的深度等于最大深度则转向第二步。（5）扩展节点n产生其全部后继节点并把它们放入OPEN表的前头。如果 没有后继节点则转向第二步。（6）如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪 从目标节点到起始节点的路径），成功退出；否则，转向第二步。2.3.2广度优先搜索广度优先搜索和深度

7、优先搜索的基本思路相同。与深度优先搜寻对应，耿国华还提出广度优先搜索（Breadth_First Search， BFS）的概念：是指按照广度方向搜索，它类似于树的层次遍历，是树的层次遍 历的推广。其基本的思想是：从图中某个顶点B出发，首先访问B；依次访问 B的各个未被访问的邻接点。最后，分别从这些邻接点（端结点）出发，依次访 问它们的各个未被访问的邻接点（新的端结点）。注意，访问时应保证：如果Bi 和Bk为当前的端结点，且在Bi和Bk之前被访问，则耳的所有未被访问的邻接 点应在Bk的所有未被访问的邻接点之前访问。再重复此步骤，直到所有的端结 点均没有未被访问的邻接点为止。若此时还有顶点未被访

8、问，则选一个未被访问 的顶点作为起始点，重复上述过程，直到所有的顶点均被访问过为止。深度优先搜索的过程：把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解)。如果OPEN是个空表，则无解，失败退出；否则继续下一步。把第一个节点(记作节点n )从OPEN表移出并把它放入CLOSED的已扩展点表中。扩展节点n如果没有后继节点，则转向第2步。把n的所有后继节点放到OPEN表的末端并提供从这些后继节点回到n的指针。如果n的任一个后继节点是个目标节点，则找到一个解(反向追踪得到从目标节点到起始节点的路径)，成功退出，否则转第3步。2.3.3 A*搜索吕国英研究者还提出了启发式搜索的概念：考

9、虑问题给定的特有的性质，选 用合适的规则，提高搜索的效率。这正是需要探索的方向。算法技术手册 提到的A*搜索就是一种启发式搜索，在搜索时能够利用启发式信息，智能地调 整搜索策略。其实，A*搜索也是一种迭代有序的搜索，它维护一个棋面状态的 开放集合。以下是算法技术手册中所讲的A*搜索的具体描述：在每次迭代时，A*搜索使用一个评价函数f*(n)评价开放集合中的所有棋 面状态，选择最小的棋面状态。定义f*(n)=g*(n)+h*(n):g*(n)估算从初始状态到状态n的最短走法序列。h*(n)估算从状态n到目标状态的最短走法序列。f*(n)估算从初始状态开始，经过状态n，到达目标状态的最短走法序列。

10、星号*表示使用了启发式信息(自从1968年开发出此算法后，这个记法就被 广泛接受)，因此f*(n)，g*(n)以及h*(n)是对实际开销f(n)，g(n)以及h(n)的估 算，而这些实际开销只能在得到解后才能够知道。简而言之，就是f*(n)越低， 表示状态n越接近目标状态。f*(n)最关键的部分是启发式的计算h*(n)，因为g*(n)能够在搜索的过程中， 通过记录状态n的深度计算出来，如果h*(n)不能准确地区分开有继续搜索价值 的状态和没有价值的状态，那么A*搜索不会表现得比上述任何盲目搜索要好。 如果能准确地估算h*(n)，那么使用f*(n)就能够得到一个开销最小的解。以下是A*搜索过程：

11、把初始节点A0放入Open表，计算f(A0)。如果Open表为空，则问题无解，退出。把Open表首个节点(即节点n)取出放入Closed表。 判断节点n是否是目标节点，如果是，则求得问题的解，退出。若节点n不可扩展，则转第2步。扩展节点n，用估价函数f( x)计算每个子节点的估价值，并为每个子 节点配置指向父节点的指针，将其子节点放入Open表中，对Open表 中的全部节点按估价值从小到大进行排序。然后转第2步。2.3.4结果比较初始状态 33,6,4,7,0.5目标状态门4,7,6,5扩展节点生成节点解的步敷有效分枝因子A*P(rrM51161.491 3A，不在位61361.533 41深

12、度优先(Q1。)473787101.948 04深度优先(20)54489 S01161.767 6宽度优先203461.799 89图1结果比较Fig.1 Comparison】7】3.总结综上，从图一和图二已经研究出来的结果可以看到，用深度优先搜索、广度(2 8 3)(12 3 )优先搜索和A*搜索解的步数，从初始状态为7 0 4到目标状态为8 0 416 5 J7 6 5)的扩展节点、生成节点以及解的步数等的比较，对比出了 A*算法的优势：在搜 索时，虽然也需要保存一些状态，但在每次扩展时，它有启发的选择了有希望的 节点进行扩展，因此大大的缩小了搜索的空间，能够较快的找到问题的解。这是

13、深度优先搜索和广度优先搜索不能达到的。深度优先搜索虽然有时候会较快的 找到解，但是如果没有利用回溯作为辅助，得到的解可能不是最优的，而且如果 对其他进行搜索深度限制的话，往往会得不到解；广度优先搜索先搜索则能够保 证找到最优解，但是由于需要保存大量的状态而使得空间复杂度非常的大，很容 易出现“组合爆炸”问题。参考文献1周浩.八数码问题DNF和BNF算法的设计与实现J.电脑知识与技术，2011,7 （22）:5487-5489. 耿国华.数据结构一一C语言描述M.北京：清华大学出版社，2009.2, 212-216.吕国英.算法设计与分析M.北京：高等教育出版社,2005,7.180-190.G

14、eorge T. Heineman,Gary Pollice,Stanley Selkow 杨晨，李明（译）.算法技术手 册M.北京：机械工业出版社，2010.3,185-208.乔宏敬.求解八数码问题的几种搜索算法比较J.福建电脑，2007,8:50-51.欧阳林艳.八数码问题的搜索算法比较J.洛阳师范学院学报，2011,30（8）： 69-71.詹志辉，胡晓敏，张军.通过八数码问题比较搜索算法的性能J.计算机工程 与设计，2007,28（11）： 2505-2508张鸿.人工智能中求解八数码问题算法的实现与分析J.软件导刊，2009,8（6）： 63-64.陶阳.VS2008环境下八数码问

15、题的BFS算法设计与实现J.电脑知识与技术 2009,5（26）:7417-7419.A.V.Aho,J.E.Hopcroft,J.D.Ullman,The Design and Analysis of Computer Algorithms,Addison Wesley,Reading,Mass.,1974.Eight Digital Algorithm for the ProblemAbstract： With the computer and network wide range of only valued the entertainment value popular computer games are also common in peoples lives, but most people are of the game（inspired thinking, to develop observation, patience, etc.）, but not with its nature, for example,what data it has a structure, it is the core algorithm and so these problems. This is a c