八数码问题DFS和BFS算法的设计与实现.doc

八数码问题DFS和BFS算法的设计与实现 　　摘要：针对八数码问题，使用宽度优先和深度优先算法进行求解，并对两种算法的求解过程以及结果进行了分析，比较了两种算法的优缺点。 　　关键词：八数码；DFS；BFS 　　中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)22-5487-03 　　Eight Digital Questions of DFS and BFS Algorithm Design and Implementation 　　ZHOU Hao 　　(Computer College, Nanjing Normal University, Nanjing 210046, China) 　　Abstract: Eight digital questions, use the BFS and DFS algorithm to solve, and two kindsof algorithms for solving process and the results of analysis, comparative advantages and disadvantages of the two algorithms. 　　Key words: Eight digital; DFS; BFS 　　所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。 　　解决八数码问题的算法很多，盲目是搜索算法如深度优先搜索、宽度优先搜索，启发式搜索如A*算法等。 　　1 八数码游戏问题的状态空间法表示 　　1.1 状态描述 　　我们在八数码问题中，将号码牌摆放的位置抽象成一个序列，用来记录不同码值的号码牌的摆放位置。 　　若用0来表示空格，则 　　将初始状态为：，目标状态为：的八数码问题转换为从开始序列：[2,8,3,1,0,4,7,6,5] 转换到目标序列 [1,2,3,8,0,4,7,6,5] 的问题。 　　1.2 操作符描述 　　对于八数码问题中空格的移动问题，我们建立以下操作符: 　　左移：1；上移：2；下移：3；右移：4 　　建立下列状态转换： 　　空格右移了一步，所以用4来表示。 　　1.3 状态空间法的数据结构 　　struct Node 　　{ 　　public: 　　int path[2];//path[0] is the line of the closed box path[1] is the direction of 　　//the father node move to this node 　　int layer;//layer is the deep nums of the node in the whole graph 　　string seq; // using the string to achieve the sequence 　　}; 　　其中string seq 记录数码位置，path[2]以及int layer。path[0]表示这个结点记录是closed表当中的第几个记录，path[1] 是本记录结点的父结点。Layer表示在已搜索的树当中是第几层。 　　空格移动规则如表1所示。 　　2 八数码游戏问题的盲目搜索技术 　　2.1 宽度优先搜索 　　2.1.1 宽度优先搜索的搜索步骤 　　① 把起始节点放到 OPEN 表中(如果该起始节点为一目标节点，则得到解) 　　② 如果 OPEN 是个空表，则无解，失败退出；否则继续下一步 　　③ 把第一个节点(记作节点 n )从 OPEN 表移出，并把它放入 CLOSED 的已扩展节点表中 　　④ 扩展节点 n 。如果没有后继节点，则转向第②步 　　⑤ 把 n 的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到 n 的指针 　　⑥ 如果 n 的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第②步 　　2.1.2 宽度优先的成员数据结构 　　string InitialString,ResultString; 　　初始序列以及结果序列 　　OPEN表：SeqQueue ws_open 　　(特别说明，这里的SeqQueue 是我自己实现的队列模板，因为想试下有没有用，就放到程序里试了一下) 　　存放待扩展的节点，从数据结构上来说，它是一个先进先出的队列 　　CL