算法之美
內容簡介
我們所有人的生活都受到有限空間和有限時間的限制，因此常常面臨一系列難以抉擇的問題。在一天或者一生的時光里，哪些事是我們應該做的，哪些是應該放棄的？我們對雜亂無序的容忍底線是什么？新的活動與熟悉并喜愛的活動之間如何平衡，才能取得令人愉快的結果？這些看似是人類特有的難題，其實不然，因為計算機也面臨同樣的問題，計算機科學家幾十年來也一直在努力解決這些問題，而他們找到的解決方案可以給我們很多啟發。
通過豐富的跨學科研究，作者指出，計算機算法也可以用來解答人類面臨的這些問題。這本書告訴我們如何更有效地利用直覺、什么時候應該把選擇權交給命運、無所適從的時候應該如何做出選擇，以及如何有效地與他人保持聯系。從找配偶到找停車位，從組織管理個人郵箱的收件箱到理解人類記憶的作用原理，這本書把計算機科學的智慧轉化為人類生活的策略，引導我們做出明智的選擇。
作者簡介
布萊恩·克里斯汀，《華爾街日報》暢銷書《最有人性的人》作者，該書入選《紐約時報》編輯推薦書目，被《紐約客》雜志評為年度好書。他的多篇作品先后刊登在《紐約客》《大西洋》《連線》《華爾街日報》《衛報》《巴黎評論》及《認知科學》等雜志上，被翻譯成11種語言。
湯姆 · 格里菲思，加州大學伯克利分校心理學和認知科學教授，計算認知科學實驗室主任。格里菲思發表過150多篇科學論文，內容涉及認知心理學、文化演進等，受到美國國家科學基金會、斯隆基金會、美國心理學會和心理環境學會等頒發的各類獎項。
本書內容
序言
假設你想租房子，正在舊金山四處尋找房源。舊金山可能是整個美國最難找房子的城市了。由于技術產業的蓬勃發展，再加上城市區劃法律嚴格限制建造新住房，舊金山的房租已經與紐約不相上下，甚至比紐約還高。房源清單列出來幾分鐘，房子就會被人們一搶而空。通常情況下，只有第一個把定金支票塞到房東手里的人，才能拿到房子的鑰匙。
理論上講，認真調查、仔細斟酌是理性消費者的一大特征，但是舊金山的殘酷市場并沒有為他們留有權衡考慮的機會。在購物中心或者網上購物時，人們可以反復權衡再做出決定，但是將要入住舊金山的租客沒有這個特權，他們必須迅速做出決定：要么舍棄其他所有可能的選擇，就選定當前正在看的這套房子，要么掉頭就走，再也不要回頭。
簡單起見，我們姑且假設，你唯一關心的就是盡最大可能增加挑中最理想公寓的機會。你的目標是把“看過的好房子被人挑走”與“還有好房子沒來得及看”這兩種遺憾的發生概率降至最低。于是，你立刻發現自己陷入了兩難境地：如果沒有衡量的標準，如何判斷一套公寓是否是最合適的呢？如果你不先看一些公寓（這些公寓將被你放棄），又如何確定衡量標準？你收集的信息越多，越能在最合適的機會出現時準確地認出它，但是你已經與最合適的機會失之交臂的可能性也越高。
那么，到底該怎么辦？如果收集信息的行為會危及結果，那么怎樣才能在掌握足夠多信息的基礎上做出明智決定呢？這個令人極其為難的情境近乎于一個悖論。
在被問及此類問題時，大多數人憑直覺給出的回答可能大致如此：這需要在繼續挑選與立刻下手之間達成某種平衡。也就是說，你必須先看足夠多的房子，確定一個標準，然后接受符合這個標準的房子。事實上，平衡概念正是解決這類問題的關鍵。但是，大多數人根本無法確定這個平衡點在哪里。好消息是，這個平衡點已經被找出來了。
答案就是37%。
如果你希望選中最合適公寓的可能性達到最大，那么在看前37%的房子時不要做出任何決定（如果你準備花一個月的時間挑選房子，那么在前11天不要做出決定）。這段時間你是在為制定標準做準備，因此看房子時把銀行卡放在家里吧。但是，過了這個時間點之后，你就要做好隨時簽約的準備（包括準備好定金等），一旦你對某套房子的滿意程度超過之前看過的所有房子，就立刻下手。在繼續挑選與立刻下手之間做出的這種妥協，并不僅僅是一種直覺，而是已經得到證明的最優解。
我們知道這個答案，是因為找房子問題屬于數學上被稱作“最優停止”（optimal stopping）的一類問題。37%法則明確了解決這些問題的一系列簡單步驟（計算機科學稱之為“算法”）。事實證明，找房子僅僅是最優停止問題在日常生活中的表現形式之一。在面臨一連串選擇時如何做出決定的難題，經常會改頭換面，以不同的形式出現在我們的生活當中。在駛入停車位之前，需要繞整個停車場多少圈？在商業風險中何時套現脫身？在買房子或者停車時，何時是結束觀望、做出決定的最佳時機？
在約會這個更加令人頭疼的問題上，人們也經常要面對這樣的難題。最優停止理論是一夫一妻婚姻制度催生的科學。
每天，人們都要面臨最優停止問題的困擾（當然，詩人更愿意追逐的話題肯定是求婚帶來的煩惱，而不是停車時的兩難境地），有時甚至會因此而痛苦不堪。不過，我們大可不必如此，因為這類問題至少可以通過數學方法來解決。借助并不繁復的算法，我們不僅可以解決找房子的問題，生活中遭遇的所有最優停止問題都可以被妥善處理。
從本質上講，我們身邊經常出現因為租房子、停車、求婚而感到苦惱的人，這些人其實就是在自尋煩惱。他們需要的不是治療師，而是一種算法。治療師告訴他們要在沖動與多慮之間找到一個正確的、舒服的平衡點。
算法告訴他們這個平衡點就是37%。
※—※—※
由于我們生活在有限的時間和空間之中，因此所有人都會面臨一系列特定的問題，諸如在一天或者十年里，哪些事必須做，哪些事應當放手？如何在嘗試新的體驗與從事自己喜愛的活動中取得平衡，才能生活得愜意自在、心滿意足？
這些問題看起來似乎都是人類特有的，其實不然。半個多世紀以來，計算機科學家苦苦思考的問題（有很多已經得到妥善解決）與這些日常難題在本質上并無區別。例如，處理器在執行用戶請求時應該如何分配自己的“注意力”，才能降低費用、節省時間？在什么情況下應該在不同任務之間來回切換？剛開始應該接受多少任務量？如何利用有限的存儲資源取得最佳效果？應該收集更多數據，還是根據已收集的數據采取行動？對人類而言，如何把握今天可能不是一件易事，但是我們身邊的計算機可以輕輕松松地把握每一毫秒。顯然，計算機有很多值得我們借鑒的地方。
將算法與人類生活相提并論似乎是一件很奇怪的事。在很多人看來，“算法”這個詞意味著神秘莫測的謀劃與操作，與大數據、大政府、大企業有密切的聯系，正在逐漸變成現代社會基礎架構中一個越來越重要的部分。其實，算法指的就是解決問題的一系列步驟，其含義遠不限于計算機，存在的歷史也遠遠長于計算機。在計算機開始使用算法之前，人類早就將算法應用到生活當中了。
“算法”（algorithm）一詞得名于波斯數學家花拉子密。公元9世紀，這位數學家寫過一本書，討論用紙筆解決數學問題的技巧。［書名為“al-Jabr wa’l-Muqabala”，其中的“al-jabr”就是后來“algebra”（代數）這個詞的前身。］不過，最早的數學算法早于花拉子密。在巴格達附近出土的4000年前的蘇美爾人泥板文獻上，就刻有一幅長除法示意圖。
但是，算法不僅限于數學。在按照食譜介紹烤面包時，食譜上的所有步驟就是一個算法。按照圖樣編織毛衣時，這份圖樣就是一個算法。使用鹿角的末端連續精確地敲打，使石器形成鋒利的刃的過程（這是制作精密石器的一個關鍵步驟），也遵循著一個算法。從石器時代開始，算法就已經是人類生活的一部分了。
※—※—※
本書將探討人類事務算法設計這個概念，以幫助人們更好地處理日常生活中遇到的難題。將計算機科學的研究方法應用于日常生活，可以在多個層面上產生深遠的影響。首先，它可以提供切實有效的建議，幫助我們解決具體問題。例如，最優停止理論可以告訴我們何時應該小心觀察，何時應該果斷行動；探索-利用平衡理論教會我們如何在嘗試新事物與因循守舊之間找到平衡點；排序理論可以幫我們判斷出是否需要以及如何整理辦公室；緩存理論可以幫助我們合理地填充櫥柜；日程安排理論則可以提供合理安排時間的高招。
其次，計算機科學還為我們理解這些領域的深層次運行規則提供了一套語匯。卡爾 · 薩根指出：“與其說科學是大量知識的匯總，不如說它是一種思考方式。”即使生活中的某些情況非常復雜，我們無法進行嚴格的數值分析，找不到任何現成的答案，我們也可以考慮這些問題的簡單化表現形式，從而得出某些直覺和概念，幫助我們理解其中的關鍵環節并取得進展。
從更廣泛的意義上看，借助計算機科學，我們可以了解人類思想的本質和理性的意義，學會回答如何度過一生這個最古老的問題。把認知視為一種解決周圍環境所造成的問題（從本質上看，都是一些計算問題）的手段，并認真地加以研究，就有可能徹底改變我們對人類理性的理解。
認為研究計算機內部運行機制能夠幫助我們學會思考與決策、判斷某個事物是否可信、選擇行為方式的觀點，在很多人看來，不僅把問題過于簡單化了，而且具有誤導性。即使計算機科學告訴我們應該如何思考、應該采取哪些行動，我們愿意接受嗎？讀一讀講人工智能和機器人的科幻小說就會發現，那樣的生活似乎都不是我們所向往的。
之所以如此，部分原因是我們把計算機看成了機械呆板的確定性系統——這些機器借助嚴謹的演繹邏輯，通過窮舉所有可選方案，無論花費多少時間、問題難度如何，它都可以給出完全正確的答案。事實上，在阿蘭 · 圖靈當時的想象中，計算機就應該是這樣。這位第一個設想出計算機的人通過類比的方式給出了計算的定義，而類比的原型就是認真鉆研的人類數學家——他們通過長長的計算步驟，最終得出絕對正確的答案。
因此，當人們發現現代計算機處理難題的方式與他們對計算機的認識并不一致的時候，他們也許會大吃一驚。當然，簡單的算術對現代計算機而言沒有任何難度。目前，計算機科學面臨的最難解決的問題其實是人機對話、修復破損文件、下圍棋取勝，這些問題都具有規則不明確、所需信息不全，或者需要考慮無數種可能性才可以找出正確答案的特點。研究人員已經開發出各種算法，使計算機在解決難度極大的問題時不需要完全依賴窮舉計算。要解決這些來自現實世界的任務，就必須正確處理好可能性問題，利用粗略估算，在時間與精確度之間做出某種妥協。
隨著計算機處理現實任務的能力不斷增強，計算機算法不僅對于人類自己的生活具有借鑒意義，同時還為人們理解人類認知提供了一個更好的比較標準。在過去的一二十年里，行為經濟學對人類進行了非常具體的研究，結果發現，人類是不理性的，很容易犯錯誤，而問題的源頭在很大程度上就是大腦這個古怪而獨特的硬件。這種自我貶低的認識越來越普遍，卻無法解釋某些令人困惑的問題。例如，在完成包括想象、語言、因果推理在內的大量認知任務時，4歲兒童的能力仍然超過成本高昂的超級計算機，這到底是什么原因？
從計算機科學為日常問題提供的解決方案可以看出，人類思維具有另外一種特點——人生充滿了難以解決的問題。人經常犯錯誤，雖然這可以說明人類大腦容易出錯，但是也表明這些問題具有難以解決的本質特點。通過算法來思考我們周圍的世界，了解我們所面臨問題的基本結構以及計算機給出的解決方案的特性，可以幫助我們真實地了解我們自己，更好地理解我們所犯的那些錯誤。
事實上，人類需要不斷面對計算機科學所研究的一些高難度問題，在不確定性及時間有限、信息不全、情況瞬息萬變等不利因素的干擾下做出決定。針對一些問題，即使最前沿的計算機科學也沒能開發出永遠不會犯錯誤的有效算法，有的情形似乎是任何算法都無法解決的。
不過，盡管有的現實問題異常復雜，人們還沒有開發出完善的算法，但是一代代計算機科學家一直在與這些難題斗爭，并且在這個過程中得出了深刻而獨到的見解。這些來之不易的真知灼見與我們對理性的直覺認識并不一致，與數學家對周圍世界的精確描述也迥然不同——數學家一心想要把這個世界變成整齊劃一的線條。計算機科學告訴我們：不要總是考慮所有的可選方案；不必每次都追求最佳結果；偶爾犯點兒錯誤；放下包袱，輕裝前進；有的事情可以暫時放一放；相信自己的本能，不要過多思考；放松自己；采用拋硬幣的方式；要體諒，但是不能忘記；忠于自我。
用計算機科學的智慧指引自己的人生之路，這似乎是一條不錯的建議。畢竟，與大多數建議不同的是，這條建議有據可依。
※—※—※
當初，算法設計在各學科的夾縫中找到了立足之地，它是數學與工程技術糅合而成的怪異混合體。現在，為人類設計算法的工作也面臨相同的境遇——找不到一個現成的歸屬學科。今天的算法設計不僅需要借助計算機科學、數學和工程技術，還需要得到統計學、運籌學等相關領域的幫助。此外，我們不僅需要考慮計算機算法設計與人類思維活動之間的關系，還需要認真研究認知學、心理學、經濟學等學科。
本書作者都有跨學科工作與研究的經歷。布萊恩學習的是計算機科學和哲學，研究生階段學習的是英語，畢業之后從事的是與這三個學科都相關的工作。湯姆學的是心理學和統計學，在加州大學伯克利分校從教期間，他主要研究人類認知與計算之間的關系。但是，人類算法設計涉及多個領域，任何人都不可能是所有領域的專家。因此，在探索研究方便人類生活的算法時，我們還與過去50年最著名的算法專家進行了交流，詢問這些全世界最聰明的人，他們的研究對他們自己的生活（包括尋覓配偶、收拾衣帽鞋襪）到底產生了什么樣的影響？
接下來，我們就將開始引領大家游覽這個神秘的領域。首先，我們將討論計算機與人類大腦都需要面對的巨大挑戰：如何應對有限空間、有限時間、有限注意力、未知的未知事物、不完整的信息與不可預見的未來給我們造成的麻煩，如何鎮定自若、充滿自信地面對這些麻煩，如何與其他人一起，共同面對這些麻煩，我們將討論這些難題的基本數學結構，了解計算機解決大多數難題的設計原理（有時，這些設計甚至與我們的想象背道而馳）。此外，我們還將了解人腦的工作原理，了解人腦在解決相同類型問題、應對相同限制條件時有哪些獨特且密切相關的處理方式。最終，我們不僅將得到有助于解決身邊問題的一系列具體建議，學會在面臨最復雜人類困境時有助于我們看清其脈絡結構的新方法，還可以清醒地認識到人與計算機深度融合過程中的痛苦與艱辛。此外，我們還會有一些意義更加深刻的收獲：一套描述周圍世界的全新語匯以及一個從全新角度了解自己的機會。
01 最優停止理論 如何選擇停止觀望的時機？
約翰尼斯 · 開普勒
所有的基督徒都會在結婚請柬的最前面鄭重宣布，他們走進婚姻的殿堂是遵從上帝的特別安排。但是，我要站在哲學的角度，詳細地探討這個問題……
簡 · 奧斯汀，《愛瑪》
如果你覺得馬丁先生是最優秀的人選，如果你覺得與他相處最為融洽，那么你還猶豫什么呢？
對于在中學時代就建立了戀愛關系的大一新生而言，感恩節就是一個嚴峻的考驗：因為回家度過短短4天的假期之后，很多戀人就勞燕分飛了。大學輔導員把這個普遍現象稱作“放棄火雞”。
大一新生布萊恩就面臨著這個問題。他中學時的女友在另外一所大學，天各一方的兩個人不僅需要解決空間距離造成的麻煩，還需要認真思考一個問題：他們兩人之間的感情到底有多深？他們從來沒有考慮過這個具有哲學深度的問題。由于沒有類似的感情可以參考，他們無從回答這個問題。于是，焦慮不安的布萊恩找到輔導員，向她尋求幫助。輔導員知道這是新生經常遭遇的一個典型難題，所以她用一種極其冷淡的語氣給出了自己的建議：“先收集一些數據吧。”
顯而易見，在連續性單配偶的生活方式中，人們不可避免地會遇到一個非常重要的問題：接觸多少人之后，才可以確定自己的理想伴侶？如果在收集數據的過程中與自己的“真命天子”失之交臂，那該怎么辦？這似乎成了感情問題上無解的“第22條軍規”。
我們知道，這個令大一新生憂心忡忡、牢騷滿腹的“第22條軍規”其實就是數學界的“最優停止問題”，它的答案其實很簡單，就是37%。
當然，前提條件是你愿意在愛情問題上做出各種假設。
秘書問題
在所有最優停止問題中，最大的難點不在于選擇哪一種可選方案，而是確定自己需要考慮多少種可選方案。這些問題往往會引發不同的后果，不僅陷入愛河的人和需要租房的人必須慎重考慮，司機、房主、入室行竊者等也常常面臨同樣的抉擇。
“37%法則”[1]源于所謂的“秘書問題”——最優停止問題中最著名的一類難題。秘書問題的情境與我們前面考慮過的租房難題十分相似。假設一堆人申請一個秘書崗位，而你是面試官，你的目標是從這堆申請人中遴選出最佳人選。你不知道如何給每一名申請人評分，但是可以輕松地判斷哪一名申請人更加優秀。（用數學語言來表述，就是說你只能看到序數，即申請人相互比較的排名，但是無法看到基數，即在一般性評分標準下的得分。）你按照隨機順序，每次面試一名申請人。你隨時可以決定將這份工作交給其中一人，而對方只能接受，于是面試工作就此結束。但是，一旦你否決其中一名申請人，就不能改變主意再回頭選擇他。
普遍認為，秘書問題第一次出現在出版物中是在1960年2月，那一期的《科學美國人》雜志在馬丁 · 伽德納最喜歡的欄目——“趣味數學”專欄中刊登了幾個難題，其中之一就是秘書問題，不過當時沒有明確地提到“秘書”這個詞。但是，這個問題到底從何而來，這是一個非常神秘的謎。除了一些推測以外，初期的調查沒有任何確鑿的結論。隨后，我們風塵仆仆地趕到斯坦福大學，查閱伽德納的文書檔案。伽德納在20世紀中期留下來的那一盒盒書信，出乎意料地把我們的調查變成了偵探工作。閱讀書信有點兒像偷聽別人打電話，你只能聽到通話一方所說的話，因此需要推斷另一方到底說了什么。從這些回信看，大約50年前，伽德納本人似乎正在調查秘書問題的來源。但是，看完這些書信，我們更是一頭霧水了。
哈佛大學數學家弗雷德里克 · 莫斯特勒回憶說，1955年，他聽同事安德烈 · 格里森提到過這個問題，而格里森又是從其他人那里聽說的。阿爾伯塔大學的里奧 · 莫澤在信中說，他曾經在波音公司 R. E. 加斯克爾的“筆記”中看到過這個問題，而加斯克爾本人則說他是從一位同事那里聽說這個問題的。羅格斯大學的羅杰 · 平克漢姆稱，他是1955年從杜克大學數學家 J. 舍恩菲爾德那里第一次聽說秘書問題的，他還說：“我記得，他說他是從密歇根大學的某個人那里聽說的。”
幾乎可以肯定，“密歇根大學的某個人”其實就是梅里爾 · 弗拉德。盡管在數學界以外幾乎沒有人知道弗拉德，但是他對計算機科學的影響很難被忽略。他把“旅行商問題”（我們將在第8章深入討論）變成了一個廣為人知的內容，還設計了“囚徒的困境”（參見第11章），甚至“軟件”（software）一詞也可能是他造出來的。1958年，他成了已知的第一個發現37%法則的人，同時他宣稱，他從1949年就開始考慮這個問題了。但是，在說到最初來源時，弗拉德本人提到了另外幾名數學家。
秘書問題是一個近乎完美的數學難題：問題本身表述簡單，解題難度非常高，答案簡潔明了，而影響力又足以讓人產生濃厚的興趣。因此，通過人們的口口相傳，這個問題以燎原之勢在20世紀50年代的數學界迅速蔓延開來。1960年，在伽德納專欄的推波助瀾之下，它又大大地激發了普通大眾的想象力。至20世紀80年代，秘書問題已經變成了一個研究分支，無數人撰文討論這個問題及與其相關的變體。
至于這個問題是如何與秘書產生聯系的，這是一個非常有意思的過程——每種文化的社會偏愛都會對社會的形式系統產生影響。例如，在我們的心中國際象棋是中世紀歐洲人的象征，但是實際上國際象棋起源于8世紀的印度。15世紀，粗暴的“歐洲化”過程把沙阿（即國王）變成了王，維齊爾（即高官）變成了王后，而大象則成了基督教主教的形象。最優停止問題同樣有多種不同化身，每種化身都是當時關注熱點的某種反映。19世紀，最優停止問題的典型形式是巴洛克彩票和女性挑選求婚者的行為；20世紀初，常見的表現形式是駕車度假的人挑選賓館、男性選擇約會對象；在官僚作風盛行、男性占主導地位的20世紀中葉，最典型的最優停止問題是討論男性老板如何挑選女性助手的問題。第一次明確提出“秘書問題”的是發表于1964年的一篇論文，自此之后，這個名稱就再也沒有發生變化。
37%從何而來？
在選擇秘書時，遴選程序停止過早或者過晚都會導致不理想的結果。停止過早，最優秀的申請人還沒有得到亮相的機會；停止過晚，就說明你在為一位根本不存在的更優秀的申請人保留這份工作。要取得最理想的結果，顯然需要在兩者之間找到最合適的平衡點，在甄選時既不可遲遲不決，又不可草草收手。
如果找到最優秀申請人是你追求的唯一目標，那么在整個面試過程中，只要不是已有申請人當中的最優秀人選，你都不會接受。但是，僅僅達到“目前最佳”這個條件，還不足以說服面試官。比如說，第一名申請人毫無疑問就符合這個條件。一般而言，我們有理由相信，隨著面試程序不斷進行下去，出現“目前最佳”申請人的概率將不斷下降。例如，第二名申請人是截至目前最優秀申請人的可能性是50%，第五名的可能性只有1/5，第六名的可能性只有1/6，以此類推。因此，隨著面試工作的深入，目前為止最優秀申請人一旦出現，必然會令人眼前一亮（別忘了，根據定義，這名申請人比之前所有申請人都更加優秀），不過，這種可能性在不斷降低。
所以說，看到第一個目前最優秀申請人就欣然接受（也就是說，面試第一名申請人之后就結束面試程序），顯然是過于草率了。在一共有100名申請人時，也不能因為第二名申請人比第一名申請人更優秀就迫不及待地選擇他，因為這種做法同樣有些操之過急。那么，我們到底該怎么辦？
憑直覺，我們可以找到幾種應對的辦法。例如，當第三次（或者第四次）出現勝過前面所有的申請人時，就把工作機會交給他。或者，在連續多個申請人都不理想的情況下，一旦出現一名目前為止最優秀的人選，就毫不猶豫地接受他。
但是，事實證明，所有這些相對來說似乎有道理的策略都算不上是最明智的做法。事實上，效果最佳的做法是接受所謂的“摸清情況再行動準則”（look-then-leap rule）：事先設定一個“觀察”期，在這段時間里，無論人選多么優秀，都不要接受他（也就是說，你的任務就是考察目標，收集數據）。“觀察”期結束之后，就進入了“行動”期。此時，一旦出現令之前最優秀申請人相形見絀的人選，就立即出手，再也不要猶豫了。
考慮申請人數極少時的秘書問題，“摸清情況再行動準則”就會自動顯露出來。如果只有一名申請人，這個問題就非常簡單——接受她的申請！如果有兩名申請人，無論你如何選擇，你成功選到優秀人選的概率都是50%。你可以接受第一名申請人（此時，她是半程最優秀申請人），或者拒絕她，而拒絕第一名申請人就意味著接受第二名申請人（她也是半程最優秀申請人）。
如果有第三名申請人，情況就一下子變得有意思了。如果隨機選擇一名申請人，得到理想結果的概率是1/3，也就是33%。有兩名申請人時，我們沒有辦法取得比碰運氣更好的結果。那么，在有三名申請人時，會怎么樣？事實證明，我們可以取得更理想的結果，而其中的關鍵就在第二場面試。在面試第一名申請人時，我們沒有任何信息——她肯定是目前最優秀的申請人。在面試第三名申請人時，我們沒有任何能動性——我們只能將工作機會交給這名申請人，因為我們已經拒絕了其他人的申請。但是，在面試第二名申請人時，我們既掌握了一些信息，又有一定的能動性——我們知道她與第一名申請人相比孰優孰劣，同時我們既可以接受她，也可以拒絕她。如果她比第一名申請人優秀，我們接受她，反之就拒絕她，那么會產生什么樣的結果？事實上，在有三名申請人時，這是最理想的方案。令人吃驚的是，在有三名申請人時采用這個方法，與有兩名申請人時選擇半程最優秀人選的方法相比，效果不相上下。[2]
在有4名申請人時，窮舉所有可能的情況之后就會發現，我們仍然應該在面試第二名申請人時采取行動；如果一共有5名申請人，我們應該等到面試第三名申請人時才采取行動。
隨著申請人數不斷增加，觀察與行動之間的分界線正好處在全部申請人37%的位置，從而得出了37%法則：在考察前37%[3]的申請人時，不要接受任何人的申請；然后，只要任何一名申請人比前面所有人選都優秀，就要毫不猶豫地選擇他。
表1-1 挑選秘書的最優方案
事實證明，利用這種最優方案，我們選中最優秀申請人的概率為37%。方案本身與出現理想結果的概率正好相等，這是這類問題表現出來的令人奇怪的數學對稱性。上表列出了申請人數不同時的秘書問題最優解決方案。從中可以看出，隨著申請人數不斷增加，取得理想結果的概率（以及從觀察期切換到行動期的時間點）在37%左右。
采用最理想的方案也會有63%的失敗率，這是一個令人警醒的事實。在面對秘書問題時，即使我們采取了最理想的行動方案，在大多數情況下也會遭遇失敗，也就是說，大多數情況下我們都無法選中所有人選當中最優秀的那名申請人。對于把愛情視為尋覓“真命天子”的人來說，這確實是一個壞消息。不過，也不完全都是壞消息。直覺告訴我們，隨著申請人數的不斷增加，選中最優秀申請人的可能性將穩步下降。例如，如果采用隨機選擇的方式，在申請人總數為100時，我們得到理想結果的可能性是1%，在總人數為100萬時，可能性就會降到0.0001%。但是，令人意想不到的是，秘書問題的計算結果不會發生變化。如果采用最優停止理論，在100人當中選中最優秀申請人的可能性是37%。而總人數是100萬時，無論你相信與否，你得到理想結果的可能性仍然是37%。因此，申請人總數越多，最優算法理論就越有價值。的確，在大多數情況下，大海撈針都會無功而返，但是，無論“海洋”多么遼闊，最優停止理論都是最理想的工具。
情場上的出手時機
托馬斯 · 馬爾薩斯
兩性之間的情欲幾乎不會隨著時代的變遷而發生改變。在代數學上，我們可以稱之為給定量。
芭芭拉 · 布什
奪走我的初吻的男人后來成了我的丈夫。我把這些告訴孩子們時，他們的反應十分強烈。
卡內基-梅隆大學的運籌學教授邁克爾 · 特里克也曾經為尋覓真愛而苦惱，當時他還是一名研究生。他回憶說：“我突然想起來，人們研究過這個問題，這不就是秘書問題嗎？我身邊有一個空缺，現在有若干人提出了申請，而我的目標就是從中選出最優秀的申請者。”于是，他進行了量化分析。他不知道他一輩子可以結識多少名女性，但是37%法則有一定的靈活性，既可以表示申請者的人數，也可以表示遴選過程持續的時間。假設遴選過程從18歲開始，至40歲結束，那么根據37%法則，在26.1歲時他就應該結束觀察期，隨時果斷出手。碰巧的是，當時的特里克正好處于這個年齡。因此，當他發現某一名女性比之前所有約會對象都優秀的時候，他知道機會來了，于是他果斷行動。他說：“我不知道她會不會是完美的妻子（模型的各種假設都無法幫助我做出這個判斷），但是毫無疑問，她符合算法為這個步驟開出的所有條件。于是，我向她求婚了。”
“結果，她拒絕了我的求婚。”
至少從17世紀開始，愛情問題就已經讓數學家頭疼了。現代人知道約翰尼斯 · 開普勒這個名字，或許是因為他發現行星軌道是橢圓形的，此外他還是“哥白尼革命”的重要成員，與伽利略、牛頓等人一起，顛覆了人類對自己在宇宙中所處位置的認知。不過，開普勒也不是不食人間煙火。1611年，在他的第一任妻子離世后，渴盼重建家庭的開普勒開始了漫長而艱苦的求愛經歷，前后一共交往了11名女性。在前4名交往對象中，開普勒最喜歡第4個（“因為她身材高挑，英姿颯爽”），但是他沒有就此打住。開普勒回憶說：“如果不是愛情和理智把第5名女性強推給我，我應該已經安定下來了。但是，這名女性對我的愛，她的謙恭忠誠、勤儉持家以及她對繼子繼女的愛，一下子征服了我。”
他接著說道：“不過，我仍然我行我素，繼續與其他女性交往。”
親朋好友繼續為開普勒牽線搭橋，開普勒也沒有拒絕，不過興致不是很高，因為他的心仍然被第5名交往對象占據著。在一共交往了11名女性之后，開普勒決定收手了。他回憶說：“就在我準備前往雷根斯堡的時候，我回過頭來去找第5名交往對象并向她求婚，結果她同意了。”于是，開普勒和蘇珊娜 · 羅伊特林格舉行了婚禮。除了第一次婚姻留給他的幾個孩子之外，開普勒和羅伊特林格又生了6個孩子。據說，開普勒之后的家庭生活十分幸福美滿。
開普勒和特里克在尋覓愛情上的親身經歷告訴我們（兩者的結局正好相反），秘書問題把情況想得過于簡單了。在經典的秘書問題中，申請者肯定希望得到那份工作，像特里克那樣遭遇拒絕的情況絕不會發生。此外，申請者一旦被否決之后，就不可以“復活”，因此開普勒采取的策略是行不通的。
在秘書問題首次被提出后的幾十年時間里，人們研究了各種各樣的情境，并結合不同的條件提出了若干最優停止策略。例如，針對可能遭到拒絕的問題，他們提出了一個簡單明了的數學答案：盡早向多名對象伸出橄欖枝。假如遭到拒絕的可能性是50%，那么得出37%法則的那個數學分析過程就會告訴你，遴選過程完成1/4后就應該隨時準備求婚了。如果遭到拒絕，那么在發現下一個最佳人選時要再次求婚，直到求婚成功為止。運用這個策略，獲得成功（即向所有人選中的最佳人選求婚并被接納）的總概率仍然可以達到25%。根據自己的標準尋覓愛情本身就有難度，再加上遭到拒絕這個不利條件，25%的成功概率可以算是一個還不錯的結果了。
開普勒把自己沒有及時出手的原因歸咎于“不安現狀、心存疑慮”。他在一封信中向自己的知己好友哀嘆：“難道非得四處碰壁，所有欲望都落空之后，我的心才會平靜下來，接受命運的擺布嗎？”在這種情況下，最優停止理論同樣可以起到一定的安慰作用。事實證明，不安現狀和心存疑慮并不是道德淪喪或者心理退化的標志，而是在合適情境下捕捉二次機會的最有效策略的一個組成部分。如果可以復活之前被放棄的人選，最優算法就會對我們所熟悉的摸清情況再行動準則做一個小的調整：推遲表態時間，制訂備用計劃。
例如，我們假設即時求婚肯定會被接受，而遲滯求婚則有一半的可能遭到拒絕。根據數學分析，我們在觀察前61%的人選時都不應該表態，等到剩余39%的人選中出現目前最優秀人選時再出手。如果考察完了所有人選之后仍然沒有找到合適對象（開普勒當時就面臨這種情況），就回過頭，在你淘汰的人選當中選擇最優秀的那個。在這種情況下，策略與結果之間再次表現出對稱性，在允許二次選擇這個條件下，你最終選中最優秀人選的概率仍然是61%。
正因為現實與經典秘書問題有所不同，所以開普勒最終還是找到了自己的幸福。事實上，經典問題發生的那個小變化也沒有導致特里克愿望落空。在遭到拒絕之后，特里克讀完大學并在德國找了一份工作。特里克回憶說：“我在酒吧里遇到一位漂亮的姑娘，我們一見鐘情，三周后就同居了。后來，我邀請她去美國‘暫住一段時間’。”姑娘接受了邀請。6年后，他們舉行了婚禮。
掌握候選對象的完整信息
經典秘書問題的前提條件是，即時表態一定會被接受，而遲滯表態肯定會遭到拒絕，但是我們在前面討論的第一組變量（拒絕與復活）則顛覆了這個前提。在這種情況下，最有效的應對辦法沒有任何變化，仍然是：不要急于表態，觀察一段時間后及時出手。
不過，秘書問題的一個更重要的前提，可能會引起我們的異議。在秘書問題中，除了可以相互比較之外，我們對這些申請者一無所知。對于優秀人員應該具有哪些特點，我們無法參考任何客觀標準或者已有標準，而且在比較這些申請者時，我們只能知道孰優孰劣，但是無法了解彼此之間的確切差距。正因為如此，“觀望”階段是不可避免的。在前期階段，我們冒著與優秀人選失之交臂的危險，不斷調整我們的期望值與權衡標準。數學家把這種最優停止問題稱作“無信息博弈”。
這種情境可能與大多數尋租公寓、尋覓伴侶和招聘秘書的情況有天壤之別。假設我們可以參考某種客觀標準。例如，安排所有秘書參加打字考試，然后像美國高考（SAT）、研究生入學考試（GRE）或者法學院入學考試（LSAT）那樣按照百分制統計成績。也就是說，根據得分，我們可以知道每名申請者的打字水平在所有人選中的位置。如果申請者得了51分，則表示她的打字水平略高于平均水平，如果得了75分，則表示她的水平高于3/4的申請者，以此類推。
假設所有申請者可以代表全體人口樣本，而且所有數據沒有受到任何傾向性或者自選擇的影響。同時，假設打字速度是我們判斷申請者是否合適的唯一條件。此時，情況就完全不同了，因為我們擁有數學家所謂的“全信息”。1966年的那篇秘書問題研討會論文指出：“不需要根據積累的經驗設定判斷標準。有時，我們可以立刻做出一個有益的選擇。”換言之，即使得95分的申請者第一個接受評判，我們也可以信心滿滿地立刻與她簽約。當然，前提是我們認為所有申請者中沒有得96分的。
問題來了。如果我們的目標是找到最適合這份工作的優秀人選，那么我們仍然需要小心斟酌，因為其余的申請者當中可能還有更加優秀的人選。不過，既然我們掌握了全信息，就可以直接計算這種可能性到底有多大。例如，下一個申請者得到96分或者更高分的可能性一定是1/20。因此，是否立刻停止的決定取決于還剩下多少申請者沒有接受面試。全信息的意義在于我們無須觀望就可以直接出手。此時，我們可以運用閾值準則，一旦發現某位申請者的分數高于某個值，就立刻接受她，而不需要先考察一批候選人并確定閾值。但是，我們需要密切關注可供選擇的人還有多少。
數學計算表明，如果還有很多人等待面試，那么你就不應該接受當前正在面試的那名申請者，即使她非常優秀，因為你有可能找到一個更優秀的人選。但是，隨著可供選擇的人數不斷減少，你就應該做好準備，隨時準備與優于平均水平的申請者確立雇傭關系。有一句我們都比較熟悉（盡管不是那么鼓舞人心）的話說得好：面對花哨的包裝，還是降低你的期待吧。我們還可以找到另外一句話，用以說明與之相反的情況：天涯何處無芳草，何必單戀一枝花！重要的是，無論是哪種情況，數學都可以告訴我們臨界點到底在哪兒。
在這種情況下，最簡單的方法是從后往前，反過來理解這些數字的含義。如果你一直面試到最后一名申請者，那么你就別無選擇，只能接受他。如果你一直在觀望，那么在面試倒數第二名申請者時你需要考慮的問題就變成了：他的分數是否高于50呢？如果是，就雇用她；如果不是，那么你可以考慮把寶押在最后一名申請者身上，因為她的分數高于50的可能性是50%。同理，如果倒數第三名申請者的高于69，倒數第四名的分數高于78，以此類推，那么你就應該立刻選擇這名申請者。也就是說，剩余的申請者越多，在評判時就應該越挑剔。無論如何，你都不應該選擇低于平均水平的申請者，除非你已經別無選擇。（此外，既然你一定要在這些申請者當中挑出最優秀的，那么如果某名申請者不是目前為止最優秀的人選，就一定不要雇用他。）
在這種全信息版本的秘書問題中，選中最優秀申請者的可能性是58%。這個概率遠談不上十拿九穩，但是已經大大優于無信息博弈中根據37%法則得到的37%的成功率。如果你掌握了所有信息，那么即使申請人數非常多，你多半也會取得成功。
全信息秘書問題中的最優停止閾值
因此，全信息博弈往往會產生令人意想不到，有時甚至會讓人感到奇怪的結果。如果追求的目標是金錢，而不是愛情，則成功的可能性更高。在根據某種客觀標準（例如收入排名情況）評判合作伙伴時，可供使用的信息比較多。如果評判標準是模糊不清的情感反應（“愛情”），則可能需要我們根據經驗以及比較結果不斷做出調整，同時可供使用的信息也相對較少。
當然，選擇對象的“資產凈值”與我們權衡的標準不一定一致。任何標準，只要可以全面反映申請者與其他人對比的情況，就會導致我們棄用摸清情況再行動準則，轉而采用閾值準則，同時我們成功找出最優秀申請者的可能性也會大大增加。
此外，人們還經常修改秘書問題的其他前提條件，使之與現實生活中尋覓愛情（或挑選秘書）等難題更為相似，結果形成了更多的秘書問題變種。不過，最優停止問題給我們的啟發不僅限于約會與招聘這兩個方面。事實上，在租房子、找停車位、見好就收的時機選擇等問題中，我們同樣需要面對一個又一個的可選方案，做出最有利的選擇。從一定程度上說，這些問題已經得到了解決。
賣房子的時機
只需修改經典秘書問題的兩個特征，就可以從浪漫的愛情跳進不浪漫的房地產領域。在前文中，我們說過租公寓的過程屬于最優停止問題，但是真的擁有房產之后，你仍然難免要與最優停止問題打交道。
假設你想賣房子。在咨詢了幾個房地產中介之后，你將粉刷一新、帶有園林景觀的房子推向市場，然后靜等有意者上門。每個看房人提出有意購買時，你基本上都要做出決定，要么接受，要么拒絕。但是，拒絕是有代價的，因為在下一個有意購買者上門之前，你需要再支付一周（甚至一個月）的抵押貸款，而且下一個購買者的報價未必更高。
賣房子與全信息博弈比較相似。我們知道有意者愿意付出的具體金額，不僅可以看出誰報出的價格更高，而且可以看出彼此之間的具體差額。此外，我們還掌握有關房地產市場行情的更多信息，至少可以對預計的報價變化幅度做一個大致的預測。（有了這樣的預測，就相當于掌握了上述打字測試中的信息。）兩者之間的差別在于目標不同。賣房子時，我們的目標其實不是得到最有利的報價，而是通過整個過程最終獲取盡可能多的錢。由于等待是有代價的，是要付出真金白銀的，因此當前的有利報價比幾個月之后略高一點兒的報價更有吸引力。
掌握了這些信息之后，我們就可以省略確定閾值所需的觀望階段，直接確定一個閾值。然后，我們可以忽略所有低于這個閾值的報價，直接接受第一個高于閾值的報價。誠然，如果在某個時間之前不把房子出手，我們有限的積蓄就會消耗殆盡，或者我們只想考慮數量有限的幾個報價，對隨后的報價不感興趣，那么在快要達到極限時，我們當然應該降低標準。（購房者喜歡找“積極的”賣主，原因就在這里。）但是，如果沒有被這兩種情況逼到墻角，那么我們就可以通過成本效益分析，確定是否應該繼續觀望。
接下來，我們分析一種非常簡單的情況：假設我們清楚報價金額的變化幅度，并且在這個變化范圍內各種報價出現的可能性是相同的。只要報價不會中斷（我們的積蓄也不會花完），我們就可以單純地考慮我們對收獲或損失的期望值，以決定是否繼續等待更有利的交易。如果拒絕當前的報價，預計出現更有利報價的可能性是多少？該報價與當前報價之間的差，乘以該報價出現的可能性，乘積是否大于繼續等待的成本呢？數學計算的結果清楚地表明，停止價格是等待成本的一個顯函數。
無論你出售的是價值高達數百萬美元的豪宅，還是搖搖欲墜的棚屋，對這個數學結果都不會有任何影響。你唯一需要關心的是你可能接收到的最高報價與最低報價之間的差值。輸入幾個具體數字，就可以看出這個算法可以提供給我們大量清楚明了的指導意見。例如，假設我們預計報價金額在400000~500000美元之間。首先，如果等待成本非常低，那么在挑選買主時我們幾乎無須有任何顧忌。如果等待下一個報價的成本僅為1美元，那么為了賺取盡可能多的錢，我們可以一直等到有人愿意支付499552.79美元時才出手。少一分錢，我們都不會賣給他。如果每次等待需要付出2000美元的代價，那我們就應該等待480000美元這個報價。如果面對的是一個不景氣的市場，每次等待需要耗費10000美元時，那么只要報價高于455279美元，我們就應該立刻出手。最后，假設等待成本為預計報價范圍的一半（在本例中，報價變化幅度的一半就是50000美元）或更高時，那么觀望對我們來說不會有任何好處，最有利的做法是直接接受第一個報價，然后立刻成交。人在屋檐下，不得不低頭。
在這個問題中，閾值完全取決于搜尋成本，這也是這類問題需要注意的關鍵要點。下一個報價令人心動的可能性（以及搜尋成本）都不會發生任何變化，因此，無論運氣如何，我們在搜尋過程中都無須降低最優停止價格。一旦確定最優停止價格之后（即使這是我們在將房子推向市場之前做出的決定），我們就再也不要有任何動搖。
賣房子問題的最優停止閾值
威斯康星大學麥迪遜分校的優化專家勞拉 · 阿爾伯特 · 麥克萊回憶說，她在賣房子時，就用到了最優停止問題的相關知識。她說：“我們收到的第一個報價就非常高，但是他們希望我們比預計的搬離日期早一個月搬走。這個代價太大了。這時候，又有人報出了一個有競爭性的報價……但是我們一直不為所動，直到最后有人報出了令我們滿意的報價為止。”對很多賣家而言，建議他們拒絕一兩個優厚的報價都會讓他們神經緊張，如果隨后的報價比不上前者，那么他們就會更加緊張。但是，麥克萊很冷靜，堅守立場沒有動搖。她承認：“如果我不知道數學計算的結果，就很難堅持下來。”
在任何情況下，只要你可以得到一系列報價，而尋找或等待下一個報價需要付出一定成本時，就可以應用上述準則。因此，除了賣房子，在很多情況下我們都可以考慮這條準則。例如，經濟學家利用這個算法構建的找工作模型，可以輕而易舉地解釋失業工人與空缺崗位并存這個看似矛盾的事實。
事實上，最優停止問題的這些變種還有一個更令人吃驚的特性。前面說過，在開普勒尋覓愛情的過程中，可以“復活”之前被自己拒絕的機會是一個非常重要的條件。但是，在賣房子或者找工作時，即使我們可以重新考慮之前的報價或工作邀請，即使我們可以肯定那個報價或工作邀請仍然有效，我們也絕不應該重新考慮它。如果之前它沒有達到閾值的要求，那么現在它也不會高于閾值。在拒絕那個報價或工作邀請之后，我們的付出已經成為已支付成本。因此，不要妥協，不要試圖亡羊補牢。堅持住，不要回頭！
最優停車位置
克拉克 · 克爾，加州大學伯克利分校校長（1958—1967年）
我發現，大學校園里有三個主要的行政管理問題：學生關心性愛，校友關心體育，教職員工關心停車問題。
最優停止問題經常出現的另一個領域與汽車駕駛有關（在這個領域，回頭同樣是不明智的）。在某些早期文獻中，秘書問題的主角是駕車者，而汽車只進不退的基本設定把駕車旅行中的所有決策過程（包括尋找飯店、尋找浴室，以及最令城市駕車者頭疼的尋找停車位等過程）全部變成了停止問題。要討論進出停車場的問題，加州大學洛杉磯分校著名的城市規劃教授、被《洛杉磯時報》稱作“停車場搖滾明星”的唐納德 · 舒普顯然是最合適的人選。我們從加州北部出發，駕車前往學校拜訪舒普。我們告訴舒普，我們為這段行程預留了大量時間，讓他不要擔心我們會因為意外的交通情況而無法按時抵達。舒普回答說：“說到針對‘意外的交通情況’制訂計劃，我認為你們應該考慮的是預計的交通情況。”舒普的知名度或許大多歸功于他的著作《免費停車的高昂代價》，此外他還做了大量工作，推動人們討論、了解駕車旅行的真實情況。
我們真應該同情那位可憐的駕駛員。根據舒普的模型，理想的停車位應該在停車位“標價”、行走所需時間及造成的麻煩、尋找停車位所需時間（隨著目的地、一天中的時間不同而發生顯著變化）以及整個過程所消耗的汽油等方面實現優化并達成精確平衡。因為車內乘客人數不同，上述等式會發生變化，因為乘客可以分擔停車費用，但是無法分擔搜尋時間，也無法分擔步行的時間與麻煩。與此同時，駕駛者還需要考慮到的一個問題是：停車位最多的地方可能也是停車需求最大的地方。停車問題含有博弈論的成分，因為在你算計道路上其他駕車者的時候，他們也在算計你。[4]話雖如此，停車難題大多歸根于一個數字，即停車位占用率——目前被占用的所有停車位占總停車位的比例。如果占用率很低，找到一個好的停車位并非難事；如果占用率很高，想為你的車找到一席之地就不是那么容易了。
舒普認為，停車的很多難題都歸因于城市政策，因為這些政策導致停車位占用率極高。如果某個地方的停車費用非常低（更糟糕的是，有的甚至免費），就會刺激人們把車停在那里，而不是停到稍遠的位置，然后步行。于是，大家都想在那兒停車，但是大多數人發現那里已經停滿了車，因此他們只好開著車四處巡游，試圖找到一個停車位，結果既浪費時間，又浪費汽油。
舒普建議的解決辦法是安裝數字停車計時器，根據停車需求自動調整價格。（舊金山市區已經采用了這種計時器。）在設定價格時，需要先設定一個目標占用率。舒普認為，這個目標值應該在85%左右（對于路邊停車率接近100%的大多數大城市而言，這個占用率已經非常低了）。舒普指出，當停車位占用率從90%升至95%時，盡管僅多停了5%的車，但是大家尋找停車位的時間就會翻一番。
一旦意識到停車其實是一個最優停止問題，你就會發現占用率對停車策略有著關鍵的影響。行駛在大街上，每次看到一個空車位時，我們都必須做出決定：是停到這個車位上，還是試試運氣，再往前開一點兒？
假設你行駛在一條無限長的道路上，路邊車位均勻分布，而你的目標是把車停到盡可能接近目的地的車位上，以便少走幾步路。那么你應該采用摸清情況再行動準則。為了實現最優停止這個目標，在距離目的地一定路程之外，即使看到空車位也不要停車；一旦進入一定距離之內，就應該從觀望階段轉變為行動階段，看到空車位后立刻停車。這段距離的長短，取決于停車位可能被占用的百分比，即停車位占用率。下表列出了與某些有代表性的停車位占用率相對應的轉變距離。
表1-2 尋找停車位的最優策略
如果這條無限長的街道與大城市一樣，停車位占用率高達99%，只有1%的停車位是空閑的，那么在距離目的地大約70個停車位（略多于1/4英里[5]）處開始，只要看到空車位，就應該停車。但是，如果舒普的辦法奏效，將占用率降低到85%左右，那么在距離目的地半個街區之前，你都無須著急停車。
我們行駛的道路大多不是筆直的，也不會是無限長的。因此，同其他最優停止問題一樣，研究人員也在上述基本情況的基礎上做出了各種調整。例如，他們考慮了若干不同情況，包括允許駕駛者調頭、距離目的地越近停車位越少、駕駛者與目的地相同的其他駕駛者形成競爭關系等。但是，無論該問題的參數發生哪些變化，增加空閑停車位的數量都可以使我們的生活更加方便。從某種意義上講，這是提示市政府的政策制定者：停車問題不是單純靠增加資源（停車位）并最大化利用資源（占用）就可以解決的。停車還是一個進程（是一個最優停止問題），消耗注意力、時間、汽油，還會導致污染和擁堵等后果。合適的政策可以徹底解決這個問題。而且，適宜居住的街區周圍有空的停車位，可能是街區運行良好的一個標志，這正好與我們的直覺相反。
我們問舒普，他在洛杉磯車流中穿行，前往加州大學洛杉磯分校上班的時候，他的研究是否可以為他提供優化方案。作為一名全世界頂尖的停車問題專家，他是否有什么秘密武器。
舒普還真的擁有一個秘密武器：“我騎車上下班。”
見好就收的時機
1997年，鮑里斯 · 別列佐夫斯基因擁有大約30億美元的財產，被《福布斯》雜志確認為俄羅斯首富。僅僅10年前，他還是蘇聯科學院的一名數學家，靠工資度日。他利用在研究過程中建立的業界關系，創建了一家公司，幫助外國汽車制造商與蘇聯汽車制造商 AvtoVAZ 溝通交流。隨后，他的公司變成了 AvtoVAZ 汽車的大型經銷商，同時還通過分期付款的方法，利用盧布的惡性通貨膨脹牟利。他還利用與 AvtoVAZ 的合作關系套取資金，用來購買這家汽車制造商及俄羅斯公共電視臺、西伯利亞石油公司的部分股份。最終，他賺得了幾十億美元的身家，成為寡頭階層的新成員。隨后，他開始參與政治。1996年，他支持鮑里斯 · 葉利欽連任；1999年，他又支持弗拉基米爾 · 普京成為葉利欽的繼任者。
但是，后來別列佐夫斯基的政治態度開始轉變。普京當選總統之后不久，別列佐夫斯基公開反對普京提出的旨在擴大總統權限的憲政改革。他在公開場合不斷批評普京，導致他與普京的關系開始惡化。2000年10月，在有人請普京就別列佐夫斯基對他的批評發表評論時，普京說：“政府手持大棒，只需一下，就能擊碎其腦殼。目前我們還沒有動用大棒……一旦我們真的動怒，就將毫不猶豫地砸下去。”當年11月，別列佐夫斯基就離開了俄羅斯，再也沒有回來。流亡到英國之后，別列佐夫斯基繼續批評普京。
別列佐夫斯基如何做出離開俄羅斯的決定？是否可以通過數學方法考慮“見好就收”這條建議？多年前，別列佐夫斯基本人就是一名數學家，而且他研究的正好就是最優停止問題，他創作的第一本書（當然也是他的唯一一本書）全部關于秘書問題，因此他當時可能也考慮了這個問題。
人們在分析見好就收這個問題時，為它披上了好幾種偽裝，但是最適合別列佐夫斯基這種情況的可能應該是“竊賊問題”（向俄羅斯寡頭表示歉意）。在竊賊問題中，竊賊可以實施一系列盜竊活動。他們的每次盜竊都會有收獲，并且每次都有機會帶著戰利品順利脫身。但是，一旦被抓住，他們就會失去之前的所有收獲。竊賊希望收獲最大，那么什么樣的算法可以給他提供合理建議呢？
竊賊問題有解，對于盜竊題材的電影劇本而言不是好消息。當盜竊團隊誘惑一位已經金盆洗手的老手，希望他復出并干最后一票的時候，這位狡猾的竊賊只需要認真分析那些數字就知道該怎么做了。憑直覺也可以得出結果。實施盜竊的次數應該大致等于順利脫身的可能性除以被抓的可能性的值。如果你是一名有經驗的竊賊，每次盜竊成功的可能性為90%（損失全部身家的可能性為10%），那么在盜竊9次（90÷10=9）之后，你就應該洗手不干了。如果是一名笨手笨腳、成功率只有一半的生手，情況會怎么樣？第一次去偷盜時，你本來就身無分文，因此無須擔心有任何損失，但是之后就不要再去碰運氣了。
盡管別列佐夫斯基是最優停止問題方面的專家，但是他的結局仍然十分凄慘。2013年3月，一名保鏢在他位于伯克郡的住所里發現了他的尸體。他死在鎖著的浴室里，脖子上系著繩子。官方在尸檢之后宣布他死于自殺。由于他在一系列高調的訴訟案中輸給了俄羅斯對手，也失去大筆財富，因此他走上了上吊自盡這條不歸路。或許他抽身而退的時間還應該更早一些，在積累幾千萬美元的財富之后就應該收手，而且不能介入政治。但是，遺憾的是，那不是他的做事風格。他在數學界的一位朋友里奧尼德 · 博古斯瓦夫斯基，曾經講過別列佐夫斯基的一件往事。當時，他和別列佐夫斯基都還是年輕的研究員。他們前往莫斯科附近，準備進行湖上滑水活動。但是，他們計劃使用的那條船出了故障。戴維 · 霍夫曼在他的《寡頭》一書中有這樣一段文字：
朋友們都跑上沙灘，點起了篝火，只有博古斯瓦夫斯基和別列佐夫斯基向船塢走去，準備修理那臺發動機……三個小時之后，他們已經把發動機拆裝了一遍，但是發動機仍然無法工作。盡管已經錯過了聚會的大多數活動，但是別列佐夫斯基仍然堅持說，他們一定要繼續嘗試修理發動機。博古斯瓦夫斯基回憶說：“我們想盡辦法，試圖修好那臺發動機。”別列佐夫斯基從來不會輕言放棄。
令人吃驚的是，在最優停止的文獻資料中也曾提到過不放棄（而且是永不放棄）。有的時序決策問題似乎沒有最優停止準則，盡管從我們前面討論的大量問題看，似乎不應該出現這種情況。“要么三倍，要么賠光”的博弈游戲就是一個簡單的例子。假設你帶著1美元去玩這個游戲。游戲規則對輪次沒有限制，但是要求你每次都要押上所有的錢，你有50%的機會贏回三倍的錢，另外50%的機會全部賠光。那么你應該參與多少輪呢？盡管這個問題非常簡單，但它沒有合適的最優停止準則，因為每參加一輪游戲，你的平均收益都會略有增加。從1美元開始，你有一半機會贏回3美元，一半機會收回0美元，平均而言，第一輪結束之后，你裝進口袋的現金期望值是1.5美元。那么，如果你在第一輪游戲中運氣不錯的話，第二輪游戲的兩個可能結果就會將你剛剛贏回來的3美元變成9美元或者0美元，也就是說，第二輪的平均收益是4.5美元。數學計算結果表明，你應該一直玩下去。但是，果真如此的話，你最終必將輸光所有的錢。可見，有的問題有解，反而會有損無益。
隨時準備停止
斯蒂芬 · 格雷列特
我的生命只有一次。因此，如果我能做點兒善事，或者可以向人們表示善意，讓我現在就做吧！別讓我拖延，別讓我疏忽，因為我沒有第二次生命！
安妮 · 迪拉德
用掉這個下午吧。你不可能把它帶走。
我們在前文討論了人們在生活中遭遇停止問題的具體實例，很顯然，我們大多數人每天都會遭遇這類問題，只不過表現形式各不相同。生活中最優停止問題無處不在，有時與秘書有關，有時又與未婚夫（或未婚妻）、公寓有關。因此我們難免會想到一個問題：進化、教育或者直覺到底能不能為我們提供最有效的策略？
乍一看，答案似乎是否定的。十幾項研究已經得出了相同的結果，人們往往在更優秀申請者還沒亮相之前就已經草草停止。為了更深入地了解這些研究成果，我們拜訪了加州大學河濱分校的阿姆農 · 拉波波特。他在實驗室里從事最優停止實驗工作已有40多年了。
20世紀90年代，拉波波特與達里爾 · 希爾合作，完成了一項與經典秘書問題關系密切的研究。在這項研究中，人們需要無數次面對秘書問題，每次申請者的人數為40或者80。結果，人們找到最優秀申請者的總成功率相當不錯，大約為31%，與最理想的37%相去不遠。大多數人都遵循了摸清情況再行動準則，但是有超過4/5的人出現了出手過早的情況。
拉波波特告訴我們，他本人在生活中遇到最優停止問題時，都會想到這個現象。例如，在尋租公寓時，他竭力控制自己希望迅速交易的沖動。他說：“盡管我天生是一個急性子，看到第一個公寓就想租下來，但是我還是竭力控制自己。”
但是，這種不耐煩的表現說明經典秘書問題忽略了另外一個需要考慮的因素——時間。別忘了，在你尋覓秘書的全過程中，你沒有秘書可用。此外，你把時間都花在面試上，自己的工作就無法完成了。
在實驗室里解決秘書問題時，停止時機的選擇往往過早，原因可能就在于這種成本。希爾和拉波波特認為，如果我們假設面試每名申請者的成本等于發現最優秀秘書所產生價值的1%，那么最優策略就會與實驗中人們從觀望階段轉變為行動階段的時間選擇正好一致。
令人難以理解的是，在希爾和拉波波特的研究中，尋覓是不需要付出任何成本的。那么，人們在實驗室中的行為為什么與尋覓需要付出成本時一致呢？
這是因為人們認為時間成本一定是存在的，而且時間成本是在人們的真實生活中產生的，與實驗如何設計沒有關系。
因此，尋覓活動的“內在”時間成本（在最優停止模型中通常沒有得到體現）也許可以解釋人類做出的決策通常與模型的描述之間存在差異的原因。研究最優停止的科研人員尼爾 · 比爾登指出：“在尋覓工作持續了一段時間之后，我們人類通常就會感到厭煩，即使理性的人也難以避免。但是，模型很難精確地反映出這個變化。”
不過，這并不意味著最優停止問題的重要性有所降低。事實上，它的重要性不降反升，因為時間的流逝會把所有決策活動變成最優停止問題。
最優停止問題的權威教科書開宗明義地指出：“最優停止理論關注的是如何選擇時機以執行特定行動的問題。”很難想出一種更好的方法，可以簡明扼要地描述人類所面臨的狀況。顯然，我們需要判斷何時應該買進股票，何時應該將這些股票賣出，我們還要決定何時應該打開我們已經封藏了一段時間的葡萄酒，何時應該打斷某人，何時應該親吻某人。
這樣看來，秘書問題最基本同時也最令人難以置信的前提條件——嚴格的連續性，即有進無退的單向行進，正好是時間自身屬性的一個體現。就此而言，最優停止問題的這個顯性前提正好就是使其充滿活力的隱性前提。這個前提迫使我們基于還沒親眼看到的可能結果做出決定，迫使我們在采取最優策略之后仍然愿意接受非常高的失敗率。我們永遠沒有二次選擇的機會。我們有可能得到類似的選擇機會，但是絕不會得到完全相同的選擇機會。猶豫不決（不作為）與行為一樣不可改變。困在單行線上的駕車者與空間的相互關系就是我們與第四維度的關系：我們的生命真的只有一次。
直覺告訴我們，合理的決策需要窮舉所有選擇，逐一權衡，然后從中找出效果最好的那個選擇。但是實際上，在鐘表嘀嘀嗒嗒的聲音中，決策活動（或者更具一般性的思維活動）的其他方面都淡化了，進一步凸顯出停止時機選擇的重要性。
[1]正文加粗字體在本書中指的是算法。
[2]采用這個方案，最優秀申請人落選與得不到面試機會的概率分別是33%和16%。具體來說，三名申請人正好有6種可能的排序，即1-2-3、1-3-2、2-1-3、2-3-1、3-1-2和3-2-1。如果考察第一名申請人并選擇比她優秀的那名申請人，這個方案會在3種情況下（2-1-3、2-3-1、3-1-2）取得成功，在另外三種情況下將得到不理想效果，其中兩種情況（1-2-3、1-3-2）會導致過度挑剔的問題，一種情況（3-2-1）會導致挑選不夠充分的問題。
[3]事實上，應該是略低于37%。準確地說，考察申請人的數學最優比例是1/e，其中 e 是復利計算中經常出現的數學常數，等于2.71828……。但是，如果你記不住 e 的12個小數位，也無須著急。只要這個比例在35%與40%之間，取得最理想結果的可能性就非常接近于最高值。
[4]第11章將詳細討論博弈論計算中的各種風險。
[5]1英里≈1.61千米。——編者注
02 探索與利用 要最新的還是要最好的？
03 排序 建立秩序
04 緩存 忘了它吧
05 時間調度理論 要事先行
06 貝葉斯法則 預測未來
07 過度擬合 不要想太多
08 松弛 順其自然
09 隨機性 何時應用隨機？
10 網絡 我們如何聯系？
11 博弈論 別人的想法
結語 計算善意
閱讀全文: http://gitbook.cn/gitchat/geekbook/5b690598fa9fe34011ed8bcf
總結
- 上一篇： attribute 扩展
- 下一篇： php透明颜色的代码,PHP image