A star 算法 八数码问题 C++ 报告+代码+详细注释

《A star 算法 八数码问题 C++ 报告+代码+详细注释》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二、程序运行测试A*算法求解八数码问题一、详细设计说明1.评价函数以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值+列下标与目标位置列下标之差的绝对值”。距离越小，该节点的效果越好。某个状态所有将牌到目标位置的距离之和用“h值”表示。2.主要函数2.1countH（state&st）;countH函数功能是计算st状态的h值。计算过程中将会用到rightPos数组，数组里记录的是目标状态下，0~9每个将牌在九宫格里的位置（位置=行下标*3+列下标）。2.2f（

2、state*p）;f()=h()+level2.3look_up_dup(vector&vec,state*p);在open表或close表中，是否存在指定状态p，当找到与p完全相等的节点时，退出函数。2.4search(state&start)；在open表不为空时，按f值由小到大对open表中元素进行排序。调用findZero()函数找到0值元素的位置。空格可以向上下左右四个方向移动，前提是移动后不能越过九宫格的边界线。确定某方向可走后，空格移动一步，生成状态p’。此时，检查open表中是否已有p’，若有

3、，更新p’数据；检查close表中是否已有p’，若有，将p’从close表中删除，添加到open表中。重复的执行这个过程，直到某状态的h值为零。2.5dump_solution(state*q)；在终端输出解路径。//A*算法八数码问题#include"stdafx.h"#include#include#include#includeusingnamespacestd;constintGRID=3;//Grid表示表格的行数(列数)，这是3*3的九宫格

4、intrightPos[9]={4,0,1,2,5,8,7,6,3};//目标状态时，若p[i][j]=OMG,那么3*i+j=rightPos[OMG]structstate{intpanel[GRID][GRID];intlevel;//记录深度inth;state*parent;state(intlevel):level(level){}booloperator==(state&q){//判断两个状态是否完全相等（对应位置元素相等），完全相等返回true,否则返回falsefor(inti=0;i

5、for(intj=0;j

6、;ipanel[i][j]<<"";cout<

7、个将牌与其目标位置的距离之和.距离定义为：行下标之差的绝对值+列下标之差的绝对值。}}returnh;}intfindZero(state&st){//找到零值元素，返回其在表中的位置for(inti=0;ilevel;}boolcompare_state(state*p,sta

8、te*q){//比较两个状态的f值returnf(p)>f(q);}vectoropen_table;//open表vectorclose_table;//close表vector::iteratorlook_up_dup(vector