这里主要介绍A*算法的实现：八数码问题
#include<stdio.h>
#include<queue>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1000000;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展开判重
// 0!1!2!3! 4! 5! 6! 7! 8! 9!
bool vis[MAXN];//标记
string path;//记录最终的路径
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//方向向量
char indexs[5]="udlr";//正向搜索
struct Node
{
int data[9];
int f,g,h;
int loc;//“0”的位置,把“x"当0
int status;//康拖展开的hash值
string path;//路径
bool operator==(const Node &t){
return status==t.status;
}
bool operator<(const Node &t)const{
return f>t.f;
}
}start,goal;//起始和终止点
int Cantor(int s[])//康拖展开求该序列的hash值
{
int sum=0;
for(int i=0;i<9;i++)
{
int num=0;
for(int j=i+1;j<9;j++)
if(s[j]<s[i])num++;
sum+=(num*fac[9-i-1]);
}
return sum+1;
}
int ABS(int x){return x<0?(-x):x;}
int Distance(Node suc, Node goal, int i) {//计算方格的错位距离
int h1,h2; //h1表示suc中i所处位置，h2表示goal中i所处的位置
for(int k = 0; k < 9; k++) {
if(suc.data[k] == i)h1 = k;
if(goal.data[k] == i)h2 = k;
}
return ABS(h1/3 - h2/3) + ABS(h1%3 - h2%3);
}
int Fvalue(Node suc, Node goal, float speed) {//计算 f 值
int h = 0;
for(int i = 1; i <= 8; i++)
h = h + Distance(suc, goal, i);
return h*speed + suc.g; //f = h + g（speed 值增加时搜索过程以找到目标为优先因此可能 不会返回最优解）
}
bool Astar()
{
memset(vis,false,sizeof(vis));
Node cur,next;
priority_queue<Node> q;
q.push(start);
while(!q.empty())
{
cur=q.top();
q.pop();
if(cur==goal)
{
path=cur.path;
return true;
}
int x=cur.loc/3;
int y=cur.loc%3;
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(tx<0||tx>2||ty<0||ty>2)continue;
next=cur;
next.loc=tx*3+ty;
next.data[cur.loc]=next.data[next.loc];
next.data[next.loc]=0;
next.status=Cantor(next.data);
if(!vis[next.status])
{
vis[next.status]=true;
next.path=next.path+indexs[i];
if(next==goal)
{
path=next.path;
return true;
}
next.g++;//g值
next.f=Fvalue(next,goal,1);//f值
q.push(next);
}
}
}
return false;
}
int main()
{
freopen("C:\\in.txt","r",stdin);
char ch;
//目的节点初始化start
for(int i=0;i<8;i++)goal.data[i]=i+1;
goal.data[8]=0;
goal.status=46234;//123456780对应的康拖展开的hash值
//end
while(cin>>ch)
{
//起始节点初始化start
if(ch==‘x‘) {start.data[0]=0;start.loc=0;}
else start.data[0]=ch-‘0‘;
for(int i=1;i<9;i++)
{
cin>>ch;
if(ch==‘x‘)
{
start.data[i]=0;
start.loc=i;
}
else start.data[i]=ch-‘0‘;
}
start.status=Cantor(start.data);//康拖hash值
start.g=0;
start.f=Fvalue(start,goal,1);//计算f值
//end
if(Astar())
{
cout<<path<<endl;
}
else cout<<"unsolvable"<<endl;
}
return 0;
}