二、程序运行测试 A*算法求解八数码问题 一、 详细设计说明 1. 评价函数 以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值 + 列下标与目标位置列下标之差的绝对值”。距离越小，该节点的效果越好。某个状态所有将牌到目标位置的距离之和用“h 值”表示。 2. 主要函数 2.1 countH（state & st）; countH 函数功能是计算st 状态的h 值。 计算过程中将会用到rightPos 数组，数组里记录的是目标状态下，0~9 每个将牌在九宫格里的位置（位置 = 行下标 * 3 + 列下标）。 2.2 f（state * p）; f()=h()+level 2.3 look_up_dup(vector
& vec, state * p); 在open 表或close 表中，是否存在指定状态p，当找到与p 完全相等的节点时，退出函数。 2.4 search(state & start)； 在open 表不为空时，按f 值由小到大对open 表中元素进行排序。 调用findZero()函数找到0 值元素的位置。空格可以向上下左右四个方向移动，前提是移动后不能越过九宫格的边界线。确定某方向可走后，空格移动一步，生成状态p’。 此时，检查 open 表中是否已有p’，若有，更新 p’数据；检查 close 表中是否已有p’，若有，将p’从 close 表中删除，添加到open 表中。 重复的执行这个过程，直到某状态的h 值为零。 2.5 dump_solution(state * q) ； 在终端输出解路径。 // A*算法 八数码问题 #include "stdafx.h" #include #include #include #include using namespace std; const int GRID = 3; //Grid表示表格的行数(列数)，这是3*3的九宫格 int rightPos[9] = { 4, 0, 1, 2, 5, 8, 7, 6, 3 }; //目标状态时，若p[i][j]=OMG,那么3*i+j = rightPos[OMG] struct state{ int panel[GRID][GRID]; int level; //记录深度 int h; state * parent; state(int level) :level(level){} bool operator == (state & q){ //判断两个状态是否完全相等（对应位置元素相等），完全相等返回true,否则返回false for (int i = 0; i
