演算法之美：如何用數學方式解決生活中的具體問題？

最新 07-19

按：在道格拉斯·亞當斯的《銀河系漫遊指南》中，一個名叫深思（Deep Thought）的巨型超級計算機經過750萬年的計算，得出「生命、宇宙以及任何事情的終極答案」是42。為什麼是42？很多人都曾經嘗試著對此作出解答。事實上，古希臘哲學家畢達哥拉斯就認為萬物的本源是數。他認為數字先於事物存在，一切事物的性質都可以被歸結為數的規定性，例如，比例關係、有限與無限的關係，此外，社會生活中也時常出現數字的隱喻類比。而當數字化如此徹底地席捲我們的生活，這種關係似乎變得更為富有深意。

在《演算法之美》中，美國暢銷書作家克里斯汀和認知科學家格里菲思告訴我們，不只是宇宙的終極答案，數學也可以解決人類生活中面對的具體問題。租房、收拾衣櫃、選擇餐廳、時間管理……無不能用演算法解決。最優停止法則、時間調度法則、貝葉斯法則等等，這些法則看似艱深，其實連找停車位都能用得上！這本書告訴我們如何更有效地利用直覺、什麼時候應該把選擇權交給命運、無所適從的時候應該如何做出選擇，以及如何有效地與他人保持聯繫。

經出版社授權，界面文化（ID：BooksAndFun）從中選擇了部分章節，以饗讀者。

文 | 布萊恩·克里斯汀湯姆·格里菲思

所有的基督徒都會在結婚請柬的最前面鄭重宣布，他們走進婚姻的殿堂是遵從上帝的特別安排。但是，我要站在哲學的角度，詳細地探討這個問題……

——約翰尼斯·開普勒

如果你覺得馬丁先生是最優秀的人選，如果你覺得與他相處最為融洽，那麼你還猶豫什麼呢？

——簡·奧斯汀，《愛瑪》

對於在中學時代就建立了戀愛關係的大一新生而言，感恩節就是一個嚴峻的考驗：因為回家度過短短4天的假期之後，很多戀人就勞燕分飛了。大學輔導員把這個普遍現象稱作「放棄火雞」。

大一新生布萊恩就面臨著這個問題。他中學時的女友在另外一所大學，天各一方的兩個人不僅需要解決空間距離造成的麻煩，還需要認真思考一個問題：他們兩人之間的感情到底有多深？他們從來沒有考慮過這個具有哲學深度的問題。由於沒有類似的感情可以參考，他們無從回答這個問題。於是，焦慮不安的布萊恩找到輔導員，向她尋求幫助。輔導員知道這是新生經常遭遇的一個典型難題，所以她用一種極其冷淡的語氣給出了自己的建議：「先收集一些數據吧。」

顯而易見，在連續性單配偶的生活方式中，人們不可避免地會遇到一個非常重要的問題：接觸多少人之後，才可以確定自己的理想伴侶？如果在收集數據的過程中與自己的「真命天子」失之交臂，那該怎麼辦？這似乎成了感情問題上無解的「第22條軍規」。

我們知道，這個令大一新生憂心忡忡、牢騷滿腹的「第22條軍規」其實就是數學界的「最優停止問題」，它的答案其實很簡單，就是37%。

當然，前提條件是你願意在愛情問題上做出各種假設。

在所有最優停止問題中，最大的難點不在於選擇哪一種可選方案，而是確定自己需要考慮多少種可選方案。這些問題往往會引發不同的後果，不僅陷入愛河的人和需要租房的人必須慎重考慮，司機、房主、入室行竊者等也常常面臨同樣的抉擇。

