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