实验三八数码问题实验三八数码问题.docVIP

枣 庄 学 院 实 验 报 告 信息科学与工程学院 计算机科学与技术专业 2011级本一班 2013年10月28日 课程名称 人工智能 指导教师 杨振 实验名称 八数码问题 学 号 201112110126 姓 名 王海洋 成 绩 实验目的 了解八数码问题，通过求解八数码问题加深对深度优先、广度优先、A或者A*算法的理解。 实验任务 利用A或者A*算法中的一种完成自己的八数码问题求解；八数码初态的生成可随机生成，也可为指定状态。 实验过程 算法描述 （1）把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。 　　　（2）如果Open表为空，则失败退出。 　　　（3）把第一个节点（节点n）从OPEN表移到CLOSED表。 　　　（4）如果节点n的深度等于最大深度，则转向（2）。 　　　（5）扩展节点n，产生其全部后裔，并把它们放入Open表中的前头。如果没有后裔，则转向（2）。 （6）如果后继节点中有任一个为目标节点，则求得一个解，成功退出;否则转向（2）。 2.算法流程图 3.算法程序实现 #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]); index = node_v[index].index; while (index != 0) { rstep_v.push_back(node_v[index]); index = node_v[index].index; } for (int i = rstep_v.size() - 1; i = 0; i--)//输出每一步的探索过程 cout Step rstep_v.size() - i endl rstep_v[i] endl; } void Swap(int a, int b) { int t; t = a; a = b; b = t; } void Assign(Node node, int