「37%法則」源於所謂的「秘書問題」——最優停止問題中最著名的一類難題。秘書問題的情境與我們前面考慮過的租房難題十分相似。假設一堆人申請一個秘書崗位，而你是面試官，你的目標是從這堆申請人中遴選出最佳人選。你不知道如何給每一名申請人評分，但是可以輕鬆地判斷哪一名申請人更加優秀。（用數學語言來表述，就是說你只能看到序數，即申請人相互比較的排名，但是無法看到基數，即在一般性評分標準下的得分。）你按照隨機順序，每次面試一名申請人。你隨時可以決定將這份工作交給其中一人，而對方只能接受，於是面試工作就此結束。但是，一旦你否決其中一名申請人，就不能改變主意再回頭選擇他。

在選擇秘書時，遴選程序停止過早或者過晚都會導致不理想的結果。停止過早，最優秀的申請人還沒有得到亮相的機會；停止過晚，就說明你在為一位根本不存在的更優秀的申請人保留這份工作。要取得最理想的結果，顯然需要在兩者之間找到最合適的平衡點，在甄選時既不可遲遲不決，又不可草草收手。

如果找到最優秀申請人是你追求的唯一目標，那麼在整個面試過程中，只要不是已有申請人當中的最優秀人選，你都不會接受。但是，僅僅達到「目前最佳」這個條件，還不足以說服面試官。比如說，第一名申請人毫無疑問就符合這個條件。一般而言，我們有理由相信，隨著面試程序不斷進行下去，出現「目前最佳」申請人的概率將不斷下降。例如，第二名申請人是截至目前最優秀申請人的可能性是50%，第五名的可能性只有1/5，第六名的可能性只有1/6，以此類推。因此，隨著面試工作的深入，目前為止最優秀申請人一旦出現，必然會令人眼前一亮（別忘了，根據定義，這名申請人比之前所有申請人都更加優秀），不過，這種可能性在不斷降低。

所以說，看到第一個目前最優秀申請人就欣然接受（也就是說，面試第一名申請人之後就結束面試程序），顯然是過於草率了。在一共有100名申請人時，也不能因為第二名申請人比第一名申請人更優秀就迫不及待地選擇他，因為這種做法同樣有些操之過急。那麼，我們到底該怎麼辦？

憑直覺，我們可以找到幾種應對的辦法。例如，當第三次（或者第四次）出現勝過前面所有的申請人時，就把工作機會交給他。或者，在連續多個申請人都不理想的情況下，一旦出現一名目前為止最優秀的人選，就毫不猶豫地接受他。

但是，事實證明，所有這些相對來說似乎有道理的策略都算不上是最明智的做法。事實上，效果最佳的做法是接受所謂的「摸清情況再行動準則」（look-then-leaprule）：事先設定一個「觀察」期，在這段時間裡，無論人選多麼優秀，都不要接受他（也就是說，你的任務就是考察目標，收集數據）。「觀察」期結束之後，就進入了「行動」期。此時，一旦出現令之前最優秀申請人相形見絀的人選，就立即出手，再也不要猶豫了。

考慮申請人數極少時的秘書問題，「摸清情況再行動準則」就會自動顯露出來。如果只有一名申請人，這個問題就非常簡單——接受她的申請！如果有兩名申請人，無論你如何選擇，你成功選到優秀人選的概率都是50%。你可以接受第一名申請人（此時，她是半程最優秀申請人），或者拒絕她，而拒絕第一名申請人就意味著接受第二名申請人（她也是半程最優秀申請人）。

如果有第三名申請人，情況就一下子變得有意思了。如果隨機選擇一名申請人，得到理想結果的概率是1/3，也就是33%。有兩名申請人時，我們沒有辦法取得比碰運氣更好的結果。那麼，在有三名申請人時，會怎麼樣？事實證明，我們可以取得更理想的結果，而其中的關鍵就在第二場面試。在面試第一名申請人時，我們沒有任何信息——她肯定是目前最優秀的申請人。在面試第三名申請人時，我們沒有任何能動性——我們只能將工作機會交給這名申請人，因為我們已經拒絕了其他人的申請。但是，在面試第二名申請人時，我們既掌握了一些信息，又有一定的能動性——我們知道她與第一名申請人相比孰優孰劣，同時我們既可以接受她，也可以拒絕她。如果她比第一名申請人優秀，我們接受她，反之就拒絕她，那麼會產生什麼樣的結果？事實上，在有三名申請人時，這是最理想的方案。令人吃驚的是，在有三名申請人時採用這個方法，與有兩名申請人時選擇半程最優秀人選的方法相比，效果不相上下。

