某位神牛曾說過，此題是涉及到人生完不完整的一道題。。

Goodness大牛曾總結了 八數碼的八重境界 ： http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html

足見此題的重要性。

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1043

本人不才，只寫出了其中幾個。。

1、 暴搜+離散+二分

一直以來沒用過hash表，這次首先想到的也是二分，先dfs找出所有狀態36w+，然后離散化，之后就可以進行暴搜了，hdu TLE，pku500ms。。

2、 單廣預處理

上網搜了下，發現逆序數hash要快好多， 以n！為基數，以當前位置的逆序數為系數構造hash表，則123456789對應的hash值為0，987654321對應的

hash值為：0*0！+1*1！+2*2！+3*3！+4*4！+5*5！+6*6！+7*7！+8*8！= 9！-1； 每一種狀態剛好對應唯一的hash值。具體的原因可以去查查一些數學書。。

從目標狀態搜能到達的所有狀態，把能到達的狀態標記下來，對于每一個輸入的實例，耗時O(1);? hdu 78ms, pku 250ms

3、A*+哈希+曼哈頓距離

??? 第一次寫A*發現A*也不是傳說中的那么難， 關鍵是要找到啟發式函數，對于此題，曼哈頓距離就是一個很不錯的啟發式函數。所謂曼哈頓距離即是

兩個點上在標準坐標系上的絕對軸距總和，|x1-x2|+|y1-y2|;?? 另外對于無解的情況要首先判斷出來： 求出不算x的時候的所有逆序數總和， 如果這個數

是奇數的話就無解，? 至于你看沒看出來，反正我是沒看出來。。。???? hdu 671ms, pku 32ms

4、IDA*+曼哈頓距離

?? 感覺A*和IDA*差不多，只不過一個用于廣搜，一個用于深搜。。。?? IDA*是先找到到達目標狀態至少需要多少步，然后迭代加深， 對其進行剪枝。。hdu 1s+，pku 47ms

貼一個A*代碼：

View Code 1 # include<stdio.h>
2 # include<string.h>
3 # include<queue>
4 # define N 363000
5 using namespace std;
6 bool visit[N];
7 char visit1[N];
8 int pre[N],st,a[10],end;
9 int dir[9]={1,1,2,6,24,120,720,5040,40320};
10 struct node{
11 int ma[10];
12 int ans1;
13 int x;
14 int f;
15 int g;
16 bool operator <(const node &a)const {
17 return a.f < f;//優先訪問f較小者
18 }
19 };
20 int hash(int s[])
21 {
22 int i,j,cnt,sum;
23 sum=0;
24 for(i=1;i<=9;i++)
25 {
26 cnt=0;
27 for(j=1;j<i;j++)
28 if(s[j]>s[i]) cnt++;
29 sum+=cnt*dir[i-1];
30 }
31 return sum;
32 }
33 int ABS(int x) {return x<0?(-x):x;}
34 int h(int s[])//不算x時的曼哈頓距離
35 {
36 int curx,cury,endx,endy,sum,i,ans;
37 sum=0;
38 for(i=1;i<=9;i++)
39 {
40 if(s[i]==9) continue;
41 ans=s[i];
42 curx=(i+2)/3;
43 cury=(i-1)%3+1;
44 endx=(ans+2)/3;
45 endy=(ans-1)%3+1;
46 sum=sum+ABS(curx-endx)+ABS(cury-endy);
47 }
48 return sum;
49 }
50 void bfs()
51 {
52 int ans,i;
53 priority_queue<node>q;
54 node cur,next;
55 cur.ans1=st=hash(a);
56 visit[cur.ans1]=1;
57 if(st==end) return;
58 for(i=1;i<=9;i++)
59 {
60 cur.ma[i]=a[i];
61 if(a[i]==9) cur.x=i;
62 }
63 cur.g=0;//表示深度
64 cur.f=h(a);
65 q.push(cur);
66 while(!q.empty())
67 {
68 cur=q.top();
69 q.pop();
70 if((cur.x+2)/3!=1) //向上翻
71 {
72 next=cur;
73 next.x=cur.x-3;
74 next.ma[cur.x]=next.ma[next.x];
75 next.ma[next.x]=9;
76 ans=hash(next.ma);
77 if(!visit[ans])
78 {
79 next.g++;
80 next.f=next.g+h(next.ma);
81 visit[ans]=1;
82 next.ans1=ans;
83 pre[ans]=cur.ans1;
84 visit1[ans]='u';
85 if(ans==end) return;
86 q.push(next);
87 }
88 }
89 if((cur.x+2)/3!=3)//向下翻
90 {
91 next=cur;
92 next.x=cur.x+3;
93 next.ma[cur.x]=next.ma[next.x];
94 next.ma[next.x]=9;
95 ans=hash(next.ma);
96 if(!visit[ans])
97 {
98 next.g++;
99 next.f=next.g+h(next.ma);
100 visit[ans]=1;
101 next.ans1=ans;
102 pre[ans]=cur.ans1;
103 visit1[ans]='d';
104 if(ans==end) return;
105 q.push(next);
106 }
107 }
108 if(cur.x%3!=1)//向左翻
109 {
110 next=cur;
111 next.x=cur.x-1;
112 next.ma[cur.x]=next.ma[next.x];
113 next.ma[next.x]=9;
114 ans=hash(next.ma);
115 if(!visit[ans])
116 {
117 next.g++;
118 next.f=next.g+h(next.ma);
119 visit[ans]=1;
120 next.ans1=ans;
121 pre[ans]=cur.ans1;
122 visit1[ans]='l';
123 if(ans==end) return;
124 q.push(next);
125 }
126 }
127 if(cur.x%3!=0)//向右翻
128 {
129 next=cur;
130 next.x=cur.x+1;
131 next.ma[cur.x]=next.ma[next.x];
132 next.ma[next.x]=9;
133 ans=hash(next.ma);
134 if(!visit[ans])
135 {
136 next.g++;
137 next.f=next.g+h(next.ma);
138 visit[ans]=1;
139 next.ans1=ans;
140 pre[ans]=cur.ans1;
141 visit1[ans]='r';
142 if(ans==end) return;
143 q.push(next);
144 }
145 }
146 }
147 }
148 int check(int s[])
149 {
150 int i,j,cnt=0;
151 for(i=1;i<=9;i++)
152 {
153 if(s[i]==9) continue;
154 for(j=1;j<i;j++)
155 {
156 if(s[j]==9) continue;
157 if(s[j]>s[i]) cnt++;
158 }
159 }
160 return cnt;
161 }
162 int main()
163 {
164 int i,j,ans;
165 char str[50];
166 while(gets(str))
167 {
168 ans=0;
169 memset(visit,0,sizeof(visit));
170 for(i=0;str[i];i++)
171 if(str[i]=='x') a[++ans]=9;
172 else if(str[i]!=' ') a[++ans]=str[i]-'0';
173 end=0;
174 ans=check(a);
175 if(ans%2) {puts("unsolvable");continue;}
176 bfs();
177 j=0;
178 while(end!=st)
179 {
180 str[j++]=visit1[end];
181 end=pre[end];
182 }
183 for(i=j-1;i>=0;i--)
184 printf("%c",str[i]);
185 puts("");
186 }
187 return 0;
188 }

轉載于:https://www.cnblogs.com/183zyz/archive/2011/08/12/2135827.html

總結

以上是生活随笔為你收集整理的hdu 1043 ，pku 1077 Eight ，八数码问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。