文档介绍：人工智能
结束4
1
A*算法实验报告
实验目的
熟悉和掌握启发式搜索的定义、估价函数和算法过程
学会利用A*算法求解N数码难题
理解求解流程和搜索顺序
实验原理
A*算法是一种有序搜索算法，其特点在于对估价函index!=0)
{
(node_v[index]);
index=node_v[index].index;
}_
人工智能
人工智能
6
11
for(inti=()-1;i>=0;i--)〃输出每一步的探索过程
cout<<"Step"<<()-i
<<endl<<rstep_v[i]<<endl;
}_
voidSwap(int&a,int&b)
{
intt;
t=a;
a=b;
b=t;
}
voidAssign(Node&node,intindex)
{
for(inti=0;i<ROW;i++)
for(intj=0;j<COL;j++)
[i][j]=node_v[index].digit[i][j];
}_
intGetMinNode()〃找到最小的节点的位置即最优节点{
intdist=MAXNUM;
intloc;//thelocationofminimizenode
for(inti=0;i<();i++)
{_
讦(node_v[i].dist==MAXNUM)continue;
elseif((node_v[i].dist+node_v[i].dep)<dist){loc=i;
dist=node_v[i].dist+node_v[i].dep;
}一一
}
returnloc;
}
boolisExpandable(Node&node)
{
for(inti=0;i<();i++){
if(isEqual(i,))
returnfalse;
}
returntrue;
人工智能
人工智能
12
7
}
intDistance(Node&node,intdigit[][COL])
{
intdistance=0;
boolflag=false;
for(inti=0;i<ROW;i++)
for(intj=0;j<COL;j++)
for(intk=0;k<ROW;k++){
for(intl=0;l<COL;l++){
讦([i][j]==digit[k][l]){distance+=abs(i-k)+abs(j-l);
flag=true;break;
}
else
flag=false;
}
讦(flag)
break;
}
returndistance;
}
intMinDistance(inta,intb)
{return(a<b?a:b);
}
voidProcessNode(intindex)
{
intx,y;
boolflag;
for(inti=0;i<ROW;i++){
for(intj=0;j<COL;j++){
讦(node_v[index].digit[i][j]==0)
{_
x=i;y=j;
flag=true;
break;
}
elseflag=false;
}
if(flag)break;
人工智能
人工智能
8
11
}
Nodenode_up;
Assign(node_up,index);//向上扩展的节点intdist_up=MAXDISTANCE;
讦(x>0)
{
Swap([x][y],[x-1][y]);
if(isExpandable(node_up))
{_
dist_up=Distance(node_up,);=index;=dist_up;
=node_v[index].dep+1;(node_up);
}""一
}
Nodenode_down;
Assign(node_down,index);//向下扩展的节点
intdist_down=MAXDISTANCE;
if(x<2)
{
Swap([x][y],[x+1][y]);i