登山之道

http://blog.163.com/sentimental_man/blog/static/73001618200881405851176/
簡介：
         所謂八數(shù)碼問題是指這樣一種游戲：將分別標(biāo)有數(shù)字1，2，3，…，8的八塊正方形數(shù)碼牌任意地放在一塊3×3的數(shù)碼盤上。放牌時(shí)要求不能重疊。于是，在3×3的數(shù)碼盤上出現(xiàn)了一個(gè)空格。現(xiàn)在要求按照每次只能將與空格相鄰的數(shù)碼牌與空格交換的原則，將任意擺放的數(shù)碼盤逐步擺成某種特殊的排列。如下圖表示了一個(gè)具體的八數(shù)碼問題求解。

問題分析：
         首先，八數(shù)碼問題包括一個(gè)初始狀態(tài)(START) 和目標(biāo)狀態(tài)(END)，所謂解八數(shù)碼問題就是在兩個(gè)狀態(tài)間尋找一系列可過渡狀態(tài)（START->STATE1->STATE2->...->END）。這個(gè)狀態(tài)是否存在就是我們要解決的第一個(gè)問題：

Q1：每一個(gè)狀態(tài)及每一次操作的表示方法？
         有許多表示方法，比如一個(gè)3*3的八數(shù)碼盤可以壓縮成一個(gè)int值表示，但不適用于15 puzzle或大于8 的puzzle問題。如果對空間要求很高，應(yīng)該還可以再壓縮。本文采用一個(gè)int表示的方法。
         表示方法如下：由于int的表示范圍大于1e9，所以我們?nèi)∫粋€(gè)int的低9位，為了方便尋找空格的位置，int的個(gè)位我們用來放空格的位置（1-9）。而前8位，按照行從上到下，列從左到右的順序依次記錄對應(yīng)位置上的數(shù)字。例如：
         可以表示成 2 3 1 5 8 4 6 7 5 ，個(gè)位的5表示空格在第5位，前八位數(shù)按順序記錄。坐標(biāo)轉(zhuǎn)換公式為：
     num（壓縮后的int） x y（求x行y列,1記起）1e(n)為 1乘10的n次
     int temp=(x-1)*3+y
     if   temp > num%10 then return (num / 1e(9-temp+1)) %10
     else return (num / 1e(9-temp) )%10

     為了方便本文介紹，取目標(biāo)狀態(tài)為：1 2 3 4 5 6 7 8 9 即-->

         操作本文用 u r d l 分別表示 空格的向上 向右 向下向左四個(gè)操作。比如，在簡介中的圖包括兩步操作 l d ，可能與平時(shí)玩這類游戲的習(xí)慣不符合，但這是為了和ACM例題相統(tǒng)一。

     對應(yīng)地，每種操作引起的狀態(tài)變化如下：
     r ：num值++              l ：num值--
     u ：有點(diǎn)復(fù)雜
     int t0 = 9-num%10 + 1
     int t1 = num / 1e(t0)
     int t2 = t1%1000
     t1= t1- t2 + (t2 % 100) * 10 + t2 / 100
     t1*= 1e(t0)
     return (t1 + ( (num % t0) - 3))
     d ：return前面同u操作， return返回   (t1 + ( (num % t0) + 3))

Q2：判斷是否存在中間狀態(tài)使START 到達(dá)END？
         用組合數(shù)學(xué)的方法可以快速地進(jìn)行判斷，例如SOJ 2061題 2360題中都是關(guān)于此類的問題。但八數(shù)碼的判斷方法比他們簡單多了。

         本文用的方法是計(jì)算排列的逆序數(shù)值，以2 3 1 5 8 4 6 7 5 為例子，5表示的是空格，不計(jì)算，那么求23158467 的逆序值為
         0 + 0 + 2 (1<2 1<3 ) + 0 + 0 + 1 ( 4<5 ) + 1 ( 6<8 ) + 1 ( 7<8 ) = 5
目標(biāo)狀態(tài)1 2 3 4 5 6 7 8 9 的逆序自然就是0。

