《八数码问题课程设计报告150409曹志》由会员分享，可在线阅读，更多相关《八数码问题课程设计报告150409曹志（19页珍藏版）》请在金锄头文库上搜索。
1、.XX学院计算机科学与技术系课程设计报告2016 2017 学年第 2 学期课程 数据结构与算法课程设计名称八数码问题求解学生姓名曹志 学号1504092011 专业班级软件工程2班 指导教师王骏 2017 年 2 月题目八数码问题求解问题描述八数码问题：在33的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。图一请使用一种盲目搜索算法深度或广度优先搜索和一种启发式搜索方法 编程求解八数码问题,并对两种算法的搜索步骤,搜索时间进行分析对比。1、 问题分析和任务定义1.1问题分
2、析由题目知给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。要求分别采用广度优先搜索和启发式搜索两种方法对八数码问题进行求解。且棋盘通过空格的上、下、右四种操作来改变状态。所以需要解决的问题为每个状态的表示和每个状态变化的操作,设计出适合相应搜索的数据结构,完成相应算法思想。1.2任务定义完成棋盘状态表示。完成空格上下左右移动操作变化的表示。分别完成适应于广度优先搜索,启发式搜索的数据结构设计。得出两种搜索的搜索路径,及时间进行对比分析。2、 数据结构
3、的选择和概要设计2.1广度优先搜索广度优先搜索思想介绍从初始节点h开始逐层的对其进行扩展,并考察其其是否为目的节点,若不是将其放入待考察队列中,在第n层节点没有完全进行考察并扩展完成前,不对第n+1层进行扩展。队列中节点总是按照先后顺序进行排列,先进的排在前面,后进的排在后面。由此可知我们可以通过队列的思想完成搜索,其具体搜索过程如下。1初始化头结点front,front=real;2若front=null,问题无解,程序结束。3对front指向的节点进行考察,若为目的节点程序结束。4判断front指向的节点的空格是否可以上下左右移动若可以,扩展节点置于队尾。重复操作。数据结构的选择和概要设计
4、1 棋盘状态的表示因为每一个棋盘状态是静止且确定的所以采取一个一维数组便可将其状态表示出来,数组按照下标顺序从左至右从上至下依次对应。空格可由零来表示。图二此状态可表示为int num9=2,5,4,3,0,7,1,8,6。2) 搜索结构设计 根据算法要求,需要对棋盘不断的进行动态扩展,且盲目搜索产生的数据巨大,所以不能采用静态链表或数组存储,因此选择采用动态链表来存储搜索过程中的每一个状态。因为搜索是根据一种状态对其进行扩展,直至达到目的状态,由于要返回一个最优路径因此需要确定扩展关系,我选择用一个*parent来记录此关系。此时存储结构可由此图表示图三当扩展至目的状态时可通过parent指
5、针找到路径。由此我们可以设置节点类型为typedef struct Node struct Node *parent; int num9; Node *next;QNode； 2.2启发式搜索1启发式搜索的思想介绍搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索,盲目搜索不考虑节点好坏,而对于八数码问题的解决过程是有迹可循的,我们通过是否接近目标状态来判断节点的好坏,因此可以通过启发式搜索中的A*算法来解决这个问题。简单来说A*就是将估值函数分成两个部分,一个部分是路径价值,另一个部分是一般性启发价值,合在一起算估整个结点的价值。在本实验中使用A*算法求解。A
6、*搜索是一种效的搜索算法,它把到达节点的耗散g和从该节点到目标节点的消耗h结合起来对节点进行评价：f=g+h。由此设计如下(1) 把起始节点放到OPEN表中,并计算节点S的(2) 如果OPEN是空表,则失败退出,无解；(3) 从OPEN表中选择一个值最小的节点。如果有几个节点值相同,当其中有一个为目标节点时,则选择此目标节点；否则就选择其中任一个节点作为节点；(4) 把节点从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中;如果是个目标节点,则成功退出,求得一个解；(5) 扩展节点,生成其全部后继节点。对于的每一个后继节点：计算；如果 既不在OPEN表中,又不在CLOCED表中
7、,则用估价函数把它添入OPEN表中。从加一指向其父节点的指针,以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中,则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小,则以此新值取代旧值。从指向,而不是指向他的父节点。如果节点在CLOSED表中,则把它移回OPEN表中。转向2。流程图如下图四(2) 数据结构的选择和概要设计 由于搜索特点,采用的基础存储结构和广度优先搜索相同,不同之处为启发式搜索使用两条链表,所以设计一个表结构,用来声明两条链表。 节点结构typedef struct Nodedouble g,f; struct Node *parent;
8、 int num9;Node； 表结构typedef struct StackNode * npoint;/指向状态节点,相当于表节点的数据域。struct Stack * next;Stack；3、 详细设计和编码3.1广度优先搜索 1相关函数1空格移动函数int move_up;int move_down;int move_left;int move_right;以上移为例,找到0的位置将其与下标比其小三的值交换,且下标为0,1,2的数字不可移动。2搜索过程函数int bfs；接收初始状态和目的状态总领搜索过程。int cansolve；判断两个数列的逆序数奇偶性,从而判断八数码问题是否可
9、解void get_num；将节点中的数组获取出来。void set_num；设置节点中数组的数据。void print；输出节点中信息2算法伪码输入初始状态数组unit,目标状态数组targetIfWhileIf结束循环；End if对队头节点进行扩展,将扩展节点加入队尾；队头指针后移； End while End if3.2启发式搜索设计1所用函数int Equal；判断节点是否相等,相等,不相等。Node * Belong判断节点是否属于OPEN表或CLOSED表,是则返回节点地址,否则返回空地址。void Putinto把节点放入OPEN 或CLOSED 表中。double Fvalu
10、e计算f值。double Distance计算方格的错位距离。int BelongProgram判断子节点是否属于OPEN或CLOSED表并作出相应的处理。int Canspread判断空格可否向该方向移动,表示空格向上向下向左向右移。void Spreadchild扩展child节点的字节点n表示方向表示空格向上向下向左向右移。int Spread扩展后继节点总函数。Node * Process总执行函数。void qf启发式搜索总函数。2搜索过程伪码输入：初始状态,目标状态输出：从初始状态到目标状态的一系列过程算法描述：Begin：读入初始状态和目标状态,并计算初始状态评价函数值f；根据初
11、始状态和目标状态,判断问题是否可解；If把初始状态加如open表中；While未找到解&状态表非空在open表中找到评价值最小的节点,作为当前结点,；判断当前结点状态和目标状态是否一致,若一致,跳出循环；否则跳转到；对当前结点,分别按照上、下、左、右方向移动空格位置来扩展新的状态结点,并在并计算新扩展结点的评价值f并记录其父节点若；对于新扩展的状态结点,判断其是否重复,若不重复,把其加入到open表中；把当前结点从open表中移至Close表；End whileEnd if输出结果；End4、 上机调试过程4.1遇到的问题和分析1本次课程设计过程是两种搜索方式分开开发,因此在综合在一起的时候两
12、种方式的代码合在一起略显杂糅,程序可读性较差。2在做启发式搜索时,发现效率并未达到预期,查阅资料得知h值取得不好,没有完全切合搜索规律,h值应为每个方格到其正确位置的路径之和,而我仅统计的是错位之和同时发现若h值取得越大其搜索速度越快单难以保证得出的是最优解。因此我设计了一个系数1000来进行加速。3在设计广度优先搜索时指针操作出现失误,导致进度一度停滞,后放弃改为数组操作才完成程序4.2时空效率分析（1） 广度优先搜索是一种十分浪费空间的搜索方法,有时会陷入死循环。同时在时间效率上广度优先搜索效率不稳定,若搜索深度过大则时间效率异常缓慢。但可确定找到最优解。（2） 启发式搜索效率较稳定,当搜素深度较小时时间效率不及广度优先但在深度搜索表现优异,同时启发式搜索有选择的创建节点,大大节省空间效率。5、 测试结果及其分析图五图六图七图八图九图十图十一图十二图十 1实验结果实验数据广度优先启发式搜索时间最优节点数时间 最优节点数初始状态283164705目标状态1238047654ms6109ms6初始状态254307186目标状态123804765无解0无解无解无解初始状态123456780目标状态1234056784399ms15196ms15初始状态123456780目标状态0
