搜索
二、程序运行测试A*算法求解八数码问题一、详细设计说明1.评价函数以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值+列下标与目标位置列下标之差的绝对值”。距离越小，该节点的效果越好。某个状态所有将牌到目标位置的距离之和用“h值”表示。2.主要函数2.1countH（state&st）;countH函数功能是计算st状态的h值。计算过程中将会用到rightPos数组，数组里记录的是目标状态下，0~9每个将牌在九宫格里的位置（位置=行下标*3+列下标）。2.2f（state*p）;f()=h()+level2.3look_up_dup(vectorstate*&vec,state*p);在open表或close表中，是否存在指定状态p，当找到与p完全相等的节点时，退出函数。2.4search(state&start)；在open表不为空时，按f值由小到大对open表中元素进行排序。调用findZero()函数找到0值元素的位置。空格可以向上下左右四个方向移动，前提是移动后不能越过九宫格的边界线。确定某方向可走后，空格移动一步，生成状态p’。此时，检查open表中是否已有p’，若有，更新p’数据；检查close表中是否已有p’，若有，将p’从close表中删除，添加到open表中。重复的执行这个过程，直到某状态的h值为零。2.5dump_solution(state*q)；在终端输出解路径。//A*算法八数码问题#includestdafx.h#includeiostream#includevector#includetime.h#includealgorithmusingnamespacestd;constintGRID=3;//Grid表示表格的行数(列数)，这是3*3的九宫格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;iGRID;i++){for(intj=0;jGRID;j++){if(panel[i][j]!=q.panel[i][j])returnfalse;}}returntrue;}state&operator=(state&p){//以状态p为当前状态赋值，对应位置元素相同for(inti=0;iGRID;i++){for(intj=0;jGRID;j++){panel[i][j]=p.panel[i][j];}}return*this;}};voiddump_panel(state*p){//将八数码按3*3矩阵形式输出for(inti=0;iGRID;i++){for(intj=0;jGRID;j++)coutp-panel[i][j];coutendl;}}intcountH(state&st){//给定状态st，计算它的h值。inth=0;for(inti=0;iGRID;i++){for(intj=0;jGRID;j++){if(st.panel[i][j]!=0)h+=abs(rightPos[st.panel[i][j]]/GRID-i)+abs(rightPos[st.panel[i][j]]%GRID-j);//h=各个将牌与其目标位置的距离之和.距离定义为：行下标之差的绝对值+列下标之差的绝对值。}}returnh;}intfindZero(state&st){//找到零值元素，返回其在表中的位置for(inti=0;iGRID;i++){for(intj=0;jGRID;j++){if(st.panel[i][j]==0)returni*3+j;}}}intf(state*p){//计算并返回f()值，即h值+levelreturncountH(*p)+p-level;}boolcompare_state(state*p,state*q){//比较两个状态的f值returnf(p)f(q);}vectorstate*open_table;//open表vectorstate*close_table;//close表vectorstate*::iteratorlook_up_dup(vectorstate*&vec,state*p){vectorstate*::iteratorit_r=vec.begin();for(;it_rvec.end();it_r++){if((*(*it_r))==*p){break;}}returnit_r;}state*search(state&start){//A*算法进行搜索intlevel=0;open_table.push_back(&start);intcount=0;while(!open_table.empty()){sort(open_table.begin(),open_table.end(),compare_state);//对open表中的元素进行排序state*p=open_table.back();open_table.pop_back();if(countH(*p)==0)returnp;//所有将牌到达目标位置，搜索过程结束level=p-level+1;intzeroPos=findZero(*p);intx=zeroPos/3;//空格的行下标inty=zeroPos%3;//空格的列下标for(inti=0;i4;i++){//上下左右四个方向intx_offset=0,y_offset=0;switch(i){case0:x_offset=0,y_offset=1;break;//右case1:x_offset=0,y_offset=-1;break;//左case2:x_offset=1,y_offset=0;break;//上case3:x_offset=-1,y_offset=0;break;//下};if(x+x_offset0||x+x_offset=GRID||y+y_offset0||y+y_offset=GRID){continue;//若移动一步后，将超出上/下/左/右边界，则这个方向不可走，尝试下一个方向}state*q=newstate(level);//这个方向可走，扩展下一个节点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;//空格沿这个方向移一步boolskip=false;vectorstate*::iteratordup=look_up_dup(open_table,q);//若q已在open表中，则对open表中的信息进行更新if(dup!=open_table.end()){if(f(q)f(*dup)){(*dup)-level=q-level;(*dup)-parent=q-parent;}skip=true;}dup=look_up_dup(close_table,q);if(dup!=close_table.end()){//若q已在close表中，且f值比原值小，if(f(q)f(*dup)){//则将q从close表清除，加入open表delete*dup;close_table.erase(dup);open_table.push_back(q);skip=true;}}if(!skip){open_table.push_back(q);}}close_table.push_back(p);}}voiddump_solution(state*q)//输出解路径{vectorstate*trace;while(q){trace.push_back(q);q=q-parent;}intcount=0;while(!trace.empty()){coutStepcount:^-^=^-^=^-^=^-^=^^=^-^=^-^=^-^=^-^=^-^=^@\n;dump_panel(trace.back());couth:countH(*trace.back())\tg:count\tf:f(trace.back())endlendl;trace.pop_back();count++;}}intmain(){statep(0);state*q;p.panel[0][0]=2;//设置初始状态p.panel[0][1]=1;p.panel[0][2]=6;p.panel[1][0]=4;p.panel[1][1]=0;p.panel[1][2]=8;p.panel[2][0]=7;p.panel[2][1]=5;p.panel[2][2]=3;p.parent=NULL;q=search(p);dump_solution(q);system(pause);}