秘書問題

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

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

普遍認為，秘書問題第一次出現在出版物中是在1960年2月，那一期的《科學美國人》雜志在馬丁·伽德納最喜歡的欄目——“趣味數學”專欄中刊登了幾個難題，其中之一就是秘書問題，不過當時沒有明確地提到“秘書”這個詞。但是，這個問題到底從何而來，這是一個非常神秘的謎。除了一些推測以外，初期的調查沒有任何確鑿的結論。隨后，我們風塵仆仆地趕到斯坦福大學，查閱伽德納的文書檔案。伽德納在20世紀中期留下來的那一盒盒書信，出乎意料地把我們的調查變成了偵探工作。閱讀書信有點兒像偷聽別人打電話，你只能聽到通話一方所說的話，因此需要推斷另一方到底說了什么。從這些回信看，大約50年前，伽德納本人似乎正在調查秘書問題的來源。但是，看完這些書信，我們更是一頭霧水了。

哈佛大學數學家弗雷德里克·莫斯特勒回憶說，1955年，他聽同事安德烈·格里森提到過這個問題，而格里森又是從其他人那里聽說的。阿爾伯塔大學的里奧·莫澤在信中說，他曾經在波音公司R.E.加斯克爾的“筆記”中看到過這個問題，而加斯克爾本人則說他是從一位同事那里聽說這個問題的。羅格斯大學的羅杰·平克漢姆稱，他是1955年從杜克大學數學家J.舍恩菲爾德那里第一次聽說秘書問題的，他還說：“我記得，他說他是從密歇根大學的某個人那里聽說的。”

幾乎可以肯定，“密歇根大學的某個人”其實就是梅里爾·弗拉德。盡管在數學界以外幾乎沒有人知道弗拉德，但是他對計算機科學的影響很難被忽略。他把“旅行商問題”（我們將在第8章深入討論）變成了一個廣為人知的內容，還設計了“囚徒的困境”（參見第11章），甚至“軟件”（software）一詞也可能是他造出來的。1958年，他成了已知的第一個發(fā)現37%法則的人，同時他宣稱，他從1949年就開始考慮這個問題了。但是，在說到最初來源時，弗拉德本人提到了另外幾名數學家。

秘書問題是一個近乎完美的數學難題：問題本身表述簡單，解題難度非常高，答案簡潔明了，而影響力又足以讓人產生濃厚的興趣。因此，通過人們的口口相傳，這個問題以燎原之勢在20世紀50年代的數學界迅速蔓延開來。1960年，在伽德納專欄的推波助瀾之下，它又大大地激發(fā)了普通大眾的想象力。至20世紀80年代，秘書問題已經變成了一個研究分支，無數人撰文討論這個問題及與其相關的變體。

至于這個問題是如何與秘書產生聯系的，這是一個非常有意思的過程——每種文化的社會偏愛都會對社會的形式系統(tǒng)產生影響。例如，在我們的心中國際象棋是中世紀歐洲人的象征，但是實際上國際象棋起源于8世紀的印度。15世紀，粗暴的“歐洲化”過程把沙阿（即國王）變成了王，維齊爾（即高官）變成了王后，而大象則成了基督教主教的形象。最優(yōu)停止問題同樣有多種不同化身，每種化身都是當時關注熱點的某種反映。19世紀，最優(yōu)停止問題的典型形式是巴洛克彩票和女性挑選求婚者的行為；20世紀初，常見的表現形式是駕車度假的人挑選賓館、男性選擇約會對象；在官僚作風盛行、男性占主導地位的20世紀中葉，最典型的最優(yōu)停止問題是討論男性老板如何挑選女性助手的問題。第一次明確提出“秘書問題”的是發(fā)表于1964年的一篇論文，自此之后，這個名稱就再也沒有發(fā)生變化。