西电八数码问题求解

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

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)的选取。一、需求分析①八数码游戏（八数码问题）描述为：在3×103组成的九宫格棋盘上，摆有八个将

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

5、数用计算不同节点的方法。三、程序运行结果四、结果分析及评价就程序结果而言，有解和无解的情况都满足，且结果经过我的检验是正确的，但是没有考虑是否为最短路径。经过本次作业，让我更深刻地理解了节点和搜索的相关知识，及八数码问题的解法。附录10#include#include#include#defineSIZE10000intstart[3][3]={0};intend[3][3]={0};structnode{intindex;//结点序号intp_index;//父结点序号intma

6、trix[3][3];//八数码状态inth_function;//启发式函数值};nodeopen[SIZE];//存放已经生成的未考察的节点intopenlength=0;intopenlast=0;//open表最后一个数据的位置nodeclosed[SIZE];//存放已经考察过得节点intclosedlength=0;intclosedlast=0;//closed表最后一个数据的位置intfail=0;//失败标记，fail=1则搜索失败intn_index=0;//节点标记序号intextend[3][3]={0};

7、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("%d",&start[i][j]);}}printf("输入目标状态：");for(i=0;i<3;i++){for(j=0;j<3;j++){scanf("%d",&end[i][j]);}}10pr

8、intf("");}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