演算法淺談——遞歸演算法與海盜分金問題
- 2020 年 3 月 5 日
- 筆記
點擊上方藍字，和我一起學技術。
最近看到一道很有意思的問題，分享給大家。
還是老規矩，在我們聊演算法問題之前，先來看一個故事。
傳說中，有5個海盜組成了一支無敵的海盜艦隊，他們在最後一次的尋寶當中找尋到了100枚價值連城的金幣。於是，很自然的，這群海盜面臨分贓的問題。為了防止海盜內訌，殘忍的海盜們制定了一個奇怪的規則。
他們決定按照功勞大小對五個人進行編號，由編號小的海盜先提出分配方案。如果方案能夠得到大多數人的同意，那麼就按照他提出的方案進行分配。如果不能通過，說明他已經失去了威望，海盜們會殘忍地將他投入海中喂鯊魚。
在一個朦朧的早上你一覺醒來，突然發現自己成了一號海盜，那麼你應該如何分配才能獲得最多的金幣，又不會被喂鯊魚呢？
在我們思考之前，我們先完善一下題意，增加幾個條件。
首先，每一個海盜都非常殘忍。這意味著，在不影響收益的情況下，他們會更傾向於殺人。其次，每一個海盜都極其聰明，都能想到最佳答案。
這兩個條件一出來，問題就比較明顯了，這是博弈論題目才有的架勢。
既然這是一道博弈論的問題，那麼我們通過常規的思路是無法找到答案的，我們需要另闢蹊徑才行。
那麼，怎麼另闢蹊徑呢？
一個比較常規的做法是先不考慮原問題，先假設一個和原問題差不多，但是規模小很多的子問題。通過對子問題的求解來摸索原問題的解法。
舉個例子，在這題當中，我們需要計算5個海盜分金幣的情況。一時之間我們有些無從下手，那麼我們簡化問題，問題的規則還是不變，但是我們把海盜的數量減少，減少到只有一個海盜。那麼根據規則，很顯然，最後的結果是這個海盜獨吞所有的金幣。
這個時候的分配方案是：[0, 0, 0, 0, 100]
我們從這個點開始往回倒推，假設這個時候多了一個海盜，一共是4號和5號兩個海盜的時候，會怎麼樣？
顯然，因為要求要一半以上同意提案，提案才可以通過。所以在這個時候，無論4號海盜如何提議，5號都不會同意，要將他投下海喂鯊魚。所以如果只剩下4和5的時候，4號海盜必死無疑。
這個時候的分配方案是：[0, 0, 0, -1, 100]，-1表示必死無疑。
那如果再加一個海盜呢？
再加一個海盜的話，是3，4，5三個海盜的情況。因為只剩4和5的時候4號必死，所以他為了活命一定會同意3號的提案（海盜對其他人殘忍，對自己不殘忍）。這個時候，3號不論如何提議，都一定可以通過。因為算上他自己的一票，和4號的一票，已經過半了，所以他的提案一定可以通過。
這個時候的分配方案是：[0, 0, 100, 0, 0]
我們再加入一個海盜，考慮一共剩下4個海盜的情況。如果2號死去，那麼3號可以獨吞所有金幣，所以顯然3號一定不會同意2號的方案。4個人的時候，至少需要3個人同意才可以通過方案，那麼2號必須要爭取4號和5號。如果2號死去，4號和5號一無所有，所以2號只需要分配給4號和5號一枚金幣，就可以拉攏他們。
這個時候的分配方案是：[0, 98, 0, 1, 1]
最後，我們再加入1號海盜。同理，1號海盜的提案需要至少3個人通過。算上他自己，他還需要爭取2票。由於1號死去2號可以獲得98枚金幣，所以1號一定無法爭取2號，還是只能從3，4，5三個人下手。可以給3號1枚，4號兩枚（比2號的方案多一枚），也可以給3號1沒，5號兩枚。
這個時候的分配方案是：[97, 0, 1, 2, 0] 或者是 [97, 0, 1, 0, 2]。
到這裡，這個問題就結束了。但是我們的思考並沒有結束，不知道大家從剛才的解法當中有沒有看出規律。我們面臨5個海盜這種錯綜複雜情況的時候根本無從下手，但是一旦當我們試著將問題的規模縮小，從簡單的情況開始思考，那麼問題一下子就豁然開朗了。
老子說：天下大事，必作於細，天下難事，必作於易。從這個問題來看，和這個道理相得益彰。
這種從最簡單推導最複雜的演算法就稱為遞歸。
假設，獲取n個海盜分配方案的函數是f。當我們計算f(2)時，我們需要根據f(1)的結果。我們試著寫成偽程式碼：
def f(n): if n == 1: return [0, 0, 0, 0, 100] else: allocation = f(n-1) # 新的分配 new_allocation = allocate(allocation) return new_allocation
我們先忽略allocate這個方法內部是怎麼實現的，單純看這段程式碼，整個框架已經有了。
遞歸的精髓也就在這裡，程式自己調用自己只是表象，內里的精髓其實是問題的分割。整個遞歸從上到下的過程，其實是一個大問題化解成小問題的過程。如果還不明白，我們再來看一個經典的例子來鞏固一下，這個問題就是大名鼎鼎的漢諾塔問題：
在印度神話當中有一個大神叫做梵天，他在創造世界的時候創造了三根金剛柱。為了排解無聊，他在其中一根柱子上擺放了64個圓盤。這64個圓盤從上往下依次增大，他給僧侶出了一個問題。一次只能移動一個圓盤，並且圓盤只能放在比它大的圓盤上，該怎麼做才能將圓盤從一根柱子移動到另一根呢？
為了簡化問題，我們先觀察擺放5個圓盤的情況。從圖中可以看出來，一開始的時候圓盤都在A柱，如果我們想要將圓盤移動到B柱應該怎麼辦呢？
我們同樣先來觀察最簡單的情況，A柱上只有一個圓盤，那很簡單，我們直接將它移動到B柱即可。如果有兩個圓盤呢？我們需要先將第一個移動到C柱，然後將第二個移動到B柱，最後再將C柱上的圓盤移動到B。那如果是三個圓盤呢，稍微複雜一些，但仔細列舉一下，也能算得出來。
但是我們怎麼通過問題規模的縮小來化簡問題呢？
這需要我們對於題目進行深入思考，找到其中的關鍵點。這題的關鍵點就是圓盤的限制，大的圓盤不能落在小的圓盤上面。所以如果我們想要將n個圓盤從A柱移動到B柱，必須要將前n-1個圓盤先移動到C柱，這樣才可以將最大的那塊放到B，如此之後再將n-1塊移動回B。
也就是說，我們將n-1塊圓盤當做是一個整體，這樣n塊圓盤的方案就和兩塊圓盤時一樣了。這就通過遞歸完成了簡化。
最後，也是最關鍵的，怎麼移動n-1塊圓盤呢？其實很簡單，我們套用同樣的方法，再將這n-1塊圓盤中的n-2塊看成是整體，遞歸操作。理解了之後，不妨試著寫出程式碼，其實只有幾行：
def hanoi_tower(num, tower_start, tower_dest, tower_other): if num == 1: print('move plate {} from {} to {}'.format(num, tower_start, tower_dest)) return hanoi_tower(num-1, tower_start, tower_other, tower_dest) print('move plate {} from {} to {}'.format(num, tower_start, tower_dest)) hanoi_tower(num-1, tower_other, tower_dest, tower_start)
我們調用一下這個方法，進行一下測試：
結果和我們的預期一致，說明我們的演算法是正確的。最後，我們再回到海盜問題，又該怎麼用程式碼實現呢？感興趣的同學不妨親自動手試試，如果實在寫不出程式碼，在公眾號回復關鍵詞」海盜分金「查看我寫的程式碼。
今天的文章就到這裡，如果覺得有所收穫的話，就點個「在看」或者轉發吧。