兩個(gè)狀態(tài)之間是否可達(dá)，可以通過計(jì)算兩者的逆序值，若兩者奇偶性相同則可達(dá)，不然兩個(gè)狀態(tài)不可達(dá)。

簡單證明一下：
         l 和 r 操作，不會(huì)影響狀態(tài)的逆序值，因?yàn)橹粫?huì)改變個(gè)位數(shù)（空格的位置）。
         u和d操作是使某個(gè)位置的數(shù)字 右/左移兩位。由于數(shù)字序列的每一次移動(dòng)會(huì)使逆序值奇偶性改變，所以             移動(dòng)兩次后奇偶性不變。
         所以四個(gè)操作均不會(huì)影響序列的奇偶性。

Q3：如何尋找一系列的中間狀態(tài)及遇到的問題？
         要尋找這一系列中間狀態(tài)的方法是搜索，但搜索很容易遇到時(shí)間和空間上的問題。以下就是搜索的基本原理：

         由1 3 7 2 4 6 8 5 2 狀態(tài)可以衍生三個(gè)狀態(tài)，假如選擇了1 2 3 7 4 6 8 5 5 ，則又衍生三個(gè)狀態(tài)，繼續(xù)按某策略進(jìn)行選擇，一直到衍生出的新狀態(tài)為目標(biāo)狀態(tài)END 為止。
容易看出，這樣的搜索類似于從樹根開始向莖再向葉搜索目標(biāo)葉子一樣的樹型狀。由于其規(guī)模的不斷擴(kuò)大，其葉子也愈加茂密，最終的規(guī)模會(huì)大到無法控制。這樣在空間上會(huì)大大加大搜索難度，在時(shí)間上也要消耗許多。

在普通搜索中遇到以下問題：
        a   搜索中易出現(xiàn)循環(huán)，即訪問某一個(gè)狀態(tài)后又來訪問該狀態(tài)。
        b 搜索路徑不佳便無法得到較好的中間狀態(tài)集（即中間狀態(tài)集的元素?cái)?shù)量過大）。
        c 搜索過程中訪問了過多的無用狀態(tài)，這些狀態(tài)對最后的結(jié)果無幫助。


         以上三個(gè)問題中，a為致命問題，應(yīng)該它可能導(dǎo)致程序死循環(huán)；b和c是非致命的，但若不處理好可能導(dǎo)致性能急劇下降。


Q4：怎樣避免重復(fù)訪問一個(gè)狀態(tài)？
         最直接的方法是記錄每一個(gè)狀態(tài)訪問否，然后再衍生狀態(tài)時(shí)不衍生那些已經(jīng)訪問的狀態(tài)了。思想是，給每個(gè)狀態(tài)標(biāo)記一個(gè)flag，若該狀態(tài)flag = true則不衍生，若為false則衍生并修改flag為true。
在某些算法描述里，稱有兩個(gè)鏈表，一個(gè)為活鏈表（待訪問），一個(gè)為死鏈表（訪問完）。每一次衍生狀態(tài)時(shí)，先判斷它是否已在兩個(gè)鏈表中，若存在，則不衍生；若不存在，將其放入活鏈表。對于被衍生的那個(gè)狀態(tài)，放入死鏈表。

         為了記錄每一個(gè)狀態(tài)是否被訪問過，我們需要有足夠的空間。八數(shù)碼問題一共有9!，這個(gè)數(shù)字并不是很大，但迎面而來的另一個(gè)問題是我們?nèi)绾慰焖僭L問這些狀態(tài)，如果是單純用鏈表的話，那么在規(guī)模相當(dāng)大，查找的狀態(tài)數(shù)目十分多的時(shí)候就不能快速找到狀態(tài)，其復(fù)雜度為O(n),為了解決這個(gè)問題，本文將采用哈希函數(shù)的方法，使復(fù)雜度減為O(1)。
         這里的哈希函數(shù)是用能對許多全排列問題適用的方法。取n!為基數(shù)，狀態(tài)第n位的逆序值為哈希值第n位數(shù)。對于空格，取其（9-位置）再乘以8!。例如，1 3 7 2 4 6 8 5 8 的哈希值等于：
