数据结构课程设计八数码问题设计申报+源码

[2019-2020-1]数据构造设计-九宫问题

题目数据构造课程设计

院 (部) 信息科学与电气工程学院

打算机科学与技能互助

专业

班级

1

学生姓名

学 号

12 月 16 日至 12 月 27 日 共 2 周

辅导西席(具名)

卖力人(具名)

2019 年 12 月 27 日

-------课程设计

院 别: 信息科学与电气工程学院

班 级:

姓 名:

学 号: 1

辅导西席: 黄

设计地点: 综合实

时 间: 2019年 12 月 16 日

至 2019年 12 月 27 日

信息科学与电气工程学院

课程设计成绩评定用表

平时成绩（30%）

答辩成绩（40%）

报告成绩（30%）

总成绩

目录

摘 要51.问题哀求及任务描述51.1.题目哀求51.2.紧张任务52.办理问题的紧张思路和方法52.1.什么是八数码问题52.2.采取办理问题的方法52.3.紧张算法和处理流程图53.程序实现73.1.程序实现时应考虑的问题73.2.紧张源代码及解释84.测试125.小结14参考文献15

摘 要

关键字词：A算法，C措辞，八数码问题，九宫格

问题哀求及任务描述题目哀求在一个 33 的九宫中，有 1-8 这 8 个数及一个空格随机的摆放在个中的格 子里。
如下面左图所示。
哀求实现这样的问题：将九宫问题调度为如右图所示的 形式。
每次只能将与空格（上、下或左、右）相邻的一个数字平移到空格中。
基本哀求： 问你通过移动中间的空格是否能达到右图所示的状态，如果能，则输出所走 的路径，如果不能，则输出：unsolvable。
最好能画出九宫的图形形式，并在其 上动态的演示移动过程。

紧张任务九宫问题是人工智能中的经典难题之一，问题是在３３方格棋盘中，放８格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交流数。
程序自动产生问题的初始状态，通过一系列交流动作将其转换成目标排列。
探求九宫格中八数码自动搜索可移动到目标状态的路径。
以及八数码初始状态有解无解。

办理问题的紧张思路和方法什么是八数码问题如八数码游戏包括一个33的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。
与空位相邻的棋子可以滑动到空位中。
游戏的目的是要达到一个特定的目标状态。
标注的形式化如下：

1

2

3

4

5

6

7

8

采取办理问题的方法八数码问题有很多种搜索策略，比如说有最常见的BFS，DFS，此外，A也是一个比较普遍的搜索算法。
但在八数码问题A每每可以得到最优的求解路径。
在此课程设计中，利用A算法。
紧张算法和处理流程图A潜在地搜索图中一个很大的区域。
和Dijkstra一样，A能用于搜索最短路径。
和BFS一样，A能用启示式函数（注：原文为heuristic）勾引它自己。
在大略的情形中，它和BFS一样快。
它把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。
在谈论A的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启示式评估代价（heuristic estimated cost）。
在上图中，yellow(h)表示阔别目标的结点而teal(g)表示阔别初始点的结点。
当从初始点向目标点移动时，A权衡这两者。
每次进行主循环时，它检讨f(n)最小的结点n，个中f(n) = g(n) + h(n)。
A算法的步骤如下：1）建立一个行列步队，打算初始结点的估价函数f，并将初始结点入队，设置行列步队头和尾指针。
2）取出行列步队头（行列步队头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。
否则对结点进行扩展。
3）检讨扩展出的新结点是否与行列步队中的结点重复，若与不能再扩展的结点重复（位于行列步队头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于行列步队头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。
跳至第五步。
4）如果扩展出的新结点与行列步队中的结点不重复，则按照它的估价函数f大小将它插入行列步队中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，末了更新行列步队尾指针。
5）如果行列步队头的结点还可以扩展，直接返回第二步。
否则将行列步队头指针指向下一结点，再返回第二步。

程序实现程序实现时应考虑的问题函数调用关系图

