特來YM+學(xué)習(xí)A*算法，A*果然快啊，在pku上曾經(jīng)寫過一個(gè)BFS,300MS，去航電直優(yōu)化的空間接TLE.用A*算法北大16MS,航電750MS,效率很高啊。當(dāng)然我的A*寫得還不是特別好，航電上有16MS AC那道題的，看來這個(gè)A*還有優(yōu)化的空間。
A*采用啟發(fā)式搜索的思維方式很值得借鑒！F=G+H
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int const maxn=365000;//總狀態(tài)數(shù)不超過362880
char s[12],t[12];
//FOR DIRECTION
int num[9]=
{2,3,2,3,4,3,2,3,2};//指示每個(gè)位置可以移動(dòng)的方向數(shù)
int dirn[9][4]=
{
{1,2},
{1,2,3},
{2,3},
{0,1,2},
{0,1,2,3},
{0,2,3},
{0,1},
{0,1,3},
{0,3}
};
//end
int xy[9][2]={{0,0},{1,0},{2,0},{0,-1},{1,-1},{2,-1},{0,-2},{1,-2},{2,-2}};//存每個(gè)位置的坐標(biāo)
int fa[maxn],cz[maxn];//cz是回溯時(shí)記錄方向
int factor[8]={1,2,6,24,120,720,5040,40320};
int dist[10][10];//存第i個(gè)位置到第j個(gè)位置要走的步數(shù)
int v[maxn];//標(biāo)記是否在OPEN表中
int goalcode;
int initzeropos;
struct node
{
int pos,g,h,code;//code is short for hashcode
char s[12];
bool operator<(node o)
{
return (g+h) < (o.g+o.h);
}
};
#define ele node//可以修改數(shù)據(jù)類型
struct MinHeap
{
ele *h;//heap數(shù)組
int Csize;//CurrentSize現(xiàn)在的容量
int Msize;//最大容量
void Down(int s,int e)//第s號(hào)位置的元素進(jìn)行下滲，數(shù)組中最大的下標(biāo)到e
{
int i=s,j=2*i+1;
ele t=h[i];
while(j<=e)
{
if(j<e&&h[j+1]<h[j])
j++;
if(t<h[j])
break;
else
{
h[i]=h[j];i=j;j=2*j+1;
}
}
h[i]=t;
}
void Up(int s)//start,上滲函數(shù)
{
int j=s,i=(j-1)/2;
ele t=h[j];
while(j)
{
if(h[i]<t) break;
else
{
h[j]=h[i];j=i;i=(i-1)>>1;
}
}
h[j]=t;
}
MinHeap(int n){Msize=n;h=new ele[Msize];Csize=0;}//構(gòu)造函數(shù)
bool Insert(const ele &x)
{
if(Csize==Msize)
return false;
h[Csize]=x;
Up(Csize);
Csize++;
return true;
}
ele RemoveMin()
{
//v[h[0].code]=false;//記錄
ele x=h[0];
h[0]=h[Csize-1];
Csize--;
Down(0,Csize-1);
return x;
}
ele GetMin(){return h[0];}
};
MinHeap H(maxn);
int GetDist(int s,int t)//計(jì)算兩個(gè)位置之間的最小步數(shù)
{
int dx=abs(xy[s][0]-xy[t][0]);
int dy=abs(xy[s][1]-xy[t][1]);
return dx+dy;
}
int cal(char s[]) //計(jì)算全排列的哈希值(hashcode)
{
int i,j,cnt,res=0;
for(i=1;i<9;i++)
{
cnt=0;
for(j=0;j<i;j++)
if(s[j]>s[i])cnt++;
cnt*=factor[i-1];
res+=cnt;
}
return res;
}
int estimate(char str[])
{
int res=0,i,des;
for(i=0;i<9;i++)
{
if(str[i]!='0')
{
des=str[i]-'0'-1;
res+=dist[i][des];
}
}
return res;
}
bool check(char s[])//檢測(cè)目標(biāo)狀態(tài)是否可達(dá)
{
int i,j,cnt,res=0;
for(i=1;i<9;i++)
{
cnt=0;
for(j=0;j<i;j++)
if(s[j]>s[i])cnt++;
res+=cnt;
}
for(i=0;i<9;i++)
{
if(s[i]=='0')
{
res+=dist[i][8];
break;
}
}
if((res%2)==0)
return true;
else return false;
}
int change(char s[],int op,int pos) //互換位置，返回?fù)Q后的空格位置
{
int end;
if(op==0)end=pos-3;
else if(op==1)end=pos+1;
else if(op==2)end=pos+3;
else if(op==3)end=pos-1;
char t=s[pos];
s[pos]=s[end];
s[end]=t;
return end;//返回調(diào)整后空格的位置
}
void Astar(char s[])
{
H.Csize=0;//清空操作
node t;
t.pos=initzeropos;
t.g=0;
t.h=estimate(s);
t.code=cal(s);
strcpy(t.s,s);
v[t.code]=true;
cz[t.code]=0;
fa[t.code]=-1;
H.Insert(t);
//以上為初始化
while(H.Csize>0)
{
node tt=H.RemoveMin();
if(tt.code==goalcode)
{
int ans[1000];
int k=0,fp;
fp=tt.code;
while(fp!=t.code)
{
ans[k++]=cz[fp];
fp=fa[fp];
}
for(int i=k-1;i>=0;i--)
{
if(ans[i]==0)printf("u");
else if(ans[i]==1)printf("r");
else if(ans[i]==2)printf("d");
else if(ans[i]==3)printf("l");
}
printf("\n");
return;
}
int len=num[tt.pos];
for(int i=0;i<len;i++)
{
node x=tt;
x.pos=change(x.s,dirn[tt.pos][i],x.pos);
x.code=cal(x.s);
x.g++;
x.h=estimate(x.s);
if(!v[x.code])
{
v[x.code]=true;
fa[x.code]=tt.code;
cz[x.code]=dirn[tt.pos][i];
H.Insert(x);
}
}
}
}
int main()
{
int i,j;
strcpy(t,"123456780");
goalcode=cal(t);
for(i=0;i<9;i++)
for(j=0;j<9;j++)dist[i][j]=GetDist(i,j);
char str[50];
while(gets(str))
{
int len=strlen(str),pos=0;
memset(v,0,sizeof(v));
for(i=0;i<len;i++)
{
if(str[i]=='x')//空格部分用0代替
{
initzeropos=pos;
s[pos++]='0';
}
else if(str[i]>='1'&&str[i]<='8')s[pos++]=str[i];
}
s[9]='\0';
if(!check(s))printf("unsolvable\n");
else Astar(s);
}
return 0;
}
代碼參考了：
http://www.shnenglu.com/longzxr/archive/2010/07/05/92978.html#119349