1、A*算法实验报告实验目的1熟悉和掌握启发式搜索的定义、估价函数和算法过程2.学会利用A*算法求解N数码难题3.理解求解流程和搜索顺序实验原理A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。实验条件1.WindowNT/xp/7及以上的操作系统2.内存在512M以上3.CPU在奔腾II以上实验内容1.分别以8数码和15数码为例实
2、际求解A*算法2.画出A*算法求解框图3.分析估价函数对搜索算法的影响4.分析A*算法的特点实验分析1.A*算法基本步骤1）生成一个只包含开始节点n。的搜索图G,把n放在一个叫OPEI的列表上。2）生成一个列表CLOSE，它的初始值为空。3）如果OPE表为空，则失败退出。4）选择OPE上的第一个节点，把它从OPE中移入CLPSEP称该节点为n。5）如果n是目标节点，顺着G中，从n到no的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。26）扩展节点n,生成其后继结点集M在G中,n的祖先不能在M中。在G中安置M勺成员，使他
3、们成为n的后继。7）从M勺每一个不在G中的成员建立一个指向n的指针（例如，既不在OPE中,也不在CLOSED）。把M的这些成员加到OPE中。对M勺每一个已在OPE中或CLOSE中的成员m如果到目前为止找到的到达m勺最好路径通过n,就把它的指针指向n。对已在CLOSE中的M勺每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。8）按递增f*值，重排OPEN相同最小f*值可根据搜索树中的最深节点来解决）。9）返回第3步。在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。已经在CLOSE中
4、的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。实验步骤算法流程图14程序代码#inelude#include#ineludeusingnamespacestd;constintROW=3;/行数constintCOL=3;/列数constintMAXDISTANCE=10000;/最多可以有的表的数目constintMAXNUM=10000;typedefstruct_NodeintdigitROWCOL;intdist;/一个表和目的表的距离intdep;/t深度
5、intindex;/节点的位置Node;Nodesrc,dest;/父节表目的表vectornode_v;/存储节点boolisEmptyOfOPEN()/open表是否为空for(inti=0;inode_v.size();i+)if(node_vi.dist!=MAXNUM)returnfalse;returntrue;判断这个最优的节boolisEqual(intindex,intdigitCOL)/点是否和目的节点一样for(inti=0;iROW;i+)for(int
6、j=0;jCOL;j+)if(node_vindex.digitij!=digitij)returnfalse;returntrue;ostreamiROW;i+)for(intj=0;jCOL;j+)osnode.digitij;osendl;returnos;输出每一输出每一步的voidPrintSteps(intindex,vectorindex=node_vindex.index;while(index!=0)rstep_v.push_back(node_vind
7、ex);index=node_vindex.index;_for(inti=rstep_v.size()-1;i=0;i-)探索过程一coutSteprstep_v.size()-iendlrstep_viendl;voidSwap(intt=a;a=b;b=t;voidAssign(NodeiROW;i+)for(intj=0;jCOL;j+)node.digitij=node_vindex.digitij;即最优节点_intGetMinNode()/找
8、到最小的节点的位置intdist=MAXNUM;intloc;/thelocationofminimizenodefor(inti=0;inode_v.size();i+)_if(node_vi.dist=MAXNUM)continue;elseif(node_vi.dist+node_vi.dep)dist)loc=i;dist=node_vi.dist+node_vi.dep;一一returnloc;boolisExpandable(Nodeinode_v.size()
9、;i+)if(isEqual(i,node.digit)returnfalse;returntrue;intDistance(Nodeboolflag=false;for(inti=0;iROW;i+)for(intj=0;jCOL;j+)for(intk=0;kROW;k+)for(intl=0;lCOL;l+)if(node.digitij=digitkl)distanee+=abs(i-k)+abs(j-l);flag=true;break;els
10、eflag=false;if(flag)break;returndistanee;intMinDistance(inta,intb)return(aba:b);voidProcessNode(intindex)intx,y;boolflag;for(inti=0;iROW;i+)for(intj=0;j0)Swap(node_up.digitxy,node_up.digitx-1y);if(isExpandable(node_up)_dist_up=Dist
11、ance(node_up,dest.digit);node_up.index=index;node_up.dist=dist_up;node_up.dep=node_vindex.dep+1;node_v.push_back(node_up);Nodenode_down;Assign(node_down,index);/向下扩展的节点intdist_down二MAXDISTANCE;if(x0)Swap(node_left.digitxy,node_left.digitxy-1);if(isE
12、xpandable(node_left)dist_left=Distance(node_left,dest.digit);node_left.index=index;node_left.dist=dist_left;node_left.dep=node_vindex.dep+1;node_v.push_back(node_left);一一一Nodenode_right;Assign(node_right,index);/向右扩展的节点intdist_right=MAXDISTANCE;if(y2)
13、Swap(node_right.digitxy,node_right.digitxy+1);if(isExpandable(node_right)_dist_right=Distance(node_right,dest.digit);node_right.index=index;node_right.dist=dist_right;node_right.dep=node_vindex.dep+1;node_v.push_back(node_right);一一一node_vindex.dist=MA
14、XNUM;intmain()/主函数intnumber;coutInputsource:endl;for(inti=0;iROW;i+)/输入初始的表for(intj=0;jnumber;src.digitij=number;src.index=0;src.dep=1;coutInputdestination:endl;输入目的表for(intm=0;mROW;m+)for(intn二0;nnumber;dest.digitmn=number;
15、node_v.push_back(src);在容器的尾部加一个数据coutSearch.endl;clock_tstart=clock();while(1)if(isEmptyOfOPEN()coutCanntsolvethisstatement!endl;return-1;else卄intloc;/thelocationoftheminimizenode最优节点的位置loc=GetMinNode();if(isEqual(loc,dest.digit)vectorrstep_v;coutSou
16、rce:endl;coutsrcendl;PrintSteps(loc,rstep_v);coutSuccessful!endl;coutUsing(clock()-start)/CLOCKS_PER_SECseconds.endl;break;elseProcessNode(loc);return0;程序运行效果图28316475（初始状态）123804765（结束状态）r:C0DE(C+4)A星鸽法DebugA.MF：CODE(C+)A星賞法D亡bugA.*严*Step2203187G5HF:COOE(C++)A星算法D訪ugA.345286ts1o7Step5123804765Successful!Using0