0*0! + 0*1! + 0*2! + 2*3! + 1*4! + 1*5! + 0*6! + 3*7! + (9-8)*8! = 55596 <9!

         具體的原因可以去查查一些數(shù)學(xué)書，其中1 2 3 4 5 6 7 8 9 的哈希值是0 最小，8 7 6 5 4 3 2 1 0 的哈希值是（9!-1）最大，而其他值都在0 到（9!-1） 中，且均唯一。

Q5：如何使搜索只求得最佳的解？
         普通的搜索稱為DFS（深度優(yōu)先搜索）。除了DFS，還有BFS，從概念上講，兩者只是在擴(kuò)展時(shí)的方向不同，DFS向深擴(kuò)張，而BFS向廣擴(kuò)張。在八數(shù)碼問題的解集樹中，樹的深度就表示了從初始態(tài)到目標(biāo)態(tài)的步數(shù)，DFS一味向深，所以很容易找出深度較大的解。
         BFS可以保證解的深度最少，因?yàn)樵谖磳⑼簧疃鹊臓顟B(tài)全部訪問完前，BFS不會(huì)去訪問更深的狀態(tài)，因此比較適合八數(shù)碼問題，至少能解決求最佳解的難題。

         但是BFS和DFS一樣不能解決問題c ，因?yàn)槊總€(gè)狀態(tài)都需要擴(kuò)張，所以廣搜很容易使待搜狀態(tài)的數(shù)目膨脹。最終影響效率。


Q6：該如何減少因廣搜所擴(kuò)張的與目標(biāo)狀態(tài)及解無關(guān)的狀態(tài)？
         前面所說的都是從START狀態(tài)向END狀態(tài)搜索，那么，將END狀態(tài)與START狀態(tài)倒一下，其實(shí)會(huì)有另一條搜索路徑（Q8策略三討論），但簡單的交換END與START并不能縮小狀態(tài)膨脹的規(guī)模。我們可以將正向與反向的搜索結(jié)合起來，這就是雙向廣度搜索。
         雙向廣搜是指同時(shí)從START和END兩端搜，當(dāng)某一端所要訪問的一個(gè)狀態(tài)是被另一端訪問過的時(shí)候，即找到解，搜索結(jié)束。它的好處是可以避免廣搜后期狀態(tài)的膨脹。
采用雙向廣度搜索可以將空間和時(shí)間節(jié)省一半！


Q7：決定一個(gè)快的檢索策略？
         雙向廣搜能大大減少時(shí)間和空間，但在有的情況下我們并不需要空間的節(jié)省，比如在Q4中已經(jīng)決定了我們需要使用的空間是9！，所以不需要節(jié)省。這樣我們可以把重點(diǎn)放在時(shí)間的縮短上。
         啟發(fā)式搜索是在路徑搜索問題中很實(shí)用的搜索方式，通過設(shè)計(jì)一個(gè)好的啟發(fā)式函數(shù)來計(jì)算狀態(tài)的優(yōu)先級(jí)，優(yōu)先考慮優(yōu)先級(jí)高的狀態(tài)，可以提早搜索到達(dá)目標(biāo)態(tài)的時(shí)間。A*是一種啟發(fā)式搜索的，他的啟發(fā)式函數(shù)f ' ()=g' () + h' () 能夠應(yīng)用到八數(shù)碼問題中來。
         g' () ----- 從起始狀態(tài)到當(dāng)前狀態(tài)的實(shí)際代價(jià)g*()的估計(jì)值，g' () >= g*()
         h' () ----- 從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的實(shí)際代價(jià)h*()的估計(jì)值，h' () <= h*()
注意兩個(gè)限制條件：
         （1）h' () <= h*()   （2）任意狀態(tài)的f '()值必須大于其父狀態(tài)的f '()值，即f '()單調(diào)遞增。

         其中，g' () 是搜索的深度， h' () 則是一個(gè)估計(jì)函數(shù)，用以估計(jì)當(dāng)前態(tài)到目標(biāo)態(tài)可能的步數(shù)。解八數(shù)碼問題時(shí)一般有兩種估計(jì)函數(shù)。比較簡單的是difference ( Status a,   Status b )， 其返回值是a 和b狀態(tài)各位置上數(shù)字不同的次數(shù)。另一種比較經(jīng)典的是曼哈頓距離    manhattan ( Status a, Status b )，其返回的是各個(gè)數(shù)字從a的位置到b的位置的距離（見例子）。