紧张源代码及解释算法伪代码：创建两个表，OPEN表保存所有已天生而未稽核的节点，CLOSED表中记录已访问过的节点。
算出发点的估代价，将出发点放入OPEN表。
while(OPEN!=NULL){　　从OPEN表中取估代价f最小的节点n;if(n节点==目标节点){break;}for(当前节点n 的每个子节点X){　　算X的估代价;if(X in OPEN){if( X的估代价小于OPEN表的估代价 ){把n设置为X的父亲;　　更新OPEN表中的估代价; //取最小路径的估代价}}if(X inCLOSE){if( X的估代价小于CLOSE表的估代价 ){把n设置为X的父亲;　　更新CLOSE表中的估代价;　　把X节点放入OPEN //取最小路径的估代价}}if(X not inboth){把n设置为X的父亲;　　求X的估代价;　　并将X插入OPEN表中; //还没有排序}}//end for　　将n节点插入CLOSE表中;　　按照估代价将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}//end while(OPEN!=NULL)保存路径，即 从终点开始，每个节点沿着父节点移动直至出发点，这便是你的路径；打算深度的代码：int Distance(Node& node, int digit[][COL]) //打算间隔 新node与目标之间的间隔{int distance = 0; //间隔bool flag = false;for(int i = 0; i < ROW; i++)for (int j = 0; j < COL; j++)for (int k = 0; k < ROW; k++){for (int l = 0; l < COL; l++){if (node.digit[i][j] == digit[k][l]){distance += abs(i - k) + abs(j - l); //当前的数要到该当在的位置绝对值和，即为间隔flag = true;break;}elseflag = false;}if (flag)break;}return distance;}展开算法void ProcessNode(int index) //展开节点{int x, y;bool flag;for (int i = 0; i < ROW; i++){for (int j = 0; j < COL; j++){if (node_v[index].digit[i][j] == 0) //探求0的位置，{x =i;y = j;flag = true;break;}else flag = false;}if(flag)break;}Node node_up; //上移操作Assign(node_up, index); //把启示值最小的节点给 node_upint dist_up = MAXDISTANCE;if (x > 0) //上移须要x＞0；x=0不能上移{Swap(node_up.digit[x][y], node_up.digit[x - 1][y]); //交流x与（x-1）if (isExpandable(node_up)) //判断是否与 node_v[i].digit 相同，不相同则可以扩展，判断有没有重复在 node_v[i]里{dist_up = Distance(node_up, dest.digit); //上移后的间隔node_up.index = index;//上移后的间隔等赋给 node_upnode_up.dist = dist_up;node_up.dep = node_v[index].dep + 1; //深度就加一node_v.push_back(node_up); //添加到node_v}}Node node_down; //下移操作Assign(node_down, index);int dist_down = MAXDISTANCE;if (x < 2){Swap(node_down.digit[x][y], node_down.digit[x + 1][y]);if (isExpandable(node_down)){dist_down = Distance(node_down, dest.digit);node_down.index = index;node_down.dist = dist_down;node_down.dep = node_v[index].dep + 1;node_v.push_back(node_down);}}Node node_left;//左移操作Assign(node_left, index);int dist_left = MAXDISTANCE;if (y > 0){Swap(node_left.digit[x][y], node_left.digit[x][y - 1]);if (isExpandable(node_left)){dist_left = Distance(node_left, dest.digit);node_left.index = index;node_left.dist = dist_left;node_left.dep = node_v[index].dep + 1;node_v.push_back(node_left);}}Node node_right; //右移操作Assign(node_right, index);int dist_right = MAXDISTANCE;if (y < 2){Swap(node_right.digit[x][y], node_right.digit[x][y + 1]);if (isExpandable(node_right)){dist_right = Distance(node_right, dest.digit);node_right.index = index;node_right.dist = dist_right;node_right.dep = node_v[index].dep + 1;node_v.push_back(node_right);}}node_v[index].dist = MAXNUM;}

测试测试结果及剖析：根据题目哀求随机天生数列为初始状态：

如果天生的数列无解，则输出“unsolvable”

小结

（1）设计碰着问题的办理方法及程序实现小结

A算法是一种常用的启示式搜索算法。
在A算法中，一个结点位置的好坏用估价函数来对它进行评估。
碰着最大的问题便是A算法的代码实现，以及办理节点重复扩展问题。

办理结点重复扩展问题:

对付一个结点有多种办法到达该结点，这样就可能多次将它加入open表中，而启示函数知足单调限定条件，后来达到该结点的路径不再是更优的，可以不予考虑。
扩展某结点时先看该结点是否已经扩展过，如果扩展过则略过。
实现的可以线形遍历closed表，但效率不高韶光繁芜度为O ( closedSize)，考虑每个结点可以用一个整数标识，用二叉平衡查找树可以得到更好的韶光繁芜度O ( log (closedSize) ) ，程序中用基于红黑树思想的set实现。

（2）尚未办理的问题及下一步事情思路

该系统还可以设置自动求解或者手动游戏模式，并进行步数的比拟。

（3）课程设计中的收成和心得体会。

A算法基本上与广度优先算法相同，但是在扩展出一个结点后，要打算它的估价函数，并根据估价函数对待扩展的结点排序，从而担保每次扩展的结点都是估价函数最小的结点。

对付八数码问题，BFS算法最慢，A算法较快。
八数码问题的一个状态实际上是0~9的一个排列，对付任意给定的初始状态和目标，不一定有解，也便是说从初始状态不一定能到达目标状态。
由于排列有奇排列和偶排列两类，从奇排列不能转化成偶排列。
如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。
因此，可以在运行程序前检讨初始状态和目标状态的排序的奇偶行是否相同，相同则问题可解，应该能搜索到路径。
否则无解。

A算法作为一种启示式搜索算法，它在启示式函数选择得当的情形下，能够极大地减少搜索节点的数目，对程序性能的提高起到了至关主要的浸染。
但是 A算法也存在这自己的一些缺陷，比如当启示式函数选择不恰当时，算法的性能就会大打折扣。
其余当搜索树的深度比很大时，利用 A算法和 BFS 算法类似，同样是很耗时的。

参考文献

（1）《数据构造实用教程（第二版）》,徐孝凯编著，清华大学出版社

（2）https://blog.csdn.net/qq_369462