A星八数码求解资料讲解.docx
《A星八数码求解资料讲解.docx》由会员分享，可在线阅读，更多相关《A星八数码求解资料讲解.docx（14页珍藏版）》请在冰点文库上搜索。
A星八数码求解资料讲解
A星八数码求解
实验二A*算法实验I
软工1303201326811825朱镇洋
一、实验目的：
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。
二、实验原理：
A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。
对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。
因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：
从起始节点到节点n的实际代价以及从节点n到达目标节点的估价代价。
三、实验内容：
1 问题描述。
八数码问题:
在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8，其中一个单元格是空的。
将任意摆放的数码盘（初始状态）逐步摆成某个指定的数码盘的排列（目标状态）：
1
2
4
3
5
6
7
8
2
1
3
4
5
6
7
8
N个步骤
目标状态
起始状态
2 设计两种不同的估价函数。
w（n）；w表示不在目标位置的节点数
h（n）=d（n）+；d（n）表示深度
p（n）；p表示所有点到其目标节点的步数总和
算法流程图：
3 在求解8数码问题的A*算法程序中，设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解
令初始状态都为：
023415687目标状态为：
123405678
通过程序运行结果我们可以发现，上述两种估价函数中明显第二种在算法效率上更具优势，第一种估价函数要通过18步才能到达目标状态，通过中间变量记录扩展节点和生成节点有1062个：
而第二种估价函数只要16步即可到达目标状态，也意味着扩展节点和生成节点只有654个，比第一种少了很多：
原因分析：
通过实验结果也说明了估计函数对启发式搜索算法的重要影响，因为第二种估价函数p（n）是节点与目标节点相比所需移动次数的总和，与第一种估价函数w（n）（只考虑错误位数）相比，p（n）不仅考虑了错位信息，还考虑了错位的距离，比w（n）更完美，所以它的执行效率更高。
4启发式算法特点。
启发式搜索算法的基本思想是：
定义一个估价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。
先定义下面几个函数的含义：
f*（n）=g*（n）+h*（n）式中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（x）为启发函数的A算法，称为A*算法。
5扩展。
稍微改进了给定的算法，给定的算法中时在求解之后才确定是否有解，而其实判断一个八数码是否有解在输入时即可判断出该是否有解。
只要将每位上（除了空格）的特定值（此位之前比该数小的个数）相加，如果得数为偶数，那么可以确定最后有解，否则无解。
所以可以在每次输入时判断是否有解，而不必在计算完再确定是否有解，这样在算法的时间复杂度上有很大的提升，该段代码如下：
if（!
pq.empty（））
{
intflag=0;
cur=pq.top（）;
for（inti=0;i<9;i++）
{
for（intj=0;j{
if（cur.s[i]=='0'||cur.s[j]=='0'）
continue;
else{
if（cur.s[j]flag++;
}
}
}
if（flag%2!
=0）
return-1;//搜索失败
}
6源程序（采用上述中更高效的第二种估价函数）。
//************************************
//*八数码问题
//************************************
#include
#include
#include
#include
#include
usingnamespacestd;
structP{
intd;//深度g（n）
intw;//不在位数h（n）
intid;//记录该节点的id，用于输出时找到该节点
strings;//状态
friendbooloperator<（constP&a,constP&b）{//按f（n）=g（n）+h（n）大小排序
returna.d+a.w>b.d+b.w;//最大堆
}
}p;
constintN=3;//棋盘大小
conststringt="123405678";//目标状态
stringstack[1000000];//记录搜索中的节点
stringrecord[1000000];//从起点开始记录解路径
intfather[10000000];//记录该节点的父节点
inttop=0;//stack的指针
priority_queue
pq;//open表
mapmp;//记录该状态是否已经访问过：
1访问过，0没有
intcalw（strings）//计算该状态的不在位数h（n）
{
intre=0;
for（inti=0;i<9;i++）
{
re+=abs（s[i]-t[i]）;
}
returnre;
}
intsolve（int&num）//搜索过程
{
Pcur;
if（!
pq.empty（））
{
intflag=0;
cur=pq.top（）;
for（inti=0;i<9;i++）
{
for（intj=0;j{
if（cur.s[i]=='0'||cur.s[j]=='0'）
continue;
else{
if（cur.s[j]flag++;
}
}
}
if（flag%2!
=0）
return-1;//搜索失败
}
while（!
pq.empty（））{
num++;
cur=pq.top（）;//open表
pq.pop（）;
if（cur.s==t）returncur.id;//达到目标状态，返回当前节点的id
intx,y;
intops=0;
while（cur.s[ops]!
='0'）ops++;
x=ops/3,y=ops%3;//空格所在位置
intr=cur.id;
if（x>0）{//空格向上移
p.s=cur.s;
swap（p.s[ops],p.s[ops-3]）;
if（!
mp[p.s]）{
p.d=cur.d+1,p.w=calw（p.s）,p.id=top+1;
pq.push（p）;
stack[++top]=p.s;
father[top]=r;
mp[p.s]=1;
}
}
if（x<2）{//空格向下移
p.s=cur.s;
swap（p.s[ops],p.s[ops+3]）;
if（!
mp[p.s]）{
p.d=cur.d+1,p.w=calw（p.s）,p.id=top+1;
pq.push（p）;
stack[++top]=p.s;
father[top]=r;
mp[p.s]=1;
}
}
if（y>0）{//空格向左移
p.s=cur.s;
swap（p.s[ops],p.s[ops-1]）;
if（!
mp[p.s]）{
p.d=cur.d+1,p.w=calw（p.s）,p.id=top+1;
pq.push（p）;
stack[++top]=p.s;
father[top]=r;
mp[p.s]=1;
}
}
if（y<2）{//空格向右移
p.s=cur.s;
swap（p.s[ops],p.s[ops+1]）;
if（!
mp[p.s]）{
p.d=cur.d+1,p.w=calw（p.s）,p.id=top+1;
pq.push（p）;
stack[++top]=p.s;
father[top]=r;
mp[p.s]=1;
}
}
}
}
voidprint（intx）////从record表中输出当前搜索的节点
{
intk=0;
for（inti=0;ifor（intj=0;jif（record[x][k]=='0'）
printf（""）;
elseprintf（"%c",record[x][k]）;
k++;
}
printf（"\n"）;
}
printf（"\n"）;
}
intmain（）
{
//freopen（"a.txt","r",stdin）;
inttt;//测试的组数
cin>>tt;
for（intk=1;k<=tt;k++）{
cout<<"Case"<\n";
inti,j;
chara;
p.s="";
for（i=0;ifor（j=0;jcin>>a;//输入0?
8数码
p.s+=a;
}
}
p.d=0,p.w=calw（p.s）,p.id=0;
father[0]=-1;
mp[p.s]=1;
stack[0]=p.s;
pq.push（p）;//往open表中加入初始状态节点
intnum=0;
intid=solve（num）;//调用搜索过程
if（id==-1）{
cout<<"无解！
\n";
}else{
intc=-1;
while（id>=0）{//把stack中存的节点按次序放入到record中
record[++c]=stack[id];
id=father[id];
}
cout<<"原图：
"<print（c）;//输出初始节点
cout<<"移动过程:
\n\n";
for（i=c-1;i>=0;i--）{
cout<<"Step"<\n";//输出当前搜索步骤
print（i）;//输出当前搜索的节点
}
cout<<"移动结束！
\n";
}
mp.clear（）;
while（!
pq.empty（））pq.pop（）;
top=0;
cout<"<cout<}
system（"pause\n"）;
return0;
}
第一种估价函数源代码：
intcalw（strings）//计算该状态的不在位数h（n）
{
intre=0;
for（inti=0;i<9;i++）if（s[i]!
=t[i]）re++;
returnre;
}
三、实验小结：
通过此次实验，我对启发式搜索有了更深的了解，在处理该实验时，给定的两种估价函数差别不大都可以接受，但如果处理一些复杂的问题，第二种估价函数显然更为优秀，可以避免不必要的扩展。
升级会员 