程式設計之美 一摞烙餅的排序問題

一摞烙餅問題其實是一個很有意思的問題，它的描述是讓一摞随機順序的烙餅通過單手翻轉的方式進行排序，以達到這摞烙餅由小到大順序放置在盤子上的目 的，其特點是每次翻轉都會導緻第一個烙餅到所要反轉的那個烙餅之間的順序變為逆序。我們的目的是求出次數最少的翻轉方案以及翻轉次數，很顯然這是一個最優 化問題，我們本能想到的是動态規劃、貪心以及分支限界三種方法。

      書中給出的遞歸算法或稱之為分支限界法（即周遊+剪枝=分支限界）秉承了遞歸算法傳統的簡單、明了，但效率偏低的特點。這個問題的實質，我們在每一次反轉 之前其實是需要做出一種選擇，這種選擇必須能夠導緻全局最優解。遞歸算法就是遞歸的建構所有解（實際是一顆搜尋樹），并在周遊過程中不斷重新整理 LowerBound和UpperBound，以及目前的最優解（剪枝），并最終找到一個最整體優解。在這種政策下，提高算法的效率隻能寄希望于剪枝方法 的改進。但是這種方法顯然不是多項式時間的，有沒有多項式時間的算法呢？

    書中P22頁提到動态規劃，但最後卻給出了解決最優化問題普遍适用但效率可能是最差的遞歸方法。這不禁讓人疑惑：這也不美啊！？如果我們能證明該問題滿足 動态規劃或貪心算法的使用條件，解決問題的時間複雜度将會降到多項式時間甚至N^2。但書中提到動态規劃卻最終沒有使用，又沒有講明原因，我覺得是一種疏 失（應該不算錯誤）。那我們就來想一下為什麼沒有動态規劃或貪心算法的原因。

    我們知道動态規劃方法是一種自底向上的擷取問題最優解的方法，它采用子問題的最優解來構造全局最優解。利用動态規劃求解的問題需要滿足兩個條件：即（1） 最優子結構（2）子結構具有重疊性。條件（1）使我們可以利用子問題的最優解來構造全局最優解，而條件（2）是我們在計算過程中可以利用子結構的重疊性來 減少運算次數。此外，《算法導論》上還以有向圖的無權最短路徑和無權最長路徑為例提出條件（3）子問題必須獨立。

    首先我們假定烙餅問題存在優化子結構。假如我們有N個烙餅，把他們以其半徑由小到大進行編号。優化子結構告訴我們對于i個烙餅，我們隻需要先排列前(i- 1)個，然後再将第i個歸位；或先排列第2到i個，最後将第一個歸位；又或是找到一個位置k[i<=k<j]像矩陣乘法加括号那樣，使得我們 先排列前k個，再排列後j-k個，最後再将二者合并，以找到一個最佳翻轉政策等等...

      根據動态規劃算法的計算過程，我們需要一個N*N矩陣M，其中M[i][j]表示将編号i至編号j的烙餅排序所需要的翻轉次數。但我們真的能從M[0] [0..j-1]和M[1][j+1]，或與M[i][j]同行同列的值來計算M[i][j]嗎？如果能，我們就能獲得多項式時間的算法。  

    我們來看書中給出的例子：(頂端)3，2，1，6，5，4，9，8，7，0(底端)，我們最終的目标是計算M[0][9]。

這裡我們以計算M[0][4]為例，計算的矩陣我已經在下面給出： 

  0 1  2  3  4  5  6  7  8  9

  ------------------------

0|0 1 (1){1}[？]

1|  0  1 (1){1} 

2|     0  1 (1)

3|        0  0

