八数码问题(A*&&双向BFS)

?

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=217

????? 首先说一下八数码问题的可解性。

?????? 1.互换2个非零位置，状态的逆序奇偶性将保持不变。

?????? 2.互换0和另一个非零位置，状态的逆序奇偶性将发生颠倒。

?????? 3.因此，如果目标状态和起始状态的逆序奇偶性相同，问题可解，否则不可解。所以对于八数码问题的一个目标状态有9!/2种可解状态

?????? 逆序奇偶性可以这样来求，将状态转化了数列，然后去掉X位，然后对于每一位，计算在它之前小于它的个数，每一位对应的值之和就是逆序奇偶数。

????? A*算法具体不多说了，它的精髓在于f(n)=g(n)+h(n),中估值函数h(n)的设计。值的注意的是：

????? 如果估价值h(n)<= n（到目标节点的实际步长），这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

　　如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

???? 因此在实际使用的时候应该更具需要来设计h(n)

???? 在zoj_1217中，为了不TLE，选择h(n)=20*dis(欧几里德距离)，但是得不到最优解

zoj_1217:

Cpp代码??

1. #include<cstdio>??
2. #include<algorithm>??
3. #include<queue>??
4. #include<string.h>??
5. #include<string>??
6. #include<math.h>??
7. #include<iostream>??
8. using?namespace?std;??
9. int?next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};??
10. string?path[4]={"d","r","u","l"};??
11. int?dp[10]={1,1,2,6,24,120,720,5040,40320,362880};??
12. int?final[9]={1,2,3,4,5,6,7,8,0};??
13. bool?hashtable[362885];??
14. class?state??
15. {??
16. public:??
17. ????int?a[9],exp,zero,dept;??
18. ????string?path;??
19. ????state(){};??
20. ????state(int?num[9])??
21. ????{??
22. ????????for(int?i=0;i<9;++i)??
23. ????????????a[i]=num[i];??
24. ????}??
25. ????void?swapn(int?c)??
26. ????{?????
27. ????????swap(a[zero],a[c]);??
28. ????}??
29. };??
30. struct?cmp?????
31. {?????
32. ????bool?operator()(const?state?x,const?state?y)?????
33. ????{?????
34. ????????return?x.exp>y.exp;?????
35. ????}?????
36. };??
37. int?getHash(int?code[9])??
38. {??
39. ????int?sum=0;??
40. ????bool?flag[9];??
41. ????int?k;??
42. ????memset(flag,false,sizeof(flag));??
43. ????for(int?i=0;i<9;++i)??
44. ????{??
45. ????????k=0;??
46. ????????for(int?j=code[i]+1;j<9;++j)??
47. ????????{??
48. ????????????if(!flag[j])??
49. ????????????????++k;??
50. ????????}??
51. ????????sum+=k*dp[8-i];??
52. ????????flag[code[i]]=true;??
53. ????}??
54. ????return?362879-sum;??
55. }??
56. int?Eudis(int?a[9])??
57. {??
58. ????int?dis=0;??
59. ????for(int?i=0;i<9;++i)??
60. ????{??
61. ????????for(int?j=0;j<9;++j)??
62. ????????{??
63. ????????????if(a[i]==final[j])??
64. ????????????{??
65. ????????????????dis+=fabs(1.0*(i/3-j/3))+fabs(1.0*(i%3-j%3));??
66. ????????????????break;??
67. ????????????}?????
68. ????????}??
69. ????}??
70. ????return?dis/2;?????
71. }??
72. state?ans;??
73. bool?bfs(state?ori)??
74. {??
75. ????priority_queue<state,vector<state>,cmp?>open;??
76. ????//queue<state>open;??
77. ????open.push(ori);??
78. ????while(!open.empty())??
79. ????{??
80. ????????state?t=open.top();??
81. ????????open.pop();??
82. ????????if(Eudis(t.a)==0)??
83. ????????{??
84. ????????????ans=t;??
85. ????????????return?true;??
86. ????????}??
87. ????????for(int?i=0;i<4;++i)??
88. ????????{??
89. ????????????int?row=t.zero/3;??
90. ????????????int?col=t.zero%3;??
91. ????????????int?arow=row+next[i][1];??
92. ????????????int?acol=col+next[i][0];??
93. ????????????if(arow<3&&arow>=0&&acol<3&&acol>=0)??
94. ????????????{??
95. ????????????????int?sw=arow*3+acol;??
96. ????????????????state?tmp=t;??
97. ????????????????tmp.swapn(sw);??
98. ????????????????tmp.zero=sw;??
99. ????????????????int?hcode=getHash(tmp.a);??
100. ????????????????if(hashtable[hcode])??
101. ????????????????????continue;??
102. ????????????????hashtable[hcode]=true;??
103. ????????????????int?dis=50*Eudis(tmp.a);??
104. ????????????????++tmp.dept;??
105. ????????????????tmp.exp=dis+tmp.dept;??
106. ????????????????tmp.path+=path[i];??
107. ????????????????open.push(tmp);???????
108. ????????????}?????????????
109. ????????}??
110. ????}?????
111. ????return?false;??
112. }??
113. void?test(bool?flag[9],int?b,int?num[9])??
114. {??
115. ????if(b>8)??
116. ????{??
117. ????????printf("%d\n",getHash(num));??
118. ????????return;??
119. ????}??
120. ????for(int?i=0;i<9;++i)??
121. ????{??
122. ????????if(!flag[i])??
123. ????????{??
124. ????????????flag[i]=true;??
125. ????????????num[b]=i;??
126. ????????????test(flag,b+1,num);??
127. ????????????flag[i]=false;??
128. ????????}??
129. ????}??
130. }??
131. bool?isSolveable?(int?statue[9])????
132. {????
133. ????int?num=0;??
134. ????for?(int?i=1;i<=8;++i)????
135. ????????{????
136. ????????????if(statue[i]==0)??
137. ????????????continue;??
138. ????????for(int?j=0;j<i;++j)????
139. ????????????{????
140. ????????????????????if(statue[j]==0)??
141. ????????????????continue;??
142. ????????????if(statue[i]>statue[j])???
143. ????????????????++num;????
144. ????????????}????
145. ????????}????
146. ????????if?(num%2==1)?return?false;????
147. ????????return?true;????
148. }????
149. ??
150. int?main()??
151. {??
152. ????//bool?ff[9];??
153. ????//int?nn[9];??
154. ????//memset(ff,false,sizeof(ff));??
155. ????//memset(nn,false,sizeof(nn));??
156. ????//test(ff,0,nn);??
157. ????//int?a[9]={0,1,2,3,4,5,6,7,8};??
158. ????//int?b[9]={8,7,6,5,4,3,2,1,0};??
159. ????//printf("%d\n",getHash(b));??
160. ????freopen("e:\\zoj\\zoj_1217.txt","r",stdin);??
161. ????while(1)??
162. ????{??
163. ????????memset(hashtable,0,sizeof(hashtable));??
164. ????????int?flag=0;??
165. ????????int?num[9];??
166. ????????int?zero;??
167. ????????char?c;??
168. ????????for(int?i=0;i<9;++i)??
169. ????????{??
170. ????????????if(scanf("?%c",&c)==EOF)??
171. ????????????????return?0;??
172. ????????????if(c=='x')??
173. ????????????{?????
174. ????????????????zero=flag;??
175. ????????????????num[flag++]=0;??
176. ????????????}??
177. ????????????if(c<='9'&&c>='1')??
178. ????????????????num[flag++]=c-48;??
179. ????????????if(flag>=9)??
180. ????????????????break;????
181. ????????}??
182. ????????state?ori(num);??
183. ????????ori.exp=20*Eudis(num);??
184. ????????ori.zero=zero;??
185. ????????ori.dept=0;??
186. ????????int?hcode=getHash(num);??
187. ????????hashtable[hcode]=true;??
188. ????????if(!isSolveable(num))??
189. ????????????printf("unsolvable\n");??
190. ????????else??
191. ????????{?????????
192. ????????bool?f=bfs(ori);??
193. ????????int?l=ans.path.length();??
194. ????????for(int?i=0;i<l;++i)??
195. ????????????printf("%c",ans.path[i]);??
196. ????????puts("");??
197. ????????}??
198. ????}??
199. }??

