 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 2180 | 回復(fù): 4 | ||||
[交流]
【轉(zhuǎn)】知其所以然（以算法學(xué)習(xí)為例） 已有2人參與
|
|
原文見(jiàn) http://mindhacks.cn/2008/07/07/the-importance-of-knowing-why/ 知其所以然（以算法學(xué)習(xí)為例） By 劉未鵬 – July 7, 2008Posted in: 學(xué)習(xí)方法, 算法 Updated(2008-7-24)：更新見(jiàn)正文部分，有標(biāo)注。 其實(shí)下文的絕大部分內(nèi)容對(duì)所有學(xué)習(xí)都是同理的。只不過(guò)最近在正兒巴經(jīng)地學(xué)算法，而后者又不是好啃的骨頭，所以平時(shí)思考總結(jié)得就自然要比學(xué)其它東西要多一些。 問(wèn)題：目前幾乎所有的算法書(shū)的講解方式都是歐幾里德式的、瀑布式的、自上而下的、每一個(gè)推導(dǎo)步驟都是精準(zhǔn)制導(dǎo)直接面向目標(biāo)的。由因到果，定義、引理、定理、證明一樣不少，井井有條一絲不亂毫無(wú)贅肉。而實(shí)際上，這完全把人類(lèi)大腦創(chuàng)造發(fā)明的步驟給反過(guò)來(lái)了。看起來(lái)是陽(yáng)關(guān)大道，實(shí)際上車(chē)馬不通。 而對(duì)讀者來(lái)說(shuō)，這就等于直接告訴你答案&做法了，然后讓你去驗(yàn)證這個(gè)答案&做法是可行&成立的。而關(guān)于答案&做法到底是怎么來(lái)的，從問(wèn)題到答案之間經(jīng)歷了怎樣的思維過(guò)程。卻鮮有書(shū)能夠很好的闡釋。就我有限的閱（算法）書(shū)經(jīng)驗(yàn)，除了波利亞的《怎樣解題》還算合格之外（也并非最理想），其它的（包括有名的《算法導(dǎo)論》、《如何解題：現(xiàn)代啟發(fā)式方法》、《Algorithms》、《編程珠璣》，甚至TAOCP——公平地說(shuō)由于高老大對(duì)算法領(lǐng)域歷史了解得非常通透，所以許多地方能夠從原始脈絡(luò)來(lái)講述一個(gè)問(wèn)題，譬如令人印象深刻的從競(jìng)賽樹(shù)到堆的講解就寥寥一頁(yè)紙道出了堆這個(gè)數(shù)據(jù)結(jié)構(gòu)的本質(zhì)來(lái)，而像剛才列的幾本有名的書(shū)卻都沒(méi)有做到），在思維的講述上都算不上合格（當(dāng)然不是說(shuō)這些書(shū)沒(méi)有價(jià)值，作為知識(shí)性的參考書(shū)籍，它們將知識(shí)整理出系統(tǒng)結(jié)構(gòu)，極大的便利了知識(shí)的掌握，就像《什么是數(shù)學(xué)》所做的工作一樣），為什么我這么說(shuō)呢，因?yàn)槲野l(fā)現(xiàn)每每需要尋找對(duì)一個(gè)算法的解釋的時(shí)候，翻開(kāi)這些書(shū)，總是直接就看到關(guān)于算法邏輯的描述，卻看不到整個(gè)算法的誕生過(guò)程背后的思想。 我們要的不是相對(duì)論，而是誕生相對(duì)論的那個(gè)大腦。我們要的不是金蛋，而是下金蛋的那只雞。 Update(2008-7-24): 收到不少同學(xué)的批評(píng)，想來(lái)這個(gè)開(kāi)頭對(duì)一些著作的語(yǔ)氣過(guò)重了，實(shí)際上，注意，我完全不否認(rèn)這些著作的價(jià)值，我自己也在通過(guò)閱讀它們來(lái)學(xué)習(xí)算法，并且有很多收獲。這篇文章更多的只是建議除了閱讀這些著作之外還需要做的功課。此外，對(duì)于這類(lèi)知識(shí)講述（歐幾里德）方式的批判西方（尤其是在數(shù)學(xué)領(lǐng)域）早就有了，早在歐拉和龐加萊的時(shí)候，他們倆就極其強(qiáng)調(diào)思維的傳授，歐拉認(rèn)為如果不能傳授思維，那數(shù)學(xué)教學(xué)是沒(méi)意義的。而龐加萊本人則更是對(duì)數(shù)學(xué)思維有極大的興趣和研究（我前陣子在討論組上還轉(zhuǎn)載了一篇龐加萊的著名演講，就是說(shuō)這個(gè)的，參見(jiàn)這里）。我只是在說(shuō)目前的算法書(shū)沒(méi)有做到思維講述的層面，因此建議閱讀這些書(shū)之余應(yīng)該尋找算法的原始出處，應(yīng)該尋根究底，多做一些功課，知道算法到底是怎么誕生的，并且我說(shuō)明了為什么應(yīng)該知其所以然，有哪些好處（見(jiàn)下文），我還給了幾個(gè)例子譬如紅黑樹(shù)作者講紅黑樹(shù)的，g9講后綴樹(shù)的，以及Knuth講heap的。唉，其實(shí)挺正統(tǒng)的觀點(diǎn)，授人以漁，不管是東方西方都有類(lèi)似的古老諺語(yǔ)。而我只是從認(rèn)知科學(xué)的角度加了點(diǎn)解釋?zhuān)瑆indstorm稱(chēng)之為“解釋文”。而已。可惜被開(kāi)頭的語(yǔ)氣搞砸了，算了，既發(fā)了也就不改了。 為什么會(huì)這樣，其實(shí)是有原因的。 我們?cè)谒伎家粋�(gè)問(wèn)題的過(guò)程中有兩種思維形式： 聯(lián)想：這種思維某種程度上可以說(shuō)是“混亂”的（雖然從一個(gè)更根本的層面上說(shuō)是有規(guī)則的），所謂混亂是指很多時(shí)候并不確定聯(lián)想到的做法最終是否可行，這些聯(lián)想也許只是基于題目中的某個(gè)詞語(yǔ)、語(yǔ)法結(jié)構(gòu)、問(wèn)題的某個(gè)切片、一些零星局部的信息。這個(gè)過(guò)程是試探性的。最后也許有很大一部分被證明是不可行的。很多時(shí)候我們解決問(wèn)題用的都是這種思維，簡(jiǎn)言之就是首先枚舉你關(guān)于這個(gè)問(wèn)題能夠想到的所有你學(xué)過(guò)的知識(shí)，然后一一往上套看看能否解決手頭的問(wèn)題。這種思維方式受限于人腦聯(lián)想能力本身的局限性。我在《跟波利亞學(xué)解題》中就提到了幾個(gè)例子。聯(lián)想本身需要記憶提取的線索，所以受到記憶提取線索的制約，如果線索不足，那怎么也聯(lián)想不起來(lái)。而提取線索的建立又取決于當(dāng)初保存記憶的時(shí)候的加工方法（《找尋逝去的自我》里面有闡述），同時(shí)，面對(duì)一個(gè)問(wèn)題，你能夠從中抽取出來(lái)的聯(lián)想線索又取決于你對(duì)問(wèn)題的認(rèn)識(shí)層度/抽象深度，表淺的線索很可能是無(wú)關(guān)的，導(dǎo)致無(wú)效的聯(lián)想&試錯(cuò)（《Psychology of Problem Solving》里面有闡述）�？傊�，聯(lián)想這個(gè)過(guò)程充滿了錯(cuò)誤的可能。 演繹&歸納：演繹&歸納是另一種思維形式。它們遠(yuǎn)比聯(lián)想有根據(jù)。其中演繹是嚴(yán)格的，必然的。歸納也是有一定根據(jù)的。在面對(duì)一個(gè)問(wèn)題的時(shí)候，我們有意無(wú)意的對(duì)問(wèn)題中的各個(gè)條件進(jìn)行著演繹；譬如福爾摩斯著名的“狗叫”推理——狗+生人=>吠叫 & 昨晚狗沒(méi)有叫 => 那個(gè)人是熟人。就是一個(gè)典型的對(duì)問(wèn)題的各個(gè)條件進(jìn)行演繹的推理過(guò)程。還有就是通過(guò)對(duì)一些特殊形式的觀察來(lái)進(jìn)行歸納，試圖總結(jié)問(wèn)題中的規(guī)律。然而，不幸的是，面對(duì)復(fù)雜的問(wèn)題，演繹&歸納也并不總是“直奔”問(wèn)題的解決方案的。人的思維畢竟只能一下子看到有限的幾步邏輯結(jié)論，一條邏輯演繹路徑是否直奔答案，不走到最后往往是不知道的，只要答案還未出現(xiàn)，我們大腦中的邏輯演繹之樹(shù)的末端就始終隱藏在黑暗之中。而當(dāng)最終答案出現(xiàn)了之后，我們會(huì)發(fā)現(xiàn)，這棵演繹之樹(shù)的很多分支實(shí)際上都并不通往答案。所以，雖然演繹&歸納是一種“必然”的推理，然而卻并不“必然”引向問(wèn)題的結(jié)論，它也是試錯(cuò)的，只不過(guò)比聯(lián)想要更為靠譜一些。 既然認(rèn)識(shí)到，人類(lèi)解決問(wèn)題的兩大思維方式實(shí)際上都是有很大的試錯(cuò)成分的（好聽(tīng)一點(diǎn)叫“探索”），那么就不難意識(shí)到，對(duì)一個(gè)問(wèn)題的思考過(guò)程實(shí)際上是相當(dāng)錯(cuò)綜復(fù)雜的，而且充滿了無(wú)效分支——在思考的過(guò)程中我們也會(huì)不斷的對(duì)分支進(jìn)行評(píng)估，做適當(dāng)?shù)募糁Α虼水?dāng)我們找到問(wèn)題的解之后，一來(lái)思維的漫長(zhǎng)繁雜的過(guò)程已經(jīng)在大腦里面淡化得差不多了，只有那些引向最終結(jié)論的過(guò)程會(huì)被加“高亮”——我們?cè)谒伎嫉倪^(guò)程中本就會(huì)不斷的拋棄無(wú)效的思路，只留下最有希望的思路。簡(jiǎn)而言之就是最后證明沒(méi)用或者早先我們就不抱希望的一些想法就被從工作記憶中扔掉了。二來(lái)，思考過(guò)程是我們的空氣和水，而“魚(yú)是最后一個(gè)感覺(jué)到水的”，我們感覺(jué)不到思維法則本身的存在，我們只是不知不覺(jué)運(yùn)用它。三來(lái)，由于我們的目標(biāo)是問(wèn)題的解，解才是我們?yōu)橹d奮和狂喜的東西，而不是求解的過(guò)程，過(guò)程只是過(guò)程，目的才是目的。這就像一個(gè)尋寶者，在漫長(zhǎng)曲折的尋寶歷程之后，在找到寶藏的時(shí)候，他會(huì)對(duì)寶藏感到狂喜（記得阿基米德的“找到了！”嗎？）而迫不及待地要展示出來(lái)，而漫長(zhǎng)的思考本身卻成了注腳。我們是有目的的動(dòng)物，目的達(dá)到了，其它的就相對(duì)不那么重要了。最后，對(duì)于傳授知識(shí)的人，也許還有其四：感到介紹思維過(guò)程是不相干的，畢竟思維過(guò)程并不是算法問(wèn)題的解，算法問(wèn)題的解才是算法問(wèn)題的解。然而不幸的是，忽視到達(dá)解的那個(gè)過(guò)程實(shí)際上卻變成了舍本逐末。我們看到的是寥寥數(shù)行精妙絕倫的算法，然后仰天長(zhǎng)嘆自己想不出來(lái)啊想不出來(lái)。為什么想不出來(lái)，因?yàn)槟悴恢滥嵌潭虜?shù)行算法背后經(jīng)歷的事怎樣漫長(zhǎng)的思考過(guò)程，如果問(wèn)題求解是一部偵探小說(shuō)，那么算法只是結(jié)局而已，而思考過(guò)程才是情節(jié)。 既然如此，也就難怪古往今來(lái)算法牛人們算法牛，但卻沒(méi)有幾個(gè)能真正在講述的時(shí)候還原自己的思維過(guò)程的（那個(gè)“ 漁”字），手把手的教學(xué)生走一遍推理的思路，就可以讓學(xué)生獲得思維過(guò)程的訓(xùn)練。金出武雄在《像外行一樣思考，像專(zhuān)家一樣實(shí)踐》中說(shuō)寫(xiě)論文應(yīng)該寫(xiě)得像偵探小說(shuō)一樣，我很贊同。歐幾里德式的介紹，除了提供枯燥的知識(shí)之外，并沒(méi)有提供幫助人獲得知識(shí)的東西——思維（關(guān)于對(duì)數(shù)學(xué)書(shū)籍的歐幾里德式寫(xiě)法的批評(píng)其實(shí)也是由來(lái)已久了，并且有人呼吁了好幾種其它的教學(xué)方法）。從這方面，我們所尊敬的一些“圣經(jīng)”級(jí)書(shū)籍在傳道授業(yè)上還不如偵探小說(shuō)，前者是羅列一大堆知識(shí)，后者則是闡述獲得知識(shí)的過(guò)程——推理&聯(lián)想。 然而，我們都是人，人類(lèi)該有的思維形式，我們難道不是都有嗎。既然如此，思維本身又有什么需要一遍遍教的呢？ 并非如此。 講述思維過(guò)程而非結(jié)果有幾個(gè)極其重要的價(jià)值： 內(nèi)隱化：思維法則其實(shí)也是知識(shí)（只不過(guò)它是元知識(shí)——是幫助我們獲得新知識(shí)的知識(shí)）；是內(nèi)隱的記憶。我們?cè)谒伎嫉倪^(guò)程中覺(jué)察不到思維法則的作用，它們卻在幕后實(shí)實(shí)在在的左右著我們的思維軌跡。要將思維方法內(nèi)隱化，需要不斷練習(xí)，就像需要不斷練習(xí)才能無(wú)意識(shí)狀態(tài)下就能騎自行車(chē)一樣。 跨情境運(yùn)用：思維法則也是知識(shí)記憶，是問(wèn)題解決策略。既然是記憶，就受到提取線索的制約，這就是為什么當(dāng)波利亞告訴你要“注意未知數(shù)”之后你還是不能真正在所有需要你“注意未知數(shù)”的地方都能提醒自己“注意未知數(shù)”。很多時(shí)候未知數(shù)是很隱蔽的，未知數(shù)并不會(huì)總是頭頂一個(gè)大帽子上面寫(xiě)著“我是未知數(shù)”。所以很多時(shí)候缺乏對(duì)這個(gè)策略的“提醒”線索，這也是為什么你學(xué)會(huì)了在解決數(shù)學(xué)問(wèn)題的時(shí)候“注意未知數(shù)”卻不一定能在解決現(xiàn)實(shí)生活中的問(wèn)題中時(shí)刻都能“注意你的未知數(shù)”（《你的燈亮著嗎？》整本書(shū)的價(jià)值便在于此），因?yàn)榻鈹?shù)學(xué)題和解決生活中問(wèn)題的場(chǎng)景不一樣，不同的環(huán)境線索，在你大腦中激發(fā)的記憶也不一樣。就連問(wèn)題求解中，不同的問(wèn)題之間的細(xì)小差別也可能導(dǎo)致思維軌跡很大的不同，有時(shí)你的注意力會(huì)被一個(gè)無(wú)關(guān)線索激發(fā)的聯(lián)想吸引開(kāi)去，忘記如“注意你的未知數(shù)”這樣的重要法則。而一本從思維角度來(lái)講問(wèn)題求解的書(shū)則可以一遍遍將你置于不同的問(wèn)題場(chǎng)景下然后在該提醒你的時(shí)候提醒你，讓你醒悟到“哦，原來(lái)這個(gè)時(shí)候也應(yīng)該想到這個(gè)啊。”，做多了這樣的思維演習(xí)你就會(huì)逐漸從中領(lǐng)悟到某種共性，并將一些思維習(xí)慣得到強(qiáng)化，于是終于能夠在需要運(yùn)用某策略的時(shí)候能適時(shí)的想起來(lái)了。 對(duì)問(wèn)題解的更多記憶提取線索：我們平時(shí)學(xué)習(xí)算法時(shí)幾乎僅止于“理解”，別人把一個(gè)方案放在你面前，你去驗(yàn)證一下，心說(shuō)“哦，不錯(cuò)，這個(gè)的確可以工作”。然后就沒(méi)了。稍微簡(jiǎn)單一點(diǎn)的算法還好，復(fù)雜一點(diǎn)的對(duì)于記憶的負(fù)擔(dān)是很大的，這就是為什么有時(shí)候我們看到一個(gè)絕妙的解法，這個(gè)解法看上去不知道從哪里來(lái)的，但經(jīng)過(guò)我們的理解，卻發(fā)現(xiàn)是對(duì)的，我們感嘆，真巧妙，結(jié)果一些天之后，別人問(wèn)起這個(gè)問(wèn)題，我們說(shuō)：“唉，那是個(gè)多么巧妙的算法啊，但是我只記得它巧妙，卻不記得它到底是怎樣的了�！� 為什么？因?yàn)樵诓恢渌匀坏那闆r下，算法只是一堆離散的機(jī)械步驟，缺少背后的思想的支撐，這些步驟之間就沒(méi)有一個(gè)本質(zhì)層面上的關(guān)聯(lián)（先知亞里士多德早就指出：學(xué)習(xí)即聯(lián)接）。所以就跟背歷史書(shū)也沒(méi)多大區(qū)別。然而，知道了算法是怎樣一步步被推導(dǎo)出來(lái)的，我們就一下?lián)碛辛舜罅康挠洃浱崛【�索：對(duì)算法發(fā)現(xiàn)過(guò)程中的任何一個(gè)關(guān)鍵步驟（尤其是本質(zhì)）的回憶都可能使我們能夠自己動(dòng)手推導(dǎo)出剩余的內(nèi)容。譬如你知道堆(heap)是怎樣由樸素的決策樹(shù)演化而來(lái)的，它又是為了解決什么問(wèn)題的，你即便忘記了具體的細(xì)節(jié)，也可以自己推導(dǎo)出來(lái)。譬如你知道KMP算法的本質(zhì)在于消除回溯，至于如何消除回溯卻并不是那么難以推導(dǎo)的，所以即便忘了也可以借助于大腦的邏輯演繹能力再現(xiàn)出來(lái)。譬如你知道Tarjan算法其實(shí)只是從后序遍歷經(jīng)過(guò)兩個(gè)優(yōu)化調(diào)整而來(lái)的（其中并査集的使用其實(shí)只是優(yōu)化手段——為了能夠迅速判斷祖先節(jié)點(diǎn)是誰(shuí)——而非算法本質(zhì)——當(dāng)然，算法設(shè)計(jì)的主要任務(wù)本來(lái)就是通過(guò)問(wèn)題條件中蘊(yùn)含的知識(shí)來(lái)“消除冗余計(jì)算”和“避免不必要計(jì)算”，所以你也可以說(shuō)并査集的使用是關(guān)乎本質(zhì)的，只不過(guò)，知道了為什么需要引入并査集，就會(huì)強(qiáng)烈地感覺(jué)到一切是順理成章的了），那這個(gè)出了名的繞人的算法也就不那么難以理解和記憶了。譬如你知道排序的本質(zhì)，就能夠?qū)κ裁词亲顑?yōu)排序，為什么它是最優(yōu)排序有深刻的認(rèn)識(shí)。四兩撥千斤。 包含了多得多的知識(shí)：記一個(gè)算法，就只有一個(gè)算法。一個(gè)蘿卜一個(gè)坑。就好比背99乘法表只能解決乘法問(wèn)題一樣。而記背后的思想，卻有助于解決一類(lèi)問(wèn)題。思想所處的抽象層面往往比到處都是實(shí)現(xiàn)細(xì)節(jié)的算法本身要低，越是低的抽象層次，越是本質(zhì)，涵蓋范圍越是廣泛。數(shù)學(xué)的發(fā)展本身就體現(xiàn)了這個(gè)過(guò)程，抽象代數(shù)就是非常好的例子。算法誕生過(guò)程中的思路往往包含了比實(shí)際算法更本質(zhì)得多的知識(shí)，實(shí)際算法乃至算法的某個(gè)特定語(yǔ)言的實(shí)現(xiàn)包含了太多表面的不相干知識(shí)，它們會(huì)阻礙對(duì)本質(zhì)的理解。 重在分析推理，而不是聯(lián)想：學(xué)了一大通算法和數(shù)據(jù)結(jié)構(gòu)之后的一個(gè)副作用就是，看到一個(gè)問(wèn)題之后，腦袋里立即不管三七二十一冒出一堆可能相干的數(shù)據(jù)結(jié)構(gòu)和算法來(lái)。聯(lián)想是強(qiáng)大的思維捷徑，在任何時(shí)候都會(huì)搶占大腦的工作記憶，由不得你控制——比如我問(wèn)你“如何尋找區(qū)間的最大值”，首先進(jìn)入你的意識(shí)的肯定就是學(xué)過(guò)的那個(gè)算法，甚至算法的實(shí)現(xiàn)細(xì)節(jié)都一一跳了出來(lái)，也許最先跳出來(lái)的還是算法實(shí)現(xiàn)中某個(gè)最容易弄錯(cuò)的邊界細(xì)節(jié)，或是某個(gè)比較tricky的實(shí)現(xiàn)技巧！然而這些其實(shí)根本不反映一個(gè)算法的本質(zhì)，結(jié)果想來(lái)想去總是停留在問(wèn)題的表層。而另一方面，重在思維的傳授則可以讓人養(yǎng)成從問(wèn)題本質(zhì)入手，逐步分析推理的習(xí)慣，而不是直接生搬硬套。當(dāng)然，完全不可否認(rèn)，聯(lián)想本身也是極其重要的思維方法，甚至可以說(shuō)是人類(lèi)思維最重要的特征。很多時(shí)候我們并不知道問(wèn)題的本質(zhì)是什么，就需要靠聯(lián)想、類(lèi)比來(lái)領(lǐng)路探索。只不過(guò)，養(yǎng)成優(yōu)先從問(wèn)題的本質(zhì)入手進(jìn)行考察的好習(xí)慣絕對(duì)是有更大的好處的。 那到底什么樣的才算是授人以漁的呢？波利亞的《如何解題》絕對(duì)算是一本，他的《數(shù)學(xué)的發(fā)現(xiàn)》也值得一看。具體到算法書(shū)，那就不是光看text book就足夠的了，為了深入理解一個(gè)算法的來(lái)龍去脈前因后果，從一個(gè)算法中領(lǐng)悟盡量深刻的東西，則需要做到三件事情： 尋找該算法的原始出處：TAOCP作為一個(gè)資料庫(kù)是絕對(duì)優(yōu)秀的，基礎(chǔ)的算法只要你能想到的，幾乎都可以在上面找到原始出處。查到原始出處之后（譬如一篇paper），就可以去網(wǎng)上搜來(lái)看了。因?yàn)樽畛醯淖髡咄鶎?duì)一個(gè)方案的誕生過(guò)程最為了解。比如經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的紅黑樹(shù)是出了名的令人費(fèi)解的結(jié)構(gòu)之一，但它的作者Sedgewick一張PPT，給你講得通通透透，比算法導(dǎo)論上的講法強(qiáng)上數(shù)倍。 原始的出處其實(shí)也未必就都推心置腹地和你講得那么到位：前面說(shuō)過(guò)，算法設(shè)計(jì)出來(lái)了之后人們幾乎是不會(huì)去回顧整個(gè)的思維過(guò)程細(xì)節(jié)的，只把直指目標(biāo)的那些東西寫(xiě)出來(lái)。結(jié)果就又是一篇?dú)W幾里德式的文章了。于是你就迷失在一大堆“定義”、“引理”、“定理”之中了。這種文章看上去整個(gè)寫(xiě)得井井有條，其實(shí)是把發(fā)明的過(guò)程整個(gè)給顛倒過(guò)來(lái)了，我一直就想，如果作者們能夠?qū)⒄麄�(gè)的思路過(guò)程寫(xiě)出來(lái)，哪怕文字多上十倍，我也絕對(duì)會(huì)比看那一堆定義定理要容易理解得多。話說(shuō)回來(lái)，怎么辦？可以再去網(wǎng)上找找，牛人講得未必比經(jīng)典教材上的差。那倘若實(shí)在找不出好的介紹呢，就只能自己揣摩了。揣摩的重要性，是怎么說(shuō)都不為過(guò)的。揣摩的一些指導(dǎo)性的問(wèn)題有：為什么要這樣（為什么這是好的）？為什么不是那樣（有其它做法嗎？有更好的做法嗎？）？這樣做是最好的嗎？（為什么？能證明嗎？）這個(gè)做法跟其它的什么做法有本質(zhì)聯(lián)系嗎？這個(gè)跟這個(gè)的區(qū)別是什么？問(wèn)題的本質(zhì)是什么？這個(gè)做法的本質(zhì)又是什么？到底本質(zhì)上是什么東西導(dǎo)致了這個(gè)做法如此..？與這個(gè)問(wèn)題類(lèi)似的還有其它問(wèn)題嗎？（同樣或類(lèi)似的做法也適用嗎？）等等。 不僅學(xué)習(xí)別人的思路，整理自己的思路也是極其重要的：詳見(jiàn)《跟波利亞學(xué)解題》的“4. 一個(gè)好習(xí)慣”和“7. 總結(jié)的意義”。 前一段時(shí)間我們討論組上有不少例子，見(jiàn)這里，或這里。 |
回復(fù)此樓» 收錄本帖的淘帖專(zhuān)輯推薦
 綜合提高 |
