指導人生演算法之最佳停時問題

前言

曾有一些學生找到蘇格拉底，問老師「人生是什麼呀？」蘇格拉底就把他們帶到一片蘋果林，要求大家從樹林的這一頭走到樹林的那一頭，每人挑選一隻最大最好的蘋果，但是不許走回頭路，不許選擇兩次。

當蘇格拉底在樹林的盡頭再看到這些學生的時候，好像他們每個人都不是很高興。有的學生說，我一進到果林就看到一個非常好的蘋果，於是把它摘了下來，可是沒想到後來又遇到了更好的蘋果。也有學生說，後面的蘋果沒有前面的好，我很後悔沒有拿前面的蘋果。蘇格拉底語重心長的說：「孩子們，這就是人生啊。人生就是一次無法重複的選擇。」

人生無法重複，沒有錯，但其實我們可以有最優解。這就是數學領域的最優停時的優化問題。如果你在前三分之一的路程上觀察各種蘋果的大小顏色。以這前1/3的蘋果為樣本，然後選擇後面的蘋果，你就有37%的概率得到最好的蘋果。這就是傳說中的37%法則。

最初的版本

我們以秘書問題做為這個法則介紹的起點。

想像你在面試一秘書，你希望能在應聘者里找到最好的人，但你並不知道怎樣的人會來應聘，所以你一個個人輪流面試。你可以隨時發offer，但你如果在面試後沒有馬上給對方offer，他就從此離開去其他地方工作了。你怎麼才能知道眼前這個應聘者是最好的呢？

方法就是給自己設定一個招聘總時間，前37%的時間裡只面試，收集數據不做決定，之後只要碰到一個比之前所有應聘者都優秀的人，馬上下offer，你能得到最好應聘者的機率也是37%。這是你能獲得的最好效果。

不要覺得37%成功率是個很低的數字。這個演算法可適用於任何大樣本。如果你有100個應聘者，你能獲得最好僱員的機率其實只有1%；而如果你有100萬應聘者，你的機率只剩百萬分之一。37%已經是一個非常好的數字了。為了達到這個成功率，你也需要付出之前37%的數據搜索時間精力。

改進

是不是只要牢記37%就一定可以取得成功呢？事實並非如此。

從前有一個聰明優秀的數學博士生在尋找女朋友，他發現這其實是一個「秘書問題」。於是他開始計算：假設從18歲到40歲都是找對象時間，37%時間點是26.1歲，而他正好在這個年齡點！他於是找到一位無論各方面他都覺得超出以往對象的姑娘，毫不猶豫地向她求婚。然而，他被拒絕了。

數學博士為愛悲傷之後，開始重新研究「秘書演算法」。他發現，女朋友比買東西複雜多了，原演算法有一個巨大假設：你發出的offer肯定會被對方接受。而即使在我們加州灣區，買房一般也是價高者得，還有中介幫忙估價，只要志在必得，總能做出讓對方接受的選擇，模型差別並不大。但是女孩子啊，君心深似海。

數學博士於是修正了演算法，他發現如果修正下前提，把對方接受概率改為50%，那麼你只有25%時間收集數據，而成功率也從37%降為25%。然而最不幸的是：我們這位博士已經超越25%數據收集時間了。

在我們的「經典秘書問題」中存在這兩個假設：首先面試官對候選人完全沒有任何了解，只能已經面試過的候選人作為樣本進行比較。所以我們才必須設置一個觀望期，來收集信息。

然而現實中我們是找秘書找房子還是找人生伴侶，大多數可以選擇的標準還是可以量化的。比如說像GRE等標準化考試，除了絕對分數之外，還可能會有百分比作為橫向比較標準。你不在數學部分，如果你獲得了滿分170分，那麼你就超過了97%的考生。在這種情況下，如果候選人是隨機樣本。那麼，傳統方法中的觀望期就可以被省略了。取而代之的方法是某一候選人。再超過某一百分比之後，就進行錄取。因此，在這種新的解法中。如果候選人非常多，可以適當提高標準。反正如果候選人比較少，就只能降低一些標準。

這個演算法的數學方法是這樣的，如果你只剩下了一位候選人，那麼毫無疑問，你只能選擇他。如果你上去了。兩位候選人，那麼你要判斷第二位候選人的分數百分比是否優於50%整體候選人。類似的邏輯，導數第四位錄取百分比為69%，倒數第四位為78%。隨著剩餘候選人的增多，選擇的標準也相應提升。最後一名候選人，錄取的百分比為95%。

也就是說最後一名候選人優於前面95%的候選人的時候，你才應該給他offer。這種策略選到最佳候選人的概率是58%。

傳統秘書問題的第二個假設，是你只有單項的一次選擇機會。然而事實真的是這樣嗎？

且讓我們看看著名天文學家開普勒如何處理這個找對象問題。1611年，開普勒妻子去世，他開始認真尋找再婚對象。在熱心紅娘們的幫助下，他最終確立了11個姑娘，逐一開始約會。但他約會到第四位姑娘時，他感覺找對人了，「我其實可以停止尋找了。」

然而開普勒是一個騎驢找馬的渣男。他並沒有停止尋找，而是吊著四姑娘，繼續按順序與剩下7個姑娘逐一約會。他最終發現第五個姑娘更好，「我喜歡她的愛、忠誠、家世、勤勞，和她給繼子們的愛。」他拋棄其他姑娘，向五姑娘求婚，餘生婚姻幸福美滿。

開普勒在「秘書問題」中，超越了演算法限制，頂著渣男的名聲，採用了「不拋棄不放棄」的策略。在姑娘們依然願意等待的演算法前提下，閱盡千帆了解了所有數據再做選擇，這當然是一種最佳策略。

假設可以重新去找你曾經錯過的姑娘，而女生有50%機率不計前嫌重修舊好，應該什麼時候開始做選擇呢？最佳停時演算法告訴我們：你可以花61%的時間搜集數據，然後在前61%的最佳選擇與之後每次碰到的最佳選擇中選最優選，你得到最佳伴侶的機率——也是61%。

結尾

說了這麼多，然而現實是蒼白的。

這個演算法本身並不能足夠精確的刻畫現實世界。人生路上，早早的摘下蘋果的也大有人在（難怪錢老會寫《圍城》）。每一次選擇都有機會成本，每一次付出都要考慮沉沒成本。歲月是把殺豬刀，誰能抵過時間呢？此情可待成追憶，只是當時已惘然。人生若只如初見，何事秋風悲畫扇。

不過，這些演算法還是為我們提供了一個新的角度，來幫助我們認識世界和我們自己。

參考資料

《algorithms to live by》

演算法和重大人生抉擇：如何最科學的選擇人生伴侶？MP3_IT科技新聞免費下載-喜馬拉雅FM

https://www.guokr.com/post/794746/