?双向BFS：

?

Cpp代码??

1. #include<cstdio>??
2. #include<algorithm>??
3. #include<queue>??
4. #include<string.h>??
5. #include<string>??
6. #include<iostream>??
7. using?namespace?std;??
8. int?next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};??
9. string?path[4]={"d","r","u","l"};??
10. string?path2[4]={"u","l","d","r"};??
11. int?dp[10]={1,1,2,6,24,120,720,5040,40320,362880};??
12. int?final[9]={1,2,3,4,5,6,7,8,0};??
13. int?hashtable[362885];??
14. class?state??
15. {??
16. public:??
17. ????int?a[9],zero;??
18. ????string?path;??
19. ????state(){};??
20. ????state(int?num[9])??
21. ????{??
22. ????????for(int?i=0;i<9;++i)??
23. ????????????a[i]=num[i];??
24. ????}??
25. ????void?swapn(int?c)??
26. ????{?????
27. ????????swap(a[zero],a[c]);??
28. ????}??
29. };??
30. state?x,y;??
31. state?sl[362885];??
32. int?getHash(int?code[9])??
33. {??
34. ????int?sum=0;??
35. ????bool?flag[9];??
36. ????int?k;??
37. ????memset(flag,false,sizeof(flag));??
38. ????for(int?i=0;i<9;++i)??
39. ????{??
40. ????????k=0;??
41. ????????for(int?j=code[i]+1;j<9;++j)??
42. ????????{??
43. ????????????if(!flag[j])??
44. ????????????????++k;??
45. ????????}??
46. ????????sum+=k*dp[8-i];??
47. ????????flag[code[i]]=true;??
48. ????}??
49. ????return?362879-sum;??
50. }??
51. bool?check(state?a,state?b)??
52. {??
53. ????bool?flag=true;??
54. ????for(int?i=0;i<9;++i)??
55. ????{??
56. ????????if(a.a[i]!=b.a[i])??
57. ????????{??
58. ????????????flag=false;??
59. ????????????break;??
60. ????????}??
61. ????}??
62. ????return?flag;??
63. }??
64. bool?bfs(state?ori,state?fin)??
65. {??
66. ????queue<state>open,open2;??
67. ????open.push(ori);??
68. ????open2.push(fin);??
69. ????int?hcode,fcode;??
70. ????state?tmp,tmp2,t1,t2;??
71. ????while(1)??
72. ????{??
73. ????????if(!open.empty())??
74. ????????{??
75. ????????????t1=open.front();??
76. ????????????open.pop();??
77. ????????????for(int?i=0;i<4;++i)??
78. ????????????{??
79. ????????????????int?row=t1.zero/3;??
80. ????????????????int?col=t1.zero%3;??
81. ????????????????int?arow=row+next[i][1];??
82. ????????????????int?acol=col+next[i][0];??
83. ????????????????if(arow<3&&arow>=0&&acol<3&&acol>=0)??
84. ????????????????{??
85. ????????????????????int?sw=arow*3+acol;??
86. ????????????????????tmp=t1;??
87. ????????????????????tmp.swapn(sw);??
88. ????????????????????tmp.zero=sw;??
89. ????????????????????tmp.path+=path[i];??
90. ????????????????????hcode=getHash(tmp.a);??
91. ????????????????????if(hashtable[hcode]==1)??
92. ????????????????????????continue;??
93. ????????????????????if(hashtable[hcode]==2)??
94. ????????????????????{??
95. ????????????????????????x=tmp;??
96. ????????????????????????y=sl[hcode];??
97. ????????????????????????return?true;??
98. ????????????????????}??
99. ????????????????????hashtable[hcode]=1;??
100. ????????????????????sl[hcode]=tmp;??
101. ????????????????????open.push(tmp);???????
102. ????????????????}?????????????
103. ????????????}??
104. ????????}??
105. ????????if(!open2.empty())??
106. ????????{??
107. ????????????t2=open2.front();??
108. ????????????open2.pop();??
109. ????????????for(int?i=0;i<4;++i)??
110. ????????????{??
111. ????????????????int?row=t2.zero/3;??
112. ????????????????int?col=t2.zero%3;??
113. ????????????????int?arow=row+next[i][1];??
114. ????????????????int?acol=col+next[i][0];??
115. ????????????????if(arow<3&&arow>=0&&acol<3&&acol>=0)??
116. ????????????????{??
117. ????????????????????int?sw=arow*3+acol;??
118. ????????????????????tmp2=t2;??
119. ????????????????????tmp2.swapn(sw);??
120. ????????????????????tmp2.zero=sw;??
121. ????????????????????tmp2.path+=path2[i];??
122. ????????????????????fcode=getHash(tmp2.a);??
123. ????????????????????if(hashtable[fcode]==2)??
124. ????????????????????????continue;??
125. ????????????????????if(hashtable[fcode]==1)??
126. ????????????????????{??
127. ????????????????????????y=tmp2;??
128. ????????????????????????x=sl[fcode];??
129. ????????????????????????return?true;??
130. ????????????????????}??
131. ????????????????????hashtable[fcode]=2;??
132. ????????????????????sl[fcode]=tmp2;??
133. ????????????????????open2.push(tmp2);?????????
134. ????????????????}?????????????
135. ????????????}?????
136. ????????}??
137. ????}?????
138. ????return?false;??
139. }??
140. bool?isSolveable?(int?statue[9])????
141. {????
142. ????int?num=0;??
143. ????for?(int?i=1;i<=8;++i)????
144. ????????{????
145. ????????????if(statue[i]==0)??
146. ????????????continue;??
147. ????????for(int?j=0;j<i;++j)????
148. ????????????{????
149. ????????????????????if(statue[j]==0)??
150. ????????????????continue;??
151. ????????????if(statue[i]>statue[j])???
152. ????????????????++num;????
153. ????????????}????
154. ????????}????
155. ????????if?(num%2==1)?return?false;????
156. ????????return?true;????
157. }????
158. ??
159. int?main()??
160. {??
161. ????freopen("e:\\zoj\\zoj_1217.txt","r",stdin);??
162. ????while(1)??
163. ????{??
164. ????????memset(hashtable,0,sizeof(hashtable));??
165. ????????int?flag=0;??
166. ????????int?num[9];??
167. ????????int?zero;??
168. ????????char?c;??
169. ????????for(int?i=0;i<9;++i)??
170. ????????{??
171. ????????????if(scanf("?%c",&c)==EOF)??
172. ????????????????return?0;??
173. ????????????if(c=='x')??
174. ????????????{?????
175. ????????????????zero=flag;??
176. ????????????????num[flag++]=0;??
177. ????????????}??
178. ????????????if(c<='9'&&c>='1')??
179. ????????????????num[flag++]=c-48;??
180. ????????????if(flag>=9)??
181. ????????????????break;????
182. ????????}??
183. ????????state?ori(num);??
184. ????????ori.zero=zero;??
185. ????????state?fin(final);??
186. ????????fin.zero=8;??
187. ????????int?ocode=getHash(num);??
188. ????????int?fcode=getHash(final);??
189. ????????hashtable[ocode]=1;??
190. ????????hashtable[fcode]=2;??
191. ????????sl[ocode]=ori;??
192. ????????sl[fcode]=fin;??
193. ????????if(!isSolveable(num))??
194. ????????????printf("unsolvable\n");??
195. ????????else??
196. ????????{?????????
197. ????????????if(check(ori,fin))??
198. ????????????????puts("");??
199. ????????????bool?f=bfs(ori,fin);??
200. ????????????int?l=x.path.length();??
201. ????????????for(int?i=0;i<l;++i)??
202. ????????????????printf("%c",x.path[i]);??
203. ????????????l=y.path.length();??
204. ????????????for(int?i=l-1;i>=0;--i)??
205. ????????????????printf("%c",y.path[i]);??
206. ????????????puts("");??
207. ????????}??
208. ????}??
209. } ?