問題：

????星期五的晚上，一幫同事在希格瑪大廈附近的“硬盤酒吧”多喝了幾杯。程序員多喝了幾杯之后談什么呢？自然是算法問題。有個同事說：“我以前在餐館打工，顧客經(jīng)常點非常多的烙餅。店里的餅大小不一，我習慣在到達顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一只手托著盤子，只好用另一只手，一次抓住最上面的幾塊餅，把它們上下顛倒個個兒，反復(fù)幾次之后，這摞烙餅就排好序了。我后來想，這實際上是個有趣的排序問題：假設(shè)有n塊大小不一的烙餅，那最少要翻幾次，才能達到最后大小有序的結(jié)果呢？”

你能否寫出一個程序，對于n塊大小不一的烙餅，輸出最優(yōu)化的翻餅過程呢？

（1）基本步驟

1、最上面的和下面“未選出的最大”的做一次翻轉(zhuǎn)——————》最大的跑到上面了

2、最大的和下面未初始化的第一個翻轉(zhuǎn)——————》最大的跑到了最下面

3、重復(fù)以上過程，直到全部有序

（2）如何改進以上的次數(shù)？

關(guān)于一摞烙餅的排序問題我們可以采用遞歸的方式來完成。其間我們要做的是盡量調(diào)整UpperBound和LowerBound，已減少運算次數(shù)。對于這種方法，在算法課中我們應(yīng)該稱之為：Tree Searching Strategy。即整個解空間為一棵搜索樹，我們按照一定的策略遍歷解空間，并尋找最優(yōu)解。一旦找到比當前最優(yōu)解更好的解，就用它替換當前最優(yōu)解，并用它來進行“剪枝”操作來加速求解過程。

書中給出的解法就是采用深度優(yōu)先的方式來遍歷這棵搜索樹，例如要排序[4,2,1,3]，最大反轉(zhuǎn)次數(shù)不應(yīng)該超過(4-1)*2=6次，所以搜索樹的深度也不應(yīng)大于6，搜索樹如下圖所示：

這里只列到第三層，其中被畫斜線的方塊由于和上層的某一節(jié)點的狀態(tài)重復(fù)而無需再擴展下去（即便擴展也不可能比有相同狀態(tài)的上層節(jié)點的代價少）。我們可以看到在右子樹中的一個分支，只需要用3次反轉(zhuǎn)即可完成，我們的目標是如何更為快速有效的找到這一分支。直觀上我們可以看到：基本的搜索方法要先從左子樹開始，所以要找到本例最佳的方案的代價是很高的（利用書中的算法需要查找292次）。

既然要遍歷搜索樹，就有廣度優(yōu)先和深度優(yōu)先之分，可以分別用棧和隊列來實現(xiàn)（當然也可以用遞歸的方法）。那么如何能更有效地解決問題呢？我們主要考慮一下幾種方法：

（1）???????爬山法

該方法是在深度優(yōu)先的搜索過程中使用貪心方法確定搜索方向，它實際上是一種深度優(yōu)先搜索策略。爬山法采用啟發(fā)式側(cè)讀來排序節(jié)點的擴展順序，其關(guān)鍵點就在于測度函數(shù)f(n)的定義。我們來看一下如何為上例定制代價函數(shù)f(n)，以快速找到右子樹中最好的那個分支（很像貪心算法，呵呵）。

我們看到在[1,2,4,3]中，[1,2,3]已經(jīng)相對有序，而[4]位與他們之間，要想另整體有序，需要4次反轉(zhuǎn)；而[3,1,2,4]中，由于[4]已經(jīng)就位，剩下的數(shù)變成了長度為3的子隊列，而子隊列中[1,2]有序，令其全體有序只需要2次反轉(zhuǎn)。

所以我們的代價函數(shù)應(yīng)該如下定義：

1?從當前狀態(tài)的最后一個餅開始搜索，如果該餅在其應(yīng)該在的位置（中間斷開不算），則跳過；

