人工智能A星算法.docx
《人工智能A星算法.docx》由会员分享，可在线阅读，更多相关《人工智能A星算法.docx（15页珍藏版）》请在冰点文库上搜索。
人工智能A星算法
A*算法实验报告
实验目的
1．熟悉和掌握启发式搜索的定义、估价函数和算法过程
2.学会利用A*算法求解N数码难题
3.理解求解流程和搜索顺序
实验原理
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。
对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。
因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：
从起始节点到节点n的代价以及从节点n到达目标节点的代价。
实验条件
1.WindowNT/xp/7及以上的操作系统
2.内存在512M以上
3.CPU在奔腾II以上
实验内容
1.分别以8数码和15数码为例实际求解A*算法
2.画出A*算法求解框图
3.分析估价函数对搜索算法的影响
4.分析A*算法的特点
实验分析
1.A*算法基本步骤
1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。
2）生成一个列表CLOSED，它的初始值为空。
3）如果OPEN表为空，则失败退出。
4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。
5）如果n是目标节点，顺着G中，从n到n0的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。
6）扩展节点n，生成其后继结点集M，在G中，n的祖先不能在M中。
在G中安置M的成员，使他们成为n的后继。
7）从M的每一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中，也不在CLOSED中）。
把M1的这些成员加到OPEN中。
对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止找到的到达m的最好路径通过n，就把它的指针指向n。
对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。
8）按递增f*值，重排OPEN（相同最小f*值可根据搜索树中的最深节点来解决）。
9）返回第3步。
在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。
已经在CLOSED中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。
实验步骤
算法流程图
程序代码
#include
#include
#include
usingnamespacestd;
constintROW=3;//行数
constintCOL=3;//列数
constintMAXDISTANCE=10000;//最多可以有的表的数目
constintMAXNUM=10000;
typedefstruct_Node{
intdigit[ROW][COL];
intdist;//一个表和目的表的距离
intdep;//t深度
intindex;//节点的位置
}Node;
Nodesrc,dest;//父节表目的表
vectornode_v;//存储节点
boolisEmptyOfOPEN（）//open表是否为空
{
for（inti=0;iif（node_v[i].dist!
=MAXNUM）
returnfalse;
}
returntrue;
}
boolisEqual（intindex,intdigit[][COL]）//判断这个最优的节点是否和目的节点一样
{
for（inti=0;ifor（intj=0;jif（node_v[index].digit[i][j]!
=digit[i][j]）
returnfalse;
}
returntrue;
}
ostream&operator<<（ostream&os,Node&node）
{
for（inti=0;ifor（intj=0;jos<os<}
returnos;
}
voidPrintSteps（intindex,vector&rstep_v）//输出每一个遍历的节点深度遍历
{
rstep_v.push_back（node_v[index]）;
index=node_v[index].index;
while（index!
=0）
{
rstep_v.push_back（node_v[index]）;
index=node_v[index].index;
}
for（inti=rstep_v.size（）-1;i>=0;i--）//输出每一步的探索过程
cout<<"Step"<<}
voidSwap（int&a,int&b）
{
intt;
t=a;
a=b;
b=t;
}
voidAssign（Node&node,intindex）
{
for（inti=0;ifor（intj=0;jnode.digit[i][j]=node_v[index].digit[i][j];
}
intGetMinNode（）//找到最小的节点的位置即最优节点
{
intdist=MAXNUM;
intloc;//thelocationofminimizenode
for（inti=0;i{
if（node_v[i].dist==MAXNUM）
continue;
elseif（（node_v[i].dist+node_v[i].dep）loc=i;
dist=node_v[i].dist+node_v[i].dep;
}
}
returnloc;
}
boolisExpandable（Node&node）
{
for（inti=0;iif（isEqual（i,node.digit））
returnfalse;
}
returntrue;
}
intDistance（Node&node,intdigit[][COL]）
{
intdistance=0;
boolflag=false;
for（inti=0;ifor（intj=0;jfor（intk=0;kfor（intl=0;lif（node.digit[i][j]==digit[k][l]）{
distance+=abs（i-k）+abs（j-l）;
flag=true;
break;
}
else
flag=false;
}
if（flag）
break;
}
returndistance;
}
intMinDistance（inta,intb）
{
return（aa:
b）;
}
voidProcessNode（intindex）
{
intx,y;
boolflag;
for（inti=0;ifor（intj=0;jif（node_v[index].digit[i][j]==0）
{
x=i;y=j;
flag=true;
break;
}
elseflag=false;
}
if（flag）
break;
}
Nodenode_up;
Assign（node_up,index）;//向上扩展的节点
intdist_up=MAXDISTANCE;
if（x>0）
{
Swap（node_up.digit[x][y],node_up.digit[x-1][y]）;
if（isExpandable（node_up））
{
dist_up=Distance（node_up,dest.digit）;
node_up.index=index;
node_up.dist=dist_up;
node_up.dep=node_v[index].dep+1;
node_v.push_back（node_up）;
}
}
Nodenode_down;
Assign（node_down,index）;//向下扩展的节点
intdist_down=MAXDISTANCE;
if（x<2）
{
Swap（node_down.digit[x][y],node_down.digit[x+1][y]）;
if（isExpandable（node_down））
{
dist_down=Distance（node_down,dest.digit）;
node_down.index=index;
node_down.dist=dist_down;
node_down.dep=node_v[index].dep+1;
node_v.push_back（node_down）;
}
}
Nodenode_left;
Assign（node_left,index）;//向左扩展的节点
intdist_left=MAXDISTANCE;
if（y>0）
{
Swap（node_left.digit[x][y],node_left.digit[x][y-1]）;
if（isExpandable（node_left））
{
dist_left=Distance（node_left,dest.digit）;
node_left.index=index;
node_left.dist=dist_left;
node_left.dep=node_v[index].dep+1;
node_v.push_back（node_left）;
}
}
Nodenode_right;
Assign（node_right,index）;//向右扩展的节点
intdist_right=MAXDISTANCE;
if（y<2）
{
Swap（node_right.digit[x][y],node_right.digit[x][y+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_v[index].dep+1;
node_v.push_back（node_right）;
}
}
node_v[index].dist=MAXNUM;
}
intmain（）//主函数
{
intnumber;
cout<<"Inputsource:
"<for（inti=0;ifor（intj=0;jcin>>number;
src.digit[i][j]=number;
}
src.index=0;
src.dep=1;
cout<<"Inputdestination:
"<for（intm=0;mfor（intn=0;ncin>>number;
dest.digit[m][n]=number;
}
node_v.push_back（src）;//在容器的尾部加一个数据
cout<<"Search..."<clock_tstart=clock（）;
while
（1）
{
if（isEmptyOfOPEN（））
{
cout<<"Cann'tsolvethisstatement!
"<return-1;
}
else
{
intloc;//thelocationoftheminimizenode最优节点的位置
loc=GetMinNode（）;
if（isEqual（loc,dest.digit））
{
vectorrstep_v;
cout<<"Source:
"<cout<PrintSteps（loc,rstep_v）;
cout<<"Successful!
"<cout<<"Using"<<（clock（）-start）/CLOCKS_PER_SEC
<<"seconds."<break;
}
else
ProcessNode（loc）;
}
}
return0;
}
程序运行效果图
2
8
3
1
6
4
7
5
（初始状态）
1
2
3
8
0
4
7
6
5
（结束状态）
个人实验小结
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。
对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。
通过本实验，我熟悉启发式搜索的定义、估价函数和算法过程，并利用A*算法求解了8数码难题，理解了求解流程和搜索顺序。
实验过程中巩固了所学的知识，通过实验也提高了自己的编程和思维能力，收获很多。
Welcome
欢迎您的下载，
资料仅供参考！
升级会员 