八数码问答题实验报告

(9页)

'八数码问答题实验报告'
/'《八数码问题》实验报告一、实验目的:熟练掌握启发式搜索算法。二、实验内容:使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题算法,采用估价函数,其中:是搜索树中结点的深度;为结点的数据库中错放的棋子个数;为结点的数据库中每个棋子与其目标位置之间的距离总和。三、实验原理:1. 问题描述:八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2. 原理描述:启发式搜索(1)原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。(2)估价函数计算一个节点的估价函数,可以分成两个部分:1、 已经付出的代价(起始节点到当前节点);2、 将要付出的代价(当前节点到目标节点)。节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值,即 = + 。是从初始节点到达当前节点n的实际代价; 是从节点n到目标节点的最佳路径的估计代价。所占的比重越大,越趋向于宽度优先或等代价搜索;反之,的比重越大,表示启发性能就越强。(3)算法描述:① 把起始节点S放到OPEN表中,并计算节点S的;② 如果OPEN是空表,则失败退出,无解;③ 从OPEN表中选择一个值最小的节点。如果有几个节点值相同,当其中有一个为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点;④ 把节点从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中;⑤ 如果是个目标节点,则成功退出,求得一个解;⑥ 扩展节点,生成其全部后继节点。对于的每一个后继节点:计算;如果 既不在OPEN表中,又不在CLOCED表中,则用估价函数把它添入OPEN表中。从加一指向其父节点的指针,以便一旦找到目标节点时记住一个解答路径;如果已在OPEN表或CLOSED表中,则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小,则(I)以此新值取代旧值。(II)从指向,而不是指向他的父节点。(III)如果节点在CLOSED表中,则把它移回OPEN表中。⑦ 转向②,即GOTO②。(3) 算法流程图:4、 实验结果输入矩阵: 目标矩阵:2831231458047607655、 实验小结通过本次试验,我对启发式搜索有了更加深入的了解。在实验中,通过对两种启发式搜索所扩在的节点数来看,看来比更加有效,能在复杂情况下求得更加优质的解,避免不必要的节点的扩展。所以,要更好地定义一个估价函数还有待深入讨论。源代码:#include"stdio.h"#define num 3 //宏定义数码的行列数为3/*显示当前待调整数码矩阵*/void show(int begin[num][num]) { for(int i = 0; i < num; i++) { for(int j = 0; j < num; j++) printf("%d ", begin[i][j]); printf("\n"); } printf("\n");}/*交换数码中的 begin[row_one][column_one] 与 begin[row_two][column_two] 这两个数*/void exchange(int begin[num][num], int row_one, int column_one, int row_two, int column_two) { int temp; temp = begin[row_two][column_two] ; begin[row_two][column_two] = begin[row_one][column_one]; begin[row_one][column_one] = temp;}/*判断待调整的数码与最终数码相比正确位置数码的个数*/int judge(int begin[num][num], int end[num][num]) { int count=0; //count记录数码中正确位置的个数 for(int i = 0; i < num; i++) //检查当前图形的正确度 for(int j = 0; j < num; j++) { if(begin[i][j] == end[i][j] && end[i][j] != 0) count++; } return count; //返回数码中正确位置的个数} /* 将待调整数码从开始位置移动到终止位置,并将其过程输出*/int yidong(int begin[num][num], int end[num][num] , int right, int jishu, int ji_shu[50][3][3] , int biaoji, int row, int column) //biaoji存储上一轮移动的反方向代号{ int temp_zhi; show(begin); //显示数组矩阵 if(jishu >= 20) return 0; int node; //,node为标记 int temp; //存储当前待调整数码正确的个数 for(int q=0; q<jishu; q++) //检查交换后的end[][]图形是否先前已经遍历过了 { node = 1; for(int w=0; w<num && node; w++) for(int r=0; r<num && node; r++) if(ji_shu[q][w][r] != begin[w][r]) node = 0; if(node == 1) //如果先前遍历过,返回0 { return 0; } } for(int i = 0; i < num; i++) for(int
关 键 词:
数码 问答题 实验 报告
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:八数码问答题实验报告
链接地址: https://www.wenku365.com/p-43429037.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开