西电八数码问题求解

《西电八数码问题求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、西安电子科技大学课程论文数据结构八数码问题的求解班级：作者：学号：时间：10摘要八数码问题也称为九宫问题，在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以0标记），与空格相邻的棋子可以移到空格中。给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有4个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下

2、左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。一般用搜索法来解决：广度优先搜索法、深度优先搜索法、A*算法等，本文用全局择优来解决该问题。引言八数码问题是人工智能中一个很典型的智力问题。一般用搜索法来解决：广度优先搜索法、深度优先搜索法、A*算法等。搜索就是按照一定规则扩展已知结点，直到找到目标结点或所有结点都不能扩展为止，广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。广度和深度优先搜索有一个很大的

3、缺陷就是他们都是在一个给定的状态空间中穷举。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。A*是一种静态路网中求解最短路径最有效的方法，公式表示为：f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价，保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取

4、。一、需求分析①八数码游戏（八数码问题）描述为：在3×103组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。②状态表示：把一个状态，自左至右，自上而下地用一个长度为9的一维数组表示。③如何判断是否无解：八数码问题不是任何情况下都有解的

5、，考察数组中出去0的其他8位，如果在位置i#include#include#defineSIZE10000intstart[3

6、][3]={0};intend[3][3]={0};structnode{intindex;//结点序号intp_index;//父结点序号intmatrix[3][3];//八数码状态inth_function;//启发式函数值};nodeopen[SIZE];//存放已经生成的未考察的节点intopenlength=0;intopenlast=0;//open表最后一个数据的位置nodeclosed[SIZE];//存放已经考察过得节点intclosedlength=0;intclosedlast

7、=0;//closed表最后一个数据的位置intfail=0;//失败标记，fail=1则搜索失败intn_index=0;//节点标记序号intextend[3][3]={0};intn_root=0;structRoot{noderesultRoot[SIZE];intlength;};voidinit(Root&r){r.length=0;};voidread(){printf("输入初始状态：");inti,j;for(i=0;i<3;i++){for(j=0;j<3;j++){scanf

8、("%d",&start[i][j]);}}printf("输入目标状态：");for(i=0;i<3;i++){for(j=0;j<3;j++){scanf("%d",&end[i][j]);}}10printf("");}intisEqual(inta[][3],intb[][3]){//判断节点是否与目标节点相同inti,j;for(i=0;i<3;i++){for(j=0;j<3;j++){if(a[i][j]!=b[i][j]){ret