|
TopLanguage上關于解題的討論已經進行了一段時候了，有很多收獲。我們的討論目的不是將題目解出來，而是在于反思解題過程中的一般性的，跨問題的思維法則。簡單的將題目解出來（或者解不出來看答案，然后“恍然大悟”），只能得到最少的東西，解出來固然能夠強化導致解出來的那個思維過程和方法，但缺少反思的話便不能抽取出一般性的東西供更多的問題所用。而解不出來，看答案然后“哦”的一聲更是等同于沒有收獲，因為“理解”和“運用”相差何止十萬八千里。每個人都有過這樣的經歷：一道題目苦思冥想不得要領，經某個人一指點其中的關鍵一步，頓時恍然大悟。——這是理解。但這個理解是因為別人已經將新的知識（那個關鍵的一步）放到你腦子里了，故而你才能理解。而要運用的話，則需要自己去想出那關鍵的一步。因此，去揣測和總結別人的思維是如何觸及那關鍵的一步，而你自己的思維又為什么觸及不到它，是很有意義的。我們很多時候會發現，一道題目，解不出來，最終在提示下面解出來之后，發現其中并沒有用到任何自己不知道的知識，那么不僅就要問，既然那個知識是在腦子里的，為什么我們當時愣是提取不出來呢？而為什么別人又能夠提取出來呢？我怎么才能像別人那樣也提取出相應的知識呢？實際上這涉及到關于記憶的最深刻的原理。（我個人對此有一點總結和猜測，但并不成熟。有興趣自己考察的建議參考以下幾本書：《追尋記憶的痕跡》，《找尋逝去的自我》，《Synaptic Self》，《Psychology of Problem Solving》）一般性的思維法則除了對于輔助聯想（起關鍵的知識）之外，另一個作用就是輔助演繹/歸納（助探），一開始學解題的時候，我們基本上是先讀懂題目條件，做可能的一些顯然的演繹。如果還沒推到答案的話，基本就只能愣在那里等著那個關鍵的步驟從腦子里冒出來了。而所謂的啟發式思維方法，就是在這個時候可以運用一些一般性的，所有題目都適用的探索手法，進一步去探索問題中蘊含的知識，從而增大成功解題的可能性。啟發式的思維方法有很多，從一般到特殊，最具一般性的，在波利亞的《How to Solve It》中已經基本全部都介紹了。一些更為特殊性的（譬如下文最后一個例子中關于分割搜索空間的法則），則需要自己在練習中總結，抽象，整理。
以下是兩篇發在討論組上的雜記（不是總有時間寫像《跟波利亞學解題》這樣的長文的:P）。
[一] 兩道經典算法題的幾種思維方法分析
題目各有各的不同，但背后的思維方式大抵都是一樣的。如何在每一道題目中總結出最多一般性的思維法則，就決定了練習的效率。
下面是非常經典，且廣為流傳的兩道題目，知道答案的也許會認為再分析這樣的題目沒有任何價值，但是題目的價值不在于新舊，而在于到底能從中總結出多少東西。這兩道題目的價值就在于，他們的求解過程中涉及到的思維法則都非常典型，而且并不是太難。
問題1描述：名人問題
一個名人就是指這樣一個人：所有其他人都認識他，并且他不認識任何其他人。現在有一個N個人的集合，以及他們之間的認識關系。求一個算法找出其中的名人（如果有的話）或者判斷出沒有名人（如果沒有的話）。
思維方法一：特例法。考慮兩個人。發現，如果A、B如果互相認識，或互相不認識，則他們都不可能是名人。如果其中之一認識另一個（不失一般性我們令A認識B），則A被淘汰。
思維方法二：倒推法。假設名人已經出現，考慮名人的定義，一個名人P是指滿足如下兩個條件的人：
任取一個人Q，Q認識P。
任取一個人Q，P不認識Q。 接著，出于對“哪些人不符合名人的標準從而可以在我們搜索解空間的時候直接淘汰掉呢？”這個問題的詢問。我們考察以上條件的反面。即“如果__則P不是名人”這個填空： 存在一個人Q，Q不認識P。
或 存在一個人Q，P認識Q。
根據這兩個條件，我們實際上就可以優化窮舉式的搜索，因為當比較兩個人P1和P2的關系的時候，我們發現利用上面兩個規則，其中最多只能有一個人具有“名人潛質”，因為根據以上規則，不管這兩人之間出現認識還是不認識關系，總有一個人要被刷掉。 思維方法三：聯想法。聯想的可能性有
這是一個涉及n的問題，嘗試用歸納法，即考慮其子問題。如何定義子問題？兩個明顯的辦法：1，二分為兩個n/2規模的子問題。一個名人必然是這兩個子問題里面的名人，所以問題歸約為求解兩個子問題，并在最后一個環節合并這兩個子問題的解。2，考慮n-1階的子問題。一個名人必然是n-1階子問題中的名人，問題被歸約為求解n-1階子問題，然后其結果——n-1階名人與最后一個人的關系進行比較。最后，不管采用兩種歸納法中的哪一個，最后一步優化都是一樣的，即將遞歸方案轉化為迭代方案。
這是一個涉及n的問題，直接聯想到遞歸算法，于是試圖去湊一個遞歸的程序，結果同上面的第2種方案一樣。 由于是在n個人中“爭”出一個名人，因此聯想到競賽，試著往傳統競賽算法上湊，即一個個的比并淘汰的方案，并因此發現內中的淘汰規則。 etc. （有人補充嗎？） 問題2描述：和最小連續子序列問題 有N個數，其中有正有負，求出其中和最小的連續子序列。（連續子序列就是a[i]~a[j]所有連續元素形成的序列，其中i，j任取）
思維方法一：倒推。假設最小和子序列已經找到，我們試著去盡量挖掘這個最小和子序列的性質，每個性質都有助于我們更“智能地”在解空間中進行搜索。我們不難發現，這個假想的最小和子序列的兩端元素必然是負的，否則我們可以削掉它們求得一個更小和的子序列。再進一步我們會發現，事實上這個最小和子序列從任意一段算起的一個前綴/后綴的和必然也是負的，否則我們也可以將其削掉來求得一個更小和的子序列。此外，與這個最小和子序列兩端緊鄰著的任意一段區間的和必然是正的，否則我們必然可以將其添加到我們假設的最小和序列上，以求得一個更小和的子序列。一旦挖掘出了以上三個被蘊含在結論中的條件，我們就可以更為智能地搜索解空間了。
思維方法二：這是一個涉及n的問題，試著考察其子問題。我們能將問題降到n-1階嗎？n階問題里面的最小和子序列與n-1階里面的最小和子序列有什么關聯嗎？如果n階問題里面的最小和子序列不含有最后一個元素，那么它肯定同樣也是n-1階問題中的最小和子序列。這種情況下我們就完全將問題降到了n-1階。但如果它包含最后一個元素，那么一個自然的問題就是，n-1階問題中的最小和子序列含在n階最小子序列切掉最后一個元素之后剩下的那個序列內嗎？如果是的話，這種情況下問題也可以歸約為n-1階，也就是說只有n-1階中的最小和序列才具有潛質成長為n階的最小和序列。然而，第二種情況下的答案卻是否定的（試著找一個反例）。所以看上去這條路行不通。一般來說，一條路行不通之后，首先要做的就是反省一下思路，看看到底什么地方出了什么問題，也許有可能修修補補之后就能夠得到正確答案——想一想，我們剛才是在試著將問題降到n-1階。那么，為什么一定要是n-1階呢？譬如二分法就是試圖將問題降到兩個n/2階子問題。為什么這里將問題降到n-1階是不奏效的？因為這樣的降階無法保證我們solve了n-1階的子問題之后能夠根據它的解來構造n階問題的解。再仔細看看我們的方法，我們也許會發現，問題實質上出在最小和子序列可能會從n-1階跨越到n階，換句話來說，問題的可能解會跨越兩個子問題，這樣的子問題分解得到的是不完全的子問題，我們除了需要solve兩個子問題之外，還需要考慮跨越這兩個子問題的潛在解，這可是個麻煩事兒。最好的子問題分解是只需要直接solve掉子問題就結了，舉個例子，我們熟悉的快速排序，快速排序將一個區間根據一個中軸元素分解為兩個區間之后，就將問題分解為了兩個子問題，然后就只需要solve這兩個子問題（將這兩個區間排序），就直接了結了。它的兩個子問題是完全分離的，我們不必擔心任何左區間內的元素和右區間內的元素會出現亂序的情況。那么，我們的這個問題，關鍵就在于應該也將它分解為兩個完全子問題，我們設想有某種手法，能夠將我們n個數分解為兩段，其中要想求全局的最小和子序列，我們只需要對這兩段分別求其中的最小和子序列，然后看看哪個小即可。我們無需考察跨越這兩個區間的子序列。這樣一來我們就可以非常省心的將問題一步步分解為完全的子問題了。然而，到底怎樣才能分解出這樣的兩個區段來呢？看看我們的未知數是什么。我們的未知數是要尋找這樣的切分。但我們現在很茫然，n-1后面切一刀不行，二分法也不行，到底怎么切呢？看來這樣盲目嘗試是不行的。試試倒推吧。我們假設這樣的切割已經出現了，它滿足“最小和序列肯定不會跨越其切割邊界”這個條件，即任取一個跨越其切割邊界的子序列，都必然不是最小和序列。那么要怎樣才能讓一個序列不是最小和序列呢？想想上面思維方法一里面推導出的結果，最小和序列的任意前綴后綴序列必然和為負；且兩端向外擴展的序列和必然為正。所以，要想讓一個序列和不是最小，我們只要讓情況不滿足這兩個條件即可。基于這個條件，細心耐心一點很快就會推導出這個切割所需滿足的性質了。
思維方法三：直接聯想到動態規劃。然后往動態規劃上硬套。硬套的過程中必然會受挫（看了下面的做法你就知道為什么不是簡單的動態規劃了），也許經過一定的試錯，會聯想到Introduction to Algorithms里面那個關于排課的問題，從而想到將區間按照結尾元素的不同來分類：（這個思路是網上抄來的，關鍵是“考慮以某個a[x]終止的所有子序列”這一步很是摸不著頭緒。有誰能夠提供這個做法背后的思維過程嗎？）
設f[x] 為以a[x] 終止且包含 a[x] 的最小序列的和，有：
f[1] = a[1]; f[x+1] = f[x] < 0 ? f[x] + a[x+1] : a[x+1] 那么最小子序列的和就是f[1] .. f[n] 中最小的一個。 Update: 鄧鋆在討論組里面提到一個很好的point：
關于動態規劃，我提醒部分習慣于看到動態規劃就以直接寫出函數為目標的同學們：部分動態規劃題目不適合直接將最終答案當作函數值來設計遞推函數，往往用一些中間的結果。比如我們要找整個解空間的最優解，但整個解空間的最優解不存在直接的遞推關系，那么可否考慮設計比如"以該位置結尾"的解空間，其最優解很大可能存在遞推關系。隨后將解空間綜合比較，可得到整體的最優解。（當然，在算法中，可以一邊求一邊解）用這種方法，在思考算法的時候，一定要確保你的遞推過程遍歷到了整個解空間。
顯然，如果我在之前腦子里就有以上的原則的話，應該是能想到根據區間結尾來劃分搜索空間的。但事后總結不代表就是事前真正發生的事情。對于這道題目，事后總結固然得到一條非常重要的原則（即上面這段），但難道最初解出題目的人由于還不知道這個原則，就沒法解出來嗎？雞和蛋的問題。顯然，最初想到這個法子的人也許使用了更一般的思維方法。而我們在知道了一道題目的答案之后，除了總結這道題目提供的領域知識性的原則之外，更重要的還要總結更一般層面上的，跨問題的，思維性質的法則。
[二] 抽象在類比聯想中的作用一例
《Psychology of Problem Solving》里面舉了一個例子，說明了對問題本質的抽象能夠增加后來遇到本質類似（但表面不類似）的題目的時候聯想到前一道題目的可能性。我在這里提到了這個例子，摘錄如下：
《Psychology of Problem Solving》的第11章舉了這樣一個例子：先讓被試（皆為大學生）閱讀一段軍事材料，這個材料是說一小撮軍隊如何通過同時從幾個不同方向小規模攻擊來擊潰一個防守嚴實的軍事堡壘的。事實上這個例子的本質是對一個點的同時的弱攻擊能夠集聚成強大的力量。然后被試被要求解決一個問題：一個醫生想要用X射線殺死一個惡性腫瘤，這個腫瘤只可以通過高強度的X射線殺死，然而那樣的話就會傷及周圍的良好組織。醫生應該怎么辦呢？在沒有給出先前的軍隊的例子的被試中只有10%想到答案，這是控制基線。然后，在先前學習了軍隊例子的被試中，這個比例也僅僅只增加到30%，也就是說只有額外20%的人"自動"地將知識進行了轉移。最后一組是在提醒之下做的，達到了75%，即比"自動"轉移組增加了45%之多。這個例子說明，知識的表象細節會迷惑我們的眼睛，阻礙我們對知識的運用，在這個例子中是阻礙問題之間的類比。
不過這個例子稍微有點人為的味道。下面則是一個更為“現實”的例子：
問題：求N個數中最大的K個數。
分析：首先很多人都能夠聯想到一個類似的問題：求N個數中的最大數。不過，關于后者的表面知識（譬如算法的詳細過程和細節）是不能直接借用的。這很大程度上會阻止利用既有問題的解來解決新的問題。對算法的非本質（表面）細節了解的越多越細，就越是可能妨礙類比聯想。
然而，如果在當時吸收第一道題目的知識的時候就進行了抽象，提取出了其中的本質：只要有一個數小于任何另一個數，它就肯定不是最大的了，從而可以淘汰。就不難將其運用到就求最大K數上：只要有一個數小于任何K個數，它就肯定不屬于最大K個數之列了，從而可以淘汰。這里的抽象元素有兩個，分別是："淘汰法"，以及"一個淘汰的準則"。（抽象越是含糊越好（只要不過于含糊），因為基本上，越含糊的抽象，越是接近本質，聯想空間也越大。也許這里可以套用愛因斯坦的一句話：抽象應該盡量含糊，只要不過于含糊。）
（當然，這個題目還有其它思考方法。譬如運用上文提到的倒推法，我們假設一個屬于最大K數的數已經找到，令為X，我們來考察它具有什么性質：至多有K-1個數大于它。將這個性質“反”一下，我們便得到一條能更為智能搜索解空間的性質：只要出現任何K個數大于X，X即可被淘汰出搜索空間。此外還可以從“N”這個變量聯想到分治（基本上凡是涉及到N的問題都可以考慮分治——動態規劃和貪婪等方法是分治的特例），即考慮問題的子問題：N-1個數中的最大K個數是怎樣的？與全局最大K數有什么關系？除了分解為N-1階子問題，還有其他分解方法嗎？N/2？或者根據某種規則進行劃分？等等。）
這樣的例子還有很多。（注：這道題目被收錄在《編程之美》中）
[三] 啟發法的局限性
（注：不太清楚什么是啟發法的，歡迎參考波利亞的《How to Solve It》或wikipedia（搜索heuristics），以及這篇。）
首先肯定的是，啟發法一定（也許很大）程度上是可以代償知識的不足的（這里的知識主要是指大腦中的“聯系”，下面還會提到另一種知識，即hard knowledge）。譬如，一道題目，別人直接就能通過類比聯想到某道解過的題目，并直接使用了其中的一個關鍵的性質把題目給解出來了。你并沒有做過那道題目，這導致兩種可能的結果：一，你就是不知道那個性質。二，你雖然“知道”那個性質，但并沒有在以前的解題經歷中將那個性質跟你手頭的這個問題中的“線索”聯系起來，所以你還是“想不到”。后一種可以稱為soft knowledge，即你“知道”，但就是聯想（聯系）不起來。所謂不能活學活用，某些時候就是這種情況，即書本上提供什么樣的知識聯系，腦子里也記住什么，而沒有事后更廣泛地去探索知識之間的本質聯系（總結的作用）。前一種則可以稱為hard knowledge，即你就是不知道，它不在你的腦子里。
而啟發式方法在兩個層面上起作用：
輔助聯想起soft knowledge：譬如，特例法是一種啟發式思考方法，它通過引入一個簡單的特例，特例中往往蘊含有更多的“線索”，通過這些線索，有可能就會激發起對既有的知識的聯想。另外一種強大的輔助聯想辦法就是對題目進行變形，變形之后就產生了新的視覺和語意線索，比如式子的對稱性、從直角坐標到極坐標從而引發對后者的知識的聯想等等。大量的啟發式方法實際上的作用就是輔助聯想，通過對題目中的線索的發掘，激起大腦中已知相關知識的浮現。在這個意義上，相對于那些能夠直接聯想到某個性質的人，那些不知道但可以通過啟發式思維聯想到的，啟發式思維就提供了一種“曲徑通幽”的策略性聯想。還是以經典的例子來說：磚頭的用途。有人立即能夠直接聯想到“敲人”。有人也許不能。然而啟發式聯想策略“抽象”就能夠幫助后者也能夠聯想到“敲人”，因為“抽象”策略啟發人去考慮磚頭的各個性質維度，如“質地”，“形狀”，當你考察到“質地堅硬”，“棱角”，離“敲人”的功能還會遠么？本質上，能夠直接聯想到“敲人”功能的人是因為大腦中從磚頭到敲人這兩個概念之間的神經通路被走過了很多遍（譬如由于經常拿磚頭敲人），神經元之間的聯系相當“粗”（形象的說法，嚴格的事實請參考《追尋記憶的痕跡》），而不經常拿磚頭敲人的人呢，這個聯系就非常的弱，乃至于根本激不起一次神經沖動。那么為什么通過啟發式方法又能聯想到呢？因為啟發式方法相當于帶入了一種新的神經調控回路，首先它增加你聯系到磚頭的屬性維度上的可能性，使得“質地堅硬”、“棱角”這兩個語意概念被激活起來（注意，如果沒有啟發式方法的參與，這是不會發生的），一旦后者被激活起來，從后者到“敲人”的聯系就被激活起來了。從本質上，解題中的啟發聯想方法做的也就是這個工作。而越是一般性的啟發式方法就越是能對廣泛的問題有幫助（譬如《How to Solve It》中介紹的那些，譬如分類討論、分治、乃至我認為很重要的一個——寫下自己的思維過程，詳細分解各個環節，考察思維路徑中有無其它可能性（我們很容易拿到一道題目便被一種沖動帶入到某一條特定的思路當中，并且遵循著“最可能的”推導路徑往下走，往往不自覺的忽略其它可能性，于是那些可能性上的聯想就被我們的注意力“抑制”了。））。
輔助探索出hard knowledge：倒推法是一種啟發式思考方法，它將你的注意力集中到問題的結論中蘊含的知識上，一旦你開始關注可能從結論中演繹出來的知識，你就可能得到hard knowledge，即并不是早先就存在你腦子里，但是可以通過演繹獲得的。上文中的最小和子序列中的倒推方法就是一個例子。 而啟發式方法的局限性也存在于這兩個方面： 有些聯系是不管怎樣“啟發”也想不起來的。譬如“當布被刺破了，干草堆就重要了”，你怎么解釋這句話？如果有人提示一下“降落傘”，每個人都會恍然大悟。這是因為從“布”到“降落傘”之間的單向聯系是近乎不存在的。而且就算運用啟發法，譬如，考慮所有布做的東西，也基本絕無可能想到降落傘，因為同樣，從“布做的東西”到“降落傘”之間的關聯也是極其微弱的。我們腦子里只能保留那些最最重要的聯系。（如果一提到布，“降落傘”和“衣服”、“被單”、“窗簾”等日常物品以同等重要級別閃現，就亂套了。）那為什么從降落傘我們能想到布呢？我們實際上不能，我們為什么有些時候能，是因為譬如有人叫你“考慮降落傘的材料”，后者就激發了“降落傘之材料”這個語意，后者又指導了我們去考察降落傘的材料構成，于是我們想到是布。否則“布”是不會直接被激發起來的。那為什么在我們的這個問題中，一旦有人提到降落傘，我們就能建立從布到降落傘的關聯呢？這是因為“降落傘”和“布”這兩個語意單元的同時興奮增大了它們之間關聯的可能性，就好比是加大另一端的電壓從而發生了“擊穿”一樣。從本質上，解數學題也是如此，費馬大定理的求解過程是一個很好的例子，谷山志村猜想，就相當于那個“降落傘”的提示。我們還聽到很多這樣的故事（或者自己經歷）：苦思冥想一個問題不得要領，某一天在路上走，看到某個東西或聽到某句話，然后忽然，一道閃電劃破長空，那個問題解開了（阿基米德是因為躺在浴缸里從而想到浮力原理的嗎？）。我敢保證，如果一個人早就把那個問題從腦海里扔到九霄云外去了（不再處于興奮狀態了），那么就算線索出現，也是不可能發生頓悟的。我們都知道，帶著一個問題（使其在大腦中處于興奮狀態）去尋找答案更可能找到，即便不是有意去尋找，只要問題還在腦子里，任何周圍的有可能與它相關的線索都不會被大腦漏掉，因為“問題”和“周圍的其他線索”同時的興奮增大了關聯的可能性。如果問題早就被從大腦（意識或者潛意識）中撤下了，即便周圍出現提示也不會被捕捉到。
許多hard knowledge是不能被啟發探索出來的。至少是不能被“直接命中目標”地探索出來的。一個問題有可能跟三角函數有關，也許你只能帶著問題去探索三角函數的所有性質，從而最終發現那個關鍵的性質。費馬大定理與橢圓方程有關，也許只能去探索橢圓方程的所有性質，這個過程一定程度上是盲目的，試錯的，遍歷的。而不是直接面向目標的。再聰明的人也無法從費馬大定理直接反推到谷山志村猜想。在這些時候，啟發式方法最多只能提供一個探索的大致方向：譬如，探索三角函數的性質，并隨時注意其中哪個可能對我這個問題有幫助。譬如，探索模運算的性質，看看哪些性質可能會有用。譬如，探索橢圓曲線的性質...等等。啟發式方法并不能使我們的探索精準地命中目標。而只能劃定一個大致的范圍。也難怪有人說數學是盲目的。 但話說回來，啟發式方法的局限性并不能否認在大量場合啟發式方法的巨大幫助，許多時候，單靠啟發式方法就能帶來突破。而且，一旦知識性的東西掌握的是一樣多的，能否運用更優秀的思維方法就決定了能力的高下。有很多介紹思維方法的書。 本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/pongba/archive/2008/05/07/2412144.aspx
|
|
|
