轉(zhuǎn)自：http://blog.csdn.net/kabini/article/details/2276723

早在一年前，當(dāng)時(shí)我的一個(gè)很牛的胖師兄受邀參加Google中國(guó)的面試，一開(kāi)始問(wèn)他考什么問(wèn)題他就用簽了保密協(xié)議打發(fā)我們。但當(dāng)最后他得知無(wú)緣Google的時(shí)候，終于打開(kāi)話匣子，跟我們這些小字輩滔滔不絕地傳授了一些“面經(jīng)”。我記得其中就有一道題就是這個(gè)一摞烙餅問(wèn)題，還有一道概率題在我面試MSRA的時(shí)候也被問(wèn)到，可恨我當(dāng)時(shí)沒(méi)在意，后來(lái)面試吃了虧。不過(guò)如此的巧合說(shuō)明微軟和Google面試題庫(kù)相同？抑或是兩個(gè)互為競(jìng)爭(zhēng)對(duì)手的公司選擇的標(biāo)準(zhǔn)驚人的一致？只可惜Google今年沒(méi)來(lái)哈爾濱招聘，我沒(méi)法證實(shí)答案到底是A還是B。但如果是后者，我相信明年參加校園招聘的朋友還是有必要把這些經(jīng)典的問(wèn)題搞清楚。只可惜我當(dāng)時(shí)對(duì)微軟的面試不甚了解導(dǎo)致準(zhǔn)備不足，而《編程之美》又出得晚了半年，否則說(shuō)不定....。算了，還是關(guān)注問(wèn)題本身吧。

? ?? 言歸正傳，一摞烙餅問(wèn)題其實(shí)是一個(gè)很有意思的問(wèn)題，它的描述是讓一摞隨機(jī)順序的烙餅通過(guò)單手翻轉(zhuǎn)的方式進(jìn)行排序，以達(dá)到這摞烙餅由小到大順序放置在盤(pán)子上的目的，其特點(diǎn)是每次翻轉(zhuǎn)都會(huì)導(dǎo)致第一個(gè)烙餅到所要反轉(zhuǎn)的那個(gè)烙餅之間的順序變?yōu)槟嫘颉Ｎ覀兊哪康氖乔蟪龃螖?shù)最少的翻轉(zhuǎn)方案以及翻轉(zhuǎn)次數(shù)，很顯然這是一個(gè)最優(yōu)化問(wèn)題，我們本能想到的是動(dòng)態(tài)規(guī)劃、貪心以及分支限界三種方法。
??
??? 書(shū)中給出的遞歸算法或稱之為分支限界法（即遍歷+剪枝=分支限界）秉承了遞歸算法傳統(tǒng)的簡(jiǎn)單、明了，但效率偏低的特點(diǎn)。這個(gè)問(wèn)題的實(shí)質(zhì)，我們?cè)诿恳淮畏崔D(zhuǎn)之前其實(shí)是需要做出一種選擇，這種選擇必須能夠?qū)е氯肿顑?yōu)解。遞歸算法就是遞歸的構(gòu)建所有解（實(shí)際是一顆搜索樹(shù)），并在遍歷過(guò)程中不斷刷新LowerBound和UpperBound，以及當(dāng)前的最優(yōu)解（剪枝），并最終找到一個(gè)最整體優(yōu)解。在這種策略下，提高算法的效率只能寄希望于剪枝方法的改進(jìn)。但是這種方法顯然不是多項(xiàng)式時(shí)間的，有沒(méi)有多項(xiàng)式時(shí)間的算法呢？

??? 書(shū)中P22頁(yè)提到動(dòng)態(tài)規(guī)劃，但最后卻給出了解決最優(yōu)化問(wèn)題普遍適用但效率可能是最差的遞歸方法。這不禁讓人疑惑：這也不美啊！？如果我們能證明該問(wèn)題滿足動(dòng)態(tài)規(guī)劃或貪心算法的使用條件，解決問(wèn)題的時(shí)間復(fù)雜度將會(huì)降到多項(xiàng)式時(shí)間甚至N^2。但書(shū)中提到動(dòng)態(tài)規(guī)劃卻最終沒(méi)有使用，又沒(méi)有講明原因，我覺(jué)得是一種疏失（應(yīng)該不算錯(cuò)誤）。那我們就來(lái)想一下為什么沒(méi)有動(dòng)態(tài)規(guī)劃或貪心算法的原因。