2?自后向前的搜索過程中，如果碰到兩個數(shù)不相鄰的情況，就+1

這樣我們就可以在本例中迅速找到最優(yōu)分枝。因為在樹的第一層

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，所以我們又找到了最佳的路徑。

上面方法看似不錯，但是數(shù)字比較多的時候呢？我們來看書中給出的10個數(shù)的例子：

[3,2,1,6,5,4,9,8,7,0]，程序給出的最佳翻轉(zhuǎn)序列為{?4,8,6,8,4,9}（從0開始算起）

那么，對于搜索樹的第一層，按照上面的算法我計算的結(jié)果如下：

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個分支的結(jié)果和最佳結(jié)果相同，也就是說，我們目前的代價函數(shù)還不夠“一擊致命”，但是這已經(jīng)比書中的結(jié)果要好一些，起碼我們能更快地找到最佳方案，這使得我們在此后的剪枝過程更加高效。

爬山法的偽代碼如下：

1?構(gòu)造由根組成的單元素棧S

2 IF Top(s)是目標節(jié)點?THEN?停止；

3 Pop(s);

4 S的子節(jié)點按照啟發(fā)式測度，由小到大的順序壓入S

5 IF?棧空?Then?失敗

Else?返回2

?

??????????????如果有時間我會把爬山法解決的烙餅問題貼在后面。

（2）???????Best-First搜索策略

最佳優(yōu)先搜索策略結(jié)合了深度優(yōu)先和廣度優(yōu)先二者的優(yōu)點，它采取的策略是根據(jù)評價函數(shù)，在目前產(chǎn)生的所有節(jié)點中選擇具有最小代價值的節(jié)點進行擴展。該策略具有全局優(yōu)化的觀念，而爬山法則只具有局部優(yōu)化的能力。具體用小根堆來實現(xiàn)搜索樹就可以了，這里不再贅述。

（3）???????A*算法

如果我們把下棋比喻成解決問題，則爬山法和Best-First算法就是兩個只能“看”未來一步棋的玩家。而A*算法則至少能夠“看”到未來的兩步棋。

我們知道，搜索樹的每一個節(jié)點的代價f*(n)=g(n)+h*(n)。其中，g(n)為從根節(jié)點到節(jié)點n的代價，這個值我們是可求的；h*(n)則是從n節(jié)點到目標節(jié)點的代價，這個值我們是無法實際算出的，只能進行估計。我們可以用下一層節(jié)點代價的最小者來替代h*(n)，這也就是“看”了兩步棋。可以證明，如果A*算法找到了一個解，那它一定是優(yōu)化解。A*算法的描述如下：

1．??使用BestFirst搜索樹

2．??按照上面所述對下層點n進行計算獲得f*(n)的估計值f(n)，并取其最小者進行擴展。

3．??若找到目標節(jié)點，則算法停止，返回優(yōu)化解

總結(jié)：歸根到底，烙餅問題之所以難于在多項式時間內(nèi)解決的關(guān)鍵就在于我們無法為搜索樹中的每一條邊設(shè)定一個合理的權(quán)值。在這里，每條邊的權(quán)值都是1，因為從上一個狀態(tài)節(jié)點到下一個狀態(tài)節(jié)點之需要一次翻轉(zhuǎn)。所以我們不能簡單地把每個節(jié)點的代價定義為翻轉(zhuǎn)次數(shù)，而應(yīng)該根據(jù)其距離最終解的接近程度來給出一個數(shù)值，而這恰恰就是該問題的難點。但是無論上面哪一種方法，都需要我們確定搜索樹各個邊的代價是多少，然后才能進行要么廣度優(yōu)先、要么深度優(yōu)先、要么A*算法的估計代價。所以，在給出一個合理的代價之前，我們所有的努力都只能是幫忙“加速”，而無法真正在多項式時間內(nèi)解決問題。

總結(jié)

以上是生活随笔為你收集整理的（1.5.1.3）编程之美：一摞烙饼的排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。