八数码问题课程设计报告_1504092011_曹志.docVIP

合肥学院 计算机科学与技术系 课程设计报告 2016 ～2017 学年第 2 学期 课程 数据结构与算法 课程设计名称 八数码问题求解 学生姓名 曹志 学号 1504092011 专业班级 软件工程2班 指导教师 王骏 2017 年 2 月 题目 八数码问题求解 【问题描述】 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 图一 请使用一种盲目有哪些信誉好的足球投注网站算法（深度或广度优先有哪些信誉好的足球投注网站）和一种启发式有哪些信誉好的足球投注网站方法 编程求解八数码问题，并对两种算法的有哪些信誉好的足球投注网站步骤，有哪些信誉好的足球投注网站时间进行分析对比。 问题分析和任务定义 1.1问题给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态 图三 当扩展至目的状态时可通过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)。 由此设计如下 把起始节点放到OPEN表中，并计算节点S的 如果OPEN是空表，则失败退出，无解； 从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点； 把节点从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中;如果是个目标节点，则成功退出，求得一个解； 扩展节点，生成其全部后继节点。对于的每一个后继节点：计算；如果 既不在OPEN表中，又不在CLOCED表中，则用估价函数把它添入OPEN表中。从加一指向其父节点的指针，以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则(I)以此新值取代旧值。(II)从指向，而不是指向他的父节点。(III)如果节点在CLOSED表中，则把它移回OPEN表中。转向（2）。 流程图如下 图四 数据结构的选择和概要设计 由于有哪些信誉好的足球投注网站特点，采用的基础存储结构和广度优先有哪些信誉好的足球投注网站相同，不同之处为启发式有哪些信誉好的足球投注网站使用两条链表，所以设计一个表结构，用来声明两条链表。 节点结构 typedef struct Node { double g,f; struct Node *parent; int num[9]; }Node； 表结构 typedef struct Stack { Node * npoint;//指向状态节点，相当于表节点的数据域。 struct Stack * next; }Stack； 详细设计和编码 3.1广度优先有哪些信誉好的足球投注网站 （1）相关函数 1）空格移动函数 int move_up(int num[]); int move_down(int num[]); int move_left(int num[]); int move_right(int num[]); 以上移为例，找到0的位置将其与下标比其小三的值交换，且下标为0,1,2的数字不可移动。 2）有哪些信誉好的足球投注网站过程函数 int bfs(int init[],int target[])；接收初始状态和目的状态总领有哪些信誉好的足球投注网站过程。 int cansolve(int num1[], int num2[])；判断两个数列的逆序数奇偶性，从而判断八数码问题是否可解 void get_num(QNode *node, int temp[])；将节点中的数组获取出来。 void set_num(QNode *node, int temp[])；设置节点中数组的数据。 void print(QNode *node)；输出节点中信息 （2)算法伪码 输入