《A星八数码求解》由会员分享，可在线阅读，更多相关《A星八数码求解（10页珍藏版）》请在金锄头文库上搜索。
1、实验二 A*算法实验I软工1303 201326811825 朱镇洋一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。二、实验原理：A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价以及从节点n到达目标节点的估价代价。三、实验内容：1问题描述。八数码问题:在一个33的方阵中放入八个数码1、2、3、4、5、6、7、8，其中
2、一个单元格是空的。将任意摆放的数码盘（初始状态）逐步摆成某个指定的数码盘的排列（目标状态）：1243567821345678N个步骤目标状态起始状态2设计两种不同的估价函数。w(n) ；w表示不在目标位置的节点数h(n)=d(n)+ ；d(n)表示深度p(n) ；p表示所有点到其目标节点的步数总和算法流程图：3在求解8数码问题的A*算法程序中，设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解令初始状态都为：023415687 目标状态为：123405678通过程序运行结果我们可以发现，上述两种估价函数中明显第二种在算法效率上更具优势，第一种估价函数要通过18步才能到达目标状态，通
3、过中间变量记录扩展节点和生成节点有1062个：而第二种估价函数只要16步即可到达目标状态，也意味着扩展节点和生成节点只有654个，比第一种少了很多：原因分析：通过实验结果也说明了估计函数对启发式搜索算法的重要影响，因为第二种估价函数p(n)是节点与目标节点相比所需移动次数的总和，与第一种估价函数w(n)（只考虑错误位数）相比，p(n)不仅考虑了错位信息，还考虑了错位的距离，比w(n)更完美，所以它的执行效率更高。4 启发式算法特点。启发式搜索算法的基本思想是：定义一个估价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。先定义下面几个函数的含义： f*(n)=g*(n)+h*(n
4、) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。估价函数的形式可定义如下式所示： f(n)=g(n)+h(n) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。利用估价函数f(n)=g(n)+h(n)来排列open表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x， h(x)=h*(x) 成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h
5、(x)为启发函数的A算法，称为A*算法。5 扩展。稍微改进了给定的算法，给定的算法中时在求解之后才确定是否有解，而其实判断一个八数码是否有解在输入时即可判断出该是否有解。只要将每位上（除了空格）的特定值（此位之前比该数小的个数）相加，如果得数为偶数，那么可以确定最后有解，否则无解。所以可以在每次输入时判断是否有解，而不必在计算完再确定是否有解，这样在算法的时间复杂度上有很大的提升，该段代码如下：if(!pq.empty()int flag=0;cur=pq.top();for(int i=0;i9;i+)for(int j=0;ji;j+)if(cur.si=0|cur.sj=0)contin
6、ue;elseif(cur.sjcur.si)flag+;if(flag%2!=0)return -1; /搜索失败6 源程序（采用上述中更高效的第二种估价函数）。/*/*八数码问题/*#include#include#include#include#includeusing namespace std;struct P int d;/深度g(n) int w;/不在位数h(n) int id;/记录该节点的id，用于输出时找到该节点 string s;/状态 friend bool operator b.d+b.w; /最大堆 p;const int N=3;/棋盘大小const strin
7、g t=123405678;/目标状态string stack1000000;/记录搜索中的节点string record1000000;/从起点开始记录解路径int father10000000;/记录该节点的父节点int top=0;/stack的指针priority_queue pq;/open表map mp;/记录该状态是否已经访问过：1访问过，0没有int calw(string s)/计算该状态的不在位数h(n) int re=0; for(int i=0;i9;i+)re+=abs(si-ti); return re;int solve(int& num)/搜索过程 P cur;
8、if(!pq.empty()int flag=0;cur=pq.top();for(int i=0;i9;i+)for(int j=0;ji;j+)if(cur.si=0|cur.sj=0)continue;elseif(cur.sj0) /空格向上移 p.s=cur.s; swap(p.sops,p.sops-3); if(!mpp.s) p.d=cur.d+1,p.w=calw(p.s),p.id=top+1; pq.push(p); stack+top=p.s; fathertop=r; mpp.s=1; if(x0) /空格向左移 p.s=cur.s; swap(p.sops,p.so
9、ps-1); if(!mpp.s) p.d=cur.d+1,p.w=calw(p.s),p.id=top+1; pq.push(p); stack+top=p.s; fathertop=r; mpp.s=1; if(y2) /空格向右移 p.s=cur.s; swap(p.sops,p.sops+1); if(!mpp.s) p.d=cur.d+1,p.w=calw(p.s),p.id=top+1; pq.push(p); stack+top=p.s; fathertop=r; mpp.s=1; void print(int x)/从record表中输出当前搜索的节点 int k=0; for(int i=0;iN;i+) for(int j=0;jN;j+) if(recordxk=0) printf( ); else printf(%c ,recordxk); k+; printf(n); printf(n);int
