用A星算法解决八数码问题

A*算法解决八数码问题1问题描述1.1什么是八数码问题八数码游戏包括一个3×3的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。与空位相邻的棋子可以滑动到空位中。游戏的目的是要达到一个特定的目标状态。标注的形式化如下：123456781.2问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。初始状态：任何状态都可以被指定为初始状态。操作符：用来产生4个行动（上下左右移动）。目标测试：用来检测状态是否能匹配上图的目标布局。路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。1.3解决方案介绍1.3.1算法思想估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。估价值h(n)=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。1.3.2启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h(n)为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有h(t)=0，对于结点m和n（n是m的子结点）有h(m)–h(n)=1=Cost(m,n)满足单调限制条件。2算法介绍2.1A*算法的一般介绍A*（A-Star)算法是一种静态路网中求解最短路最有Astar算法在静态路网中的应用效的方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。2.2算法伪代码创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。while(OPEN!=NULL){从OPEN表中取估价值f最小的节点n;if(n节点==目标节点){break;}for(当前节点n的每个子节点X){算X的估价值;if(XinOPEN){if(X的估价值小于OPEN表的估价值){把n设置为X的父亲;更新OPEN表中的估价值;//取最小路径的估价值}}if(XinCLOSE){if(X的估价值小于CLOSE表的估价值){把n设置为X的父亲;更新CLOSE表中的估价值;把X节点放入OPEN//取最小路径的估价值}}if(Xnotinboth){把n设置为X的父亲;求X的估价值;并将X插入OPEN表中;//还没有排序}}//endfor将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。}//endwhile(OPEN!=NULL)保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；3算法实现3.1实验环境与问题规模对于８数码问题，每个结点有８个数字和一个空格，可以将空格看成０，那么一共有９个数字，３２位的int可以表示２*109，可以用一个整数表示一个结点对应的信息。计算一个整数中０（即空格）的位置比较耗时间，用一个整数存储当前结点０的位置，还要存储对应的g,h值以及该结点由哪个结点扩展来的信息。本实验用C++编写源程序，环境选用VisualStudio2005。程序采用文本输入输出，输入文件为astar.in，A*算法输出文件为astar.out，可以用记事本打开。输入格式为一个测试用例由两个中间由一空行隔开的８数码格局组成，输出为对应测试用例的走法路径及相关统计信息，程序假定输入数据符合要求，未做检查。3.2数据结构3.2.1open表的数据结构表示考虑对open表的操作，每次需要得到所有待扩展结点中f值最小的那个结点，用堆进行实现，可以达到O(log(heapSize))时间复杂度。3.2.2closed表的数据结构表示closed表存储已扩展的结点间的扩展关系，主要用于输出路径。考虑结点扩展的操作，设待扩展的结点为m，由它扩展生成的结点为n1,n2,…。结点m扩展完成后被放到closed表中，放入后它在closed表中位置不发生变化，可以将n1,n2,…的前驱结点置为m在closed表中的位置，当n1,n2,..中有结点设为n1被扩展放入closed表时，n1的前驱刚好已经存储好。下面说明closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱结点的下标位置，可以用数组实现，每个结点记录整数表示的８数码格局和它的前驱结点的下标，输出路径时，根据前驱结点形成到达根结点的链条，递归输出即可。3.2.3解决结点重复扩展问题对于一个结点有多种方式到达该结点，这样就可能多次将它加入open表中，而启发函数满足单调限制条件，后来达到该结点的路径不再是更优的，可以不予考虑。扩展某结点时先看该结点是否已经扩展过，如果扩展过则略过。实现的可以线形遍历closed表，但效率不高时间复杂度为O(closedSize)，考虑每个结点可以用一个整数标识，用二叉平衡查找树可以得到更好的时间复杂度O(log(closedSize))，程序中用基于红黑树思想的set实现。3.3实验结果输入数据（0表示空格）步数扩展结点数生成结点数搜索用时(毫秒)31240567825110312475680417280372815460无解123456780227943120192266参考文献王勋，凌云，费玉莲.2005.人工智能导论.北京：科学出版社广树建，王钰淇.2008.新编C/C++程序设计教程.广州：华南理工大学出版社王文杰，史忠植.2007.人工智能原理辅导与练习.北京：清华大学出版社出附录—源代码及其注释源代码及测试数据/*算法：A*是否最优解：是启发函数：每一个数字位与目标中该数字位的距离，满足单调限制。说明：A*算法是启发式搜索算法，搜索时充分利用当前状态距目标距离远近的启发信息，选取当前未扩展结点中估价函数最小的进行扩展，生成结点数少，搜索空间较小，实现稍复杂，备注：程序未对输入数据进行检查*/#pragmawarning(disable:4786)#includealgorithm#includecstdio#includeset#includeutility#includectime#includecassert#includecstringusingnamespacestd;/*item记录搜索空间中一个结点state记录用整数形式表示的8数码格局blank记录当前空格位置，主要用于程序优化，扩展时可不必在寻找空格位置g,h对应g(n),h(n)pre记录当前结点由哪个结点扩展而来*/structitem{intstate;intblank;intg;inth;intpre;};constintMAXSTEPS=100000;constintMAXCHAR=100;charbuf[MAXCHAR][MAXCHAR];//open表itemopen[MAXSTEPS];intsteps=0;//closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径//每次只需得到对应f值最小的待扩展结点，用堆实现提高效率pairint,intclosed[MAXSTEPS];//读入，将8数码矩阵格局转换为整数表示boolread(pairint,int&state){if(!gets(buf[0]))returnfalse;if(!gets(buf[1]))returnfalse;if(!gets(buf[2]))returnfalse;assert(strlen(buf[0])==5&&strlen(buf[1])==5&&strlen(buf[2])==5);state.first=0;for(inti=0,p=1;i3;++i){for(intj=0;j6;j+=2){if(buf[i][j]=='')state.second=i*3+j/2;elsestate.first+=p*(buf[i][j]-'0');p*=10;}}returntrue;}/*intcalculate(intcurrent,inttarget){intcnt=0;for(inti=0;i9;++i){if((current%10!=0)&&(current%10)!=(target%10))++cnt;current/=10;target/=10;}returncnt;}*///计算当前结点距目标的距离intcalculate(intcurrent,inttarget){intc[9],t[9];inti,cnt=0;for(i=0;i9;++i){c[current%10]=t[target%10]=i;current/=10;target/=10;}for(i=1;i9;++i)cnt+=abs(c[i]/3-t[i]/3)+abs(c[i]%3-t[i]%3);returncnt;}//open表中结点间选择时的规则f(n)=g(n)+h(n)classcmp{public:inlinebooloperator()(itema,itemb){returna.g+a.hb.g+b.h;}};//将整数形式表示转换为矩阵表示输出voidpr(intstate){memset(buf,'',sizeof(buf));for(inti=0;i3;++i){for(intj=0;j6;j+=2){if(state%10)buf[i][j]=state%10+'0';state/=10;}buf[i][5]='\0';puts(buf[i]);}}//用于判断当前空格是否可以向对应方向移动inlineboolsuit(inta,intb){return(a=0&&a3&&b=0&&b3);}//递归输出搜索路径voidpath(intindex){if(index==0){pr(closed[index].first);puts();return;}path(closed[index].second);pr(closed[index].first);puts();++steps;}intmain(){unsignedintt1=clock();freopen(astar.in,r,stdin);freopen(astar2.out,w,stdout);setintstates;chartmp[100];inti,x,y,a,b,nx,ny,end,next,index,kase=0;pairint,intstart,target;itemhead;//4个方向移动时的偏移量constintxtran[4]={-1,0,1,0};constintytran[4]={0,1,0,-1};constintp[]={1,10,100,1000,10000,100000,1000000,10000000,