4|           0

  ------------------

  實際上如果我們要向将0-4号烙餅(注意：烙餅編号也等同于其半徑)排為正序(中間有其他烙餅也沒關系)，按照程式給出的結果， 我們需要進行3次翻轉，分别為[2,5,9](即分别翻轉隊列中第二(從零開始)、五、九個烙餅，這裡的數字不是烙餅的編号)： 

  [1]  [2]  [3]  6   5  [4]  9  8  7  [0]

  [4]   5    6  [3] [2] [1]  9  8  7  [0]

  [0]   7    8   9  [1] [2] [3] 6  5  [4]

        我們知道，該矩陣中每一個數的背後都隐含着一個烙餅的排列，例如M[0][4]就應該對應0,7,8,9,1,2,3,6,5,4

  是以，每一個M[i][j]的選取都蘊含着其子排列的順序的變化。

      在計算M[i][j]的時候，我們需要計算i-j号餅的全部劃分(不包括全部為1的劃分)所能構成的翻轉結構，并取其翻轉 次數最少的哪一個最為M[i][j]的最終值。例如，我們在計算M[0][4]的時候，需要檢視：

   M[0][0],M[1][4]

   M[0][1],M[2][4]

   M[0][2],M[3][4]

   M[0][3],M[4][4]

   M[0][0],M[1][1],M[2][2],M[3][4]

   .....//中間略

   M[0][3],M[4][4]

   如果再加上運算過程中我們可以淘汰超過最大反轉次數的方案（剪枝？），我們完成全部的運算，所經曆的運算過程的時間複雜度已經不是多項式時間的，而是和先前所說的遞歸方法已沒什麼兩樣。

     造成這種現象的原因是：某個子問題的最優解不一定是整體的最優解，是以我們在處理整個問題的時候，需要周遊所有可能的子問題，并計算它到整體問題所消耗的代價，才能最終作出有利于整體問題的選擇。

   是以我們一開始的假設，即烙餅問題有優化子結構的假設是錯誤的。是以我們不能用動态規劃，同理也不能用貪心算法。

   但說到每一步的“選擇”問題，我記得算法導論上有一個叫做“A*”的算法，它的思想是在進行每一步選擇的時候都“推算”最終可能需要的代價，并選擇目前代價最小的分支進行周遊。這個“推算”的結果可能不會是最終的代價，而隻是作為分支選擇的依據。

    我 們已經知道，關于一摞烙餅的排序問題我們可以采用遞歸的方式來完成。其間我們要做的是盡量調整UpperBound和LowerBound，已減少運算次 數。對于這種方法，在算法課中我們應該稱之為：Tree Searching Strategy。即整個解空間為一棵搜尋樹，我們按照一定的政策周遊解空間，并尋找最優解。一旦找到比目前最優解更好的解，就用它替換目前最優解，并用 它來進行“剪枝”操作來加速求解過程。

書中給出的解法就是采用深度優先的方式來周遊這棵搜尋樹，例如要排序[4,2,1,3]，最大反轉次數不應該超過(4-1)*2=6次，是以搜尋樹的深度也不應大于6，搜尋樹如下圖所示：

