【文件属性】：
文件名称：使用A*算法实现8数码问题的求解
文件大小：5KB
文件格式：TXT
更新时间：2012-01-08 10:17:38
人工智能
include
using namespace std;
struct node{
int nodesun[4][4];
int pre; //上一步在队列中的位置
int flag ; //步数标识，表示当前的步数为有效的
int value; //与目标的差距
int x,y; //空格坐标
}queue[1000];
//移动方向数组
int zx[4]={-1,0,1,0};
int zy[4]={0,-1,0,1};
//当前步数
int top;
int desti[4][4];//目标状态
int detect(struct node *p)//检查是否找到
{int i,j;
for(i=1;i<4;i++)
for(j=1;j<4;j++)
if(p->nodesun[i][j]!=desti[i][j])
return 0;
return 1;
}
//打印
void printlj()
{int tempt;
int i,j;
tempt=top;
while(tempt!=0)
{ for(i=1;i<4;i++)
for(j=1;j<4;j++)
{cout<nodesun[i][j]!=desti[i][j])
count++;
return count;
}
void main()
{ //初始化
int i,j,m,n,f;
int min=10;
int temp,find=0,minnumber;
top=1;
for(i=1;i<4;i++)
for(j=1;j<4;j++)
{cout<<"请输入第"<>temp;
queue[1].nodesun[i][j]=temp;
}
cout<<"请输入初始状态的空格的位置(行)"<>temp;
queue[1].x=temp;
cout<<"请输入初始状态的空格的位置(列)"<>temp;
queue[1].y=temp;
queue[1].value=VALUE(&queue[1]);
queue[1].pre=0; //上一步在队列中的位置
queue[1].flag=0;
//目标状态
for(i=1;i<4;i++)
for(j=1;j<4;j++)
{cout<<"请输入目标状态第"<>temp;
desti[i][j]=temp;
} //根据估价函数
while(!find&&top>0)
{
for(i=1;i<=top;i++)
////////////////////////////////////////////
//min为上一图中与目标图有多少个元素不相同，queue[i]为当前图与目标图有多少个元素不相同通过这两个数的比较，就可以得出当前图较之上一图向目标图接近同时把当前的i记录下来进行下一步比较
{if(queue[i].value=1&&i<=3&&j>=1&&j<=3)
{top++;
/////////////////////////////////////////////
//位置交换
queue[top]=queue[minnumber];
queue[top].nodesun[m][n]=queue[minnumber].nodesun[i][j];
queue[top].nodesun[i][j]=0;
///////////////////////////////////////
//空格移动方向
queue[top].x=i;
queue[top].y=j;
///////////////////////////////////////
queue[top].pre=minnumber; //上一步在队列中的位置
queue[top].value=VALUE(&queue[top]); //有多少位与目标不同
queue[top].flag=0; //标识位初始化
if(detect(&queue[top])) //检查是否为目标
{printlj(); //打印
find=1; //设找到标识位
break;
}
}
}
}
}
