合肥学院
计算机科学与技术系
课程设计报告
2016 ～2017 学年第 2 学期
课程 | 数据结构与算法 |
| if i aint got you 课程设计名称 | 八数码问题求解 |
学生姓名 | 曹志 |
学号 | 1504092011 |
专业班级 | 软件工程2班 |
指导教师 | 王骏 weekender |
| |
2017 年 2 月
题目
zhon
八数码问题求解
【问题描述】
八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
图一
请使用一种盲目搜索算法（深度或广度优先搜索）和一种启发式搜索方法 编程求解八数码问题，并对两种算法的搜索步骤，搜索时间进行分析对比。
1、问题分析和任务定义on a night like this
1.1问题分析
由题目知给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。要求分别采用广度优先搜索和启发式搜索两种方法对八数码问题进行求解。且棋盘通过空格的上、下、右四种操作来改变状态。所以需要解决的问题为每个状态的表示和每个状态变化的操作，设计出适合相应搜索的数据结构，完成相应算法思想。
1.2任务定义
(1)完成棋盘状态表示。
(2)完成空格上下左右移动操作变化的表示。
(3)分别完成适应于广度优先搜索，启发式搜索的数据结构设计。
(4)得出两种搜索的搜索路径，及时间进行对比分析。
2、数据结构的选择和概要设计
2.1广度优先搜索
(1)广度优先搜索思想介绍
从初始节点h开始逐层的对其进行扩展，并考察其其是否为目的节点，若不是将其放入待考察队列中，在第n层节点没有完全进行考察并扩展完成前，不对第n+1层进行扩展。队列中节点总是按照先后顺序进行排列，先进的排在前面，后进的排在后面。
由此可知我们可以通过队列的思想完成搜索，其具体搜索过程如下。
1)初始化头结点front，front=real;
2)若front==null,问题无解,程序结束。
3)对front指向的节点进行考察，若为目的节点程序结束。
4)判断front指向的节点的空格是否可以上下左右移动若可以，扩展节点置于队尾。重复操作(2)。
(2)数据结构的选择和概要设计
1) 棋盘状态的表示
因为每一个棋盘状态是静止且确定的所以采取一个一维数组便可将其状态表示出来，数组按照下标顺序从左至右从上至下依次对应。空格可由零来表示。
图二
此状态可表示为int num[9]={2,5,4,3,0,7,1,8,6}。
2)搜索结构设计
根据算法要求，需要对棋盘不断的进行动态扩展，且盲目搜索产生的数据巨大，所以不能采用静态链表或数组存储，因此选择采用动态链表来存储搜索过程中的每一个状态。
因为搜索是根据一种状态对其进行扩展，直至达到目的状态，由于要返回一个最优路径因此需要确定扩展关系，我选择用一个*parent来记录此关系。此时存储结构可由此图表示trickortreat
mayday是什么意思图三
当扩展至目的状态时可通过parent指针找到路径。由此我们可以设置节点类型为
typedef struct Node
{
struct Node *parent;
int num[9];
Node *next;
}QNode；
2.2启发式搜索
（1）启发式搜索的思想介绍
搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，盲目搜索不考虑节点好坏，而对于八数码问题的解决过程是有迹可循的，我们通过
是否接近目标状态来判断节点的好坏，因此可以通过启发式搜索中的A*算法来解决这个问题。
贸易收支简单来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值。在本实验中使用A*算法求解。A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。
由此设计如下
creepy(1)把起始节点放到OPEN表中，并计算节点S的
(2)如果OPEN是空表，则失败退出，无解；
(3)从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点；
(4)把节点从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中;如果是个目标节点，则成功退出，求得一个解；
(5)扩展节点，生成其全部后继节点。对于的每一个后继节点翻译英语句子：计算；如果 既不在OPEN表中，又不在CLOCED表中，则用估价函数把它添入OPEN表中。从加一指向其父节点的指针，以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则(I)以此新值取代旧值。(II)从指向，而不是指向他的父节点。(III)如果节点在CLOSED表中，则把它移回OPEN表中。转向（2）。
流程图如下
图四
scouts
(2)数据结构的选择和概要设计
由于搜索特点，采用的基础存储结构和广度优先搜索相同，不同之处为启发式搜索使用两条链表，所以设计一个表结构，用来声明两条链表。
节点结构
typedef struct Node
