课 程 设 计 任 务 书

[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语言，八数码问题，九宫格

问题要求及任务描述题目要求

在一个 3*3 的九宫中，有 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;

}

else

flag = 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_up

int 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_up

node_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）