被稱為不做人生不完整的題，昨天用A*過了，晚上請教了yayamao大神雙向廣搜的精髓，今天決定用雙廣實現一下。從時間效率來看，用雙廣實現似乎比A*略微慢一點，不過從應用的廣度來看，雙向廣度優先搜索顯然比A*用得要廣，所以學會雙廣是很有意義的。
總結一下幾種搜索算法吧
BFS
DFS
一般都是這兩種
DBFS
在一個節點擴展出來的子節點特別多時使用
A*在特殊的問題上面使用，范圍窄
IDA*，基本用不著，不學了。。。讀研以后再說吧
現在好好熟悉前三種就好了，搜索萬歲！
//八數碼問題雙向廣搜實現
//2010年7月11日17:29:58
//coded by abilitytao
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
char s[50],t[50];
int initpos;
char in[100];
int can=0;//能不能搜索到結果
int midcode;
struct node
{
char s[12];
int step;
int pos;
};
int const maxn=400000;
node Front_Q[maxn];
node Back_Q[maxn];
int Front_Hash[maxn];
int Back_Hash[maxn];
int Front_pre[maxn];
int Front_dir[maxn];
int Back_pre[maxn];
int Back_dir[maxn];
int factor[8]={1,2,6,24,120,720,5040,40320};
int num[9]={2,3,2,3,4,3,2,3,2};//指示每個位置可以移動的方向數
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}
};
int cal(char s[]) //計算全排列的哈希值(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;
}
bool check(char s[])//檢測目標狀態是否可達
{
int i,j,cnt,res=0;
for(i=1;i<9;i++)
{
if(s[i]=='0')
continue;
cnt=0;
for(j=0;j<i;j++)
if(s[j]>s[i])cnt++;
res+=cnt;
}
if((res%2)==0)
return true;
else return false;
}
void input()
{
can=0;
memset(Front_Hash,0,sizeof(Front_Hash));
memset(Back_Hash,0,sizeof(Back_Hash));
int pos=0;
int len=strlen(in);
for(int i=0;i<len;i++)
{
if(in[i]=='x')
{
initpos=pos;
s[pos++]='0';
}
else
if(in[i]>='1'&&in[i]<='8')
s[pos++]=in[i];
}
in[pos]='0';
}
int change(char s[],int op,int pos) //互換位置，返回換后的空格位置
{
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;//返回調整后空格的位置
}
void DBFS()
{
int Fl=1;
int Fr=1;
node tnode;
strcpy(tnode.s,s);
tnode.step=0;
tnode.pos=initpos;
Front_Hash[cal(tnode.s)]=1;
Front_pre[cal(tnode.s)]=-1;
Front_dir[cal(tnode.s)]=-1;
Front_Q[1]=tnode;
//init
int Bl=1;
int Br=1;
strcpy(tnode.s,t);
tnode.step=0;
tnode.pos=8;
Back_Hash[cal(tnode.s)]=1;
Back_pre[cal(tnode.s)]=-1;
Back_dir[cal(tnode.s)]=-1;
Back_Q[1]=tnode;
//init
while(Fl<=Fr||Bl<=Br)
{
node New_node;
int step=Front_Q[Fl].step;
while(Fl<=Fr&&step==Front_Q[Fl].step)
{
int len=num[Front_Q[Fl].pos];
for(int i=0;i<len;i++)
{
int pos=Front_Q[Fl].pos;
New_node=Front_Q[Fl];
New_node.pos=change(New_node.s,dirn[New_node.pos][i],New_node.pos);
New_node.step++;
int code=cal(New_node.s);
if(Front_Hash[code])
continue;
Front_Hash[code]=1;
Front_pre[code]=cal(Front_Q[Fl].s);
Front_dir[code]=dirn[pos][i];
Fr++;
Front_Q[Fr]=New_node;
if(Back_Hash[code])
{
can=1;
midcode=code;
return;
}
}
Fl++;
}
step=Back_Q[Bl].step;
while(Bl<=Br&&step==Back_Q[Bl].step)
{
int len=num[Back_Q[Bl].pos];
for(int i=0;i<len;i++)
{
int pos=Back_Q[Bl].pos;
New_node=Back_Q[Bl];
New_node.pos=change(New_node.s,dirn[New_node.pos][i],New_node.pos);
New_node.step++;
int code=cal(New_node.s);
if(Back_Hash[code])
continue;
Back_Hash[code]=1;
Back_pre[code]=cal(Back_Q[Bl].s);
Back_dir[code]=dirn[pos][i];
Br++;
Back_Q[Br]=New_node;
if(Front_Hash[code])
{
can=1;
midcode=code;
return;
}
}
Bl++;
}
}
}
void output()
{
int ans[1000];
int k=0;
int p=midcode;
int scode=cal(s);
int tcode=cal(t);
while(p!=scode)
{
ans[k++]=Front_dir[p];
p=Front_pre[p];
}
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");
}
p=midcode;
while(p!=tcode)
{
if(Back_dir[p]==0)printf("d");
else if(Back_dir[p]==1)printf("l");
else if(Back_dir[p]==2)printf("u");
else if(Back_dir[p]==3)printf("r");
p=Back_pre[p];
}
printf("\n");
}
int main()
{
while(gets(in))
{
input();
strcpy(t,"123456780");
if(!check(s))
{
printf("unsolvable\n");
continue;
}
DBFS();
if(can)
output();
else
printf("unsolvable\n");
}
return 0;
}