例如狀態(tài) 1 3 7 2 4 6 8 5 2 和狀態(tài) 1 2 3 4 5 6 7 8 9 的difference 是5（不含空格）。而他的manhattan 距離是：
1 (7d一次) + 1 (2u一次) + 2 (4l兩次) + 3 (6r兩次u一次) + 2 (5u一次l一次) = 9
單個(gè)數(shù)字的manhattan應(yīng)該小于5，因?yàn)閷堑木嚯x才4，若大于4則說明計(jì)算有誤。

         無論是difference還是manhattan，估計(jì)為越小越接近END，所以優(yōu)先級(jí)高。
         在計(jì)算difference和manhattan時(shí)，推薦都將空格忽略，因?yàn)樵赿ifference中空格可有可無，對整體搜索影響不大。

         本文后面的實(shí)現(xiàn)將使用manhattan 不計(jì)空格的方法。其實(shí)，每移動(dòng)一步，不計(jì)空格，相當(dāng)于移動(dòng)一個(gè)數(shù)字。如果每次移動(dòng)都是完美的，即把一個(gè)數(shù)字歸位，那么START態(tài)到END態(tài)的距離就是manhattan。反過來說，manhattan是START到END態(tài)的至少走的步數(shù)。
         回到f '()=g' ()+ h' ()，其實(shí)廣度搜索是h' ()=0的一種啟發(fā)式搜索的特例，而深度搜索是    f ' ()=0 的一般搜索。h' ()對于優(yōu)化搜索速度有很重要的作用。

Q8：能否進(jìn)一步優(yōu)化檢索策略？
         答案是肯定的。
         A*搜索策略的優(yōu)劣就是看h' ()的決定好壞。前面列舉了兩個(gè)h' ()的函數(shù)，但光有這兩個(gè)是不夠的。經(jīng)過實(shí)驗(yàn)分析，在f '()中，g '()決定的是START態(tài)到END態(tài)中求得的解距離最優(yōu)解的距離。 而h' () 能影響搜索的速度。
         所以優(yōu)化的第一條策略是，放大h' ()，比如，讓h '()= 10* manhattan()，那么f '()= g' ()+10*manhattan()，可能提高搜索速度。可惜的是所得的解將不再會(huì)是最優(yōu)的了。
         為什么放大h'()能加快搜索速度，我們可以想象一下，h'()描述的是本狀態(tài)到END態(tài)的估計(jì)距離，估計(jì)距離越短自然快一點(diǎn)到達(dá)END態(tài)。而 g' ()描述的是目前的深度，放大h' ()的目的是盡量忽略深度的因素，是一種帶策略的深搜，自然速度會(huì)比廣搜和深搜都快，而因?yàn)闇p少考慮了深度因素，所以離最優(yōu)解就越來越遠(yuǎn)了。關(guān)于h' ()放大多少，是很有趣的問題，有興趣可以做些實(shí)驗(yàn)試試。

         第二條是更新待檢查的狀態(tài)，由于A*搜索會(huì)需要一個(gè)待檢查的序列。首先，在Q4已經(jīng)提到用哈希避免重復(fù)訪問同一狀態(tài)。而在待檢查隊(duì)列中的狀態(tài)是未完成擴(kuò)張的狀態(tài)，如果出現(xiàn)了狀態(tài)相同但其g '()比原g '()出色的情況，那么我們更希望的是搜索新狀態(tài)，而不是原狀態(tài)。這樣，在待檢查隊(duì)列中出現(xiàn)重復(fù)狀態(tài)時(shí)，只需更新其g'() 就可以了。

         第三條是注意實(shí)現(xiàn)程序的方法，在起初我用sort排序f '()后再找出權(quán)值最大的狀態(tài)，而后發(fā)現(xiàn)用make_heap要更快。想一想，由于需要訪問的接點(diǎn)較多，待訪問隊(duì)列一大那么自然反復(fù)排序?qū)λ俣葧?huì)有影響，而堆操作則比排序更好。另一點(diǎn)是，實(shí)現(xiàn)更新待檢查隊(duì)列時(shí)的搜索也要用比較好的方法實(shí)現(xiàn)。我在JAVA的演示程序中用的PriorityQueue，可是結(jié)果不是很令人滿意。

         第四條優(yōu)化策略是使用IDA*的算法，這是A*算法的一種，ID名為Iterative deepening是迭代加深的意思。思想是如下：
