西电八数码问题求解.doc

西安电子科技大学课程论文 数据结构 八数码问题的求解 班级： 作者： 学号： 时间： 摘要 八数码问题也称为九宫问题，在33的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以0标记），与空格相邻的棋子可以移到空格中。给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有4个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。一般用搜索法来解决：广度优先搜索法、深度优先搜索法、A*算法等，本文用全局择优来解决该问题。 引言 八数码问题是人工智能中一个很典型的智力问题。一般用搜索法来解决：广度优先搜索法、深度优先搜索法、A*算法等。搜索就是按照一定规则扩展已知结点，直到找到目标结点或所有结点都不能扩展为止，广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。A*是一种静态路网中求解最短路径最有效的方法，公式表示为：f(n)=g(n)+h(n),其中f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价，保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取。一、需求分析 八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 状态表示：把一个状态，自左至右，自上而下地用一个长度为9的一维数组表示。 如何判断是否无解：八数码问题不是任何情况下都有解的，考察数组中出去0的其他8位，如果在位置ij时，有，则说明存在一个逆序，在任何情况下，逆序总数不会改变。二、设计启发函数用计算不同节点的方法。三、程序运行结果四、结果分析及评价 就程序结果而言，有解和无解的情况都满足，且结果经过我的检验是正确的，但是没有考虑是否为最短路径。经过本次作业，让我更深刻地理解了节点和搜索的相关知识，及八数码问题的解法。附录#include#include#include#define SIZE 10000int start33=0;int end33=0;struct node int index;/结点序号 int 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_root=0;struct Rootnode resultRootSIZE;int length;void init(Root &r)r.length=0;void read()printf(输入初始状态：n);int i,j;for(i=0;i3;i+)for(j=0;j3;j+)scanf(%d,&startij);printf(输入目标状态：n);for(i=0;i3;i+)for(j=0;j3;j+)scanf(%d,&endij);printf(n);int isEqual(int a3,int b3)/判断节点是否与目标节点相同int i,j;for(i=0;i3;i+)for(j=0;j3;j+)if(aij!=bij)return 0;return 1;int arouse(int a3)/用曼哈顿路径求启发函数int distance=0;int i,j;int locate(int m3,int n);for(i=0;i3;i+)for(j=0;j3;j+)int location=locate(end,aij);int i1=location/3;int j1=location%3;distance+=(int)fabs(i1-i)+(int)fabs(j1-j);return distance;void copy_matrix(int a3,int b3)int i,j;for(i=0;i3;i+)for(j=0;j3;j+)aij=bij;void inopen(int a3)/节点进入open表，同时节点编号置0，配以指向父节点的指针，同时openlength和openlast加一copy_matrix(openopenlast.matrix,extend);/将第二个参数矩阵copy到第一个openopenlast.index=0;/放入open表中，序号为0openopenlast.p_index=n_index;openopenlast.h_function=arouse(extend);openlength+;openlast+;void cut()/将open0放入closed表中closedclosedlast.index=n_index;closedclosedlast.p_index=open0.p_index;closedclosedlast.h_function=open0.h_function;copy_matrix(closedclosedlast.matrix,open0.matrix);open0.index=-1;openlength-;closedlength+;closedlast+;int locate(int a3,int b)/返回0所在位置int i,j;for(i=0;i3;i+)for(j=0;j3;j+)if(aij=b)return i*3+j;return -1;void exchange(int *a,int *b)int t;t=*a;*a=*b;*b=t;void copy(node &a,node &b)a.index=b.index;a.p_index=b.p_index;a.h_function=b.h_function;copy_matrix(a.matrix,b.matrix);void adjust()/调整open表和closed表int i;for(i=0;iopenlast;i+)if(openi.index=-1)copy(openi,openopenlast-1);openlast-;for(i=0;i0;i-)for(j=0;jopenj+1.h_function)exchangeNode(j,j+1);int seekfather(node a)int i;for(i=0;iclosedlast;i+)if(closedi.index=a.p_index)return i;return -1;int judge()int i;for(i=0;iopenlast;i+)if(openi.index!=-1&isEqual(openi.matrix,extend)return 0;for(i=0;i0)/空格上移int *p=&extendij;int *q=&extendi-1j;exchange(p,q);if(judge()inopen(extend);copy_matrix(extend,now);if(i0)/空格左移exchange(&extendij,&extendij-1);if(judge()inopen(extend);copy_matrix(extend,now);if(j10000)fail=1;return;adjust();sort();void print_matrix(int a3)int i,j;for(i=0;i3;i+)for(j=0;j=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;for(j=0;ji;j+)j1=j/3;j2=j%3;if(ai1i2!=0&aj1j2!=0&ai1i2aj1j2)num+;return num;int canSolve()int n_start,n_end;n_start=countContray(start);n_end=countContray(end);if(n_st