还剩5页未读,继续阅读
文本内容:
二、程序运行测试算法求解八数码问题A*
一、具体设计说明
1.评价函数以当前状态下各将牌到目标位置的距离之和作为节点的评价标准距离的定义为“某将牌行下标与目标位置行下标之差的肯定值+列下标与目标位置列下标之差的肯定值”距离越小,该节点的效果越好某个状态全部将牌到目标位置的距离之和用“h值”表示
2.主要函数
2.1countH statest;countll函数功能是计算st状态的h值计算过程中将会用到rightPos数组,数组里记录的是目标状态下,0~9每个将牌在九宫格里的位置位置=行下标*3+列下标
2.2f state*p;f=h+level
2.33Iook_up_dupvectorstate*vec,state*p;在open表或close表中,是否存在指定状态p,当找到与p完全相等的节点时,退出函数
2.4search statestart;在open表不为空时,按f值由小到大对open表中元素进行排序调用findZero函数找到0值元素的位置空格可以向上下左右四个方向移动,前提是移动后不能越过九宫格的边界线确定某方向可走后,空格移动一步,生成状态p此时,检查open表中是否已有p,,若有,更新p数据;检查close表中是否已有p,若有,将p从close表中删除,添加到open表中重复的执行这个过程,直到某状态的h值为零
2.5dump_soIut ionstate*q;在终端输出解路径//A*算法八数码问题ftinclude stdafx.h#includeiostream#includevector#includetime.h#includealgorithm usingnamespace std;const intGRID=3;〃Grid表示表格的行数列数,这是3*3的九宫格int rightPos
[9]={4,0,1,2,5,8,7,6,3};〃目标状态时,若p[i][j]=0MG,那么3*i+j=rightPos[OMG]struct state{int panel[GRID][GRID];int level;〃记录深度int h;state*parent;stateint level:level level{}bool operator==stateq{〃推断两个状态是否完全相等对应位置元素相等,完全相等返回true,否则返回falsefor inti=0;iGRID;i++{for intj=0;jGRID;j++{if panel[i][j]!=q.panel[i][j]returnfalse;return true;stateoperator=statep{//以状态p为当前状态赋值,对应位置元素相同for inti=0;iGRID;i++{for intj=0;jGRID;j++{panel[i][j]=p.panel[i][j];return*this;}};void dump_panel state*p{〃将八数码按3*3矩阵形式输出for inti=0;iGRID;i++{for intj=0;jGRID;j++coutp-panel[i][j]〃〃;coutendl;int countHstatest{〃给定状态st,计算它的h值int h=0;for inti=0;iGRID;i++{for intj=0;jGRID;j++{if st.panel[i][j]!=0h+=absrightPos[st.panel[i][j]]/GRID-i+abs rightPos[st.panel[i][j]]%GRID-j;〃h二各个将牌与其目标位置的距离之和.距离定义为行下标之差的肯定值+列下标之差的肯定值return h;int findZerostatest{//找到零值元素,返回其在表中的位置for inti=0;iGRID;i++{for intj=0;jGRID;j++{if st.panel[i][j]==0int fstate*p{//计算并返回f值,即h值+levelreturn i*3+j;return countH*p+p-level;}bool compare_statestate*p,returnstate*q{〃比较两个状态的f值f pf q;vectorstate*opentable;〃open表vectorstate*〉close_table;//close表vectorstate*::iterator look up dupvectorstate*vec,state*p{vectorstate^::iterator it_r=vec.begin;for;it_rvec.end;it_r++{if**it_r二二*p{break;return it_r;}state*search statestart{〃A*算法进行搜寻int level=0;open table.push backstart;int count=0;while!open_table.empty{sortopen_table.begin,open table,end,compare_state;〃对open袤中的元素进行排序state*p=open_table.back;open_table.pop_back;if countH*p二二0return p;〃全部将牌到达目标位置,搜寻过程结束level=p-level+1;int zeroPos=findZero*p;int x=zeroPos/3;〃空格的行下标int y=zeroPos%3;〃空格的列下标for inti=0;i4;i++{〃上下左右四个方向int xoffset=0,y_offset=0;switch i{0,y_offset=1;break;〃右case0:x_offset=0,y_offset=-1;break;〃左1,y_offset=0;case1:xoffset=casebreak;//_t-1,y_offset=0;break;//T2:x_offset=case3:x_offset=;if x+x_offset0||x+x_offset=GRID|y+y_offset0|y+y_offset=GRID{continue;〃若移动一步后,将超出上/下/左/右边界,则这个方向不行走,尝试下一个方向}state*q=new statelevel;//这个方向可走,扩展下一个节点q-parent=p;*q=*p;q-panel[x][y]=q-panel[x+x_offset][y+y_offset];q-panel[x+x_offset][y+y_offset]二0;〃空格沿这个方向移一步bool skip=false;vectorstate*::iterator dup=look_up_dupopen_table,q;〃若q已在open表中,则对open表中的信息进行更新if dup!=open_table.end{if fqf*dup{*dup-level=q-level;*dup-parent=q-parent;skip=true;dup=lookupdup close_table,q;if dup!=close_table.end{〃若q已在close表中,且f值比原值小,if fqf*dup{〃则将q从close表清除,加入open表delete*dup;close_table.erasedup;open_table.push backq;skip=true;}if!skip{open_table.push backq;close table,push backp;void dumpsolution state*q〃输出解路径vectorstate*trace;while q{trace,push backq;q=q-parent;int count=0;while!trace,empty{cout〃Step〃count〃_—_—_—_八八八八八八八八八八八八\〃=-=-=-=-=-=@\n;dump_paneltrace,back;cout〃h:〃countH*trace.back〈〃\tg:〃〈count〃\tf:ftrace,backendlendl;trace,pop back;count++;int mainp.panel
[0]
[0]p.panel
[0]
[1]state p0;p.panel
[0]
[2]state*q;p.panel
[1]
[0]p.panel
[1]
[1]=6;p.panel
[1]
[2]=4;p.panel
[2]
[0]=0;p.panel
[2]
[1]=8;p.panel
[2]
[2]=7;=2;//设置初始状态=5;=1;=3;p.parent=NULL;q二search p;dump_solution q;systempause;。