順便準(zhǔn)備一個(gè)記錄一次循環(huán)最小值的temp=MAX, h' 取 manhattan距離
     先估算從START態(tài)到END態(tài)的h'() 記錄為MIN，將START放入待訪問隊(duì)列
     讀取隊(duì)列下一個(gè)狀態(tài)，到隊(duì)列尾則GOTO⑦
     若g'() > MIN GOTO ⑥
     若g'() + h'()   > MIN 是否為真，真GOTO ⑥，否 GOTO ⑤
     擴(kuò)展該狀態(tài)，并標(biāo)記此狀態(tài)已訪問。找到END態(tài)的話就結(jié)束該算法。GOTO ②
     temp = min(manhattan , temp),GOTO ③
     若無擴(kuò)展過狀態(tài)，MIN=temp （ID的意思在這里體現(xiàn)）從頭開始循環(huán)GOTO ②

         第五條優(yōu)化策略本身與搜索無關(guān)，在做題時(shí)也沒能幫上忙，不過從理論上講是有參考價(jià)值的。記得Q6中介紹的從END開始搜起嗎？如果我們的任務(wù)是對多個(gè)START 與END進(jìn)行搜索，那么我們可以在每搜索完一次后記錄下路徑，這個(gè)路徑很重要，因?yàn)樵谝院蟮乃阉髦腥绻嬖赟TART和END的路徑已經(jīng)被記錄過了，那么可以直接調(diào)出結(jié)果。
         從END搜起，可以方便判斷下一次的START是否已經(jīng)有路徑到END了。當(dāng)前一次搜索完時(shí)，其已訪問狀態(tài)是可以直接使用的，若START不在其中，則從待訪問的狀態(tài)鏈表中按搜索策略找下一個(gè)狀態(tài)，等于接著上一次的搜索結(jié)果開始找。
         之所以沒能在速度上幫上忙，是因?yàn)檫@個(gè)優(yōu)化策略需要加大g' ()的比重，否則很容易出現(xiàn)深度相當(dāng)大的情況，由于前一次搜索的策略與下一次的基本無關(guān)，導(dǎo)致前一次的路徑無法預(yù)料，所以就會(huì)出現(xiàn)深度過大的情況。解決方法是加大g' ()。
策略五類似給程序加一個(gè)緩沖區(qū)，避免重復(fù)計(jì)算。如果要做八數(shù)碼的應(yīng)用，緩沖區(qū)會(huì)幫上忙的。

Q10：怎樣記錄找到的路徑？
         當(dāng)找到解的時(shí)候我們就需要有類似回退的工作來整理一條解路徑，由于使用了不是簡單的DFS，所以不能借助通過函數(shù)調(diào)用所是使用的程序棧。
         我們可以手工加一個(gè)模擬棧。在Q4中解決了哈希的問題，利用哈希表就能快速訪問狀態(tài)對應(yīng)的值，在這里，我們把原來的bool值改為char或其他能表示一次操作（至少需要5種狀態(tài)，除了u r l d 外還要能表示狀態(tài)已訪問）的值就行了。
         在搜索到解時(shí)，記錄下最后一個(gè)訪問的狀態(tài)值，然后從讀取該狀態(tài)對應(yīng)的操作開始，就像棧操作的退棧一樣，不停往回搜，直到找到搜索起點(diǎn)為止。記錄好棧退出來的操作值，就是一條路徑。