這 裡隻列到第三層，其中被畫斜線的方塊由于和上層的某一節點的狀态重複而無需再擴充下去（即便擴充也不可能比有相同狀态的上層節點的代價少）。我們可以看到 在右子樹中的一個分支，隻需要用3次反轉即可完成，我們的目标是如何更為快速有效的找到這一分支。直覺上我們可以看到：基本的搜尋方法要先從左子樹開始， 是以要找到本例最佳的方案的代價是很高的（利用書中的算法需要查找292次）。 既然要周遊搜尋樹，就有廣度優先和深度優先之分，可以分别用棧和隊列來實作（當然也可以用遞歸的方法）。那麼如何能更有效地解決問題呢？我們主要考慮一下幾種方法： （1）       爬山法 該 方法是在深度優先的搜尋過程中使用貪心方法确定搜尋方向，它實際上是一種深度優先搜尋政策。爬山法采用啟發式側讀來排序節點的擴充順序，其關鍵點就在于測 度函數f(n)的定義。我們來看一下如何為上例定制代價函數f(n)，以快速找到右子樹中最好的那個分支（很像貪心算法，呵呵）。 我們看到在[1,2,4,3]中，[1,2,3]已經相對有序，而[4]位與他們之間，要想另整體有序，需要4次反轉；而[3,1,2,4]中，由于[4]已經就位，剩下的數變成了長度為3的子隊列，而子隊列中[1,2]有序，令其全體有序隻需要2次反轉。 是以我們的代價函數應該如下定義： 1 從目前狀态的最後一個餅開始搜尋，如果該餅在其應該在的位置（中間斷開不算），則跳過； 2 自後向前的搜尋過程中，如果碰到兩個數不相鄰的情況，就+1 這樣我們就可以在本例中迅速找到最優分枝。因為在樹的第一層 f(2,4,1,3)=3，f(1,2,4,3)=2，f(3,1,2,4)=1，是以我們選擇[3,1,2,4]那一枝，而在[3,1,2,4]的下一層： f(1,3,2,4)=2，f(2,1,3,4)=1，f(4,2,1,3)=2，是以我們又找到了最佳的路徑。 上面方法看似不錯，但是數字比較多的時候呢？我們來看書中給出的10個數的例子： [3,2,1,6,5,4,9,8,7,0] ， 程式給出的最佳翻轉序列為{ 4,8,6,8,4,9 }（從0開始算起） 那麼，對于搜尋樹的第一層，按照上面的算法我計算的結果如下： f(2,3,1,6,5,4,9,8,7,0)=4        f(1,2,3,6,5,4,9,8,7,0)=3        f(6,1,2,3,5,4,9,8,7,0)=4        f(5,6,1,2,3,4,9,8,7,0)=3        f( 4,5,6,1,2,3,9,8,7,0 ) =3        f(9,4,5,6,1,2,3,8,7,0)=4        f(8,9,4,5,6,1,2,3,7,0)=4 f(7,8,9,4,5,6,1,2,3,0)=3 f(0,7,8,9,4,5,6,1,2,3)=3 我們看到有4個分支的結果和最佳結果相同，也就是說，我們目前的代價函數還不夠“一擊緻命”，但是這已經比書中的結果要好一些，起碼我們能更快地找到最佳方案，這使得我們在此後的剪枝過程更加高效。 爬山法的僞代碼如下： 1 構造由根組成的單元素棧S 2 IF Top(s)是目标節點 THEN 停止； 3 Pop(s); 4 S的子節點按照啟發式測度，由小到大的順序壓入S 5 IF 棧空 Then 失敗 Else 傳回2                 如果有時間我會把爬山法解決的烙餅問題貼在後面。 （2）       搜尋政策 Best-First 最佳優先搜尋政策結合了深度優先和廣度優先二者的優點，它采取的政策是根據評價函數，在目前産生的所有節點中選擇具有最小代價值的節點進行擴充。該政策具有全局優化的觀念，而爬山法則隻具有局部優化的能力。具體用小根堆來實作搜尋樹就可以了，這裡不再贅述。 （3）       算法 A* 如果我們把下棋比喻成解決問題，則爬山法和Best-First算法就是兩個隻能“看”未來一步棋的玩家。而A*算法則至少能夠“看”到未來的兩步棋。 我 們知道，搜尋樹的每一個節點的代價f*(n)=g(n)+h*(n)。其中，g(n)為從根節點到節點n的代價，這個值我們是可求的；h*(n)則是從n 節點到目标節點的代價，這個值我們是無法實際算出的，隻能進行估計。我們可以用下一層節點代價的最小者來替代h*(n)，這也就是“看”了兩步棋。可以證 明，如果A*算法找到了一個解，那它一定是優化解。A*算法的描述如下： 1．  使用BestFirst搜尋樹 2．  按照上面所述對下層點n進行計算獲得f*(n)的估計值f(n)，并取其最小者進行擴充。 3．  若找到目标節點，則算法停止，傳回優化解 總 結：歸根到底，烙餅問題之是以難于在多項式時間内解決的關鍵就在于我們無法為搜尋樹中的每一條邊設定一個合理的權值。在這裡，每條邊的權值都是1，因為從 上一個狀态節點到下一個狀态節點之需要一次翻轉。是以我們不能簡單地把每個節點的代價定義為翻轉次數，而應該根據其距離最終解的接近程度來給出一個數值， 而這恰恰就是該問題的難點。但是無論上面哪一種方法，都需要我們确定搜尋樹各個邊的代價是多少，然後才能進行要麼廣度優先、要麼深度優先、要麼A*算法的 估計代價。是以，在給出一個合理的代價之前，我們所有的努力都隻能是幫忙“加速”，而無法真正在多項式時間内解決問題。