人生第一个A*算法～好激动……
八数码难题……又称八数码水题，首先要理解一些东西：
1.状态可以转化成整数，比如状态： 1 2 3
4 5 6
7 8 0
可以转化成：123456780这个整数
2.看上去有9*9种不同状态，实际上只有9!种（即9*8*7*6*5*4*3*2*1）种状态，哈希表大小开成一个大素数即可，每次用这个大素数去对当前的状态（整数）取余获得哈希表的键值
3.移动一个数码到0这个位置可以理解成0这个数码移动到四周的数码的位置
我先用广搜水过，速度大约是20ms左右：
1 #include <iostream>
2 #include <queue>
3 #include <cstdlib>
4 #define hash(x) (x%14233333)
5 using namespace std;
6 const int _end=123804765;
7 int _sta;
8 bool h_tab[14233333];
9 queue<int> que,tque;
10 int move(int key,char c)
11 {
12 int p0=1,kb=key,_map[3][3],x0,y0;
13 while(1){if(kb%10==0)break;p0++,kb/=10;}
14 kb=key,x0=(9-p0)/3,y0=(9-p0)%3;
15 for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_map[i][j]=kb%10,kb/=10;
16 switch(c)
17 {
18 case 'l':if(y0==0)return key;swap(_map[x0][y0],_map[x0][y0-1]);break;
19 case 'r':if(y0==2)return key;swap(_map[x0][y0],_map[x0][y0+1]);break;
20 case 'u':if(x0==0)return key;swap(_map[x0][y0],_map[x0-1][y0]);break;
21 case 'd':if(x0==2)return key;swap(_map[x0][y0],_map[x0+1][y0]);break;
22 default:break;
23 }
24 kb=0;
25 for(int i=0;i<3;i++)for(int j=0;j<3;j++)kb=kb*10+_map[i][j];
26 return kb;
27 }
28 int main()
29 {
30 cin>>_sta;
31 if(_sta==_end)cout<<0,exit(0);
32 que.push(_sta),tque.push(0),h_tab[hash(_sta)]=1;
33 while(!que.empty())
34 {
35 int _new=move(que.front(),'u');
36 if(_new==_end)cout<<tque.front()+1,exit(0);
37 if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
38 _new=move(que.front(),'d');
39 if(_new==_end)cout<<tque.front()+1,exit(0);
40 if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
41 _new=move(que.front(),'l');
42 if(_new==_end)cout<<tque.front()+1,exit(0);
43 if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
44 _new=move(que.front(),'r');
45 if(_new==_end)cout<<tque.front()+1,exit(0);
46 if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
47 que.pop(),tque.pop();
48 }
49 return 0;
50 }
又用了双向广搜试了试，速度大概是10ms左右：
1 #include <iostream>
2 #include <queue>
3 #include <cstdlib>
4 #define hash(x) (x%14233333)
5 using namespace std;
6 const int _end=123804765;
7 int _sta;
8 unsigned short th_tab[2][14233333];
9 bool h_tab[2][14233333];
10 queue<int> que[2];
11 int move(int key,char c)
12 {
13 int p0=1,kb=key,_map[3][3],x0,y0;
14 while(1){if(kb%10==0)break;p0++,kb/=10;}
15 kb=key,x0=(9-p0)/3,y0=(9-p0)%3;
16 for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_map[i][j]=kb%10,kb/=10;
17 switch(c)
18 {
19 case 'l':if(y0==0)return key;swap(_map[x0][y0],_map[x0][y0-1]);break;
20 case 'r':if(y0==2)return key;swap(_map[x0][y0],_map[x0][y0+1]);break;
21 case 'u':if(x0==0)return key;swap(_map[x0][y0],_map[x0-1][y0]);break;
22 case 'd':if(x0==2)return key;swap(_map[x0][y0],_map[x0+1][y0]);break;
23 default:break;
24 }
25 kb=0;
26 for(int i=0;i<3;i++)for(int j=0;j<3;j++)kb=kb*10+_map[i][j];
27 return kb;
28 }
29 int main()
30 {
31 cin>>_sta;
32 if(_sta==_end)cout<<0,exit(0);
33 que[0].push(_sta),que[1].push(_end),h_tab[0][hash(_sta)]=h_tab[1][hash(_end)]=1,th_tab[0][hash(_sta)]=th_tab[1][hash(_end)]=0;
34 while(!que[0].empty()||!que[1].empty())
35 {
36 int _new;
37 if(!que[0].empty())
38 {
39 _new=move(que[0].front(),'u');
40 if(!h_tab[0][hash(_new)])
41 {
42 h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
43 if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
44 }
45 _new=move(que[0].front(),'d');
46 if(!h_tab[0][hash(_new)])
47 {
48 h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
49 if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
50 }
51 _new=move(que[0].front(),'l');
52 if(!h_tab[0][hash(_new)])
53 {
54 h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
55 if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
56 }
57 _new=move(que[0].front(),'r');
58 if(!h_tab[0][hash(_new)])
59 {
60 h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
61 if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
62 }
63 que[0].pop();
64 }
65 if(!que[1].empty())
66 {
67 _new=move(que[1].front(),'u');
68 if(!h_tab[1][hash(_new)])
69 {
70 h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
71 if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
72 }
73 _new=move(que[1].front(),'d');
74 if(!h_tab[1][hash(_new)])
75 {
76 h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
77 if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
78 }
79 _new=move(que[1].front(),'l');
80 if(!h_tab[1][hash(_new)])
81 {
82 h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
83 if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
84 }
85 _new=move(que[1].front(),'r');
86 if(!h_tab[1][hash(_new)])
87 {
88 h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
89 if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
90 }
91 que[1].pop();
92 }
93 }
94 return 0;
95 }
然后我一条路走到黑，研究起了A*算法……
A*算法我现在研究也不透彻……也是一种广搜，它通过一个估值函数，估算当前扩展出的新状态到目标状态的代价，再选中代价最小的新状态扩展，直到扩展到目标状态……
非常快，速度大概是0~1ms
先转发一个写A*算法很不错的博客：http://www.cnblogs.com/yanlingyin/archive/2012/01/15/2322640.html
再贴个代码：
1 #include <iostream>
2 #include <deque>
3 #include <algorithm>
4 #include <cstdlib>
5 #define _abs(x) (x>=0?x:-x)//绝对值函数
6 #define h_size 14233333//哈希表大小
7 #define hash(x) (x%h_size)
8 using namespace std;
9 typedef pair<int,int> pii;
10 const int _end=123804765,_enp[2][9]={{1,0,0,0,1,2,2,2,1},{1,0,1,2,2,2,1,0,0}};//end为目标状态,enp[0][i]表示目标状态中数字i所在的行,enp[1][i]表示数字i所在的列
11 int _sta;//开始状态
12 bool _clo[h_size];//a*算法的close表
13 deque<pii> _ol;//a*算法的open表（使用双端队列）
14 int h(int key)//估值函数，使用曼哈顿距离估值
15 {
16 int _map[3][3],_kp[2][9],sum=0;
17 for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_kp[0][key%10]=i,_kp[1][key%10]=j,key/=10;
18 for(int i=0;i<9;i++)sum+=abs(_kp[0][i]-_enp[0][i])+abs(_kp[1][i]-_enp[1][i]);
19 return sum;
20 }
21 int move(int key,char _ctr)//移动数字0函数,u表示向上，d表示向下,l表示向左,r表示向右
22 {
23 int _kb=key,_map[3][3],i0,j0;
24 for(int i=2;i>=0;i--)for(int j=2;j>=0;j--){_map[i][j]=_kb%10,_kb/=10;if(_map[i][j]==0)i0=i,j0=j;}
25 switch(_ctr)//如果无法扩展（即到达边界）就返回移动前的值
26 {
27 case 'u':if(i0==0)return key;swap(_map[i0][j0],_map[i0-1][j0]);break;
28 case 'd':if(i0==2)return key;swap(_map[i0][j0],_map[i0+1][j0]);break;
29 case 'l':if(j0==0)return key;swap(_map[i0][j0],_map[i0][j0-1]);break;
30 case 'r':if(j0==2)return key;swap(_map[i0][j0],_map[i0][j0+1]);break;
31 }
32 for(int i=0;i<3;i++)for(int j=0;j<3;j++)_kb=_kb*10+_map[i][j];
33 return _kb;
34 }
35 bool cmp(pii a,pii b){return a.second<b.second;}//二分查找比较函数
36 void work(pii _nex)//处理新状态
37 {
38 if(_nex.first==_end)cout<<_nex.second-h(_nex.first),exit(0);//发现正解，直接输出并结束程序
39 if(!_clo[hash(_nex.first)])_ol.insert(lower_bound(_ol.begin(),_ol.end(),_nex,cmp),_nex);//二分查找插入新状态
40 }
41 int main()
42 {
43 cin>>_sta;
44 _ol.push_back(make_pair(_sta,h(_sta)));//把开始状态加入到open表中
45 while(!_ol.empty())//处理open表
46 {
47 pii _now=_ol.front();
48 _ol.pop_front(),_clo[hash(_now.first)]=1;//把当前open表中的最优状态取出并加入到close表中
49 int _nex=move(_now.first,'u');//扩展新状态
50 work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'d');
51 work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'l');
52 work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'r');
53 work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1));
54 }
55 return 0;
56 }