在有4名申請人時，窮舉所有可能的情況之後就會發現，我們仍然應該在面試第二名申請人時採取行動；如果一共有5名申請人，我們應該等到面試第三名申請人時才採取行動。

隨著申請人數不斷增加，觀察與行動之間的分界線正好處在全部申請人37%的位置，從而得出了37%法則：在考察前37%的申請人時，不要接受任何人的申請；然後，只要任何一名申請人比前面所有人選都優秀，就要毫不猶豫地選擇他。

事實證明，利用這種最優方案，我們選中最優秀申請人的概率為37%。方案本身與出現理想結果的概率正好相等，這是這類問題表現出來的令人奇怪的數學對稱性。上表列出了申請人數不同時的秘書問題最優解決方案。從中可以看出，隨著申請人數不斷增加，取得理想結果的概率（以及從觀察期切換到行動期的時間點）在37%左右。

採用最理想的方案也會有63%的失敗率，這是一個令人警醒的事實。在面對秘書問題時，即使我們採取了最理想的行動方案，在大多數情況下也會遭遇失敗，也就是說，大多數情況下我們都無法選中所有人選當中最優秀的那名申請人。對於把愛情視為尋覓「真命天子」的人來說，這確實是一個壞消息。不過，也不完全都是壞消息。直覺告訴我們，隨著申請人數的不斷增加，選中最優秀申請人的可能性將穩步下降。例如，如果採用隨機選擇的方式，在申請人總數為100時，我們得到理想結果的可能性是1%，在總人數為100萬時，可能性就會降到0.0001%。但是，令人意想不到的是，秘書問題的計算結果不會發生變化。如果採用最優停止理論，在100人當中選中最優秀申請人的可能性是37%。而總人數是100萬時，無論你相信與否，你得到理想結果的可能性仍然是37%。因此，申請人總數越多，最優演算法理論就越有價值。的確，在大多數情況下，大海撈針都會無功而返，但是，無論「海洋」多麼遼闊，最優停止理論都是最理想的工具。

在秘書問題首次被提出後的幾十年時間裡，人們研究了各種各樣的情境，並結合不同的條件提出了若干最優停止策略。例如，針對（求愛）可能遭到拒絕的問題，他們提出了一個簡單明了的數學答案：儘早向多名對象伸出橄欖枝。假如遭到拒絕的可能性是50%，那麼得出37%法則的那個數學分析過程就會告訴你，遴選過程完成1/4後就應該隨時準備求婚了。如果遭到拒絕，那麼在發現下一個最佳人選時要再次求婚，直到求婚成功為止。運用這個策略，獲得成功（即向所有人選中的最佳人選求婚並被接納）的總概率仍然可以達到25%。根據自己的標準尋覓愛情本身就有難度，再加上遭到拒絕這個不利條件，25%的成功概率可以算是一個還不錯的結果了。

此外，人們還經常修改秘書問題的其他前提條件，使之與現實生活中尋覓愛情（或挑選秘書）等難題更為相似，結果形成了更多的秘書問題變種。不過，最優停止問題給我們的啟發不僅限於約會與招聘這兩個方面。事實上，在租房子、找停車位、見好就收的時機選擇等問題中，我們同樣需要面對一個又一個的可選方案，做出最有利的選擇。從一定程度上說，這些問題已經得到了解決。

（本文選自《演算法之美》第一章《最優停止理論：如何準確選擇停止觀望的時機？》，有刪節。）