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

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

ID:40523975

大小:187.29 KB

页数:8页

时间:2019-08-04

A star 算法 八数码问题 C++ 报告+代码+详细注释_第1页
A star 算法 八数码问题 C++ 报告+代码+详细注释_第2页
A star 算法 八数码问题 C++ 报告+代码+详细注释_第3页
A star 算法 八数码问题 C++ 报告+代码+详细注释_第4页
A star 算法 八数码问题 C++ 报告+代码+详细注释_第5页
资源描述:

《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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。