2009年8月11日 星期二

題目鏈接：PKU 1077 Eight  

分類：bfs,雙向bfs,A*

題目分析與算法原型
         這道題目是前一陣子做的，一直沒(méi)有寫解題報(bào)告，主要是想找個(gè)時(shí)間好好的總結(jié)一下這道題，因?yàn)閺倪@道題中收獲了很多東西，比方說(shuō)A*的大體思想，如何設(shè)計(jì)啟發(fā)式函數(shù)使得其滿足A*算法的約束性，還有就是全排列哈希的方式（不存在沖突），以及堆優(yōu)化時(shí)遇到已經(jīng)標(biāo)記過(guò)的但是當(dāng)前值更小的情況下如何去更新而不是再次插入（以前的時(shí)候我一直都采用的是再次插入，這樣子空間的復(fù)雜度高起來(lái)了）等等........總的來(lái)說(shuō)收獲很多，所有需要好好地記錄一下
        關(guān)于此題的A*解法（當(dāng)然bfs或雙向bfs也可以解決），8數(shù)碼問(wèn)題經(jīng)典的啟發(fā)式函數(shù)有兩種：比較簡(jiǎn)單的是difference ( Status a,  Status b )， 其返回值是a 和b狀態(tài)各位置上數(shù)字（空格除外）不同的次數(shù)。另一種比較經(jīng)典的是曼哈頓距離   manhattan ( Status a, Status b )，其返回的是各個(gè)數(shù)字（除卻空格）從a的位置到b的位置的最短距離的和。學(xué)過(guò)A*的都應(yīng)該知道，若想設(shè)計(jì)的A*算法能夠保證找到最優(yōu)解，其啟發(fā)式函數(shù)(f(n)=g(n)+h(n) ，其中f(n) 是節(jié)點(diǎn)n的估價(jià)函數(shù)，g(n)實(shí)在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目 標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià))必須滿足兩點(diǎn)：1.h(n)<h'(n),h'(n)為從當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的實(shí)際的最優(yōu)代價(jià)值。2.每次擴(kuò)展的節(jié)點(diǎn)的f值至少不比父節(jié)點(diǎn)的f值小。
       我們先來(lái)看第一個(gè)啟發(fā)函數(shù)，即difference,容易看出此時(shí)第一個(gè)條件顯然滿足，關(guān)于第二個(gè)條件，g( n)以為搜索的深度，所以子節(jié)點(diǎn)的g比父節(jié)點(diǎn)的g大1，然而，每次將空白位置與周圍的某個(gè)數(shù)字交換后（不算空格），對(duì)于交換的這個(gè)數(shù)字，有兩種結(jié)果，I.其和目標(biāo)的位置相同。II.和目標(biāo)的位置不同，即就是說(shuō)h最多減少1，或者不變，所以g+h要么不變，要么比原先大1，此時(shí)兩個(gè)條件都滿足，因此該啟發(fā)式函數(shù)能保證找到最優(yōu)解。
        再看第二個(gè)啟發(fā)式函數(shù)，即 manhattan ，也容易看出其定符合第一個(gè)條件，對(duì)于第二個(gè)條件，因?yàn)椴凰憧崭瘢悦看谓粨Q我們只考慮和空格交換的那個(gè)數(shù)字，可以發(fā)現(xiàn)那個(gè)數(shù)字最多離目標(biāo)位置前進(jìn)一個(gè)（或者不變，或者后退一個(gè)），也就是說(shuō)h之多減少1個(gè)，然而g已經(jīng)加了1，所以g+h至少和原來(lái)的相等，或者更大，這樣一來(lái)，第二個(gè)條件也滿足了，由此我們可以發(fā)現(xiàn)，這兩個(gè)啟發(fā)式函數(shù)都可以保證A*找到最優(yōu)解（關(guān)于為什么滿足了A*的這兩個(gè)條件就一定保證能找到最優(yōu)解，可以去參考一下相應(yīng)的人工智能的書籍，里面有詳細(xì)的證明）
        還有關(guān)于這道題的判重可采用全排列之哈希方式（點(diǎn)此鏈接）..........
         （PS：說(shuō)起這道題，不得不提一件事，那就是我在寫的時(shí)候?qū)?#8220;des=now[i]-'0'-1;”不小心寫成了“des=now[i]-1”，拜托，兩個(gè)值整整差了48啊，而且我是將他作為D數(shù)組的一個(gè)下標(biāo)，我的D數(shù)組才定義了D[10][10],這樣你會(huì)發(fā)現(xiàn)顯然已經(jīng)數(shù)組越界了，然后神奇的事情居然就發(fā)生了，這樣子居然........AC了!!!!!!!!!，orz............真不知道是不是偶的RP太好了，這樣子能A掉，想想很不可思議，也正因?yàn)槿绱耍沟梦业某绦虍?dāng)時(shí)出現(xiàn)了一個(gè)異常詭異的地方，這個(gè)詭異的地方說(shuō)起來(lái)有點(diǎn)麻煩就不多說(shuō)了，反正我一直都沒(méi)找出是怎么回事，后來(lái)才發(fā)現(xiàn)這個(gè)致命的筆誤，再次膜拜自己，居然這樣子都能過(guò)，狂暈啊，RP太好了點(diǎn)吧.........,而且改這個(gè)錯(cuò)誤之前的程序跑的是150ms左右，改了后就能跑到0ms了，很想不通，這個(gè)錯(cuò)誤居然還能影響時(shí)間........orz.......orz........orz..........
           總結(jié)：RP的力量果然很強(qiáng)大，所以偶們都需要好好積攢RP，適當(dāng)?shù)臅r(shí)候說(shuō)不定能創(chuàng)造奇跡.........）

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
  8char 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表示堆元素的個(gè)數(shù)，從0開始編號(hào),從h開始往下調(diào)整
 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開始往上調(diào)整
 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[])  //計(jì)算全排列的哈希值（唯一對(duì)應(yīng)）
 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)//計(jì)算兩個(gè)位置之間的最小步數(shù)
 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//啟發(fā)函數(shù)采用曼哈頓距離，即從當(dāng)前狀態(tài)下的每個(gè)數(shù)字（空格除開），分別到目標(biāo)狀態(tài)下相應(yīng)數(shù)字的最小步數(shù)之和
 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) //互換位置，返回?fù)Q后的空格位置
 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;/**////返回調(diào)整后空格的位置
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[])//檢測(cè)目標(biāo)狀態(tài)是否可達(dá)
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