? ? 我們知道動(dòng)態(tài)規(guī)劃方法是一種自底向上的獲取問(wèn)題最優(yōu)解的方法，它采用子問(wèn)題的最優(yōu)解來(lái)構(gòu)造全局最優(yōu)解。利用動(dòng)態(tài)規(guī)劃求解的問(wèn)題需要滿足兩個(gè)條件：即（1）最優(yōu)子結(jié)構(gòu) （2）子結(jié)構(gòu)具有重疊性。條件（1）使我們可以利用子問(wèn)題的最優(yōu)解來(lái)構(gòu)造全局最優(yōu)解，而條件（2）是我們?cè)谟?jì)算過(guò)程中可以利用子結(jié)構(gòu)的重疊性來(lái)減少運(yùn)算次數(shù)。此外，《算法導(dǎo)論》上還以有向圖的無(wú)權(quán)最短路徑和無(wú)權(quán)最長(zhǎng)路徑為例提出條件（3）子問(wèn)題必須獨(dú)立。
??
? 首先我們假定烙餅問(wèn)題存在優(yōu)化子結(jié)構(gòu)。假如我們有N個(gè)烙餅，把他們以其半徑由小到大進(jìn)行編號(hào)。優(yōu)化子結(jié)構(gòu)告訴我們對(duì)于i個(gè)烙餅，我們只需要先排列前(i-1)個(gè)，然后再將第i個(gè)歸位；或先排列第2到i個(gè)，最后將第一個(gè)歸位；又或是找到一個(gè)位置k[i<=k<j]像矩陣乘法加括號(hào)那樣，使得我們先排列前k個(gè)，再排列后j-k個(gè)，最后再將二者合并，以找到一個(gè)最佳翻轉(zhuǎn)策略等等...
??
??? 根據(jù)動(dòng)態(tài)規(guī)劃算法的計(jì)算過(guò)程，我們需要一個(gè)N*N矩陣M，其中M[i][j]表示將編號(hào)i至編號(hào)j的烙餅排序所需要的翻轉(zhuǎn)次數(shù)。但我們真的能從M[0][0..j-1]和M[1][j+1]，或與M[i][j]同行同列的值來(lái)計(jì)算M[i][j]嗎？如果能，我們就能獲得多項(xiàng)式時(shí)間的算法。??

??? 我們來(lái)看書(shū)中給出的例子：(頂端)3，2，1，6，5，4，9，8，7，0(底端)，我們最終的目標(biāo)是計(jì)算M[0][9]。
這里我們以計(jì)算M[0][4]為例，計(jì)算的矩陣我已經(jīng)在下面給出：??
? 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
? ------------------?
??
? 實(shí)際上如果我們要向?qū)?-4號(hào)烙餅(注意：烙餅編號(hào)也等同于其半徑)排為正序(中間有其他烙餅也沒(méi)關(guān)系)，按照程序給出的結(jié)果， 我們需要進(jìn)行3次翻轉(zhuǎn)，分別為[2,5,9](即分別翻轉(zhuǎn)隊(duì)列中第二(從零開(kāi)始)、五、九個(gè)烙餅，這里的數(shù)字不是烙餅的編號(hào))：??
? [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]
??
????? 我們知道，該矩陣中每一個(gè)數(shù)的背后都隱含著一個(gè)烙餅的排列，例如M[0][4]就應(yīng)該對(duì)應(yīng)0,7,8,9,1,2,3,6,5,4
? 所以，每一個(gè)M[i][j]的選取都蘊(yùn)含著其子排列的順序的變化。
????? 在計(jì)算M[i][j]的時(shí)候，我們需要計(jì)算i-j號(hào)餅的全部劃分(不包括全部為1的劃分)所能構(gòu)成的翻轉(zhuǎn)結(jié)構(gòu)，并取其翻轉(zhuǎn) 次數(shù)最少的哪一個(gè)最為M[i][j]的最終值。例如，我們?cè)谟?jì)算M[0][4]的時(shí)候，需要查看：
??
?? /**先將0和1-4號(hào)分別排序，最后將二者合并為有序所需要的翻轉(zhuǎn)次數(shù)*/
?? M[0][0],M[1][4]?
???
?? /** 同上 */
?? M[0][1],M[2][4]
???
?? /** 同上 */
?? M[0][2],M[3][4]
???
?? /** 同上 */
?? M[0][3],M[4][4]
???
?? /* 先將0、1、2、3-4號(hào)分別排序，最后將4者合并為有序所需要的翻轉(zhuǎn)次數(shù).
??? * 注意這里又包含將4個(gè)分組再次進(jìn)行劃分的問(wèn)題！?
??? */
?? M[0][0],M[1][1],M[2][2],M[3][4]
?? .....//中間略
?? M[0][3],M[4][4]
??
?? 如果再加上運(yùn)算過(guò)程中我們可以淘汰超過(guò)最大反轉(zhuǎn)次數(shù)的方案（剪枝？），我們完成全部的運(yùn)算，所經(jīng)歷的運(yùn)算過(guò)程的時(shí)間復(fù)雜度已經(jīng)不是多項(xiàng)式時(shí)間的，而是和先前所說(shuō)的遞歸方法已沒(méi)什么兩樣。

