登山之道

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

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

Q1：每一個狀態及每一次操作的表示方法？
         有許多表示方法，比如一個3*3的八數碼盤可以壓縮成一個int值表示，但不適用于15 puzzle或大于8 的puzzle問題。如果對空間要求很高，應該還可以再壓縮。本文采用一個int表示的方法。
         表示方法如下：由于int的表示范圍大于1e9，所以我們取一個int的低9位，為了方便尋找空格的位置，int的個位我們用來放空格的位置（1-9）。而前8位，按照行從上到下，列從左到右的順序依次記錄對應位置上的數字。例如：
         可以表示成 2 3 1 5 8 4 6 7 5 ，個位的5表示空格在第5位，前八位數按順序記錄。坐標轉換公式為：
     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

     為了方便本文介紹，取目標狀態為：1 2 3 4 5 6 7 8 9 即-->

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

     對應地，每種操作引起的狀態變化如下：
     r ：num值++              l ：num值--
     u ：有點復雜
     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：判斷是否存在中間狀態使START 到達END？
         用組合數學的方法可以快速地進行判斷，例如SOJ 2061題 2360題中都是關于此類的問題。但八數碼的判斷方法比他們簡單多了。

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

兩個狀態之間是否可達，可以通過計算兩者的逆序值，若兩者奇偶性相同則可達，不然兩個狀態不可達。

簡單證明一下：
         l 和 r 操作，不會影響狀態的逆序值，因為只會改變個位數（空格的位置）。
         u和d操作是使某個位置的數字 右/左移兩位。由于數字序列的每一次移動會使逆序值奇偶性改變，所以             移動兩次后奇偶性不變。
         所以四個操作均不會影響序列的奇偶性。

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

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

在普通搜索中遇到以下問題：
        a   搜索中易出現循環，即訪問某一個狀態后又來訪問該狀態。
        b 搜索路徑不佳便無法得到較好的中間狀態集（即中間狀態集的元素數量過大）。
        c 搜索過程中訪問了過多的無用狀態，這些狀態對最后的結果無幫助。


         以上三個問題中，a為致命問題，應該它可能導致程序死循環；b和c是非致命的，但若不處理好可能導致性能急劇下降。


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

         為了記錄每一個狀態是否被訪問過，我們需要有足夠的空間。八數碼問題一共有9!，這個數字并不是很大，但迎面而來的另一個問題是我們如何快速訪問這些狀態，如果是單純用鏈表的話，那么在規模相當大，查找的狀態數目十分多的時候就不能快速找到狀態，其復雜度為O(n),為了解決這個問題，本文將采用哈希函數的方法，使復雜度減為O(1)。
         這里的哈希函數是用能對許多全排列問題適用的方法。取n!為基數，狀態第n位的逆序值為哈希值第n位數。對于空格，取其（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!

         具體的原因可以去查查一些數學書，其中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（深度優先搜索）。除了DFS，還有BFS，從概念上講，兩者只是在擴展時的方向不同，DFS向深擴張，而BFS向廣擴張。在八數碼問題的解集樹中，樹的深度就表示了從初始態到目標態的步數，DFS一味向深，所以很容易找出深度較大的解。
         BFS可以保證解的深度最少，因為在未將同一深度的狀態全部訪問完前，BFS不會去訪問更深的狀態，因此比較適合八數碼問題，至少能解決求最佳解的難題。

         但是BFS和DFS一樣不能解決問題c ，因為每個狀態都需要擴張，所以廣搜很容易使待搜狀態的數目膨脹。最終影響效率。


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


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

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

例如狀態 1 3 7 2 4 6 8 5 2 和狀態 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
單個數字的manhattan應該小于5，因為對角的距離才4，若大于4則說明計算有誤。

         無論是difference還是manhattan，估計為越小越接近END，所以優先級高。
         在計算difference和manhattan時，推薦都將空格忽略，因為在difference中空格可有可無，對整體搜索影響不大。

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

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

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

         第三條是注意實現程序的方法，在起初我用sort排序f '()后再找出權值最大的狀態，而后發現用make_heap要更快。想一想，由于需要訪問的接點較多，待訪問隊列一大那么自然反復排序對速度會有影響，而堆操作則比排序更好。另一點是，實現更新待檢查隊列時的搜索也要用比較好的方法實現。我在JAVA的演示程序中用的PriorityQueue，可是結果不是很令人滿意。

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

         第五條優化策略本身與搜索無關，在做題時也沒能幫上忙，不過從理論上講是有參考價值的。記得Q6中介紹的從END開始搜起嗎？如果我們的任務是對多個START 與END進行搜索，那么我們可以在每搜索完一次后記錄下路徑，這個路徑很重要，因為在以后的搜索中如果存在START和END的路徑已經被記錄過了，那么可以直接調出結果。
         從END搜起，可以方便判斷下一次的START是否已經有路徑到END了。當前一次搜索完時，其已訪問狀態是可以直接使用的，若START不在其中，則從待訪問的狀態鏈表中按搜索策略找下一個狀態，等于接著上一次的搜索結果開始找。
         之所以沒能在速度上幫上忙，是因為這個優化策略需要加大g' ()的比重，否則很容易出現深度相當大的情況，由于前一次搜索的策略與下一次的基本無關，導致前一次的路徑無法預料，所以就會出現深度過大的情況。解決方法是加大g' ()。
策略五類似給程序加一個緩沖區，避免重復計算。如果要做八數碼的應用，緩沖區會幫上忙的。

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