Astar算法.docx
《Astar算法.docx》由会员分享，可在线阅读，更多相关《Astar算法.docx（21页珍藏版）》请在冰点文库上搜索。
Astar算法
HarbinInstituteofTechnology
研究生课程实验报告
2011年春季学期
科目：
人工智能
学生所在院系：
计算机科学与技术
学生所在学科：
计算机应用技术
报告题目：
搜索算法实验
姓名：
黄磊
学号：
10SD03008
学生类别：
代培生
搜索算法实验
——使用A*算法解决八数码问题
1问题描述
1.1待解决问题的解释
有一个3×3的棋盘，其中有0～8九个数字，0表示空格，其他的数字可以和0交换位置。
问题：
要求给定一种初始的布局或结构（称初始状态）和一个目标布局（称目标状态），问如何移动数码实现从初始状态到目标状态的转变，问题的实质就是寻找一个合法的动作序列，如下图所示
图1八数码问题的一实例图解
1.2问题的搜索形式描述（4要素）
初始状态：
初始状态向量—规定向量中各分量对应的位置，各位置上的初始数字。
后继函数：
移动规则——按照某条规则移动数字，将得到的新向量。
目标测试：
新向量是否是目标状态（也是向量形式）。
路径耗散函数：
每次移动代价为1。
1.3解决方案介绍（原理）
A*算法在人工智能中是基于A算法的一种典型的启发式搜索，主要是对估价函数加以特别的定义和描述时，从而得到一种具有较强的启发能力的有序搜索法，A*搜索的评价函数为f（n）=g（h）+h（n）
•g（n）是从初始节点到该节点n的路径耗散，h（n）是从节点n到目标节点的最低耗散路径的估计耗散值，称为启发式或启发函数；
•f（n）=经过节点n具有最低耗散值的解的估计耗散，找到g（n）+h（n）值最小的节点进行搜索；
•若启发函数h（n）满足一定条件，则A*搜索是完备的和最优的；
具体的算法过程如下：
算法流程图如下图所示：
图2A*算法流程图
2算法介绍
2.1搜索算法一般介绍
启发式搜索是利用问题拥有启发信息引导搜索，以达到减小搜索范围、降低问题复杂度的目的。
在启发式搜索过程中要对Open表进行排序，这就要有一种方法来计算待扩展结点有希望通向目标结点的不同程度，人们总是希望能找到最有可能通向目标结点的待扩展结点优先扩展。
一种最常用的方法是定义一个评价函数对各个结点进行计算,其目的就是用来估算出“有希望”的结点。
用f来标记评价函数,用f（n）表示结点n的评价函数值,并用f来排列等待扩展的结点,然后选择具有最小f值的结点，选取f值最小的结点作为下一个要扩展的结点。
A*算法是一种有序搜索算法,其特点在于对评函数的定义上。
这个评价函数f使得在任意结点上其函数值f（n）能估算出从结点S到结点n的最小代价路径的代价与从结点n到某一目标结点的最小代价路径的代价的总和，也就是说f（n）是约束通过结点n的一条最小代价路径的代价的一个估计。
再定义一个函数f*使得在任意一个结点n上的函数值f*（n）就是从结点S到结点n的一条最佳路径的实际代价加上从结点n到目标结点的一条最佳路径的代价之和，即
f*（n）=g*（n）+h*（n）
评价函数f是f*的一个估计,这个估计可由下式给出:
f（n）=g（n）+h（n）
其中g是g*的估计;h是h*的估计。
对g*（n）的估计g（n）的选择就是搜索树中从S到n的这段路径的代价,这一代价可以由从n到S寻找指针时,把遇到的各段路径的代价加起来给出。
h*（n）的估计h（n）依赖于有关问题的领域的启发信息,于是称作启发函数。
在启发函数中,应用的启发信息（问题知识）越多,扩展的结点就越少,这样就能更快地搜索到目标结点。
本实验中运用的是下面这种评价函数:
f（n）=g（n）+h（n）
其中,g（n）代表搜索树中结点n的深度,根结点深度是0。
启发函数h（n）定义为结点n的状态和目标状态的不同位置的个数即错位数。
2.2算法伪代码
创建三个表，OPEN表保存所有已生成而未扩展的结点，CLOSED表中记录已扩展过的结点，SON表保存节点扩展的子节点。
计算起始结点的估价值，并将其放入OPEN表中;
while（OPEN!
=NULL）
{
从OPEN表中取估价值f最小的结点n;
if（n结点==目标结点）{
break;
}
计算节点n的子节点并存入表SON中；
for（表SON中的每个节点X）
{
计算X的估价值;
if（Xnotinboth）{
把n设置为X的父亲;
并将X插入OPEN表中;//未排序
}
if（XinOPEN）
{
if（X的估价值小于OPEN表中相同节点的估价值）{
把n设置为X的父亲;
更新OPEN表中的估价值;//取最小路径的估价值
}
}
if（XinCLOSE）{
if（X的估价值小于CLOSE表中相同节点的估价值）{
n设置为X的父亲;
更新CLOSE表中的估价值;
把X结点放入OPEN//取最小路径的估价值
}
}
}//endfor
将n结点插入CLOSE表中；
估价值将OPEN表中的结点排序；
}//endwhile（OPEN!
=NULL）
利用所求节点间的关系输出搜索过程。
3算法实现
3.1实验环境与问题规模
Myeclipse
3.2数据结构
classEightDigital{//8数码类
inte[][]=newint[3][3];
intfa,fa;//保存父状态中0的位置
intf;//评价函数
intdepth;//深度
EightDigitalparent;//指向父节点,搜索完毕后输出
publicEightDigital（）{//无参构造
fa=-1;
fa=-1;
f=-1;
depth=0;
parent=null;
}
publicEightDigital（inta[][]）{//有参构造
for（inti=0;i<3;i++）
for（intj=0;j<3;j++）{
e[i][j]=a[i][j];
}
fa=-1;
fb=-1;
f=-1;
depth=0;
parent=null;
}
publicEightDigital（EightDigitalother）{//有参构造
for（inti=0;i<3;i++）
for（intj=0;j<3;j++）{
e[i][j]=other.e[i][j];
}
fa=other.faX;
fa=other.faY;
f=other.f;
depth=other.depth;
parent=other.parent;
}
}
3.3实验结果
本程序主要是用A*算法来搜索八数码问题的最优解。
通过输入大量的初始状态和目标状态发现在一般情况下都可以找到最优的动作序列,但对某些复杂的初始状态虽能得到正确解却不能完全得到最短的搜索路径。
这是有待改进的地方。
3.4系统中间及最终输出结果（要求有屏幕显示）
（1）初始状态和目标状态的输入:
初始状态:
initial[][]={{2,3,4},{1,8,5},{0,7,6}}
目标状态:
dest[][]={{1,2,3},{8,0,4},{7,6,5}}
（2）求解步骤显示:
图3求解过程一
图4求解过程二
参考文献
[1]朱永红,张燕平.用VC++实现基于A*算法的八数码问题.计算机技术与发展.2006（9）.
[2]胡敏杰.A*算法的探讨及其对八数码问题的实现.漳州师范学院学报.2005（3）.
附录—源代码及其注释
packagehaha;
classEightDigital{//8数码类
inte[][]=newint[3][3];
intfaX,faY;//保存父状态中0的位置
intf;//评价函数
intdepth;//深度
EightDigitalformer;//指向父节点,搜索完毕后输出
publicEightDigital（）{//无参构造
faX=-1;
faY=-1;
f=-1;
depth=0;
former=null;
}
publicEightDigital（inta[][]）{//有参构造
for（inti=0;i<3;i++）
for（intj=0;j<3;j++）{
e[i][j]=a[i][j];
}
faX=-1;
faY=-1;
f=-1;
depth=0;
former=null;
}
publicEightDigital（EightDigitalother）{//有参构造
for（inti=0;i<3;i++）
for（intj=0;j<3;j++）{
e[i][j]=other.e[i][j];
}
faX=other.faX;
faY=other.faY;
f=other.f;
depth=other.depth;
former=other.former;
}
publicvoidprint（）{//打印一个节点
for（inti1=0;i1<3;i1++）
for（intj1=0;j1<3;j1++）{
System.out.print（e[i1][j1]）;
if（j1==2）
System.out.println（""）;
}
}
publicvoidlistAll（EightDigitale）{//打印整个搜索状态过程
System.out.println（"=====目标8数码========"）;
e.print（）;
while（e.former!
=null）{
System.out.println（"<=====第"+e.depth+"步推导========"）;
e.former.print（）;
e=newEightDigital（e.former）;
}
return;
}
}
classQueue{//队列类,用于保存open-list表和close-list表
privateintsize;
EightDigitalqe[]=newEightDigital[200];
publicvoidprint（）{
for（inti=0;iqe[i].print（）;
}
publicvoidaddElement（EightDigitale）{//增加节点到列队中
if（size>=100）
{
System.out.println（"open/close表空间不够"）;
System.exit
（1）;
}
qe[size]=e;
size++;
}
publicbooleancontains（EightDigitale）{//是否包含节点e
if（size==0）
returnfalse;
else{
for（inti=0;iif（qe[i].equals（e））
returntrue;
}
}
returnfalse;
}
publicbooleanisEmpty（）{//判断队列是否为空
if（size==0）{
returntrue;
}
elsereturnfalse;
}
publicEightDigitalelementAt（intindex）{
returnqe[index];
}
publicvoidsetElementAt（EightDigitale,intindex）{
qe[index]=e;
}
publicintsize（）{
returnsize;
}
publicintindexOf（EightDigitale）{
for（inti=0;iif（qe[i].equals（e））
returni;
}
return-1;
}
publicvoidremoveFirst（）{
for（inti=0;iqe[i]=qe[i+1];
}
size--;
}
publicvoidremove（EightDigitale）{
for（inti=0;iif（qe[i].equals（e））
qe[i]=null;
}
size--;
}
publicvoidremoveAllElements（）{
for（inti=0;iqe[i]=null;
}
size=0;
}
}
//算法实现类
publicclassAsearch{
staticintdest[][]={{1,2,3},{8,0,4},{7,6,5}};
staticvoidSwap（EightDigitalee,inti,intj,intm,intn）{//交换
inttemp;
temp=ee.e[i][j];
ee.e[i][j]=ee.e[m][n];
ee.e[m][n]=temp;
}
staticintcompare（EightDigitala）{//计算h（）---启发式函数（用与目标数码之间的错位数表示）
inth=0,i,j;
for（i=0;i<3;i++）
for（j=0;j<3;j++）{
if（a.e[i][j]!
=dest[i][j]）
h++;
}
returnh;
}
staticQueueborn（EightDigitale）{//产生e的后继结点
intm=1,n=1,i=0,j=0;
booleanflag=true;
Queuesons=newQueue（）;
for（i=0;i<3&&flag;i++）
for（j=0;j<3&&flag;j++）{
if（e.e[i][j]==0）{
flag=false;
break;
}
}
i--;
if（i-1>=0）{
m=i-1;
if（m!
=e.faX）{
Swap（e,m,j,i,j）;
//e.print（）;
EightDigitalson1=newEightDigital（e）;
son1.faX=i;
son1.faY=j;
son1.former=e;
son1.depth=e.depth+1;
sons.addElement（son1）;
Swap（e,i,j,m,j）;
}
}
if（i+1<3）{
m=i+1;
if（m!
=e.faX）{
Swap（e,m,j,i,j）;
//e.print（）;
EightDigitalson2=newEightDigital（e）;
son2.faX=i;
son2.faY=j;
son2.former=e;
son2.depth=e.depth+1;
sons.addElement（son2）;
Swap（e,i,j,m,j）;
}
}
if（j-1>=0）{
n=j-1;
if（n!
=e.faY）{
Swap（e,i,n,i,j）;
//e.print（）;
EightDigitalson3=newEightDigital（e）;
son3.faX=i;
son3.faY=j;
son3.former=e;
son3.depth=e.depth+1;
sons.addElement（son3）;
Swap（e,i,j,i,n）;
}
}
if（j+1<3）{
n=j+1;
if（n!
=e.faY）{
Swap（e,i,n,i,j）;
//e.print（）;
EightDigitalson4=newEightDigital（e）;
son4.faX=i;
son4.faY=j;
son4.former=e;
son4.depth=e.depth+1;
sons.addElement（son4）;
Swap（e,i,j,i,n）;
}
}
returnsons;
}
publicstaticvoidmain（String[]args）{
inta[][]={{2,3,4},{1,8,5},{0,7,6}};//初始8数码状态
EightDigitaln=newEightDigital（a）;
EightDigitaltemp1=newEightDigital（）,temp2=newEightDigital（）;
//open表
Queueopen=newQueue（）;
//closed表
Queueclosed=newQueue（）;
//保存后继结点的表
Queueson=newQueue（）;
open.addElement（n）;
while（!
open.isEmpty（））{
n=open.elementAt（0）;
open.removeFirst（）;
if（compare（n）==0）{
n.listAll（n）;
System.out.println（"成功!
"）;
return;
}
son=born（n）;//扩展Best-node节点生成后继结点
intcount=son.size（）;
if（count==0）
continue;
elsefor（intt=0;ttemp1=son.elementAt（t）;
if（!
open.contains（temp1）&&!
closed.contains（temp1））{
//不属于Open-list也不属于Closed-list
temp1.f=temp1.depth+compare（temp1）;//计算评价函数发f（n）（f（n）=g（n）+h（n））,
//g（n）用节点到初始节点的步数表示，h（n）用错位数表示
open.addElement（temp1）;//放入Open-list
}
elseif（open.contains（temp1））{//属于Open-list
temp1.f=temp1.depth+compare（temp1）;
intpos=open.indexOf（son.elementAt（t））;
temp2=open.elementAt（pos）;
if（temp1.f//比较open表中本已存在的节点与此后继结点的评价函数大小
open.setElementAt（temp1,pos）;
}
}
elseif（closed.contains（temp1））{//属于Closed-list
temp1.f=temp1.depth+compare（temp1）;
intpos=closed.indexOf（temp1）;
temp2=closed.elementAt（pos）;
if（temp1.f//比较close表中本已存在的节点与此后继结点的评价函数大小
closed.remove（son.elementAt（t））;
open.addElement（temp1）;
}
}
}//endfor
closed.addElement（n）;
for（inti=open.size（）-1;i>0;i--）
//Open-list中的节点按评价函数升序重新排序
for（intj=0;jtemp1=（EightDigital）open.elementAt（j）;
temp2=（EightDigital）open.elementAt（j+1）;
if（temp1.f>temp2.f）{
EightDigitaltq=newEightDigital（）;
tq=open.elementAt（j）;
open.setElementAt（open.elementAt（j+1）,j）;
open.setElementAt（tq,j+1）;
}
}
}//endwhile
System.out.println（"失败!
"）;
return;
}//endmain
}
升级会员 