???? 造成這種現(xiàn)象的原因是：某個(gè)子問(wèn)題的最優(yōu)解不一定是整體的最優(yōu)解，所以我們?cè)谔幚碚麄€(gè)問(wèn)題的時(shí)候，需要遍歷所有可能的子問(wèn)題，并計(jì)算它到整體問(wèn)題所消耗的代價(jià)，才能最終作出有利于整體問(wèn)題的選擇。

?? 所以我們一開(kāi)始的假設(shè)，即烙餅問(wèn)題有優(yōu)化子結(jié)構(gòu)的假設(shè)是錯(cuò)誤的。因此我們不能用動(dòng)態(tài)規(guī)劃，同理也不能用貪心算法。

前面已經(jīng)寫(xiě)了一些關(guān)于烙餅問(wèn)題的簡(jiǎn)單分析，但因?yàn)槟翘焯塾行┮猹q未盡，今天再充實(shí)一些內(nèi)容那這個(gè)問(wèn)題研究透。我想，通過(guò)這篇文章，我們就可以把這一類問(wèn)題搞懂。再遇到優(yōu)化問(wèn)題，如果我們想不到別的辦法，就可以采用搜索樹(shù)算法來(lái)解決，至少我們不至于拿不出解決方案。前面我們已經(jīng)知道，關(guān)于一摞烙餅的排序問(wèn)題我們可以采用遞歸的方式來(lái)完成。其間我們要做的是盡量調(diào)整UpperBound和LowerBound，已減少運(yùn)算次數(shù)。對(duì)于這種方法，在算法課中我們應(yīng)該稱之為：Tree Searching Strategy。即整個(gè)解空間為一棵搜索樹(shù)，我們按照一定的策略遍歷解空間，并尋找最優(yōu)解。一旦找到比當(dāng)前最優(yōu)解更好的解，就用它替換當(dāng)前最優(yōu)解，并用它來(lái)進(jìn)行“剪枝”操作來(lái)加速求解過(guò)程。

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

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

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

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

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

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

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

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

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

這樣我們就可以在本例中迅速找到最優(yōu)分枝。因?yàn)樵跇?shù)的第一層

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

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

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

那么，對(duì)于搜索樹(shù)的第一層，按照上面的算法我計(jì)算的結(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個(gè)分支的結(jié)果和最佳結(jié)果相同，也就是說(shuō)，我們目前的代價(jià)函數(shù)還不夠“一擊致命”，但是這已經(jīng)比書(shū)中的結(jié)果要好一些，起碼我們能更快地找到最佳方案，這使得我們?cè)诖撕蟮募糁^(guò)程更加高效。

爬山法的偽代碼如下：

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

2 IF Top(s)是目標(biāo)節(jié)點(diǎn)?THEN?停止；

3 Pop(s);

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

5 IF?棧空?Then?失敗

Else?返回2

?

??????????????如果有時(shí)間我會(huì)把爬山法解決的烙餅問(wèn)題貼在后面。

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

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

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

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

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

1．??使用BestFirst搜索樹(shù)

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

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

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

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的烙饼问题与搜索树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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