為什么算法這么難？？？
點擊下方卡片，關注“新機器視覺”公眾號
重磅干貨，第一時間送達
作者：劉末鵬
轉自：算法與數(shù)據(jù)結構
鏈接：http://mindhacks.cn/2011/07/10/the-importance-of-knowing-why-part3/
廣大碼農同學們大多都有個共識，認為算法是個硬骨頭，很難啃，悲劇的是啃完了還未必有用——除了面試的時候。實際工程中一般都是用現(xiàn)成的模塊，一般只需了解算法的目的和時空復雜度即可。
不過話說回來，面試的時候面算法，包括面項目中幾乎不大可能用到的算法，其實并不能說是毫無道理的。算法往往是對學習和理解能力的一塊試金石，難的都能掌握，往往容易的事情不在話下。志于高者得于中。反之則不成立。另一方面，雖說教科書算法大多數(shù)都是那些即便用到也是直接拿模塊用的，但不幸的是，我們這群搬磚頭的有時候還非得做些發(fā)明家的事情：要么是得把算法當白盒加以改進以滿足手頭的特定需求；要么干脆就是要發(fā)明輪子。所以，雖說面試的算法本身未必用得到，但熟悉各種算法的人通常更可能熟悉算法的思想，從而更可能具備這里說的兩種能力。
那么，為什么說算法很難呢？這個問題只有兩種可能的原因：
算法本身就很難。也就是說，算法這個東西對于人類的大腦來說本身就是個困難的事兒。 講得太爛。
下面會說明，算法之所以被絕大多數(shù)人認為很難，以上兩個原因兼具。
我們說算法難的時候，有兩種情況：一種是學算法難。第二種是設計算法難。對于前者，大多數(shù)人（至少我當年如此）學習算法幾乎是在背算法，就跟背菜譜似的（“Cookbook”是深受廣大碼農喜愛的一類書），然而算法和菜譜的區(qū)別在于，算法包含的細節(jié)復雜度是菜譜的無數(shù)倍，算法的問題描述千變萬化，邏輯過程百轉千回，往往看得人愁腸百結，而相較之下任何菜譜涉及到的基本元素也就那么些（所以程序員肯定都具有成為好廚師的潛力:D）注意，即便你看了算法的證明，某種程度上還是“背”（為什么這么說，后面會詳述）。我自己遇到新算法基本是會看證明的，但是發(fā)現(xiàn)沒多久還是會忘掉，這是死記硬背的標準癥狀。如果你也啃過算法書，我相信很大可能性你會有同感：為什么當時明明懂了，但沒多久就忘掉了呢？為什么當時明明非常理解其證明，但沒過多久想要自己去證明時卻發(fā)現(xiàn)怎么都沒法補上證明中缺失的一環(huán)呢？
初中學習幾何證明的時候，你會不會傻到去背一個定理的證明？不會。你只會背結論。為什么？一方面，因為證明過程包含大量的細節(jié)。另一方面，證明的過程環(huán)環(huán)相扣，往往只需要注意其中關鍵的一兩步，便能夠自行推導出來。算法邏輯描述就好比定理，算法的證明的過程就好比定理的證明過程。但不幸的是，與數(shù)學里面大量簡潔的基本結論不同，算法這個“結論”可不是那么好背的，許多時候，算法本身的邏輯就幾乎包含了與其證明過程等同的信息量，甚至算法邏輯本身就是證明過程（隨便翻開一本經典的算法書，看幾個經典的教科書算法，你會發(fā)現(xiàn)算法邏輯和算法證明的聯(lián)系有多緊密）。于是我們又回到剛才那個問題：你會去背數(shù)學證明么？既然沒人會傻到去背整個證明，又為什么要生硬地去背算法呢？
那么，不背就不背，去理解算法的證明如何？理解了算法的證明過程，便更有可能記住算法的邏輯細節(jié)，理解記憶嘛。然而，仍然不幸的是，絕大多數(shù)算法書在這方面做的實在糟糕，證明倒是給全了，邏輯也倒是挺嚴謹?shù)模墒撬坪鯖]有作者能真正還原算法發(fā)明者本身如何得到算法以及算法證明的思維過程，按理說，證明的過程應該反映了這個思維過程，但是在下文關于霍夫曼編碼的例子中你會看到，其實飽受贊譽的CLRS和《Algorithms》不僅沒能還原這個過程，反而掩蓋了這個過程。
必須說明的是，沒有哪位作者是故意這樣做的，但任何人在講解一個自己已經理解了的東西的時候，往往會無意識地對自己的講解進行“線性化”，例如證明題，如果你回憶一下高中做平面幾何證明題的經歷，就會意識到，其實證明的過程是一個充滿了試錯，聯(lián)想，反推，特例，修改問題條件，窮舉等等一干“非線性”思維的，混亂不堪的過程，而并不像寫在課本上那樣——引理1，引理2，定理1，定理2，一口氣直到最終結論。這樣的證明過程也許容易理解，但絕對不容易記憶。過幾天你就會忘記其中一個或幾個引理，其中的一步或幾步關鍵的手法，然后當你想要回過頭來自己試著去證明的時候，就會發(fā)現(xiàn)卡在某個關鍵的地方，為什么會這樣？因為證明當中并沒有告訴你為什么作者當時會想到證明算法需要那么一個引理或手法，所以，雖說看完證明之后，對算法這個結論而言你是知其所以然了，但對于算法的證明過程你卻還沒知其所以然。在我們大腦的記憶系統(tǒng)當中，新的知識必須要和既有的知識建立聯(lián)系，才容易被回憶起來（《如何有效地學習與記憶》），聯(lián)系越多，越容易回憶，而一個天外飛仙似地引理，和我們既有的知識沒有半毛錢聯(lián)系，沒娘的孩子沒人疼，自然容易被遺忘。（為什么還原思維過程如此困難呢？我曾經在知其所以然（一）里詳述）
正因為絕大多數(shù)算法書上悲劇的算法證明過程，很多人發(fā)現(xiàn)證明本身也不好記，于是寧可選擇直接記結論。當年我在數(shù)學系，考試會考證明過程，但似乎計算機系的考試考算法證明過程就是荒謬的？作為“工程”性質的程序設計，似乎更注重使用和結果。但是如果是你需要在項目中自己設計一個算法呢？這種時候最起碼需要做的就是證明算法的正確性吧。我們面試的時候往往都會遇到一些算法設計問題，我總是會讓應聘者去證明算法的正確性，因為即便是一個“看上去”正確的算法，真正需要證明起來往往發(fā)現(xiàn)并不是那么容易。
所以說，絕大多數(shù)算法書在作為培養(yǎng)算法設計者的角度來說是失敗的，比數(shù)學教育更失敗。大多數(shù)人學完了初中平面幾何都會做證明題（數(shù)學書不會要求你記住幾何所有的定理），但很多人看完了一本算法書還是一團漿糊，不會證明一些起碼的算法，我們背了一坨又一坨結論，非但這些結論許多根本用不上，就連用上的那些也不會證明。為什么會出現(xiàn)這樣的差異？因為數(shù)學教育的理想目的是為了讓你成為能夠發(fā)現(xiàn)新定理的科學家，而碼農系的算法教育的目的卻更現(xiàn)實，是為了讓你成為能夠使用算法做事情的工程師。然而，事情真的如此簡單么？如果真是這樣的話干脆連算法結論都不要背了，只要知道算法做的是什么事情，時空復雜度各是多少即可。
如果說以上提到的算法難度（講解和記憶的難度）屬于Accidental Complexity的話，算法的另一個難處便是Essential Complexity了：算法設計。還是拿數(shù)學證明來類比（如果你看過《Introduction to Algorithms：A Creative Approach》就知道算法和數(shù)學證明是多么類似。），與單單只需證明相比，設計算法的難處在于，定理和證明都需要你去探索，尤其是前者——你需要去自行發(fā)現(xiàn)關鍵的那（幾）個定理，跟證明已知結論相比（已經確定知道結論是正確的了，你只需要用邏輯來連接結論和條件），這件事情的復雜度往往又難上一個數(shù)量級。
一個有趣的事實是，算法的探索過程往往蘊含算法的證明過程，理想的算法書應該通過還原算法的探索過程，從而讓讀者不僅能夠自行推導出證明過程，同時還能夠具備探索新算法的能力。之所以這么說，皆因為我是個懶人，懶人總夢想學點東西能夠實現(xiàn)以下兩個目的：
一勞永逸：程序員都知道“一次編寫到處運行”的好處，多省事啊。學了就忘，忘了又得學，翻來覆去浪費生命。為什么不能看了一遍就再也不會忘掉呢？到底是教的不好，還是學得不好？ 事半功倍：事實上，程序員不僅講究一次編寫到處運行，更講究“一次編寫到處使用”（也就是俗稱的“復用”）。如果學一個算法所得到的經驗可以到處使用，學一當十，推而廣之，時間的利用效率便會大大提高。究竟怎樣學習，才能夠使得經驗的外推（extrapolate）效率達到最大呢？
想要做到這兩點就必須盡量從知識樹的“根節(jié)點”入手，雖然這是一個美夢，例如數(shù)學界尋找“根節(jié)點”的美夢由來已久（《跟波利亞學解題》的“一點歷史”小節(jié)），但哥德爾一個證明就讓美夢成了泡影（《永恒的金色對角線》））；但是，這并不阻止我們去尋找更高層的節(jié)點——更具普適性的解題原則和方法。所以，理想的算法書或者算法講解應該是從最具一般性的思維法則開始，順理成章地推導出算法，這個過程應該盡量還原一個”普通人“思考的過程，而不是讓人看了之后覺得”這怎么可能想到呢？
以本文上篇提到的霍夫曼編碼為例，第一遍看霍夫曼編碼的時候是在本科，只看了算法描述，覺得挺直觀的，過了兩年，忘了，因為不知道為什么要把兩個節(jié)點的頻率加在一起看做單個節(jié)點——一件事情不知道“為什么”就會記不牢，知道了“為什么”的話便給這件事情提供了必然性。不知道“為什么”這件事情便可此可彼，我們的大腦對于可此可彼的事情經常會弄混，它更容易記住有理有據(jù)的事情（從信息論的角度來說，一件必然的事情概率為1，信息量為0，而一件可此可彼的事情信息量則是大于0的）。第二遍看是在工作之后，終于知道要看證明了，拿出著名的《Algorithms》來看，邊看邊點頭，覺得講得真好，一看就理解了為什么要那樣來構造最優(yōu)編碼樹?？墒菦]多久，又給忘了！這次忘了倒不是忘了要把兩個節(jié)點的頻率加起來算一個，而是忘了為什么要這么做，因為當時沒有弄清霍夫曼為什么能夠想到為什么應該那樣來構造最優(yōu)編碼樹。結果只知其一不知其二。
必須說明的是，如果只關心算法的結論（即算法邏輯），那么理解算法的證明就夠了，光背算法邏輯難記住，理解了證明會容易記憶得多。但如果也想不忘算法的證明，那么不僅要理解證明，還要理解證明背后的思維，也就是為什么背后的為什么。后者一般很難在書和資料上找到，唯有自己多加揣摩。為什么要費這個神？只要不會忘記結論不就結了嗎？取決于你想做什么，如果你想真正弄清算法設計背后的思想，不去揣摩算法原作者是怎么想出來的是不行的。
回到霍夫曼編碼問題，我們首先看一看《Algorithms》上是怎么講的：
首先它給出了一棵編碼樹的cost function：
cost of tree = Σ freq(i) * depth(i)
這個cost function很直白，就是把編碼的定義復述了一遍。但是接下來就說了：
There is another way to write this cost function that is very helpful.?Although we are only given frequencies for the leaves, we can define the frequency of any internal node to be the sum of the frequencies of its descendant leaves; this is, after all, the number of times the internal node is visited during encoding or decoding…
接著就按照這個思路把cost function轉換了一下：
The cost of a tree is the sum of the frequencies of all leaves and internal nodes, except the root.
然后就開始得出算法邏輯了：
The?first formulation?of the cost function tells us that the?two symbols with the smallest frequencies must be at the bottom of the optimal tree, as children of the lowest internal node (this internal node has two children since the tree is full). Otherwise, swapping these two symbols with whatever is lowest in the tree would improve the encoding.
This suggests that we start constructing the tree greedily: find the two symbols with the smallest frequencies, say i and j, and make them children of a new node, which then has frequency fi + fj. To keep the notation simple, let’s just assume these are f1 and f2. By the?second formulation?of the cost function, any tree in which f1 and f2 are sibling-leaves has cost f1 + f2 plus the cost for a tree with n – 1 leaves of frequencies (f1 + f2), f3, f4, .., fn.?The latter problem is just a smaller version of the one we started with.
讀到這里我想大多數(shù)人有兩種反應：
覺得理所當然。 覺得恍然大悟。
因為我當時也是這么覺得的?？墒呛髞懋斘野l(fā)現(xiàn)自己無法從頭證明一遍的時候，我知道肯定是理解的不夠深刻。如果理解的夠深刻，那么基本上是不會忘掉的。
如果看完霍夫曼編碼這樣一個簡短證明你覺得順理成章，一切都挺顯然，那就壞了，即便是看上去最基本的性質也往往實際上沒那么顯然。“逢山開路，遇水架橋”在我們今天看來是無比顯然的事實，但是試想在沒有橋的遠古時代，一個原始人走到一條湍急的河流前，他會怎么想，他又能有什么法子呢？這是個他從來沒有遇見過的問題。如果后來有一天，他路過另外一條小溪，看到小溪上有一截被閃電劈斷的枯樹，于是他踏著樹干走過了小溪，并意識到“樹橫過河面”可以達到“過河”這個目的，這就將條件和目的建立了直接的聯(lián)系（事實上，是自然界展示了這個聯(lián)系，我們的原始人只是記住了這個聯(lián)系）。后來他又路過那條河流，他尋思如何達到“過河”這個目的的時候，忽然意識到在他的記憶中已經遇到過需要達成同樣目的的時候了，那個時候的條件是“樹橫過河面”，于是問題便歸結為如何滿足這個“樹橫過河面”的條件，而后一個問題就簡單多了。（事實上波利亞在他的著作《How to Solve it》中舉的正是這么個例子）
為什么那么多的算法書，就看不到有一本講得好的？因為我們求解問題過程中的思維步驟太容易被自己當作“顯然”的了，但除了我們天生就會的認知模式（聯(lián)系，類比），沒有什么是應該覺得顯然的，試錯是我們天生就會的思維法則么？是的，但是可供嘗試的方案究竟又是怎么來的呢？就拿上面的例子來說，一個從沒有見過枯樹干架在小溪上的原始人，怎么知道用樹架橋是一種可選的方案呢？俗話說巧婦難為無米之炊啊。我們大腦的神經系統(tǒng)會的是將目的和條件聯(lián)系起來，第一次原始人遇到小溪過不去，大腦中留下了一個未實現(xiàn)的目的，后來見到小溪上的樹干，忽然意識到樹干是實現(xiàn)這個目的的條件，兩者便聯(lián)系起來了，因此問題就規(guī)約為如何架樹干了。
回到《Algorithms》中的證明上，這個看似簡潔明了的證明其實有幾處非常不顯然的地方，甚至不嚴謹?shù)牡胤剑@些地方也正是你過段時間之后試圖自己證明的話會發(fā)現(xiàn)卡住的地方：
作者輕飄飄地就給出了cost function的另外一種關鍵的描述，而對于如何發(fā)現(xiàn)這種描述卻只是一語帶過："There is another way to write this cost function that is very helpful..?we can define the frequency of any internal node to be the sum of the frequencies of its descendant leaves“這其實就是我常常痛恨的“我們考慮…”，這里作者其實就是在說”讓我們考慮下面這樣一種奇妙的轉換“，可是怎么來的卻不說。但必須承認，《Algorithms》的作者還是算厚道的，因為后面他又稍微解釋了一下：“this is, after all, the number of times the internal node is visited during encoding or decoding…”這個解釋就有點讓人恍然大悟了，但是千萬別忘了，這種恍然大悟是一種錯覺，你還是沒明白為什么他會想到這一點。這就像是作者對你說“仔細觀察問題條件，我們容易發(fā)現(xiàn)這樣一種奇妙的性質..”，怎么個“仔細”法？憑什么我自己“觀察”半天就是發(fā)現(xiàn)不了呢？霍夫曼本人難道也是死死盯著問題“觀察”了一學期然后就“發(fā)現(xiàn)”了么？我們有理由相信霍夫曼肯定嘗試了各種各樣的方法，作出了各種各樣的努力，否則當年Shannon都沒搞定的這個問題花了他一學期，難道他在這個學期里面大腦就一片空白（或者所有的嘗試全都是完全不相干的徒勞），然后到學期末尾忽然“靈光一現(xiàn)”嗎？ 如果“仔細觀察”:)，我們會發(fā)現(xiàn)兩個cost function表達中frequency的概念有微妙的差異，在第一個cost function中，只有葉子節(jié)點有frequency，而這個frequency必須和葉子節(jié)點的深度相乘。而在第二個cost function中，內部節(jié)點也具有了frequency，可是所有節(jié)點的“frequency”忽然全都不跟深度相乘了。frequency的不同含義令人困惑。 作者提到：第一個cost function告訴我們頻率最低的兩個節(jié)點必然處于最優(yōu)編碼樹的底端，作為最低內部節(jié)點的兩個子節(jié)點。這是一個不嚴謹?shù)恼f法，從前文給出的條件和性質，只能推導出編碼樹的最底層必然能找到頻率最低的兩個節(jié)點，但它們未必一定要是兄弟節(jié)點，如果樹的最底層不止能容納兩個節(jié)點的話它們就可以有不同的父節(jié)點。“我們不妨考慮”這樣一個例子：對A,B,C,D四個字母進行編碼，假設它們的頻率分別是1， 1， 2， 2。這個時候我們可以構造如下圖所示的兩棵樹，兩棵樹的cost都是12，都是最優(yōu)的。但其中一棵樹中，兩個頻率最低的節(jié)點并非兄弟。
為什么要提到上面這幾點不顯然和不嚴謹?shù)牡胤?，因為只要當你看到算法書上出現(xiàn)不顯然和不嚴謹?shù)牡胤?，基本上就意味著作者其實跳過了關鍵的思維步驟。
不幸的是《Algorithms》這本書里面講霍夫曼編碼已經算是講的好的了，如果你翻開著名的CLRS，看一看當中是怎么證明的，你就知道我說的什么意思了。有時候這些證明是如此的企圖追求formal和嚴謹，一上來就定義符號一大摞，讓人看了就想吐。
說了這么多，有沒有可能把霍夫曼編碼講的更好呢？前面說過，霍夫曼編碼我記了又忘，忘了又記，好幾次了，有一次終于煩了，心想如果要自己去證明，會怎么去證，那個時候我已經忘了《Algorithms》里面怎么講的了。所以我得從頭來起，首先，對于算法問題，有一個一般性原則是，先看一看解空間的構成。尤其是對于搜索問題（最優(yōu)化問題可以看做搜索問題的一個特例），這一點尤其重要?；舴蚵幋a的可能的編碼樹是有窮的，如果窮舉所有的編碼樹，然后找到那棵代價最小的，這種方法至少是可行的，有了可行的方法（即便是窮舉）至少讓我們內心感到踏實。
接下來便是提高搜尋效率的問題。而提高搜尋效率的關鍵（同樣也是一個一般性原則），便是盡量去尋找問題條件能夠推導出來的性質，****然后利用這些性質去避免不必要的搜尋，只要你學過二分搜索就應該理解這個一般性原則：二分搜索的效率之所以高于“窮搜”（O(n)），便是因為它利用了問題中的性質（有序）來避免了不必要的搜尋。有時候這個性質甚至可以直接將時間降為O(1)，例如在一個有序數(shù)組中尋找出現(xiàn)次數(shù)大于n/2的數(shù)（假設該數(shù)存在），利用“該數(shù)一定出現(xiàn)在數(shù)組正中間”這個性質，我們直接就避免了所有的計算。
不過，話雖如此，有時候這些性質并不是那么“顯然”的，需要對問題進行深入的折騰才能有可能發(fā)現(xiàn)。第三個一般原則：如果你要搜尋的元素是某個滿足特定條件的元素（例如尋找最優(yōu)解的時候，“最優(yōu)”的定義就是這個“特定條件”），那么可以“倒過來推”（數(shù)學證明常用手法，結論當條件使），即假設你已經找到了你要找的元素，那么能得出哪些結論，每一個結論都是最優(yōu)解的一個必要條件，而每一個必要條件都能夠幫助你避免不必要的搜尋，因為你只要發(fā)現(xiàn)某個候選解不滿足某個必要條件，就可以立即將其丟棄，前面提到的尋找出現(xiàn)次數(shù)大于n/2的例子是一個極端情況，我們得出的必要條件導致我們可以直接丟棄除中點元素之外的一切其他元素，再例如如果有人叫你尋找有序數(shù)組中最小元素，你會毫不猶豫地把該數(shù)組頭尾元素中較小的那個給他，因為你知道“如果那個最小元素存在，那么它必然位于頭尾”——這個必要條件直接允許你丟棄掉n-2個候選解。
回到霍夫曼編碼問題，按照這個原則，我們會去假設已經得到了最優(yōu)編碼樹，那么我們能夠發(fā)現(xiàn)關于它的什么性質呢？這里又要提到另一個適用于很多最優(yōu)化問題的原則（前面提到的原則適用于一般性搜索問題），所謂最優(yōu)解，就是說比其他所有解都要更好，雖然這句話聽上去像是廢話，但是它的一個直接推論——比與它鄰近的所有候選解都要好——就是一個非常有用的，不是廢話的性質了。學過微積分的都知道，光滑函數(shù)的最值點必然是大（?。┯谄溧徲騼鹊乃悬c的，然后再根據(jù)這個就自然推出該點的一階導數(shù)（切線斜率）必然為0的性質，這個性質（必要條件）讓我們直接省掉了去整個區(qū)間內搜索的麻煩，從而可以直接鎖定有限幾個候選解。那么，既然我們說最優(yōu)霍夫曼樹一定比它“附近”的樹更好，我們就想看看，怎么來找到它附近的樹。我們知道要從一個點到它附近，往往是對這個點進行一些調整，例如N+1是到達附近的另一個整數(shù)?；舴蚵鼧涫且豢脴?，所以對這棵樹的所有的一次“改動”（或“折騰”）都能夠到達與它的“改動”距離為1的點（是不是想起“編輯距離”這個概念），怎么改動呢？最符合直覺的（雖然并不是唯一的）改動便是把葉子節(jié)點進行互換。
于是我們得到一個重要的推論：
在最優(yōu)霍夫曼樹中，無論互換哪兩個葉子節(jié)點，得到的樹都變得更“差”。（嚴格來說是不會變得更“好”，因為最優(yōu)樹未必唯一）
這個性質看上去有點像廢話，值得費這么多事么？值得。因為雖然前文說了很多，但都是大多數(shù)人大腦里面既有的，一般性的法則，前面說過，如果我們能夠從我們已經掌握的一般法則出發(fā)來推導出問題的解，那么記憶負擔是最小的，因為這里面用到的所有法則我們都很清楚，也知道怎么一步步往下走。
上面這個性質究竟意味著什么呢？如果你假設這兩個葉子節(jié)點的頻率為f1和f2，深度為d1和d2，互換它們的時候，其他葉子節(jié)點的cost保持不變，令為常量C，那么互換前總cost為C+f1d1+f2d2，互換后為C+f1d2+f2d1，既然互換之后的樹一定更”差“那么就是說f1d1+f2d2 < f1d2 + f2d1，簡單變換一下就得到結論：f1(d1-d2)
有了這個結論之后，我們便能夠對最優(yōu)霍夫曼樹的構建走出確定性的一步，即，將頻率最低的兩個葉子節(jié)點放在最底層。別小看這一步，這一步已經排除了大量的可能性。這里，我們容易一開始天真地覺得最底層只有這兩個葉子節(jié)點，于是它們擁有共同父節(jié)點，這樣一來霍夫曼樹的整個拼圖便已經拼好了一個小小的角落。
然后我們會發(fā)現(xiàn)，要是它們不是兄弟怎么辦呢？這里提到另一個一般原則——歸約。不是兄弟的情況能否歸約為是兄弟的情況？反正我們要求的是一個最優(yōu)解，而不是所有的最優(yōu)解，我們只需證明，如果當這兩個最低頻率的葉子不是兄弟的時候的確存在著某棵最優(yōu)霍夫曼樹，那么通過交換它們各自的兄弟，從而讓這兩個葉子團聚之后，修改后的樹仍然是最優(yōu)的就可以了。事實情況也的確如此，證明非常直接——既然這里涉及到的所有4個節(jié)點都在最底層同一個高度上，那么互相交換的時候不會改變他們任何一個人的深度值，所以總cost不會改變。
但是接下來我們犯了難，整個樹的一個小小的櫻桃狀的局部是確定下來了，接下來怎么辦呢？一個最自然的思路就是考慮第三小的葉子，因為前面說了，元素頻率越低就越位于樹的底部嘛。第三小的葉子有兩種可能的歸屬，一是跟最小的兩個葉子同樣位于最底層（這不會違反我們前面得到的推論），這個時候第三小的葉子的兄弟葉子肯定是第四小的葉子，如下圖：
另一種歸屬就是往上一層去（注意，一旦第三小的葉子往上去了一層，那么剩下的所有葉子都必須至少在這個層以上），往上一層去了之后，它的兄弟是誰呢？不妨將它和剛才第一第二葉子的父節(jié)點結為兄弟（前面證明過，同層之前節(jié)點互換不會改變編碼的cost），如下圖：
可是現(xiàn)在問題出現(xiàn)了：雖然第一步構建（最小的兩個葉子）是確定的，但是到了第二步擺在我們面前的就有兩個選擇了，到底選擇哪個呢？一個辦法就是把兩種選擇都記下來，然后繼續(xù)往下走。可是別小看兩種選擇，接下去每一步都有兩種選擇的話就變成指數(shù)復雜度了。所以現(xiàn)在我們便有了動機回頭看一看，看問題中是否有什么沒有發(fā)現(xiàn)的性質能夠幫助我們再排除掉其中一個選擇。理想情況下如果每一步都是必然的，確定的，那么N步我們就可以構建出整棵樹，這是我們希望看到的，抱著這個良好的愿望，我們仔細觀察上面兩種構型，一個自然而然的問題是：這兩種構型都有潛質成為最優(yōu)解嗎？如果我們能夠證明其中一種構型不能成為最優(yōu)解那該多好？就省事多了嘛。這里引入另一個一般性的解題法則：特例。我們的大腦喜歡具體的東西，在特例中折騰和觀察會方便的多。
上面這個{1, 2, 3, 4}的例子就是個很好的特例，如圖（注：圖中節(jié)點旁的數(shù)字一概為頻率值，而非編號）：
多加折騰一番也許我們不難發(fā)現(xiàn)，如果將1，2及其父節(jié)點跟葉子4進行交換（注意：交換的時候1，2也被一同帶走了，因為反正1，2兩個節(jié)點已確定是好兄弟永遠不會分家了，折騰的時候只能作為一個整體移動，所以這里也可以說是交換子樹），那么樹的編碼將會變得更優(yōu)，因為這樣一次交換會將1和2的深度+1，意味著整棵樹的代價+3，而同時會將葉子4的深度-1，也就是說整棵樹的代價-4，總體上整棵樹的代價就是+3-4=-1（注意，在計算的時候我們只需考慮被交換的局部，因為樹的其他部分的代價保持不變）。如下圖：
這個交換啟發(fā)了我們，其實前面一開始說的交換兩個葉子節(jié)點可以推廣為交換內部節(jié)點和葉子節(jié)點，然后很快我們就會意識到其實可以推廣到交換任意兩個節(jié)點。（注意，當我們說交換內部節(jié)點的時候，其實是連同該內部節(jié)點作為局部根節(jié)點的整個子樹都交換過去）于是前面我們的推論就可以推廣為：
在最優(yōu)霍夫曼樹中，無論互換哪兩個節(jié)點，得到的樹都變得更“差”（交換內部節(jié)點則是連同該內部節(jié)點作為局部根的子樹一同帶走）
這個推論很容易理解，只不過是多增加了一種“編輯”最優(yōu)霍夫曼樹的方法罷了（記住最優(yōu)霍夫曼樹無論怎么“編輯”都不會變得更“好”，包括“交換子樹”這種“編輯”），我們前面沒有想到這種“編輯”方法是因為它不那么顯然，而且當時我們已經想到一種最直接的“編輯”方法了，即交換葉子，就容易順著那個思路一直走下去，直到我們發(fā)現(xiàn)必須尋找新的性質，才回過頭來看看有沒有其他法子。
當然，并不排除一開始就想到這種推廣的可能性，問題求解的過程并不是這么線性的，如果我們習慣了推而廣之的思維，也許一下就能想到這個推廣來。類似的，也不排除從另一種思路出發(fā)想到這種推廣的可能性。所以這里只是可能的思維軌跡中的一種，重點在于其中并沒有某處忽然出現(xiàn)一個不知從哪里冒出來的，神啟一般的結論。
剛才提到，構造最優(yōu)樹的第二步是考慮第三小的葉子，但也有另一種常見的思維：考慮到第一步（即選取頻率最小的兩個葉子）所做的事情是從N個葉子中選擇兩個黏在一起作為兄弟，那么也許對于一些人來說自然而然的第二步就是試圖繼續(xù)選取兩個節(jié)點黏在一起作為兄弟（注意這里不僅可以選擇葉子，也可以選擇已經生成的內部節(jié)點），然后依次類推來拼完整棵樹。按照這一思路，第二步的選項仍然還是集中在第三小的葉子上，因為這個選擇要么是讓第三第四小的葉子結拜為兄弟，要么是讓最小兩個葉子的父節(jié)點和第三小的葉子結拜。
回到剛才我們的推論：在最優(yōu)霍夫曼樹中，無論互換哪兩個節(jié)點，得到的樹都變得更“差”（交換內部節(jié)點則是連同該內部節(jié)點作為局部根的子樹一同帶走） 。根據(jù)這個推論我們容易計算出，在最優(yōu)霍夫曼樹當中，兩個內部節(jié)點n1和n2，如果n1比n2更深，那么n1下面的所有葉子的頻率之和必然要小于n2下面所有葉子的頻率之和。如果交換的是一個內部節(jié)點和一個葉子節(jié)點，則道理是類似的。這個性質的證明和上面的類似，就不贅述了。
這個性質暗示了一個重要的推廣結論：如果我們把每個內部節(jié)點的所有葉子的頻率之和標在它旁邊，那么整棵樹的每個節(jié)點便都有了一個數(shù)值，這個數(shù)值遵循統(tǒng)一的規(guī)律：即越往深層越小。這就意味著，我們剛才的二選一困境有辦法了！當我們將最小的兩個葉子f1和f2合并的時候，生成了一個新的節(jié)點M，這個節(jié)點有一個數(shù)字（為兩個葉子的頻率之和f1+f2），根據(jù)上面的推論，這個數(shù)字f1+f2跟所有頻率一同，遵循最小的在最底層的原則，所以我們下一步必須在剩下的那些互相之間關系待確定的節(jié)點（葉子節(jié)點和內部節(jié)點）之中，即{(f1 + f2), f3, f4}里面選擇最小的兩個數(shù)字結合成兄弟（由于f1和f2這兩個節(jié)點已經鐵板釘釘結為整體了，所以從集合里面可以看做移除）。到這里，我們就發(fā)現(xiàn)遞歸已經出現(xiàn)了，接下去的過程對于絕大多數(shù)人應該就真的很顯然了。
以上的解釋，比《Algorithms》更簡短嗎？顯然不是。反而要長得多（其實真正的思維過程比這要更長，因為中間還會涉及各種不成功的嘗試）。但是它比《Algorithms》當中的版本更不容易被忘記，因為其中關鍵的思維拐點并不是毫無來由的，而是從你已經熟知的，或者說雖然不知道，但容易理解的一般性解題法則出發(fā)自然推導出來的，所以你基本上不需要記憶什么東西，因為你需要記的已經在你腦海中了。
在上面的證明過程中，還有一個不像看上去那么顯然的事情：在我們尋找最優(yōu)霍夫曼樹的時候，我們曾經試圖去比較假想的最優(yōu)樹和它的“臨近”的樹，從而去探索最優(yōu)樹的性質。但是，究竟什么是臨近的樹？在前面的講解中，我們說如果交換A和B這兩個葉子節(jié)點，便得到一顆不同的樹，可以看做和原樹的“編輯距離”為1的樹。但是，真的這么顯然么？難道除了交換葉子的位置，就沒有其他辦法去“折騰”這棵樹了？后來我們看到，可以交換子樹而不僅僅是葉子，而交換子樹讓我們得到了至關重要的推論。此外，如果不是交換，而是像AVL樹那樣“旋轉”呢？說到底，二叉樹是一個離散的東西，并不像連續(xù)值那樣，天生就有“距離”這個概念，如果我們離散而孤立地去看待所有的樹，那么沒有什么臨近不臨近的，臨近本是一個距離的概念，除非我們定義樹和樹之間的距離函數(shù)，才能說臨近與否，而距離函數(shù)怎么定義才是“顯然”的呢？
還有，其實以上只是試圖給出最優(yōu)霍夫曼樹的證明的一個更自然的過程，而當年霍夫曼面臨這個問題的時候根本還沒有人想到要用二叉樹呢！更不要說在二叉樹的前提之下進行證明了。根據(jù)wikipedia的介紹，霍夫曼同學（當年還在讀Ph.D，所以的確是“同學”，而這個問題是坑爹的導師Robert M. Fano給他們作為大作業(yè)的，F(xiàn)ano自己和Shannon合作給出了一個suboptimal的編碼方案，為得不到optimal的方案而寢食難安，情急之下便死馬當活馬醫(yī)扔給他的學生們了）當年為這個問題憔悴了一個學期，最后就快到deadline的時候“忽然”想到二叉樹這個等價模型，然后在這個模型下三下五除二就搞定了一篇流芳千古的論文，超越了其導師。
最后說兩個有趣的現(xiàn)象：也許很多人會覺得，越是大師來寫入門教科書越是好，其實很多時候并非如此，尤其是在算法設計和數(shù)學領域，往往越是在其中浸淫久了越是難寫出貼近初學者的書，因為大量對初學者來說一點都不顯然的事情在他看來已經是“不假思索”了，成了他的內隱記憶，尤其是當他想要和你解釋一個復雜的東西的時候你就會發(fā)現(xiàn)他會常常邏輯跳躍，滿嘴跑術語，根本沒有意識到別人對有些術語和隱含的邏輯根本沒有像他那樣的理解。
最適合將一個東西講給別人聽的時候并不是等懂了很多年以后，而是剛剛弄懂的時候，這個時候從不懂到懂的差別記憶還非常鮮明，能夠清清楚楚地記得到底是哪些關鍵的地方是最折磨人的，也最能夠站在不懂者的角度來思考問題。像波利亞這樣，成了大師還能夠站在不懂者角度去換位思考的，可以說是鳳毛麟角。所以說前Amazon CAO（首席算法官）的《Introduction to Algorithms: a Creative Approach》絕對是本罕見的好算法書）
知其所以然（一）里面曾經提到，要弄清來龍去脈，最好去看看原始作者是怎么想的，可是正如上文所說，即便是最初的發(fā)明者，在講述的時候也會有意無意地“線性化”，我就去查看了霍夫曼最初的論文，那叫一個費解，不信你可以自己看看(PDF)。
可以歸約為搜索算法的問題（非常多）一般來說相對還是有一些頭緒的，因為搜索空間一般還比較容易界定，難點在于要從問題的條件中推導出用于節(jié)省搜索的性質。而策略設計問題則完全是另一個世界，因為策略的設計空間貌似是可列無窮的，常常讓人感覺無從下手，摸不著頭緒，許多讓人撓頭的智力問題就有這個特點（例如著名的100個囚徒和1個燈泡的房間就讓很多人有這種感覺），策略設計問題也有一些較通用的法則，以后再說。
怎么才能在學算法的時候學到背后的東西呢？有以下幾點很重要：
不要覺得每個步驟都很顯然，每個nontrivial的算法背后都有一段艱辛的探索經歷，覺得顯然的話必然是一種幻覺。Stay foolish，才能發(fā)現(xiàn)某些環(huán)節(jié)其實并不是那么顯然的。 檢驗是否真正理解的最佳方法就是過一段時間之后，自己試著證明一次。如果真正理解了的話，你的證明便會比較順暢。如果當時沒有真正理解，那么凡是那些你當時覺得顯然但其實不顯然的地方，都會成為你證明里面缺失的環(huán)節(jié)。 對于一個算法，多尋找各種來源的資料，也許能夠找到一個講的比較深刻的。我在《數(shù)學之美番外篇：快排為什么那么快》和《知其所以然（一）》里面都舉到了這樣的例子。 多試著去抽象背后的一般性法則，即便后來發(fā)現(xiàn)抽象得是錯的，也比不去抽象要好。抽象是推廣的基礎。只有抽象出更深層的法則，才能讓你事半功倍，觸類旁通，否則一個蘿卜永遠是一個坑。（注意，其實我們的下意識是會進行一定程度的抽象的，例如前面提到的原始人的例子，小溪和小河（或者小溝）細節(jié)上是不同的，但本質上是一樣的，我們的大腦會自動進行這種簡單抽象，提出事物的共性。正因此，即便你不去有意識地總結一般規(guī)律，只要你看的足夠多，練的足夠多，必然就會越來越諳熟。）
最后留個問題：雖然按照上文的方式來構造霍夫曼樹一定能夠得到一個最優(yōu)樹，但是怎么證明一定能得到呢？乍一看這個問題似乎很多余，因為證明很簡單：我們拼裝整棵樹的每一步都沒得選，而且每一步都必然拼湊出最優(yōu)樹的一個小小局部，如果最終還沒有得到最優(yōu)樹的話，只能說最優(yōu)樹是不存在的了，然而最優(yōu)樹是一定存在的，因為所有樹的集合是有窮的，有窮集必有最值，因此證畢。這個證明固然是沒問題的，但它其實是一個間接證明，換句話說，我們在構建樹的過程中的邏輯是這樣的：“之所以我們選擇粘結n1和n2，是因為其他粘法必然違反最優(yōu)樹的兩個性質。所以我們別無選擇?！钡?，這并沒有說，我們選擇了粘結n1和n2，一定就符合了最優(yōu)樹的性質。（也就是說“其他做法都是錯”并不能推出“這種做法必然對”，這就像是你在一大堆豆子當中尋找一個特殊的豆子，你拿起一個，看看不是，扔掉，又拿起一個，還不是，扔掉，排除到最后只剩一個豆子了，假設你又知道這個特殊的豆子必然存在，那么這個時候你根本不用看就知道這個豆子一定就是你要找的）那么，你能否直接證明，拼裝最優(yōu)樹的過程每一步都符合最優(yōu)樹的性質呢？
本文僅做學術分享，如有侵權，請聯(lián)系刪文。