» 猜你喜歡
本人考085602 化學(xué)工程 專(zhuān)碩
已經(jīng)有23人回復(fù)
-
求調(diào)劑院校信息
已經(jīng)有4人回復(fù)
-
085600材料與化工306
已經(jīng)有4人回復(fù)
-
286求調(diào)劑
已經(jīng)有10人回復(fù)
-
328求調(diào)劑，英語(yǔ)六級(jí)551，有科研經(jīng)歷
已經(jīng)有9人回復(fù)
-
一志愿北京化工大學(xué)070300 學(xué)碩336求調(diào)劑
已經(jīng)有4人回復(fù)
-
286分人工智能專(zhuān)業(yè)請(qǐng)求調(diào)劑愿意跨考！
已經(jīng)有8人回復(fù)
-
資源與環(huán)境 調(diào)劑申請(qǐng)(333分)
已經(jīng)有5人回復(fù)
-
280求調(diào)劑
已經(jīng)有12人回復(fù)
-
269專(zhuān)碩求調(diào)劑
已經(jīng)有5人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- 困惑——想問(wèn)下金屬材料國(guó)內(nèi)與國(guó)外的差距在哪里
已經(jīng)有5人回復(fù)
- 想跟大家交流下藥物合成工作怎么做好？
已經(jīng)有16人回復(fù)
- 注冊(cè)立項(xiàng)之菜鳥(niǎo)晉級(jí)全攻略（1）——級(jí)數(shù)設(shè)定
已經(jīng)有100人回復(fù)
- 我的考博后隨想（中科院+985）
已經(jīng)有132人回復(fù)
- 考數(shù)學(xué)專(zhuān)業(yè)研究生個(gè)人的一點(diǎn)感受
已經(jīng)有5人回復(fù)
- 純電動(dòng)及混合動(dòng)力汽車(chē)設(shè)計(jì)基礎(chǔ)（原書(shū)第2版）_（美）IQBAL HUSAIN_2012.05
已經(jīng)有351人回復(fù)
- 激發(fā)態(tài)的躍遷密度（TD）和電荷差異密度(CDD)
已經(jīng)有15人回復(fù)
- 吸水性（hygroscopicity）和親水性（hydrophilic）有什么區(qū)別
已經(jīng)有11人回復(fù)
- 扁桃酸 拆分手性 腫胺
已經(jīng)有30人回復(fù)
- 有關(guān)圖像特征提取的問(wèn)題。
已經(jīng)有13人回復(fù)
- 外審后的主編審稿問(wèn)題
已經(jīng)有8人回復(fù)
- 這篇論文外審了嗎？
已經(jīng)有19人回復(fù)
- 第一次投稿，論文未外審，編輯直接要求修改英語(yǔ)語(yǔ)法，怎么辦？謝謝！
已經(jīng)有11人回復(fù)
- 藥物載體是用納米粒子好還是微米粒子好啊
已經(jīng)有17人回復(fù)
- 【求助】嵌段共聚物如何表征
已經(jīng)有25人回復(fù)
|
知其所以然（續(xù)） By 劉未鵬 – November 14, 2010Posted in: 學(xué)習(xí)方法, 算法 查了一下，上篇知其所以然（以學(xué)習(xí)算法為例）是08年7月寫(xiě)的，現(xiàn)在已經(jīng)是10年11月，過(guò)去了兩年零4個(gè)月，這說(shuō)明了三件事情：1，一個(gè)問(wèn)題其實(shí)你可以一直放在腦子里面，利用暗時(shí)間對(duì)其軟泡硬磨，時(shí)間足夠久你總會(huì)有一點(diǎn)新的感悟，問(wèn)題其實(shí)就像那句老話說(shuō)的那樣，不怕賊偷就怕賊惦記，聚精會(huì)神的思考一天，也許比不上惦記一個(gè)星期（據(jù)說(shuō)數(shù)學(xué)家龐加萊就特別會(huì)惦記問(wèn)題）。2，事實(shí)上，當(dāng)你感覺(jué)懂了的時(shí)候，你至少得反問(wèn)自己一句，真的懂了嗎？當(dāng)你確信自己真的懂了的時(shí)候，你至少得講給別人聽(tīng)，別人聽(tīng)懂了嗎？考察你自己是否真懂了的一個(gè)很好的依據(jù)是，你是否有一種“哦，原來(lái)是這樣啊，這下再也不可能忘記了”的感覺(jué)。3，我其實(shí)沒(méi)有忘記這個(gè)博客。如我之前說(shuō)的，記錄只是學(xué)習(xí)和思考的副作用，只要還在學(xué)習(xí)和思考，就必然會(huì)有新的記錄。 我有一個(gè)習(xí)慣，看定理必看證明。一個(gè)你不明白其證明的定理在我看來(lái)比不知道這個(gè)定理還要糟糕，因它給你造成一種懂了的錯(cuò)覺(jué)。在沒(méi)有明白背后的證明之前，任何一個(gè)定理對(duì)你來(lái)說(shuō)都是等價(jià)的——等價(jià)于背乘法口訣（只不過(guò)有的長(zhǎng)一點(diǎn)有的短一點(diǎn)）。一個(gè)原本美妙的定理，把其證明扔掉就是真正的買(mǎi)櫝還珠，暴殄天物。 從現(xiàn)實(shí)意義來(lái)說(shuō)，去理解一個(gè)定理的證明會(huì)帶來(lái)巨大的好處，首當(dāng)其沖的好處就是你很難再忘掉它。這一點(diǎn)其實(shí)很容易解釋——在理解一個(gè)定理的證明之前，定理對(duì)你而言是一堆沒(méi)有內(nèi)在聯(lián)系的詞句，而在理解了證明之后，定理就歸約為證明它所需的條件加上邏輯，“邏輯”本來(lái)就存在于你的大腦里面，而證明的過(guò)程中除了公理和用到的常見(jiàn)定理（往往沒(méi)幾條）之外，寬泛地說(shuō)，需要你去記的，一般來(lái)說(shuō)也只有一個(gè)或兩個(gè)關(guān)鍵的insights，也就是我們常說(shuō)的證明中的神來(lái)之筆，比如幾何證明里面的某條看上去莫名其妙的輔助線，一旦你知道了這條輔助線，那么整個(gè)證明就毫無(wú)難處，那么該定理的信息量便直接縮減為一條輔助線的信息量；雖然看上去這一步信息并沒(méi)有縮減多少，但是如果你考慮到類(lèi)似的輔助線不僅會(huì)用在這個(gè)特定的定理上，往往會(huì)在很多地方用到。很多關(guān)鍵的證明手法是通用的。那么其實(shí)你就是把所有以這個(gè)輔助線為關(guān)鍵證明手法的定理的集合的信息量歸約為了這條輔助線。如果你進(jìn)而甚至能夠理解了作這條輔助線的思想精髓，那就更牛逼了，因?yàn)榻鉀Q問(wèn)題的思路更具有一般性，理解了尋找正確的輔助線的思路，你就根本不需要去記得某條特定輔助線的作法，你就把所有以作一條或幾條輔助線為證明核心的定理的集合的信息量歸約為了這個(gè)“尋找輔助線的思路”。 這是一個(gè)樹(shù)狀的知識(shí)結(jié)構(gòu)，越往上層走，需要記憶的節(jié)點(diǎn)就越少。所謂觸類(lèi)旁通者，其實(shí)便是因?yàn)樗瞄L(zhǎng)去理解解法背后的更具一般性的東西。所以我還有一個(gè)習(xí)慣，就是看到美妙的證明和解法總是會(huì)去一遍又一遍的去反復(fù)揣摩，試圖理解想出這個(gè)證明的人到底是怎么想出來(lái)的，有沒(méi)有什么一般性的方法可循，很多時(shí)候，在這樣揣摩的過(guò)程中，你會(huì)理解到更深刻的東西，對(duì)問(wèn)題性質(zhì)更深刻的認(rèn)識(shí)，對(duì)解決問(wèn)題的思路更深刻的認(rèn)識(shí)，這些認(rèn)識(shí)不僅對(duì)于你理解當(dāng)前這個(gè)定理或問(wèn)題有極大的幫助，同時(shí)也有助于你解決以后會(huì)遇到的表面不同但本質(zhì)一樣的問(wèn)題。 與看定理必看證明類(lèi)似，看一個(gè)問(wèn)題的解法，必然要看解法所誕生的過(guò)程，背后是否隱藏著更具一般性的解決問(wèn)題的思路和原則。否則一個(gè)解法就只是一個(gè)問(wèn)題的解法，跟背口訣一樣。即便記住了也無(wú)法推廣，即便當(dāng)時(shí)記住了也容易遺忘。 舉個(gè)經(jīng)典的例子：每本算法書(shū)都會(huì)講動(dòng)態(tài)規(guī)劃，每本講動(dòng)態(tài)規(guī)劃的書(shū)都會(huì)講背包問(wèn)題，每次講背包問(wèn)題都會(huì)講可重復(fù)背包和01背包，我們就拿《Algorithms》這本還算不錯(cuò)的算法書(shū)對(duì)背包問(wèn)題的講解來(lái)說(shuō)吧，重復(fù)背包問(wèn)題的遞歸公式是這樣的： K(W) = max { K(W-Wi) + Vi : Wi <= W } 這個(gè)公式的理解倒是很簡(jiǎn)單：為了把問(wèn)題降階，我們?cè)谧罱K的最優(yōu)解里面去掉一個(gè)元素，對(duì)這個(gè)元素的可能性進(jìn)行討論，它必然是任何Vi之一（前提是Wi <= W，否則就裝不下），而在去掉這個(gè)元素之后，剩下的元素肯定構(gòu)成問(wèn)題 K(W-Wi) 的最優(yōu)解，于是遞歸關(guān)系出現(xiàn)了。 此外也可以這樣來(lái)理解：要拿一組最優(yōu)元素，那么總得開(kāi)始一個(gè)個(gè)拿吧，對(duì)第一個(gè)拿的元素進(jìn)行討論，而問(wèn)題的最優(yōu)解等于討論的各個(gè)分支的最優(yōu)解中的最優(yōu)者；如果拿掉Vi之后，剩下來(lái)要怎么拿才能最優(yōu)呢？這就是一個(gè) K(W-Wi) 的問(wèn)題了。 01背包問(wèn)題就大不一樣了——每個(gè)物品都只有一件，拿掉之后就不能再拿了。我們不妨看看重復(fù)背包問(wèn)題的解法是不是能用到01背包上呢？還是討論第一個(gè)拿的元素，設(shè)被拿掉的是第i個(gè)元素，問(wèn)題就歸結(jié)為把剩下的物品（注意，可拿的物品少了一件）最優(yōu)地裝入容量為 W-Wi 的包里，所以，問(wèn)題的參數(shù)便變成了兩個(gè)，一個(gè)是背包剩余容量 W-Wi，另一個(gè)是剩余可拿的物品集合 S\{i} （表示去掉i之后的子集），顯而易見(jiàn)第二個(gè)參數(shù)是物品集合的各種可能的子集，那么其可能性個(gè)數(shù)就是 2^n ，這就導(dǎo)致子問(wèn)題的個(gè)數(shù)是 2^n， 由于要依次計(jì)算每個(gè)子問(wèn)題，那么算法復(fù)雜度顯然也是 2^n ，是不可接受的。 那么，《Algorithms》上又是怎么來(lái)講解01背包問(wèn)題的解法的呢？以下是原文： Our earlier subproblems now become completely useless. We must therefore refine our concept of a subproblem to carry additional information about the items being used. We add a second parameter, 0 <= j <= n: K(W, j) = maximum value achievable using a knapsack of capacity w and items 1..j: The answer we seek is K(W, n). 首先作者說(shuō)了，之前重復(fù)背包問(wèn)題的解法在這里完全廢掉了，所以我們必須重新定義子問(wèn)題，并且子問(wèn)題的條件必須要包含目前拿剩下的物品。以上這些都還不錯(cuò)，關(guān)鍵是接下來(lái)就讓人吐血了。作者接著說(shuō)道，我們給子問(wèn)題加上一個(gè)新的參數(shù)j… 憑什么啊？ 還是讓我們回顧一下這樣一幅經(jīng)典的漫畫(huà)吧： “我們給子問(wèn)題加上一個(gè)參數(shù)j”，這就像你在看數(shù)學(xué)證明時(shí)看到無(wú)比邪惡的“我們考慮…“一樣，一看到這樣的句子，你就知道，這個(gè)問(wèn)題的證明遠(yuǎn)遠(yuǎn)不像看上去那么簡(jiǎn)單，之所以你一路看下去理解上全無(wú)困難，那完全是因?yàn)樽髡咧苯影炎钪匾囊粋�(gè)insight告訴你了，舉個(gè)很簡(jiǎn)單的例子，證明素?cái)?shù)無(wú)最大，誰(shuí)都會(huì)第一時(shí)間想到去反證：假設(shè)存在一個(gè)最大的素?cái)?shù)P，那么找到比P大的素?cái)?shù)就是證明中最關(guān)鍵的一步，怎么找的？一般書(shū)上是不會(huì)說(shuō)的，你會(huì)看到書(shū)上這樣說(shuō)：假設(shè)P是最大的素?cái)?shù)，那么我們考慮P’ = 小于等于P的所有素?cái)?shù)的乘積+1。那么P’一來(lái)顯然大于P，二來(lái)不能被小于它的所有素?cái)?shù)整除，那么P’就成了大于P的素?cái)?shù)。 如果你經(jīng)常注意反證法，你會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象，反證法里面經(jīng)常會(huì)有這樣一句“我們考慮”，而“我們考慮”后面幾乎肯定接著一個(gè)天外飛仙一般的insight。素?cái)?shù)無(wú)最大這個(gè)古老的證明里面的“我們考慮”尚算是比較有跡可循的（我們想要構(gòu)造一個(gè)更大的素?cái)?shù)，而素?cái)?shù)的等價(jià)定義就是“不能被小于它的所有素?cái)?shù)整除，為了達(dá)到這個(gè)目的，構(gòu)造的方法就較明顯了）。但是有非常非常多的證明，其中關(guān)鍵的一步就跟嗑藥磕出來(lái)做夢(mèng)做出來(lái)走路跌跟頭跌出來(lái)的一樣（不信去翻一翻《Proofs from THE Book》），讓你完全不知道他怎么想到的。 話說(shuō)回來(lái)，雖然有很多數(shù)學(xué)證明的關(guān)鍵步驟是很難逆向工程的（因?yàn)楹芏鄷r(shí)候想出那個(gè)關(guān)鍵步驟的本人其實(shí)也是嘗試了各種方法，撞了無(wú)數(shù)堵墻，在尋求證法的嘗試空間中作了N次回溯才“妙手偶得”，與其說(shuō)是妙手偶得，不如說(shuō)是絞盡腦汁），但并非全無(wú)章法可循，否則陶哲軒也不會(huì)寫(xiě)出《Solving Mathematical Problems》這樣的著作來(lái)，而求解問(wèn)題也就成了真正的Black Art了。 算法的解法則比精妙的數(shù)學(xué)證明稍加更容易逆向工程一點(diǎn)。只要你有耐心仔細(xì)地去琢磨算法的關(guān)鍵步驟和本質(zhì)，總能從中窺探到一些更general的思想和思路來(lái)。 此外，很多經(jīng)典問(wèn)題，算法書(shū)上的講法雖然時(shí)時(shí)令我們失望，但如果去網(wǎng)上一搜，則通常會(huì)發(fā)現(xiàn)更優(yōu)秀的解釋來(lái)。比如背包問(wèn)題就是如此。 簡(jiǎn)單地說(shuō)，如果你對(duì)于每個(gè)問(wèn)題都能真正弄清以下這幾個(gè)問(wèn)題的答案，那么可以肯定的是，你的理解，記憶，以及學(xué)習(xí)的效率都會(huì)得到質(zhì)的提高： 為什么這種解法是對(duì)的？ 為什么那種解法是錯(cuò)的？ 為什么這種解法不是最優(yōu)的？ 證明為什么沒(méi)有更優(yōu)的解法。 回到人民群眾喜聞樂(lè)見(jiàn)的經(jīng)典例子：背包問(wèn)題。為什么01背包問(wèn)題的正確（高效）算法是正確（高效）的。表面的解釋是，因?yàn)?1背包問(wèn)題的子問(wèn)題定義是 K(W, j)，其兩個(gè)維度相乘的可能性一共有nW種，也就是說(shuō)一共要計(jì)算nW個(gè)子問(wèn)題，而計(jì)算每個(gè)子問(wèn)題的復(fù)雜度是O(1)的。 但是如果僅僅滿足于這樣的解釋?zhuān)梢哉f(shuō)是隔靴搔癢，并沒(méi)有觸及到本質(zhì)。算法本質(zhì)上可以看做是在一個(gè)解空間當(dāng)中的搜索問(wèn)題，所以要分析一個(gè)算法的好壞，首先弄清它的解空間的結(jié)構(gòu)，然后分析它是怎么來(lái)探索這個(gè)解空間的。 弄清解空間的是第一步，例如排序算法，其解空間可以看做是所有可能的下標(biāo)排列組合，其中有且僅有一個(gè)排列是正確的排序排列（簡(jiǎn)單起見(jiàn)假設(shè)元素各不相同）。那么一個(gè)算法在探索這個(gè)解空間方面的行為就決定了它的效率高低，最簡(jiǎn)單的，如果一個(gè)算法每次只能檢查解空間中的一個(gè)點(diǎn)，那么這個(gè)算法的復(fù)雜度就是解空間的大小。對(duì)排序算法而言也就是n!。從這個(gè)角度來(lái)看，我們就會(huì)很容易的發(fā)現(xiàn)，所有基于比較的排序算法，其復(fù)雜度為什么是以O(shè)(nlogn)為下界的，因?yàn)橐淮伪容^操作最多有兩個(gè)結(jié)果，a>b或a<b，既然只有兩種結(jié)果，那么最多只能將解空間進(jìn)行2分，如果每次都能完美的2分，那么找到那個(gè)唯一點(diǎn)最終需要的步驟就是log(n!) = O(nlogn)。如此就不難理解什么基于比較的排序算法的復(fù)雜度最好不過(guò)如此了。 回到01背包問(wèn)題，01背包問(wèn)題的解空間其實(shí)也是類(lèi)似的。一次選取就是一個(gè)01數(shù)組，其中每個(gè)元素代表其所對(duì)應(yīng)的物品要不要選取。很顯然，這個(gè)解空間的大小是2^n。在01背包的算法里面，每當(dāng)我們解出K(W, j)（需要O(W)次計(jì)算）之后，解空間就會(huì)被折半（排除掉1/2的可能性），一共如此做n次，就能得到最終解。由于每次折半的代價(jià)是O(W)，便不難理解為什么算法復(fù)雜度是O(nW)了。 那么，為什么每次計(jì)算出K(W,j)就能使解空間折半呢？那就需要來(lái)看看這個(gè)算法是如何探索解空間的，算法探索解空間的方式在其遞歸公式里面： K(W, j) = max { K(W, j-1), K(W-Wj, j – 1) + Vj } 也就是說(shuō)，首先看你要不要選取第一個(gè)物品，有兩種可能性（兩個(gè)分支），每個(gè)分支都是一個(gè)更低階的子問(wèn)題，即在其中的任意一個(gè)分支下都要決定要不要選取第二個(gè)物品（又是兩個(gè)分支），如此下遞歸去，可以構(gòu)建出一棵有2^n方個(gè)葉子節(jié)點(diǎn)的樹(shù)，每條從根結(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑“01..101”就對(duì)應(yīng)一個(gè)解，其中每個(gè)分叉代表“選”或“不選”當(dāng)前的物品。 建立在對(duì)這個(gè)解空間的理解上，我們?cè)賮?lái)看為什么01背包問(wèn)題的正確解法能做到O(nW)。（首先你最好將這棵樹(shù)畫(huà)在紙上，其中每個(gè)節(jié)點(diǎn)都是一個(gè)子問(wèn)題K(W,j)，每條分叉都是0或1。）當(dāng)我們計(jì)算出所有的K(W, 1)（需要O(W)次操作）之后，我們?nèi)菀鬃⒁獾剑须x葉子節(jié)點(diǎn)的距離為1的內(nèi)部節(jié)點(diǎn)K(W, 2)到葉子節(jié)點(diǎn)的兩個(gè)分支都必然只能取其一了，也就是說(shuō)，有一半的葉子節(jié)點(diǎn)被排除掉了（對(duì)解空間折半）。當(dāng)我們進(jìn)而計(jì)算出K(W,2)之后，同樣的道理，我們?nèi)菀卓吹剑饺~子節(jié)點(diǎn)距離為2的內(nèi)部節(jié)點(diǎn)的兩個(gè)分支也只能取其一了，這就進(jìn)而再次將解空間折半。由于每次折半需要O(W)的復(fù)雜度，所以就不難理解算法的總復(fù)雜度為O(nW)了。另一種理解的方法是，當(dāng)我們計(jì)算出K(W,j)的時(shí)候，從內(nèi)部節(jié)點(diǎn)K(W,j)到根節(jié)點(diǎn)的唯一路徑便確定了。經(jīng)過(guò)O(nW)次計(jì)算，從根節(jié)點(diǎn)到那個(gè)唯一解（葉子節(jié)點(diǎn)）的路徑便完全確定了。 知道怎么做是從正確（高效）解法得到的，而知道為什么必須得那樣做則往往是從錯(cuò)誤（低效）的解法當(dāng)中得到的。 然而遺憾的是，絕大多數(shù)算法書(shū)或教程都只顧一上來(lái)就告訴你正確的做法是什么，對(duì)于一些常見(jiàn)的錯(cuò)誤解法，或者常見(jiàn)的低效解法，卻根本不加分析。經(jīng)驗(yàn)告訴我們，理解錯(cuò)誤的做法為什么錯(cuò)誤同樣甚至更為重要，往往是在理解了錯(cuò)誤的解法為什么錯(cuò)誤之后，我們才能深刻的體會(huì)到為什么正確的解法是如此正確。 還是拿經(jīng)典的背包問(wèn)題來(lái)作例子，你幾乎看不到哪本書(shū)會(huì)告訴你一個(gè)典型的低效解法為什么低效的深刻原因。我們都知道動(dòng)態(tài)規(guī)劃的核心在于子問(wèn)題的劃分，同樣的問(wèn)題，不同的劃分辦法得到的復(fù)雜度完全不一樣。前面已經(jīng)提到了，重復(fù)背包問(wèn)題的思路在01背包問(wèn)題上會(huì)帶來(lái)指數(shù)級(jí)的復(fù)雜度，但是為什么呢？如果你滿足于說(shuō)：因?yàn)槿绻弥貜?fù)背包問(wèn)題的思路來(lái)解01背包問(wèn)題，那么子問(wèn)題定義的第二個(gè)維度（物品的子集）（見(jiàn)前文）是指數(shù)級(jí)的，那么要計(jì)算所有子問(wèn)題，當(dāng)然是指數(shù)級(jí)的。那么你只是看到這個(gè)問(wèn)題的表象。 如果從對(duì)解空間的探索方式來(lái)說(shuō)，可以容易看出這個(gè)現(xiàn)象的本質(zhì)，我們回顧一下01背包問(wèn)題的正確（高效）算法： K(W, j) = max { K(W, j-1), K(W-Wj, j – 1) + Vj } 這個(gè)算法討論的是兩種情況，“要”或者“不要”選取第j個(gè)物品，這兩種情況所對(duì)應(yīng)的解空間是完全不交的，這就有效地將解空間劃分為了不重復(fù)的兩個(gè)部分。 而再來(lái)看利用重復(fù)背包問(wèn)題思路的解法： K(W, S) = max { K(W-Wi, S\{i}) + Vi : Wi <= W } 這里討論的是首先拿掉哪一個(gè)物品，還是那句話，討論的每一個(gè)分支都對(duì)應(yīng)了算法對(duì)解空間的一個(gè)切分，我們?nèi)菀卓闯�，在“先拿物品i”和”先拿物品j“這兩個(gè)分支里面，存在大量的重復(fù)，因?yàn)橄饶梦锲穒再拿j，和先拿物品j再拿i對(duì)應(yīng)的是完全一樣的一組選取。事實(shí)上，如果你將這個(gè)遞歸公式畫(huà)成樹(shù)狀結(jié)構(gòu)，會(huì)發(fā)現(xiàn)有n!個(gè)葉子節(jié)點(diǎn)。n!是什么概念？01背包問(wèn)題的解空間大小本質(zhì)上就只有2^n次方，窮舉也不過(guò)O(2^n)的復(fù)雜度，結(jié)果這樣一切分卻變成了n!，可見(jiàn)這種對(duì)解空間的切分方法的冗余度是多么高了。你不妨看看，每一次計(jì)算K(W, S)子問(wèn)題能對(duì)解空間排查多少呢？是否能像前面正確的算法那樣，每次都能有效排查一半情況？理解了這一點(diǎn)之后，我們便注意到在劃分解空間，也就是定義子問(wèn)題的時(shí)候的一個(gè)原則，就是在建立遞歸公式的時(shí)候，盡量將解空間進(jìn)行不交的切分。同時(shí)我們便有了趁手的工具去分析一個(gè)動(dòng)態(tài)規(guī)劃的解法的效率。 最后再舉一個(gè)例子：算法書(shū)上幾乎必講的霍夫曼樹(shù)。你所看的算法書(shū)在講霍夫曼樹(shù)的時(shí)候給了證明嗎？講過(guò)霍夫曼樹(shù)的歷史八卦嗎？也許你看了霍夫曼樹(shù)的構(gòu)造方法之后覺(jué)得：“哦，這樣啊，顯然”。但是你可曾想到，在最優(yōu)編碼這個(gè)問(wèn)題上，連香農(nóng)本人之前給出的解法都只是suboptimal的，而且霍夫曼本人在得到這個(gè)算法之前也是絞盡腦汁幾近放棄。如果你10分鐘就“理解”了，那么百分之百只是背了課文而已。 |
2樓2015-05-08 03:01:13
|
知其所以然（三）：為什么算法這么難？ By 劉未鵬 – July 10, 2011Posted in: 算法 不知不覺(jué)《知其所以然》系列竟然也寫(xiě)到第三篇了，雖然前面兩篇也說(shuō)了不少，但是總覺(jué)得還有東西沒(méi)有說(shuō)“透”，或者說(shuō)沒(méi)有說(shuō)“好”。所以這篇試圖從不同的角度用更好的例子來(lái)繼續(xù)深入闡述。（感謝silwile對(duì)本文的review和意見(jiàn)） 廣大碼農(nóng)同學(xué)們大多都有個(gè)共識(shí)，認(rèn)為算法是個(gè)硬骨頭，很難啃，悲劇的是啃完了還未必有用——除了面試的時(shí)候。實(shí)際工程中一般都是用現(xiàn)成的模塊，一般只需了解算法的目的和時(shí)空復(fù)雜度即可。 不過(guò)話說(shuō)回來(lái)，面試的時(shí)候面算法，包括面項(xiàng)目中幾乎不大可能用到的算法，其實(shí)并不能說(shuō)是毫無(wú)道理的。算法往往是對(duì)學(xué)習(xí)和理解能力的一塊試金石，難的都能掌握，往往容易的事情不在話下。志于高者得于中。反之則不成立。另一方面，雖說(shuō)教科書(shū)算法大多數(shù)都是那些即便用到也是直接拿模塊用的，但不幸的是，我們這群搬磚頭的有時(shí)候還非得做些發(fā)明家的事情：要么是得把算法當(dāng)白盒加以改進(jìn)以滿足手頭的特定需求；要么干脆就是要發(fā)明輪子。所以，雖說(shuō)面試的算法本身未必用得到，但熟悉各種算法的人通常更可能熟悉算法的思想，從而更可能具備這里說(shuō)的兩種能力。 那么，為什么說(shuō)算法很難呢？這個(gè)問(wèn)題只有兩種可能的原因： 算法本身就很難。也就是說(shuō)，算法這個(gè)東西對(duì)于人類(lèi)的大腦來(lái)說(shuō)本身就是個(gè)困難的事兒。 講得太爛。 下面會(huì)說(shuō)明，算法之所以被絕大多數(shù)人認(rèn)為很難，以上兩個(gè)原因兼具。 我們說(shuō)算法難的時(shí)候，有兩種情況：一種是學(xué)算法難。第二種是設(shè)計(jì)算法難。對(duì)于前者，大多數(shù)人（至少我當(dāng)年如此）學(xué)習(xí)算法幾乎是在背算法，就跟背菜譜似的（“Cookbook”是深受廣大碼農(nóng)喜愛(ài)的一類(lèi)書(shū)），然而算法和菜譜的區(qū)別在于，算法包含的細(xì)節(jié)復(fù)雜度是菜譜的無(wú)數(shù)倍，算法的問(wèn)題描述千變?nèi)f化，邏輯過(guò)程百轉(zhuǎn)千回，往往看得人愁腸百結(jié)，而相較之下任何菜譜涉及到的基本元素也就那么些（所以程序員肯定都具有成為好廚師的潛力  ）注意，即便你看了算法的證明，某種程度上還是“背”（為什么這么說(shuō)，后面會(huì)詳述）。我自己遇到新算法基本是會(huì)看證明的，但是發(fā)現(xiàn)沒(méi)多久還是會(huì)忘掉，這是死記硬背的標(biāo)準(zhǔn)癥狀。如果你也啃過(guò)算法書(shū)，我相信很大可能性你會(huì)有同感：為什么當(dāng)時(shí)明明懂了，但沒(méi)多久就忘掉了呢？為什么當(dāng)時(shí)明明非常理解其證明，但沒(méi)過(guò)多久想要自己去證明時(shí)卻發(fā)現(xiàn)怎么都沒(méi)法補(bǔ)上證明中缺失的一環(huán)呢？初中學(xué)習(xí)幾何證明的時(shí)候，你會(huì)不會(huì)傻到去背一個(gè)定理的證明？不會(huì)。你只會(huì)背結(jié)論。為什么？一方面，因?yàn)樽C明過(guò)程包含大量的細(xì)節(jié)。另一方面，證明的過(guò)程環(huán)環(huán)相扣，往往只需要注意其中關(guān)鍵的一兩步，便能夠自行推導(dǎo)出來(lái)。算法邏輯描述就好比定理，算法的證明的過(guò)程就好比定理的證明過(guò)程。但不幸的是，與數(shù)學(xué)里面大量簡(jiǎn)潔的基本結(jié)論不同，算法這個(gè)“結(jié)論”可不是那么好背的，許多時(shí)候，算法本身的邏輯就幾乎包含了與其證明過(guò)程等同的信息量，甚至算法邏輯本身就是證明過(guò)程（隨便翻開(kāi)一本經(jīng)典的算法書(shū)，看幾個(gè)經(jīng)典的教科書(shū)算法，你會(huì)發(fā)現(xiàn)算法邏輯和算法證明的聯(lián)系有多緊密）。于是我們又回到剛才那個(gè)問(wèn)題：你會(huì)去背數(shù)學(xué)證明么？既然沒(méi)人會(huì)傻到去背整個(gè)證明，又為什么要生硬地去背算法呢？ 那么，不背就不背，去理解算法的證明如何？理解了算法的證明過(guò)程，便更有可能記住算法的邏輯細(xì)節(jié)，理解記憶嘛。然而，仍然不幸的是，絕大多數(shù)算法書(shū)在這方面做的實(shí)在糟糕，證明倒是給全了，邏輯也倒是挺嚴(yán)謹(jǐn)?shù)�，可是似乎沒(méi)有作者能真正還原算法發(fā)明者本身如何得到算法以及算法證明的思維過(guò)程，按理說(shuō)，證明的過(guò)程應(yīng)該反映了這個(gè)思維過(guò)程，但是在下文關(guān)于霍夫曼編碼的例子中你會(huì)看到，其實(shí)飽受贊譽(yù)的CLRS和《Algorithms》不僅沒(méi)能還原這個(gè)過(guò)程，反而掩蓋了這個(gè)過(guò)程。 必須說(shuō)明的是，沒(méi)有哪位作者是故意這樣做的，但任何人在講解一個(gè)自己已經(jīng)理解了的東西的時(shí)候，往往會(huì)無(wú)意識(shí)地對(duì)自己的講解進(jìn)行“線性化”，例如證明題，如果你回憶一下高中做平面幾何證明題的經(jīng)歷，就會(huì)意識(shí)到，其實(shí)證明的過(guò)程是一個(gè)充滿了試錯(cuò)，聯(lián)想，反推，特例，修改問(wèn)題條件，窮舉等等一干“非線性”思維的，混亂不堪的過(guò)程，而并不像寫(xiě)在課本上那樣——引理1，引理2，定理1，定理2，一口氣直到最終結(jié)論。這樣的證明過(guò)程也許容易理解，但絕對(duì)不容易記憶。過(guò)幾天你就會(huì)忘記其中一個(gè)或幾個(gè)引理，其中的一步或幾步關(guān)鍵的手法，然后當(dāng)你想要回過(guò)頭來(lái)自己試著去證明的時(shí)候，就會(huì)發(fā)現(xiàn)卡在某個(gè)關(guān)鍵的地方，為什么會(huì)這樣？因?yàn)樽C明當(dāng)中并沒(méi)有告訴你為什么作者當(dāng)時(shí)會(huì)想到證明算法需要那么一個(gè)引理或手法，所以，雖說(shuō)看完證明之后，對(duì)算法這個(gè)結(jié)論而言你是知其所以然了，但對(duì)于算法的證明過(guò)程你卻還沒(méi)知其所以然。在我們大腦的記憶系統(tǒng)當(dāng)中，新的知識(shí)必須要和既有的知識(shí)建立聯(lián)系，才容易被回憶起來(lái)（《如何有效地學(xué)習(xí)與記憶》），聯(lián)系越多，越容易回憶，而一個(gè)天外飛仙似地引理，和我們既有的知識(shí)沒(méi)有半毛錢(qián)聯(lián)系，沒(méi)娘的孩子沒(méi)人疼，自然容易被遺忘。（為什么還原思維過(guò)程如此困難呢？我曾經(jīng)在知其所以然（一）里詳述） 正因?yàn)榻^大多數(shù)算法書(shū)上悲劇的算法證明過(guò)程，很多人發(fā)現(xiàn)證明本身也不好記，于是寧可選擇直接記結(jié)論。當(dāng)年我在數(shù)學(xué)系，考試會(huì)考證明過(guò)程，但似乎計(jì)算機(jī)系的考試考算法證明過(guò)程就是荒謬的？作為“工程”性質(zhì)的程序設(shè)計(jì)，似乎更注重使用和結(jié)果。但是如果是你需要在項(xiàng)目中自己設(shè)計(jì)一個(gè)算法呢？這種時(shí)候最起碼需要做的就是證明算法的正確性吧。我們面試的時(shí)候往往都會(huì)遇到一些算法設(shè)計(jì)問(wèn)題，我總是會(huì)讓?xiě)?yīng)聘者去證明算法的正確性，因?yàn)榧幢闶且粋�(gè)“看上去”正確的算法，真正需要證明起來(lái)往往發(fā)現(xiàn)并不是那么容易。 所以說(shuō)，絕大多數(shù)算法書(shū)在作為培養(yǎng)算法設(shè)計(jì)者的角度來(lái)說(shuō)是失敗的，比數(shù)學(xué)教育更失敗。大多數(shù)人學(xué)完了初中平面幾何都會(huì)做證明題（數(shù)學(xué)書(shū)不會(huì)要求你記住幾何所有的定理），但很多人看完了一本算法書(shū)還是一團(tuán)漿糊，不會(huì)證明一些起碼的算法，我們背了一坨又一坨結(jié)論，非但這些結(jié)論許多根本用不上，就連用上的那些也不會(huì)證明。為什么會(huì)出現(xiàn)這樣的差異？因?yàn)閿?shù)學(xué)教育的理想目的是為了讓你成為能夠發(fā)現(xiàn)新定理的科學(xué)家，而碼農(nóng)系的算法教育的目的卻更現(xiàn)實(shí)，是為了讓你成為能夠使用算法做事情的工程師。然而，事情真的如此簡(jiǎn)單么？如果真是這樣的話干脆連算法結(jié)論都不要背了，只要知道算法做的是什么事情，時(shí)空復(fù)雜度各是多少即可。 如果說(shuō)以上提到的算法難度（講解和記憶的難度）屬于Accidental Complexity的話，算法的另一個(gè)難處便是Essential Complexity了：算法設(shè)計(jì)。還是拿數(shù)學(xué)證明來(lái)類(lèi)比（如果你看過(guò)《Introduction to Algorithms：A Creative Approach》就知道算法和數(shù)學(xué)證明是多么類(lèi)似。），與單單只需證明相比，設(shè)計(jì)算法的難處在于，定理和證明都需要你去探索，尤其是前者——你需要去自行發(fā)現(xiàn)關(guān)鍵的那（幾）個(gè)定理，跟證明已知結(jié)論相比（已經(jīng)確定知道結(jié)論是正確的了，你只需要用邏輯來(lái)連接結(jié)論和條件），這件事情的復(fù)雜度往往又難上一個(gè)數(shù)量級(jí)。 一個(gè)有趣的事實(shí)是，算法的探索過(guò)程往往蘊(yùn)含算法的證明過(guò)程，理想的算法書(shū)應(yīng)該通過(guò)還原算法的探索過(guò)程，從而讓讀者不僅能夠自行推導(dǎo)出證明過(guò)程，同時(shí)還能夠具備探索新算法的能力。之所以這么說(shuō)，皆因?yàn)槲沂莻�(gè)懶人，懶人總夢(mèng)想學(xué)點(diǎn)東西能夠?qū)崿F(xiàn)以下兩個(gè)目的： 一勞永逸：程序員都知道“一次編寫(xiě)到處運(yùn)行”的好處，多省事啊。學(xué)了就忘，忘了又得學(xué)，翻來(lái)覆去浪費(fèi)生命。為什么不能看了一遍就再也不會(huì)忘掉呢？到底是教的不好，還是學(xué)得不好？ 事半功倍：事實(shí)上，程序員不僅講究一次編寫(xiě)到處運(yùn)行，更講究“一次編寫(xiě)到處使用”（也就是俗稱(chēng)的“復(fù)用”）。如果學(xué)一個(gè)算法所得到的經(jīng)驗(yàn)可以到處使用，學(xué)一當(dāng)十，推而廣之，時(shí)間的利用效率便會(huì)大大提高。究竟怎樣學(xué)習(xí)，才能夠使得經(jīng)驗(yàn)的外推（extrapolate）效率達(dá)到最大呢？ 想要做到這兩點(diǎn)就必須盡量從知識(shí)樹(shù)的“根節(jié)點(diǎn)”入手，雖然這是一個(gè)美夢(mèng)，例如數(shù)學(xué)界尋找“根節(jié)點(diǎn)”的美夢(mèng)由來(lái)已久（《跟波利亞學(xué)解題》的“一點(diǎn)歷史”小節(jié)），但哥德?tīng)栆粋�(gè)證明就讓美夢(mèng)成了泡影（《永恒的金色對(duì)角線》））；但是，這并不阻止我們?nèi)ふ腋邔拥墓?jié)點(diǎn)——更具普適性的解題原則和方法。所以，理想的算法書(shū)或者算法講解應(yīng)該是從最具一般性的思維法則開(kāi)始，順理成章地推導(dǎo)出算法，這個(gè)過(guò)程應(yīng)該盡量還原一個(gè)”普通人“思考的過(guò)程，而不是讓人看了之后覺(jué)得”這怎么可能想到呢？ 以本文上篇提到的霍夫曼編碼為例，第一遍看霍夫曼編碼的時(shí)候是在本科，只看了算法描述，覺(jué)得挺直觀的，過(guò)了兩年，忘了，因?yàn)椴恢罏槭裁匆褍蓚�(gè)節(jié)點(diǎn)的頻率加在一起看做單個(gè)節(jié)點(diǎn)——一件事情不知道“為什么”就會(huì)記不牢，知道了“為什么”的話便給這件事情提供了必然性。不知道“為什么”這件事情便可此可彼，我們的大腦對(duì)于可此可彼的事情經(jīng)常會(huì)弄混，它更容易記住有理有據(jù)的事情（從信息論的角度來(lái)說(shuō)，一件必然的事情概率為1，信息量為0，而一件可此可彼的事情信息量則是大于0的）。第二遍看是在工作之后，終于知道要看證明了，拿出著名的《Algorithms》來(lái)看，邊看邊點(diǎn)頭，覺(jué)得講得真好，一看就理解了為什么要那樣來(lái)構(gòu)造最優(yōu)編碼樹(shù)�？墒菦](méi)多久，又給忘了！這次忘了倒不是忘了要把兩個(gè)節(jié)點(diǎn)的頻率加起來(lái)算一個(gè)，而是忘了為什么要這么做，因?yàn)楫?dāng)時(shí)沒(méi)有弄清霍夫曼為什么能夠想到為什么應(yīng)該那樣來(lái)構(gòu)造最優(yōu)編碼樹(shù)。結(jié)果只知其一不知其二。 必須說(shuō)明的是，如果只關(guān)心算法的結(jié)論（即算法邏輯），那么理解算法的證明就夠了，光背算法邏輯難記住，理解了證明會(huì)容易記憶得多。但如果也想不忘算法的證明，那么不僅要理解證明，還要理解證明背后的思維，也就是為什么背后的為什么。后者一般很難在書(shū)和資料上找到，唯有自己多加揣摩。為什么要費(fèi)這個(gè)神？只要不會(huì)忘記結(jié)論不就結(jié)了嗎？取決于你想做什么，如果你想真正弄清算法設(shè)計(jì)背后的思想，不去揣摩算法原作者是怎么想出來(lái)的是不行的。 回到霍夫曼編碼問(wèn)題，我們首先看一看《Algorithms》上是怎么講的： 首先它給出了一棵編碼樹(shù)的cost function： cost of tree = Σ freq(i) * depth(i) 這個(gè)cost function很直白，就是把編碼的定義復(fù)述了一遍。但是接下來(lái)就說(shuō)了： 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… 接著就按照這個(gè)思路把cost function轉(zhuǎn)換了一下： The cost of a tree is the sum of the frequencies of all leaves and internal nodes, except the root. 然后就開(kāi)始得出算法邏輯了： 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ù)人有兩種反應(yīng)： 覺(jué)得理所當(dāng)然。 覺(jué)得恍然大悟。 因?yàn)槲耶?dāng)時(shí)也是這么覺(jué)得的�？墒呛髞�(lái)當(dāng)我發(fā)現(xiàn)自己無(wú)法從頭證明一遍的時(shí)候，我知道肯定是理解的不夠深刻。如果理解的夠深刻，那么基本上是不會(huì)忘掉的。 如果看完霍夫曼編碼這樣一個(gè)簡(jiǎn)短證明你覺(jué)得順理成章，一切都挺顯然，那就壞了，即便是看上去最基本的性質(zhì)也往往實(shí)際上沒(méi)那么顯然�！胺晟介_(kāi)路，遇水架橋”在我們今天看來(lái)是無(wú)比顯然的事實(shí)，但是試想在沒(méi)有橋的遠(yuǎn)古時(shí)代，一個(gè)原始人走到一條湍急的河流前，他會(huì)怎么想，他又能有什么法子呢？這是個(gè)他從來(lái)沒(méi)有遇見(jiàn)過(guò)的問(wèn)題。如果后來(lái)有一天，他路過(guò)另外一條小溪，看到小溪上有一截被閃電劈斷的枯樹(shù)，于是他踏著樹(shù)干走過(guò)了小溪，并意識(shí)到“樹(shù)橫過(guò)河面”可以達(dá)到“過(guò)河”這個(gè)目的，這就將條件和目的建立了直接的聯(lián)系（事實(shí)上，是自然界展示了這個(gè)聯(lián)系，我們的原始人只是記住了這個(gè)聯(lián)系）。后來(lái)他又路過(guò)那條河流，他尋思如何達(dá)到“過(guò)河”這個(gè)目的的時(shí)候，忽然意識(shí)到在他的記憶中已經(jīng)遇到過(guò)需要達(dá)成同樣目的的時(shí)候了，那個(gè)時(shí)候的條件是“樹(shù)橫過(guò)河面”，于是問(wèn)題便歸結(jié)為如何滿足這個(gè)“樹(shù)橫過(guò)河面”的條件，而后一個(gè)問(wèn)題就簡(jiǎn)單多了。（事實(shí)上波利亞在他的著作《How to Solve it》中舉的正是這么個(gè)例子） 為什么那么多的算法書(shū)，就看不到有一本講得好的？因?yàn)槲覀兦蠼鈫?wèn)題過(guò)程中的思維步驟太容易被自己當(dāng)作“顯然”的了，但除了我們天生就會(huì)的認(rèn)知模式（聯(lián)系，類(lèi)比），沒(méi)有什么是應(yīng)該覺(jué)得顯然的，試錯(cuò)是我們天生就會(huì)的思維法則么？是的，但是可供嘗試的方案究竟又是怎么來(lái)的呢？就拿上面的例子來(lái)說(shuō)，一個(gè)從沒(méi)有見(jiàn)過(guò)枯樹(shù)干架在小溪上的原始人，怎么知道用樹(shù)架橋是一種可選的方案呢？俗話說(shuō)巧婦難為無(wú)米之炊啊。我們大腦的神經(jīng)系統(tǒng)會(huì)的是將目的和條件聯(lián)系起來(lái)，第一次原始人遇到小溪過(guò)不去，大腦中留下了一個(gè)未實(shí)現(xiàn)的目的，后來(lái)見(jiàn)到小溪上的樹(shù)干，忽然意識(shí)到樹(shù)干是實(shí)現(xiàn)這個(gè)目的的條件，兩者便聯(lián)系起來(lái)了，因此問(wèn)題就規(guī)約為如何架樹(shù)干了。 回到《Algorithms》中的證明上，這個(gè)看似簡(jiǎn)潔明了的證明其實(shí)有幾處非常不顯然的地方，甚至不嚴(yán)謹(jǐn)?shù)牡胤剑@些地方也正是你過(guò)段時(shí)間之后試圖自己證明的話會(huì)發(fā)現(xiàn)卡住的地方： 作者輕飄飄地就給出了cost function的另外一種關(guān)鍵的描述，而對(duì)于如何發(fā)現(xiàn)這種描述卻只是一語(yǔ)帶過(guò)："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“這其實(shí)就是我常常痛恨的“我們考慮…”，這里作者其實(shí)就是在說(shuō)”讓我們考慮下面這樣一種奇妙的轉(zhuǎn)換“，可是怎么來(lái)的卻不說(shuō)。但必須承認(rèn)，《Algorithms》的作者還是算厚道的，因?yàn)楹竺嫠稚晕⒔忉屃艘幌拢骸皌his is, after all, the number of times the internal node is visited during encoding or decoding…”這個(gè)解釋就有點(diǎn)讓人恍然大悟了，但是千萬(wàn)別忘了，這種恍然大悟是一種錯(cuò)覺(jué)，你還是沒(méi)明白為什么他會(huì)想到這一點(diǎn)。這就像是作者對(duì)你說(shuō)“仔細(xì)觀察問(wèn)題條件，我們?nèi)菀装l(fā)現(xiàn)這樣一種奇妙的性質(zhì)..”，怎么個(gè)“仔細(xì)”法？憑什么我自己“觀察”半天就是發(fā)現(xiàn)不了呢？霍夫曼本人難道也是死死盯著問(wèn)題“觀察”了一學(xué)期然后就“發(fā)現(xiàn)”了么？我們有理由相信霍夫曼肯定嘗試了各種各樣的方法，作出了各種各樣的努力，否則當(dāng)年Shannon都沒(méi)搞定的這個(gè)問(wèn)題花了他一學(xué)期，難道他在這個(gè)學(xué)期里面大腦就一片空白（或者所有的嘗試全都是完全不相干的徒勞），然后到學(xué)期末尾忽然“靈光一現(xiàn)”嗎？ 如果“仔細(xì)觀察”  ，我們會(huì)發(fā)現(xiàn)兩個(gè)cost function表達(dá)中frequency的概念有微妙的差異，在第一個(gè)cost function中，只有葉子節(jié)點(diǎn)有frequency，而這個(gè)frequency必須和葉子節(jié)點(diǎn)的深度相乘。而在第二個(gè)cost function中，內(nèi)部節(jié)點(diǎn)也具有了frequency，可是所有節(jié)點(diǎn)的“frequency”忽然全都不跟深度相乘了。frequency的不同含義令人困惑。作者提到：第一個(gè)cost function告訴我們頻率最低的兩個(gè)節(jié)點(diǎn)必然處于最優(yōu)編碼樹(shù)的底端，作為最低內(nèi)部節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)。這是一個(gè)不嚴(yán)謹(jǐn)?shù)恼f(shuō)法，從前文給出的條件和性質(zhì)，只能推導(dǎo)出編碼樹(shù)的最底層必然能找到頻率最低的兩個(gè)節(jié)點(diǎn)，但它們未必一定要是兄弟節(jié)點(diǎn)，如果樹(shù)的最底層不止能容納兩個(gè)節(jié)點(diǎn)的話它們就可以有不同的父節(jié)點(diǎn)。“我們不妨考慮”這樣一個(gè)例子：對(duì)A,B,C,D四個(gè)字母進(jìn)行編碼，假設(shè)它們的頻率分別是1， 1， 2， 2。這個(gè)時(shí)候我們可以構(gòu)造如下圖所示的兩棵樹(shù)，兩棵樹(shù)的cost都是12，都是最優(yōu)的。但其中一棵樹(shù)中，兩個(gè)頻率最低的節(jié)點(diǎn)并非兄弟。 tree2 為什么要提到上面這幾點(diǎn)不顯然和不嚴(yán)謹(jǐn)?shù)牡胤�，因�(yàn)橹灰?dāng)你看到算法書(shū)上出現(xiàn)不顯然和不嚴(yán)謹(jǐn)?shù)牡胤�，基本上就意味著作者其�?shí)跳過(guò)了關(guān)鍵的思維步驟。 不幸的是《Algorithms》這本書(shū)里面講霍夫曼編碼已經(jīng)算是講的好的了，如果你翻開(kāi)著名的CLRS，看一看當(dāng)中是怎么證明的，你就知道我說(shuō)的什么意思了。有時(shí)候這些證明是如此的企圖追求formal和嚴(yán)謹(jǐn)，一上來(lái)就定義符號(hào)一大摞，讓人看了就想吐。 說(shuō)了這么多，有沒(méi)有可能把霍夫曼編碼講的更好呢？前面說(shuō)過(guò)，霍夫曼編碼我記了又忘，忘了又記，好幾次了，有一次終于煩了，心想如果要自己去證明，會(huì)怎么去證，那個(gè)時(shí)候我已經(jīng)忘了《Algorithms》里面怎么講的了。所以我得從頭來(lái)起，首先，對(duì)于算法問(wèn)題，有一個(gè)一般性原則是，先看一看解空間的構(gòu)成。尤其是對(duì)于搜索問(wèn)題（最優(yōu)化問(wèn)題可以看做搜索問(wèn)題的一個(gè)特例），這一點(diǎn)尤其重要�；舴蚵幋a的可能的編碼樹(shù)是有窮的，如果窮舉所有的編碼樹(shù)，然后找到那棵代價(jià)最小的，這種方法至少是可行的，有了可行的方法（即便是窮舉）至少讓我們內(nèi)心感到踏實(shí)。 接下來(lái)便是提高搜尋效率的問(wèn)題。而提高搜尋效率的關(guān)鍵（同樣也是一個(gè)一般性原則），便是盡量去尋找問(wèn)題條件能夠推導(dǎo)出來(lái)的性質(zhì)，然后利用這些性質(zhì)去避免不必要的搜尋，只要你學(xué)過(guò)二分搜索就應(yīng)該理解這個(gè)一般性原則：二分搜索的效率之所以高于“窮搜”（O(n)），便是因?yàn)樗昧藛?wèn)題中的性質(zhì)（有序）來(lái)避免了不必要的搜尋。有時(shí)候這個(gè)性質(zhì)甚至可以直接將時(shí)間降為O(1)，例如在一個(gè)有序數(shù)組中尋找出現(xiàn)次數(shù)大于n/2的數(shù)（假設(shè)該數(shù)存在），利用“該數(shù)一定出現(xiàn)在數(shù)組正中間”這個(gè)性質(zhì)，我們直接就避免了所有的計(jì)算。 不過(guò)，話雖如此，有時(shí)候這些性質(zhì)并不是那么“顯然”的，需要對(duì)問(wèn)題進(jìn)行深入的折騰才能有可能發(fā)現(xiàn)。第三個(gè)一般原則：如果你要搜尋的元素是某個(gè)滿足特定條件的元素（例如尋找最優(yōu)解的時(shí)候，“最優(yōu)”的定義就是這個(gè)“特定條件”），那么可以“倒過(guò)來(lái)推”（數(shù)學(xué)證明常用手法，結(jié)論當(dāng)條件使），即假設(shè)你已經(jīng)找到了你要找的元素，那么能得出哪些結(jié)論，每一個(gè)結(jié)論都是最優(yōu)解的一個(gè)必要條件，而每一個(gè)必要條件都能夠幫助你避免不必要的搜尋，因?yàn)槟阒灰l(fā)現(xiàn)某個(gè)候選解不滿足某個(gè)必要條件，就可以立即將其丟棄，前面提到的尋找出現(xiàn)次數(shù)大于n/2的例子是一個(gè)極端情況，我們得出的必要條件導(dǎo)致我們可以直接丟棄除中點(diǎn)元素之外的一切其他元素，再例如如果有人叫你尋找有序數(shù)組中最小元素，你會(huì)毫不猶豫地把該數(shù)組頭尾元素中較小的那個(gè)給他，因?yàn)槟阒馈叭绻莻�(gè)最小元素存在，那么它必然位于頭尾”——這個(gè)必要條件直接允許你丟棄掉n-2個(gè)候選解。 回到霍夫曼編碼問(wèn)題，按照這個(gè)原則，我們會(huì)去假設(shè)已經(jīng)得到了最優(yōu)編碼樹(shù)，那么我們能夠發(fā)現(xiàn)關(guān)于它的什么性質(zhì)呢？這里又要提到另一個(gè)適用于很多最優(yōu)化問(wèn)題的原則（前面提到的原則適用于一般性搜索問(wèn)題），所謂最優(yōu)解，就是說(shuō)比其他所有解都要更好，雖然這句話聽(tīng)上去像是廢話，但是它的一個(gè)直接推論——比與它鄰近的所有候選解都要好——就是一個(gè)非常有用的，不是廢話的性質(zhì)了。學(xué)過(guò)微積分的都知道，光滑函數(shù)的最值點(diǎn)必然是大（�。┯谄溧徲騼�(nèi)的所有點(diǎn)的，然后再根據(jù)這個(gè)就自然推出該點(diǎn)的一階導(dǎo)數(shù)（切線斜率）必然為0的性質(zhì)，這個(gè)性質(zhì)（必要條件）讓我們直接省掉了去整個(gè)區(qū)間內(nèi)搜索的麻煩，從而可以直接鎖定有限幾個(gè)候選解。那么，既然我們說(shuō)最優(yōu)霍夫曼樹(shù)一定比它“附近”的樹(shù)更好，我們就想看看，怎么來(lái)找到它附近的樹(shù)。我們知道要從一個(gè)點(diǎn)到它附近，往往是對(duì)這個(gè)點(diǎn)進(jìn)行一些調(diào)整，例如N+1是到達(dá)附近的另一個(gè)整數(shù)�；舴蚵鼧�(shù)是一棵樹(shù)，所以對(duì)這棵樹(shù)的所有的一次“改動(dòng)”（或“折騰”）都能夠到達(dá)與它的“改動(dòng)”距離為1的點(diǎn)（是不是想起“編輯距離”這個(gè)概念），怎么改動(dòng)呢？最符合直覺(jué)的（雖然并不是唯一的）改動(dòng)便是把葉子節(jié)點(diǎn)進(jìn)行互換。 于是我們得到一個(gè)重要的推論： 在最優(yōu)霍夫曼樹(shù)中，無(wú)論互換哪兩個(gè)葉子節(jié)點(diǎn)，得到的樹(shù)都變得更“差”。（嚴(yán)格來(lái)說(shuō)是不會(huì)變得更“好”，因?yàn)樽顑?yōu)樹(shù)未必唯一） 這個(gè)性質(zhì)看上去有點(diǎn)像廢話，值得費(fèi)這么多事么？值得。因?yàn)殡m然前文說(shuō)了很多，但都是大多數(shù)人大腦里面既有的，一般性的法則，前面說(shuō)過(guò)，如果我們能夠從我們已經(jīng)掌握的一般法則出發(fā)來(lái)推導(dǎo)出問(wèn)題的解，那么記憶負(fù)擔(dān)是最小的，因?yàn)檫@里面用到的所有法則我們都很清楚，也知道怎么一步步往下走。 上面這個(gè)性質(zhì)究竟意味著什么呢？如果你假設(shè)這兩個(gè)葉子節(jié)點(diǎn)的頻率為f1和f2，深度為d1和d2，互換它們的時(shí)候，其他葉子節(jié)點(diǎn)的cost保持不變，令為常量C，那么互換前總cost為C+f1d1+f2d2，互換后為C+f1d2+f2d1，既然互換之后的樹(shù)一定更”差“那么就是說(shuō)f1d1+f2d2 < f1d2 + f2d1，簡(jiǎn)單變換一下就得到結(jié)論：f1(d1-d2)<f2(d1-d2)，也就是說(shuō)如果d1<d2，那么f1必然>f2，如果d1>d2，那么f1必然<f2。換言之就是葉子節(jié)點(diǎn)的深度越高，頻率必須越低，否則就不可能是最優(yōu)霍夫曼樹(shù)。那么，之前我們覺(jué)得不那么顯然的結(jié)論便呼之欲出了：頻率最低的葉子節(jié)點(diǎn)必然位于樹(shù)的最底層，頻率最高的葉子節(jié)點(diǎn)必然位于樹(shù)的最高層。 有了這個(gè)結(jié)論之后，我們便能夠?qū)ψ顑?yōu)霍夫曼樹(shù)的構(gòu)建走出確定性的一步，即，將頻率最低的兩個(gè)葉子節(jié)點(diǎn)放在最底層。別小看這一步，這一步已經(jīng)排除了大量的可能性。這里，我們?nèi)菀滓婚_(kāi)始天真地覺(jué)得最底層只有這兩個(gè)葉子節(jié)點(diǎn)，于是它們擁有共同父節(jié)點(diǎn)，這樣一來(lái)霍夫曼樹(shù)的整個(gè)拼圖便已經(jīng)拼好了一個(gè)小小的角落。 然后我們會(huì)發(fā)現(xiàn)，要是它們不是兄弟怎么辦呢？這里提到另一個(gè)一般原則——?dú)w約。不是兄弟的情況能否歸約為是兄弟的情況？反正我們要求的是一個(gè)最優(yōu)解，而不是所有的最優(yōu)解，我們只需證明，如果當(dāng)這兩個(gè)最低頻率的葉子不是兄弟的時(shí)候的確存在著某棵最優(yōu)霍夫曼樹(shù)，那么通過(guò)交換它們各自的兄弟，從而讓這兩個(gè)葉子團(tuán)聚之后，修改后的樹(shù)仍然是最優(yōu)的就可以了。事實(shí)情況也的確如此，證明非常直接——既然這里涉及到的所有4個(gè)節(jié)點(diǎn)都在最底層同一個(gè)高度上，那么互相交換的時(shí)候不會(huì)改變他們?nèi)魏我粋�(gè)人的深度值，所以總cost不會(huì)改變。 但是接下來(lái)我們犯了難，整個(gè)樹(shù)的一個(gè)小小的櫻桃狀的局部是確定下來(lái)了，接下來(lái)怎么辦呢？一個(gè)最自然的思路就是考慮第三小的葉子，因?yàn)榍懊嬲f(shuō)了，元素頻率越低就越位于樹(shù)的底部嘛。第三小的葉子有兩種可能的歸屬，一是跟最小的兩個(gè)葉子同樣位于最底層（這不會(huì)違反我們前面得到的推論），這個(gè)時(shí)候第三小的葉子的兄弟葉子肯定是第四小的葉子，如下圖： tree3 另一種歸屬就是往上一層去（注意，一旦第三小的葉子往上去了一層，那么剩下的所有葉子都必須至少在這個(gè)層以上），往上一層去了之后，它的兄弟是誰(shuí)呢？不妨將它和剛才第一第二葉子的父節(jié)點(diǎn)結(jié)為兄弟（前面證明過(guò)，同層之前節(jié)點(diǎn)互換不會(huì)改變編碼的cost），如下圖： tree5 可是現(xiàn)在問(wèn)題出現(xiàn)了：雖然第一步構(gòu)建（最小的兩個(gè)葉子）是確定的，但是到了第二步擺在我們面前的就有兩個(gè)選擇了，到底選擇哪個(gè)呢？一個(gè)辦法就是把兩種選擇都記下來(lái)，然后繼續(xù)往下走。可是別小看兩種選擇，接下去每一步都有兩種選擇的話就變成指數(shù)復(fù)雜度了。所以現(xiàn)在我們便有了動(dòng)機(jī)回頭看一看，看問(wèn)題中是否有什么沒(méi)有發(fā)現(xiàn)的性質(zhì)能夠幫助我們?cè)倥懦羝渲幸粋�(gè)選擇。理想情況下如果每一步都是必然的，確定的，那么N步我們就可以構(gòu)建出整棵樹(shù)，這是我們希望看到的，抱著這個(gè)良好的愿望，我們仔細(xì)觀察上面兩種構(gòu)型，一個(gè)自然而然的問(wèn)題是：這兩種構(gòu)型都有潛質(zhì)成為最優(yōu)解嗎？如果我們能夠證明其中一種構(gòu)型不能成為最優(yōu)解那該多好？就省事多了嘛。這里引入另一個(gè)一般性的解題法則：特例。我們的大腦喜歡具體的東西，在特例中折騰和觀察會(huì)方便的多。 上面這個(gè){1, 2, 3, 4}的例子就是個(gè)很好的特例，如圖（注：圖中節(jié)點(diǎn)旁的數(shù)字一概為頻率值，而非編號(hào)）： tree3 多加折騰一番也許我們不難發(fā)現(xiàn)，如果將1，2及其父節(jié)點(diǎn)跟葉子4進(jìn)行交換（注意：交換的時(shí)候1，2也被一同帶走了，因?yàn)榉凑?，2兩個(gè)節(jié)點(diǎn)已確定是好兄弟永遠(yuǎn)不會(huì)分家了，折騰的時(shí)候只能作為一個(gè)整體移動(dòng)，所以這里也可以說(shuō)是交換子樹(shù)），那么樹(shù)的編碼將會(huì)變得更優(yōu)，因?yàn)檫@樣一次交換會(huì)將1和2的深度+1，意味著整棵樹(shù)的代價(jià)+3，而同時(shí)會(huì)將葉子4的深度-1，也就是說(shuō)整棵樹(shù)的代價(jià)-4，總體上整棵樹(shù)的代價(jià)就是+3-4=-1（注意，在計(jì)算的時(shí)候我們只需考慮被交換的局部，因?yàn)闃?shù)的其他部分的代價(jià)保持不變）。如下圖： tree4 這個(gè)交換啟發(fā)了我們，其實(shí)前面一開(kāi)始說(shuō)的交換兩個(gè)葉子節(jié)點(diǎn)可以推廣為交換內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)，然后很快我們就會(huì)意識(shí)到其實(shí)可以推廣到交換任意兩個(gè)節(jié)點(diǎn)。（注意，當(dāng)我們說(shuō)交換內(nèi)部節(jié)點(diǎn)的時(shí)候，其實(shí)是連同該內(nèi)部節(jié)點(diǎn)作為局部根節(jié)點(diǎn)的整個(gè)子樹(shù)都交換過(guò)去）于是前面我們的推論就可以推廣為： 在最優(yōu)霍夫曼樹(shù)中，無(wú)論互換哪兩個(gè)節(jié)點(diǎn)，得到的樹(shù)都變得更“差”（交換內(nèi)部節(jié)點(diǎn)則是連同該內(nèi)部節(jié)點(diǎn)作為局部根的子樹(shù)一同帶走） 這個(gè)推論很容易理解，只不過(guò)是多增加了一種“編輯”最優(yōu)霍夫曼樹(shù)的方法罷了（記住最優(yōu)霍夫曼樹(shù)無(wú)論怎么“編輯”都不會(huì)變得更“好”，包括“交換子樹(shù)”這種“編輯”），我們前面沒(méi)有想到這種“編輯”方法是因?yàn)樗荒敲达@然，而且當(dāng)時(shí)我們已經(jīng)想到一種最直接的“編輯”方法了，即交換葉子，就容易順著那個(gè)思路一直走下去，直到我們發(fā)現(xiàn)必須尋找新的性質(zhì)，才回過(guò)頭來(lái)看看有沒(méi)有其他法子。 當(dāng)然，并不排除一開(kāi)始就想到這種推廣的可能性，問(wèn)題求解的過(guò)程并不是這么線性的，如果我們習(xí)慣了推而廣之的思維，也許一下就能想到這個(gè)推廣來(lái)。類(lèi)似的，也不排除從另一種思路出發(fā)想到這種推廣的可能性。所以這里只是可能的思維軌跡中的一種，重點(diǎn)在于其中并沒(méi)有某處忽然出現(xiàn)一個(gè)不知從哪里冒出來(lái)的，神啟一般的結(jié)論。 剛才提到，構(gòu)造最優(yōu)樹(shù)的第二步是考慮第三小的葉子，但也有另一種常見(jiàn)的思維：考慮到第一步（即選取頻率最小的兩個(gè)葉子）所做的事情是從N個(gè)葉子中選擇兩個(gè)黏在一起作為兄弟，那么也許對(duì)于一些人來(lái)說(shuō)自然而然的第二步就是試圖繼續(xù)選取兩個(gè)節(jié)點(diǎn)黏在一起作為兄弟（注意這里不僅可以選擇葉子，也可以選擇已經(jīng)生成的內(nèi)部節(jié)點(diǎn)），然后依次類(lèi)推來(lái)拼完整棵樹(shù)。按照這一思路，第二步的選項(xiàng)仍然還是集中在第三小的葉子上，因?yàn)檫@個(gè)選擇要么是讓第三第四小的葉子結(jié)拜為兄弟，要么是讓最小兩個(gè)葉子的父節(jié)點(diǎn)和第三小的葉子結(jié)拜。 回到剛才我們的推論：在最優(yōu)霍夫曼樹(shù)中，無(wú)論互換哪兩個(gè)節(jié)點(diǎn)，得到的樹(shù)都變得更“差”（交換內(nèi)部節(jié)點(diǎn)則是連同該內(nèi)部節(jié)點(diǎn)作為局部根的子樹(shù)一同帶走） 。根據(jù)這個(gè)推論我們?nèi)菀子?jì)算出，在最優(yōu)霍夫曼樹(shù)當(dāng)中，兩個(gè)內(nèi)部節(jié)點(diǎn)n1和n2，如果n1比n2更深，那么n1下面的所有葉子的頻率之和必然要小于n2下面所有葉子的頻率之和。如果交換的是一個(gè)內(nèi)部節(jié)點(diǎn)和一個(gè)葉子節(jié)點(diǎn)，則道理是類(lèi)似的。這個(gè)性質(zhì)的證明和上面的類(lèi)似，就不贅述了。 這個(gè)性質(zhì)暗示了一個(gè)重要的推廣結(jié)論：如果我們把每個(gè)內(nèi)部節(jié)點(diǎn)的所有葉子的頻率之和標(biāo)在它旁邊，那么整棵樹(shù)的每個(gè)節(jié)點(diǎn)便都有了一個(gè)數(shù)值，這個(gè)數(shù)值遵循統(tǒng)一的規(guī)律：即越往深層越小。這就意味著，我們剛才的二選一困境有辦法了！當(dāng)我們將最小的兩個(gè)葉子f1和f2合并的時(shí)候，生成了一個(gè)新的節(jié)點(diǎn)M，這個(gè)節(jié)點(diǎn)有一個(gè)數(shù)字（為兩個(gè)葉子的頻率之和f1+f2），根據(jù)上面的推論，這個(gè)數(shù)字f1+f2跟所有頻率一同，遵循最小的在最底層的原則，所以我們下一步必須在剩下的那些互相之間關(guān)系待確定的節(jié)點(diǎn)（葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)）之中，即{(f1 + f2), f3, f4}里面選擇最小的兩個(gè)數(shù)字結(jié)合成兄弟（由于f1和f2這兩個(gè)節(jié)點(diǎn)已經(jīng)鐵板釘釘結(jié)為整體了，所以從集合里面可以看做移除）。到這里，我們就發(fā)現(xiàn)遞歸已經(jīng)出現(xiàn)了，接下去的過(guò)程對(duì)于絕大多數(shù)人應(yīng)該就真的很顯然了。 以上的解釋?zhuān)取禔lgorithms》更簡(jiǎn)短嗎？顯然不是。反而要長(zhǎng)得多（其實(shí)真正的思維過(guò)程比這要更長(zhǎng)，因?yàn)橹虚g還會(huì)涉及各種不成功的嘗試）。但是它比《Algorithms》當(dāng)中的版本更不容易被忘記，因?yàn)槠渲嘘P(guān)鍵的思維拐點(diǎn)并不是毫無(wú)來(lái)由的，而是從你已經(jīng)熟知的，或者說(shuō)雖然不知道，但容易理解的一般性解題法則出發(fā)自然推導(dǎo)出來(lái)的，所以你基本上不需要記憶什么東西，因?yàn)槟阈枰浀囊呀?jīng)在你腦海中了。 在上面的證明過(guò)程中，還有一個(gè)不像看上去那么顯然的事情：在我們尋找最優(yōu)霍夫曼樹(shù)的時(shí)候，我們?cè)?jīng)試圖去比較假想的最優(yōu)樹(shù)和它的“臨近”的樹(shù)，從而去探索最優(yōu)樹(shù)的性質(zhì)。但是，究竟什么是臨近的樹(shù)？在前面的講解中，我們說(shuō)如果交換A和B這兩個(gè)葉子節(jié)點(diǎn)，便得到一顆不同的樹(shù)，可以看做和原樹(shù)的“編輯距離”為1的樹(shù)。但是，真的這么顯然么？難道除了交換葉子的位置，就沒(méi)有其他辦法去“折騰”這棵樹(shù)了？后來(lái)我們看到，可以交換子樹(shù)而不僅僅是葉子，而交換子樹(shù)讓我們得到了至關(guān)重要的推論。此外，如果不是交換，而是像AVL樹(shù)那樣“旋轉(zhuǎn)”呢？說(shuō)到底，二叉樹(shù)是一個(gè)離散的東西，并不像連續(xù)值那樣，天生就有“距離”這個(gè)概念，如果我們離散而孤立地去看待所有的樹(shù)，那么沒(méi)有什么臨近不臨近的，臨近本是一個(gè)距離的概念，除非我們定義樹(shù)和樹(shù)之間的距離函數(shù)，才能說(shuō)臨近與否，而距離函數(shù)怎么定義才是“顯然”的呢？ 還有，其實(shí)以上只是試圖給出最優(yōu)霍夫曼樹(shù)的證明的一個(gè)更自然的過(guò)程，而當(dāng)年霍夫曼面臨這個(gè)問(wèn)題的時(shí)候根本還沒(méi)有人想到要用二叉樹(shù)呢！更不要說(shuō)在二叉樹(shù)的前提之下進(jìn)行證明了。根據(jù)wikipedia的介紹，霍夫曼同學(xué)（當(dāng)年還在讀Ph.D，所以的確是“同學(xué)”，而這個(gè)問(wèn)題是坑爹的導(dǎo)師Robert M. Fano給他們作為大作業(yè)的，F(xiàn)ano自己和Shannon合作給出了一個(gè)suboptimal的編碼方案，為得不到optimal的方案而寢食難安，情急之下便死馬當(dāng)活馬醫(yī)扔給他的學(xué)生們了）當(dāng)年為這個(gè)問(wèn)題憔悴了一個(gè)學(xué)期，最后就快到deadline的時(shí)候“忽然”想到二叉樹(shù)這個(gè)等價(jià)模型，然后在這個(gè)模型下三下五除二就搞定了一篇流芳千古的論文，超越了其導(dǎo)師。 最后說(shuō)兩個(gè)有趣的現(xiàn)象：也許很多人會(huì)覺(jué)得，越是大師來(lái)寫(xiě)入門(mén)教科書(shū)越是好，其實(shí)很多時(shí)候并非如此，尤其是在算法設(shè)計(jì)和數(shù)學(xué)領(lǐng)域，往往越是在其中浸淫久了越是難寫(xiě)出貼近初學(xué)者的書(shū)，因?yàn)榇罅繉?duì)初學(xué)者來(lái)說(shuō)一點(diǎn)都不顯然的事情在他看來(lái)已經(jīng)是“不假思索”了，成了他的內(nèi)隱記憶，尤其是當(dāng)他想要和你解釋一個(gè)復(fù)雜的東西的時(shí)候你就會(huì)發(fā)現(xiàn)他會(huì)常常邏輯跳躍，滿嘴跑術(shù)語(yǔ)，根本沒(méi)有意識(shí)到別人對(duì)有些術(shù)語(yǔ)和隱含的邏輯根本沒(méi)有像他那樣的理解。 最適合將一個(gè)東西講給別人聽(tīng)的時(shí)候并不是等懂了很多年以后，而是剛剛弄懂的時(shí)候，這個(gè)時(shí)候從不懂到懂的差別記憶還非常鮮明，能夠清清楚楚地記得到底是哪些關(guān)鍵的地方是最折磨人的，也最能夠站在不懂者的角度來(lái)思考問(wèn)題。像波利亞這樣，成了大師還能夠站在不懂者角度去換位思考的，可以說(shuō)是鳳毛麟角。所以說(shuō)前Amazon CAO（首席算法官）的《Introduction to Algorithms: a Creative Approach》絕對(duì)是本罕見(jiàn)的好算法書(shū)） 知其所以然（一）里面曾經(jīng)提到，要弄清來(lái)龍去脈，最好去看看原始作者是怎么想的，可是正如上文所說(shuō)，即便是最初的發(fā)明者，在講述的時(shí)候也會(huì)有意無(wú)意地“線性化”，我就去查看了霍夫曼最初的論文，那叫一個(gè)費(fèi)解，不信你可以自己看看(PDF)。 可以歸約為搜索算法的問(wèn)題（非常多）一般來(lái)說(shuō)相對(duì)還是有一些頭緒的，因?yàn)樗阉骺臻g一般還比較容易界定，難點(diǎn)在于要從問(wèn)題的條件中推導(dǎo)出用于節(jié)省搜索的性質(zhì)。而策略設(shè)計(jì)問(wèn)題則完全是另一個(gè)世界，因?yàn)椴呗缘脑O(shè)計(jì)空間貌似是可列無(wú)窮的，常常讓人感覺(jué)無(wú)從下手，摸不著頭緒，許多讓人撓頭的智力問(wèn)題就有這個(gè)特點(diǎn)（例如著名的100個(gè)囚徒和1個(gè)燈泡的房間就讓很多人有這種感覺(jué)），策略設(shè)計(jì)問(wèn)題也有一些較通用的法則，以后再說(shuō)。 怎么才能在學(xué)算法的時(shí)候?qū)W到背后的東西呢？有以下幾點(diǎn)很重要： 不要覺(jué)得每個(gè)步驟都很顯然，每個(gè)nontrivial的算法背后都有一段艱辛的探索經(jīng)歷，覺(jué)得顯然的話必然是一種幻覺(jué)。Stay foolish，才能發(fā)現(xiàn)某些環(huán)節(jié)其實(shí)并不是那么顯然的。 檢驗(yàn)是否真正理解的最佳方法就是過(guò)一段時(shí)間之后，自己試著證明一次。如果真正理解了的話，你的證明便會(huì)比較順暢。如果當(dāng)時(shí)沒(méi)有真正理解，那么凡是那些你當(dāng)時(shí)覺(jué)得顯然但其實(shí)不顯然的地方，都會(huì)成為你證明里面缺失的環(huán)節(jié)。 對(duì)于一個(gè)算法，多尋找各種來(lái)源的資料，也許能夠找到一個(gè)講的比較深刻的。我在《數(shù)學(xué)之美番外篇：快排為什么那么快》和《知其所以然（一）》里面都舉到了這樣的例子。 多試著去抽象背后的一般性法則，即便后來(lái)發(fā)現(xiàn)抽象得是錯(cuò)的，也比不去抽象要好。抽象是推廣的基礎(chǔ)。只有抽象出更深層的法則，才能讓你事半功倍，觸類(lèi)旁通，否則一個(gè)蘿卜永遠(yuǎn)是一個(gè)坑。（注意，其實(shí)我們的下意識(shí)是會(huì)進(jìn)行一定程度的抽象的，例如前面提到的原始人的例子，小溪和小河（或者小溝）細(xì)節(jié)上是不同的，但本質(zhì)上是一樣的，我們的大腦會(huì)自動(dòng)進(jìn)行這種簡(jiǎn)單抽象，提出事物的共性。正因此，即便你不去有意識(shí)地總結(jié)一般規(guī)律，只要你看的足夠多，練的足夠多，必然就會(huì)越來(lái)越諳熟。） 最后留個(gè)問(wèn)題：雖然按照上文的方式來(lái)構(gòu)造霍夫曼樹(shù)一定能夠得到一個(gè)最優(yōu)樹(shù)，但是怎么證明一定能得到呢？乍一看這個(gè)問(wèn)題似乎很多余，因?yàn)樽C明很簡(jiǎn)單：我們拼裝整棵樹(shù)的每一步都沒(méi)得選，而且每一步都必然拼湊出最優(yōu)樹(shù)的一個(gè)小小局部，如果最終還沒(méi)有得到最優(yōu)樹(shù)的話，只能說(shuō)最優(yōu)樹(shù)是不存在的了，然而最優(yōu)樹(shù)是一定存在的，因?yàn)樗袠?shù)的集合是有窮的，有窮集必有最值，因此證畢。這個(gè)證明固然是沒(méi)問(wèn)題的，但它其實(shí)是一個(gè)間接證明，換句話說(shuō)，我們?cè)跇?gòu)建樹(shù)的過(guò)程中的邏輯是這樣的：“之所以我們選擇粘結(jié)n1和n2，是因?yàn)槠渌撤ū厝贿`反最優(yōu)樹(shù)的兩個(gè)性質(zhì)。所以我們別無(wú)選擇�！钡牵@并沒(méi)有說(shuō)，我們選擇了粘結(jié)n1和n2，一定就符合了最優(yōu)樹(shù)的性質(zhì)。（也就是說(shuō)“其他做法都是錯(cuò)”并不能推出“這種做法必然對(duì)”，這就像是你在一大堆豆子當(dāng)中尋找一個(gè)特殊的豆子，你拿起一個(gè)，看看不是，扔掉，又拿起一個(gè)，還不是，扔掉，排除到最后只剩一個(gè)豆子了，假設(shè)你又知道這個(gè)特殊的豆子必然存在，那么這個(gè)時(shí)候你根本不用看就知道這個(gè)豆子一定就是你要找的）那么，你能否直接證明，拼裝最優(yōu)樹(shù)的過(guò)程每一步都符合最優(yōu)樹(shù)的性質(zhì)呢？ P.S. [1] 《逃出你的肖申克》和《BetterExplained》是我喜歡的兩個(gè)系列，還會(huì)繼續(xù)寫(xiě)，我有很多問(wèn)題，也在Evernote里面記了不少零碎的思考和資料，但只有當(dāng)我覺(jué)得理解的足夠深入，系統(tǒng)，以及手頭有足夠的有意思和有說(shuō)服力的例子的時(shí)候，我才會(huì)把整條線串起來(lái)成文，所以這事慢慢來(lái)不著急，反正這個(gè)博客也不會(huì)關(guān)掉。 [2] 工作之后可用業(yè)余時(shí)間急劇減少，已經(jīng)陸續(xù)基本把GReader砍掉了，時(shí)間再往前推，砍掉郵件列表，再往前是Twitter，再往前是BBS�，F(xiàn)在基本就只剩郵件了。越來(lái)越發(fā)現(xiàn)當(dāng)時(shí)間有限的時(shí)候，看書(shū)比看網(wǎng)要有效得多，也不會(huì)那么信息焦慮，網(wǎng)絡(luò)上的那些消息當(dāng)中真正重要的會(huì)自己來(lái)找你，不用每天去刷屏。不過(guò)有個(gè)例外，我過(guò)一陣子就會(huì)去逛一下Amazon的個(gè)性化推薦項(xiàng)目。如果你已經(jīng)工作，苦于時(shí)間有限，我建議你這么做。最近看過(guò)的幾本值得好好推薦的書(shū)有：《Number Sense》，《Reading in the Brain》，《The Vision Revolution》，《The Tell-Tale Brain》，《Kluge》。 [3] 順便吐槽國(guó)內(nèi)出版社引進(jìn)Pop Science類(lèi)書(shū)籍的效率和質(zhì)量，就我觀察，臺(tái)灣引進(jìn)Pop Science類(lèi)書(shū)籍需要延遲兩年左右，大陸則從三四年到無(wú)限期不等（某種程度上，一個(gè)國(guó)家的出版方的認(rèn)識(shí)水平，決定了這個(gè)國(guó)家大眾的認(rèn)識(shí)水平。你去看下我在豆瓣的書(shū)單就知道有多少好書(shū)與國(guó)內(nèi)讀者失之交臂了），例如《Number Sense》這本好書(shū)，到現(xiàn)在還沒(méi)有引進(jìn)，99年出版的書(shū)啊�！禟luge》更是譯為《亂亂腦》這種坑爹的書(shū)名，封面搞得跟少兒讀物一樣�！禦eading in the Brain》引入的算較快的，但也延遲了一年半了，而且翻譯質(zhì)量也不是很上乘（算是不功不過(guò)吧），說(shuō)到這里要贊中信出版社，最近一年引入了很多給力的Pop Science暢銷(xiāo)書(shū)，眼光還算不錯(cuò)。最近在Amazon上搜一些好的發(fā)展心理學(xué)的書(shū)，通過(guò)Amazon的推薦引擎看到了《Pink Brain，Blue Brain》，這本受到因研究大腦記憶的分子機(jī)制而獲諾獎(jiǎng)的Eric Kandel盛贊的科普09年就出了，到現(xiàn)在國(guó)內(nèi)影子都見(jiàn)不著，還好在卓越上買(mǎi)到了原版。雖然基本還沒(méi)開(kāi)始看，但可以鄭重推薦給初為父母的同學(xué)們 |
3樓2015-05-08 03:01:55
dililafter
鐵桿木蟲(chóng) (著名寫(xiě)手)
- 應(yīng)助: 17 (小學(xué)生)
- 金幣: 11155.2
- 散金: 849
- 紅花: 8
- 帖子: 1819
- 在線: 998.9小時(shí)
- 蟲(chóng)號(hào): 1370273
- 注冊(cè): 2011-08-16
- 性別: GG
- 專(zhuān)業(yè): 無(wú)機(jī)非金屬類(lèi)光電信息與功
4樓2018-07-25 11:30:10
5樓2022-11-04 07:26:32
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 dameng 的主題更新
| 5 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 一志愿211，0703化學(xué)310分求調(diào)劑 +3 | 努力奮斗112 2026-03-15 | 3/150 |
|
|---|---|---|---|---|
|
[考研] 考研化學(xué)學(xué)碩調(diào)劑，一志愿985 +5 | 張vvvv 2026-03-15 | 7/350 |
|
|
|
[考研] 0703化學(xué)調(diào)劑 +11 | 妮妮ninicgb 2026-03-15 | 15/750 |
|
|
|
[考研] 297求調(diào)劑 +3 | 喜歡還是不甘心 2026-03-20 | 3/150 |
|
|
|
[考研] 生物學(xué)調(diào)劑 +3 | Surekei 2026-03-21 | 3/150 |
|
|
|
[考研] 一志愿深大，0703化學(xué)，總分302，求調(diào)劑 +4 | 七月-七七 2026-03-21 | 4/200 |
|
|
|
[考研] 297求調(diào)劑 +11 | 戲精丹丹丹 2026-03-17 | 12/600 |
|
|
|
[考研] 311求調(diào)劑 +3 | 勇敢的小吳 2026-03-20 | 3/150 |
|
|
|
[考研] 生物學(xué)一志愿985，分?jǐn)?shù)349求調(diào)劑 +3 | zxts12 2026-03-21 | 3/150 |
|
|
|
[考研] 一志愿 西北大學(xué) ，070300化學(xué)學(xué)碩，總分287，雙非一本，求調(diào)劑。 +3 | 晨昏線與星海 2026-03-18 | 3/150 |
|
|
|
[考研] 考研調(diào)劑求學(xué)校推薦 +3 | 伯樂(lè)29 2026-03-18 | 5/250 |
|
|
|
[考研] 一志愿蘇州大學(xué)材料求調(diào)劑，總分315（英一） +5 | sbdksD 2026-03-19 | 5/250 |
|
|
|
[考研] 329求調(diào)劑 +9 | 想上學(xué)吖吖 2026-03-19 | 9/450 |
|
|
|
[考研] A區(qū)線材料學(xué)調(diào)劑 +5 | 周周無(wú)極 2026-03-20 | 5/250 |
|
|
|
[考研]
 295復(fù)試調(diào)劑
+8
|
簡(jiǎn)木ChuFront 2026-03-19 | 8/400 |
|
|
|
[考研] 261求B區(qū)調(diào)劑，科研經(jīng)歷豐富 +3 | 牛奶很忙 2026-03-20 | 4/200 |
|
|
|
[考研] 材料工程專(zhuān)碩274一志愿211求調(diào)劑 +6 | 薛云鵬 2026-03-15 | 6/300 |
|
|
|
[論文投稿] 有沒(méi)有大佬發(fā)小論文能帶我個(gè)二作 +3 | 增銳漏人 2026-03-17 | 4/200 |
|
|
|
[考研] 070300化學(xué)學(xué)碩求調(diào)劑 +6 | 太想進(jìn)步了0608 2026-03-16 | 6/300 |
|
|
|
[考研] 327求調(diào)劑 +6 | 拾光任染 2026-03-15 | 11/550 |
|