1、西安电子科技大学课程论文 数据结构 八数码问题的求解 班级： 作者： 学号： 时间： 1 摘要 八数码问题也称为九宫问题 ，在 3 3 的棋盘，摆 有八个棋子，每个棋子上标有 1 至 8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以 0 标记），与空格相邻的棋子可以移到空格中。给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有 4 个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目
2、标状态。 一般用搜索法来解决：广度优先搜索法、深度优先搜索法、 A*算法等，本 文用全局择优来解决该问题。 引言 八数码问题是人工智能中一个很典型的智力问题。 一般用搜索法来解决：广度优先搜索法、 深度优先搜索法、 A*算法等。搜索就是按照一定规则扩展已知结点，直到找到目标结点或所有结点都不能扩展为止，广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举 。由于八数码问题状态空间共有 9!个状态，对于八数码问题如果选定了初始状态和目标状态，有
3、 9!/2 个状态要搜索，考虑到时间和空间的限制，在这里采用 A*算法作为搜索策略 。 A*是一种静态路网中求解最短路径最有效的方法，公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点 n 到目标点的估价函数 ， g(n) 是在状态空间中从初始节点到 n 节点的实际代价 ， h(n) 是从 n 到目标节点最佳路径的估计代价 ，保证找到 最短路径 （最优解的）条件，关键在于估价函数 h(n)的 选取。 一 、 需求分析 八数码游戏（八 数码问题）描述为：在 3 3 组成的九宫格棋盘上，摆有八2 个将牌，每一个将牌都刻有 1-8 八个数码中的某一个数码。棋盘中留有一个空
4、格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 状态表示：把一个状态，自左至右，自上而下地用一个长度为 9 的一维数组表示。 如何判断是否无解：八数码问题不是任何情况下都有解的，考察数组中出去0 的其他 8 位 ，如果 在位置 i #include #include #define SIZE 10000 int start33=0; int end33=0; struct node int index;/结点序号 in
5、t p_index;/父结点序号 int matrix33;/ 八数码状态 int h_function;/启发式函数值 ; node openSIZE; /存放已经生成的未考察的节点 int openlength=0; int openlast=0;/open表最后一个数据的位置 node closedSIZE; /存放已 经考察过得节点 int closedlength=0; int closedlast=0;/closed表最后一个数据的位置 int fail=0;/失败标记， fail=1则搜索失败 int n_index=0;/节点标记序号 int extend33=0; int n
6、_root=0; struct Root node resultRootSIZE; int length; ; void init(Root ; void read() printf(“输入初始状态： n“); int i,j; 4 for(i=0;i0;i-) for(j=0;jopenj+1.h_function) exchangeNode(j,j+1); 7 int seekfather(node a) int i; for(i=0;i0)/空格上移 int *p= int *q= exchange(p,q); if(judge() inopen(extend); copy_matrix
7、(extend,now); if(i0)/空格左移 exchange( if(judge() inopen(extend); copy_matrix(extend,now); if(j10000) fail=1; return; 9 adjust(); sort(); void print_matrix(int a3) int i,j; for(i=0;i=0;j-) print_matrix(result.resultRootj.matrix); printf(“步数为 %dn“,n_root); int countContray(int a3) int num=0; int i,j; int i1,i2,j1,j2; for(i=1;i9;i+) i1=i/3; i2=i%3;
