631306050120刘忠钊+状态空间搜索+启发式搜索

《631306050120刘忠钊+状态空间搜索+启发式搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、重庆交通大学计算机与信息学院验证性实验报告班级：计算机科学与技术（软件开发）专业13级1班学号：631306050120姓名：刘忠钊实验项目名称：状态空间搜索8数码问题实验项目性质：验证性实验实验所属课程：人工智能实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国实验完成时间：2016年6月11日评阅意见：实验成绩：签名：年月日一、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。二、实验内容及要求（一、）实验内容八数码问题：在3×3的方格棋盘上，摆放着1到8这八个

2、数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。图1八数码问题示意图请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A算法或A*算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。三、实验设备及软件WIN7系统64位系统笔记本电脑TC2.0或VC6.0编程语言或其它编程语言四、设计方案㈠题目状态空间搜索8数码问题㈡设计的主要思路程序采用宽度优先搜索算法，基本流程如下：㈢主要功能完成对八数码问题的求解。五、主要代码#inclu

3、de#include#includeusingnamespacestd;constintROW=3;//行数constintCOL=3;//列数constintMAXDISTANCE=10000;//最多可以有的表的数目constintMAXNUM=10000;typedefstruct_Node{intdigit[ROW][COL];intdist;//distancebetweenonestateandthedestination一个表和目的表的距离intdep;//thedepthofnode深度//Sotheco

4、mmentfunction=dist+dep.估价函数值intindex;//pointtothelocationofparent父节点的位置}Node;Nodesrc,dest;//父节表目的表vectornode_v;//storethenodes存储节点boolisEmptyOfOPEN()//open表是否为空{for(inti=0;i

5、/判断这个最优的节点是否和目的节点一样{for(inti=0;i

6、r&rstep_v)//输出每一个遍历的节点深度遍历{rstep_v.push_back(node_v[index]);index=node_v[index].index;while(index!=0){rstep_v.push_back(node_v[index]);index=node_v[index].index;}for(inti=rstep_v.size()-1;i>=0;i--)//输出每一步的探索过程cout<<"Step"<

7、t&b){intt;t=a;a=b;b=t;}voidAssign(Node&node,intindex){for(inti=0;i