631306050120刘忠钊+状态空间搜索+启发式搜索讲诉.doc

重庆交通大学计算机与信息学院 验证性实验报告 班 级：计算机科学与技术（软件开发）专业13级1班 学 号： 631306050120 姓 名： 刘忠钊 实验项目名称： 状态空间搜索 8数码问题 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼） 指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 11 日 一、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 二、实验内容及要求 （一、） 实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 图1 八数码问题示意图 请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。 三、实验设备及软件 WIN7系统64位系统笔记本电脑 TC2.0 或 VC6.0 编程语言或其它编程语言 四、设计方案 ㈠ 题目 状态空间搜索 8数码问题 ㈡ 设计的主要思路 程序采用宽度优先搜索算法，基本流程如下： ㈢ 主要功能 完成对八数码问题的求解。 五、主要代码 #include iostream #include ctime #include vector using namespace std; const int ROW = 3;//行数 const int COL = 3;//列数 const int MAXDISTANCE = 10000;//最多可以有的表的数目 const int MAXNUM = 10000; typedef struct _Node{ int digit[ROW][COL]; int dist; // distance between one state and the destination一个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; Node src, dest;// 父节表 目的表 vectorNode node_v; // store the nodes存储节点 bool isEmptyOfOPEN() //open表是否为空 { for (int i = 0; i node_v.size(); i++) { if (node_v[i].dist != MAXNUM) return false; } return true; } bool isEqual(int index, int digit[][COL]) //判断这个最优的节点是否和目的节点一样 { for (int i = 0; i ROW; i++) for (int j = 0; j COL; j++) { if (node_v[index].digit[i][j] != digit[i][j]) return false; } return true; } ostream operator(ostream os, Node node) { for (int i = 0; i ROW; i++) { for (int j = 0; j COL; j++) os node.digit[i][j] ; os endl; } return os; } void PrintSteps(int index, vectorNode rstep_v)//输出每一个遍历的节点 深度遍历 { rstep_v.push_back(node_v[index]); inde