八数码问题求解西安电子科技大学数据结构结课大作业.doc

西安电子科技大学课程论文 数据结构 八数码问题求解 班级：071271 作者：方正阳 学号 时间：2013.12.17 摘要：八数码求解问题是人工智能中一个很典型的智力问题。本文套用经典宽度搜索框架根据宽搜的策略，被搜索到的顶点上的distance标记就是到源顶点的最短路径的距离，因此可以解决无权图的最短路径问题以及由其抽象而来的最优问题。?八数码游戏（八数码问题）描述为：在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格（可以看作是空格移动，它最多可以有４个方向的移动，即上、下、左、右），这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 需求分析 初始状态：8个数字码和空格在3×3棋盘上:1 2 3 8 0 4 7 6 5 2.实现从初始状态到目标状态的转换（如不能实现，程序应输出不能实现的提示信息）； 3.输出结果，每移动一步都必须在屏幕上显示: ａ、移动每一步时的序号，最后一步的序号即为移动总步数； ｂ、每一步移动后以3x3表格形式显示状态。 4.要求能使移动步数尽可能少； 二、程序设计 变量说明： int num[9]; //棋盘状态 int deepth; //派生的深度 g(n) int diffnum; //不在位的数目 h(n) int value; //耗散值 f(n)=g(n)+h(n) int expand(numNode *item); //扩展节点 int chu_shi_zhuang_tai[9]; //棋盘初始状态 int mu_biao_zhuang_tai[9]; //棋盘目标状态 int numNode_num,total_step; numNode *open,*close; //Open表和Close表 函数声明： void print_num(int num[9]); //打印棋盘状态 int print_result(numNode *item); //打印结果 void init(); //初始化，获得棋盘初始状态和目标状态 void swap(int *a,int *b);//交换2个数 void open_insert(numNode *head,numNode *item); //向Open表中按序插入新节点 void close_append(numNode *head,numNode *item); //向Close表中插入新节点 算法分析： 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。宽度优先搜索是一种搜索算法，其主要用来解决最优解问题。原型是图的宽度优先遍历问题，即从源顶点s出发，遍历每一个节点，它的基本思路是：先扩展当前节点所有邻接的节点，然后再从这些顶点出发，遍历所有顶点，即分层处理，将遍历路径表示成树，就是按层次遍历。宽度优先搜索实现要依赖队列，即先进先出表（FIFO），这样保证了搜索的顺序正确。 4.具体步骤： 1.确定问题的规模：对于任一给定可解初始状态，状态空间有9!/2=181440个状态，考虑搜索的时间复杂度，合理选择搜索方式。 2.明确问题的规则：移动空格（上、下、左、右）和周围的任一棋子一次，比较当前状态和目标状态的格局是否一致，重复以上步骤，直到达到目标状态。 3.套用合适的算法：在此采用宽度优先搜索，来解决无权图的最优问题，即找出从初始状态到目标状态所需步骤最短的一系列过程。 4.验证程序结果的正确性。 测试结果 测试结果1： 测试结果2： 结果分析评价：针对两种代表性测试结果正确，但是在按下Enter键输出结果时会清除以前输入的数据，不知该如何调试。 程序评价： 程序中有些地方需改进，编写时出现的问题还很大，算法的描述欠佳。 测试的数据少不能保证程序的完全正确性，不能够用程序验证得到的结果一定是最优的（即从初始状态到目标状态转换的步骤最少）。 宽度优先搜索基本优化解决了八数码问题，不能确定