2009年8月11日 星期二
題目鏈接：PKU 1077 Eight
分類：bfs,雙向bfs,A*
題目分析與算法原型
這道題目是前一陣子做的，一直沒有寫解題報告，主要是想找個時間好好的總結一下這道題，因為從這道題中收獲了很多東西，比方說A*的大體思想，如何設計啟發式函數使得其滿足A*算法的約束性，還有就是全排列哈希的方式（不存在沖突），以及堆優化時遇到已經標記過的但是當前值更小的情況下如何去更新而不是再次插入（以前的時候我一直都采用的是再次插入，這樣子空間的復雜度高起來了）等等........總的來說收獲很多，所有需要好好地記錄一下
關于此題的A*解法（當然bfs或雙向bfs也可以解決），8數碼問題經典的啟發式函數有兩種：比較簡單的是difference ( Status a, Status b )， 其返回值是a 和b狀態各位置上數字（空格除外）不同的次數。另一種比較經典的是曼哈頓距離 manhattan ( Status a, Status b )，其返回的是各個數字（除卻空格）從a的位置到b的位置的最短距離的和。學過A*的都應該知道，若想設計的A*算法能夠保證找到最優解，其啟發式函數(f(n)=g(n)+h(n) ，其中f(n) 是節點n的估價函數，g(n)實在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目 標節點最佳路徑的估計代價)必須滿足兩點：1.h(n)<h'(n),h'(n)為從當前節點到目標點的實際的最優代價值。2.每次擴展的節點的f值至少不比父節點的f值小。
我們先來看第一個啟發函數，即difference,容易看出此時第一個條件顯然滿足，關于第二個條件，g( n)以為搜索的深度，所以子節點的g比父節點的g大1，然而，每次將空白位置與周圍的某個數字交換后（不算空格），對于交換的這個數字，有兩種結果，I.其和目標的位置相同。II.和目標的位置不同，即就是說h最多減少1，或者不變，所以g+h要么不變，要么比原先大1，此時兩個條件都滿足，因此該啟發式函數能保證找到最優解。
再看第二個啟發式函數，即 manhattan ，也容易看出其定符合第一個條件，對于第二個條件，因為不算空格，所以每次交換我們只考慮和空格交換的那個數字，可以發現那個數字最多離目標位置前進一個（或者不變，或者后退一個），也就是說h之多減少1個，然而g已經加了1，所以g+h至少和原來的相等，或者更大，這樣一來，第二個條件也滿足了，由此我們可以發現，這兩個啟發式函數都可以保證A*找到最優解（關于為什么滿足了A*的這兩個條件就一定保證能找到最優解，可以去參考一下相應的人工智能的書籍，里面有詳細的證明）
還有關于這道題的判重可采用全排列之哈希方式（點此鏈接）..........
（PS：說起這道題，不得不提一件事，那就是我在寫的時候將“des=now[i]-'0'-1;”不小心寫成了“des=now[i]-1”，拜托，兩個值整整差了48啊，而且我是將他作為D數組的一個下標，我的D數組才定義了D[10][10],這樣你會發現顯然已經數組越界了，然后神奇的事情居然就發生了，這樣子居然........AC了!!!!!!!!!，orz............真不知道是不是偶的RP太好了，這樣子能A掉，想想很不可思議，也正因為如此，使得我的程序當時出現了一個異常詭異的地方，這個詭異的地方說起來有點麻煩就不多說了，反正我一直都沒找出是怎么回事，后來才發現這個致命的筆誤，再次膜拜自己，居然這樣子都能過，狂暈啊，RP太好了點吧.........,而且改這個錯誤之前的程序跑的是150ms左右，改了后就能跑到0ms了，很想不通，這個錯誤居然還能影響時間........orz.......orz........orz..........
總結：RP的力量果然很強大，所以偶們都需要好好積攢RP，適當的時候說不定能創造奇跡.........）
Code：
1
#include<stdio.h>
2#include<string.h>
3#include<math.h>
4#include<time.h>
5#include<stdlib.h>
6#define max 365000
7
8
char beg[12],end[12],pace[9][5]=
{"dr","dlr","dl","udr","udlr","udl","ur","ulr","ul"},cz[max],ss[50];
9int count,pp,mincost[max],fm[max],place[max],jc[8]={1,2,6,24,120,720,5040,40320},D[10][10];
10int a[9][2]={{0,0},{1,0},{2,0},{0,-1},{1,-1},{2,-1},{0,-2},{1,-2},{2,-2}},goal;
11bool flag[max];
12
13struct node
14{
15
int pos,g,h,num;
16 char s[10];
17
}queue[max];
18void down_min_heap(int n,int h)//n表示堆元素的個數，從0開始編號,從h開始往下調整
19{
20 int i=h,j=2*i+1;
21 node temp=queue[i];
22 while(j<n)
23
{
24 if(j<n-1&&queue[j].g+queue[j].h>queue[j+1].g+queue[j+1].h)j++;//若右孩子存在，且右孩子比較小，取右
25 if(temp.g+temp.h<queue[j].g+queue[j].h)break;
26 else
27 {
28 place[queue[j].num]=i;
29 queue[i]=queue[j];
30 i=j;
31 j=2*i+1;
32
}
33 }
34 queue[i]=temp;
35 place[temp.num]=i;
36}
37void up_min_heap(int s)
38{
39 while (s>0&&queue[s].g+queue[s].h<queue[(s-1)/2].g+queue[(s-1)/2].h) //從s開始往上調整
40 {
41 place[queue[s].num]=(s-1)/2;
42 place[queue[(s-1)/2].num]=s;
43 node tt=queue[s];
44 queue[s]=queue[(s-1)/2];
45 queue[(s-1)/2]=tt;
46 s=(s-1)/2;
47 }
48}
49node pop()
50{
51 node res=queue[0];
52 queue[0]=queue[count-1];
53 place[queue[count-1].num]=0;
54 count--;
55 down_min_heap(count,0);
56 return res;
57}
58void push(node x)
59{
60 queue[count]=x;
61 place[x.num]=count;
62 count++;
63 up_min_heap(count-1);
64}
65int cal(char s[]) //計算全排列的哈希值（唯一對應）
66{
67 int i,j,cnt,res=0;
68 for(i=1;i<9;i++)
69 {
70 cnt=0;
71 for(j=0;j<i;j++)if(s[j]>s[i])cnt++;
72 cnt*=jc[i-1];
73 res+=cnt;
74 }
75 return res;
76}
77int dist(int now ,int des)//計算兩個位置之間的最小步數
78{
79 int px=(int)(fabs(a[now][0]-a[des][0])),py=(int)(fabs(a[now][1]-a[des][1]));
80 return px+py;
81}
82
83//啟發函數采用曼哈頓距離，即從當前狀態下的每個數字（空格除開），分別到目標狀態下相應數字的最小步數之和
84
85int estimate(char now[])
86{
87 int res=0,i,des;
88 for(i=0;i<9;i++)
89 {
90 if(now[i]!='0')
91 {
92 des=now[i]-'0'-1;
93 res+=D[i][des];
94 }
95 }
96 return res;
97}
98int change(char s[],char op,int pos) //互換位置，返回換后的空格位置
99{
100 int end;
101 switch(op)
102 {
103 case 'u':end=pos-3;break;
104 case 'd':end=pos+3;break;
105 case 'l':end=pos-1;break;
106 case 'r':end=pos+1;break;
107 }
108 char mid=s[pos];
109 s[pos]=s[end];
110 s[end]=mid;
111 return end;/**////返回調整后空格的位置
112}
113void bfs(char beg[],char end[])
114{
115 int i,num;
116 queue[0].pos=pp;
117 queue[0].g=0;
118 queue[0].h=estimate(beg);
119 num=cal(beg);
120 queue[0].num=num;
121 strcpy(queue[0].s,beg);
122 count=1;
123
124 flag[num]=true;
125 cz[num]='*';
126 fm[num]=-1;
127 place[num]=0;
128 mincost[num]=queue[0].h;
129 while(count>0)
130 {
131 node tt=pop();
132 place[tt.num]=count;
133 if(tt.num==goal)
134 {
135 char ans[1000];
136 int k=0,fp;
137 fp=tt.num;
138 while(fp!=num)
139 {
140 ans[k++]=cz[fp];
141 fp=fm[fp];
142 }
143 int jj;
144 for(jj=k-1;jj>=0;jj--)printf("%c",ans[jj]);
145 printf("\n");
146 return;
147 }
148 int len=strlen(pace[tt.pos]);
149 for(i=0;i<len;i++)
150 {
151 node x=tt;
152 x.pos=change(x.s,pace[tt.pos][i],x.pos);
153 int k=cal(x.s);
154 x.num=k;
155 x.g++;
156 x.h=estimate(x.s);
157 if(!flag[k])
158 {
159 flag[k]=true;
160 mincost[k]=x.g+x.h;
161 fm[k]=tt.num;
162 cz[k]=pace[tt.pos][i];
163 push(x);
164 }
165 else if(flag[k]&&x.g+x.h<mincost[k])
166 {
167 mincost[k]=x.g+x.h;
168 fm[k]=tt.num;
169 cz[k]=pace[tt.pos][i];
170 queue[place[k]]=x;
171 up_min_heap(place[k]);
172 }
173 }
174 }
175}
176bool check(char beg[])//檢測目標狀態是否可達
177{
178 int i,j,cnt,res=0;
179 for(i=1;i<9;i++)
180 {
181 cnt=0;
182 for(j=0;j<i;j++)if(beg[j]>beg[i])cnt++;
183 res+=cnt;
184 }
185 for(i=0;i<9;i++)
186 {
187 if(beg[i]=='0')
188 {
189 res+=D[i][8];
190 break;
191 }
192 }
193 if((res%2)==0)return true;
194 else return false;
195}
196int main()
197{
198 int i,j;
199 strcpy(end,"123456780");
200 goal=cal(end);
201
202 for(i=0;i<9;i++)
203 for(j=0;j<9;j++)D[i][j]=dist(i,j);
204 while(gets(ss))
205 {
206 int len=strlen(ss),pos=0;
207 memset(flag,false,sizeof(flag));
208 for(i=0;i<len;i++)
209 {
210 if(ss[i]=='x')//空格部分用0代替
211 {
212 pp=pos;
213 beg[pos++]='0';
214 }
215 else if(ss[i]>='1'&&ss[i]<='8')beg[pos++]=ss[i];
216 }
217 beg[9]='\0';
218 if(!check(beg))printf("unsolvable\n");
219 else bfs(beg,end);
220 }
221 return 1;
222}
223