費曼50年前一紙解決“點菜難題”，最近2500人實測結果相差無幾！

在決策理論中，有一類被稱為“最優停止”的經典問題，生活中有很多場景下的決策都和這類問題有關。早在近50年前的一個泰國菜餐廳里，著名物理學家費曼就在幾張草稿紙上解決了選擇菜品的最優問題，但他的草稿一直無人理解。最近一組科學家重新研究了費曼的計算，并進行了一項行為學實驗，證實人們雖然在選擇時不會精準計算，但最終的決策結果十分接近最優策略。

撰文 | 一根弦

四十多年前的一個謎題

時間回到 1970 年代末的加州格倫代爾，費曼和他的朋友拉爾夫·萊頓（Ralph Leighton，注[1]）一起進入了一家叫 Indra 的泰國菜餐館。他倆是這家餐廳的常客。

圖1. 拉爾夫·萊頓（左）和理查德·費曼（右），兩人在表演無實物打鼓。｜圖源：圖瓦之友協會。

在點餐時，萊頓犯了“選擇困難癥”：是繼續點自己最喜歡的姜汁雞（Ginger Chicken），還是解鎖菜單上其他的菜品呢？這家餐廳的姜汁雞發揮向來穩定，吃它絕對不會踩雷。可萬一菜單上還有更美味可口的菜品呢？每次都吃姜汁雞那豈不是很虧？[1]

大部分人直覺上會選擇“前半程探索（exploring），后半程利用（exploiting）”，也就是說，剛開始先去嘗試不同的菜品，根據前面探索的結果，選擇一個自己覺得最好的菜品。

顯然，費曼不滿足于這樣感性的直覺，他希望用嚴謹的數學來回答這個問題：當探索到什么時候，就可以不再繼續冒險能做到最優解？

文獻[2]的附錄）；如果之前所有嘗過的菜品分數都沒超過閾值，則繼續嘗試新菜；若有菜品分數超過這個閾值，則不再嘗試，直接選擇已經嘗試的菜品中分數最高的那個。

圖2. 理查德·費曼“餐廳問題”的手寫筆記，最后一張框住的部分即答案。｜圖源：參考文獻[2]

這幾頁涂鴉似的草稿被萊頓保存了下來，在2000年時萊頓還整理出來并給出自己的理解，但并未引起關注。直至近些年，幾位對此感興趣的科學家破譯了這幾頁塵封的手稿，在潦草的筆跡中發現費曼提出并解決的餐廳問題正是決策理論中的最優停止問題（Optimal Stopping problem）[2]。

最優停止問題

最優停止問題是決策理論中的一類經典問題，在這類問題中最被人津津樂道的是秘書問題（Secretary Problem）或者相親問題（Marriage Problem）（《返樸》之前的文章里就曾介紹過，見《相親結婚，數學教你找到最佳伴侶》）。

一個更通俗的表述是“尋找最大玉米問題”：假設這片地里一共有 n 個玉米，且每個玉米的大小各不相同，決策者只能向前走，不能回頭，全場只能摘一次。那么，如何才能挑選到最大的那顆玉米？最優答案和自然底數e有關：先觀察前37%（1/e）的玉米不摘，之后一旦遇到比前面都大的玉米就立刻摘下。這個策略能保證決策者摘到最大玉米的概率是最高的。

相傳這個問題最初由運籌學先驅梅里爾·弗洛德（Merrill M. Flood；他合作提出囚徒困境模型）口頭提出，并在1950年代數學界流行。1960年，數學科普大家馬丁·加德納（Martin Gardner）在其《科學美國人》專欄上公開了這個問題，命名為Googol游戲。在60年代，該問題及延伸變體已作為嚴肅數學問題討論（詳細的歷史探源可見文獻[3]）。

因此，費曼很可能早就知道這個數學游戲，也很可能知道數學家早已給出了答案，所以沒將他的餐廳問題發表。他的初衷或許只是想幫助好朋友解決一個生活上的小困擾罷了，這也很符合他的人設，“看我露一手”（就不必在數學家面前顯擺了吧）。

在費曼提出的原始問題中，研究對象是同一個餐館里面的不同菜品；為了更方便設計行為學實驗，研究人員把研究對象改成了同一座城市的不同餐館，每晚去一個（顯然這不會影響問題的本質），并把這個問題命名成“費曼餐廳問題”。費曼餐廳問題雖然和秘書問題同屬最優停止問題，但存在三點本質的區別：

• 餐館所服從的分布是已知的；
• 用餐者可以返回之前去過的餐館 ；
• 其目標是在多個夜晚中最大化總得分，而不是找出單個最佳選項的概率。

為了更加形象地說明兩者的區別，拿相親問題打個比方：相親者僅有一次選擇機會，而且不能回頭（“好馬不吃回頭草”），一旦選擇后就不能反悔（不能再選其他候選人了），相親者所需要做的是保證自己的選擇是最優解。在費曼餐廳問題中，相親者有多次選擇機會，而且還可以回頭，他的目標是在整個相親過程中選擇到最佳的。

換句話說，相親者是個務實派——目的性很強，擇一人而終老；費曼餐廳問題中的相親者則是個妥妥的體驗派，充分享受整個過程。

在費曼原始的問題中，他把餐廳菜品分數的分布設定成了均勻分布。研究人員把這種分布推廣到了另外三種分布（指數分布、冪分布和三角分布）上，并且給出了四種分布下閾值的解析解。當然，科學家在均勻分布下計算得出的閾值和費曼在40多年前計算出來的結果完全相同。

圖3. （左）不同餐廳評分分布函數圖，（右）不同分布下理論計算出來的閾值隨著剩余嘗試次數減少的閾值曲線。橙色代表均勻分布，藍色代表指數分布，綠色表達冪分布，紫色代表三角分布。｜圖源：參考文獻[2]

從圖3不難看出，無論哪種分布，閾值并非定值，而是會隨著決策次數（橫坐標的“Night Remaining”可理解成剩余的嘗試次數）的減少而降低。這也符合常理——當可選次數不斷減少時，人們會適當下調自己預期，以便做出一個更穩定的選擇。還是拿相親作為例子，當年齡逐漸增加，理性告訴我們需要下調自己的擇偶標準，否則可能會孤獨終老。

盡管按照科學家們給出的閾值來做決策可以達到最優解，可問題在于，一般人在做決策時不太可能用概率論精準地計算一通，那么他們的行為會遵循什么樣的規律？會和從理論上推導出來的規律接近還是相差甚遠？

行為學實驗

為了得到一般人的決策策略，研究者通過Prolific在線平臺招募了2520位志愿者參與實驗，年齡從18歲到94歲不等，平均40.4歲，其中53.2%是男性，46.6%是女性，還有剩下0.2%不愿意透露性別。

在實驗開始時，被試者被告知了一個虛擬場景：他們將要在一座陌生城市生活一段時間，每晚都需要選擇一家餐廳用餐。每家餐廳都有一個固定的質量評分，但在光顧前無法得知具體分數。只有嘗試過某家餐廳后，才會知曉其評分并記錄下來，之后可以隨時再次選擇該餐廳。被試的目標是在有限的停留時間內獲得盡可能高的總評分。

不同被試接觸到的餐廳評分來自不同的概率分布（均勻分布、指數分布、冪分布或三角分布），但這些分布經過處理后具有相同的平均值（50分）。實驗階段，不同測試組的被試者需要在7晚、14晚或28晚的時間（相當于總的訪問次數有7次、14次和28次）內連續做出餐廳選擇。總結來說，2520個被試者按照餐廳評分概率分布（4種情況）和總嘗試次數（3種情況）分成了12組。

在正式實驗前，研究者先向他們展示了84個隨機抽取的餐廳評分樣本。通過觀察這些樣本，被試者可以對餐廳評分的分布特征形成初步認識。

在正式實驗階段，每到一個晚上，他們都面臨兩種選擇：要么嘗試一家從未去過的新餐廳（探索），從而發現一個新的評分；要么返回目前已經發現的最佳餐廳（利用），獲得已知的最高收益。如果不按照這個規則做，比如在某個夜晚去了一家之前訪問過的餐廳，但這家餐廳不是已知最高評分的，那么被試者將會被警告或者被踢出局。

整個過程中，被試者不斷在繼續尋找更好餐廳的可能收益與穩定選擇已知優質餐廳之間進行權衡。研究者記錄了被試者在決策節點上的選擇行為，并分析他們何時停止探索、轉而持續利用已發現的最佳餐廳。

研究人員使用Logistic模型擬合了被試者的閾值曲線，發現：在模擬真實場景中，人們的閾值是線性下降的，不同的評分分布和不同的嘗試次數影響的是線性函數的斜率和截距（參見圖4）。

圖4. 根據被試者行為擬合出的閾值曲線，可以看到統計意義上人們采用了線性的閾值策略。｜圖源：參考文獻[2]

圖4里還展示了一個很有趣的現象：在任務開始階段，被試者的閾值被拉得非常高，這就是顯著的“早期探索偏向”（early exploration bias）。具體而言，被試者在最初幾輪決策中的探索傾向顯著高于總體的線性閾值，即使已經發現了質量較高的餐廳，他們仍傾向于繼續嘗試新的選項，而不是立即轉向保守。

這種“早期探索偏向”可以通過在線性閾值模型中加入一個隨時間指數衰減項后得到很好的擬合。這表明，在決策初期人們會額外賦予探索行為更高的價值，希望獲取更多信息，這種探索動機會隨著時間的推移而快速減弱。這也是常說的好奇心驅動。

線性閾值策略看起來如此的簡單，使用這種策略和理論推導出的最優策略相差多少呢？

出乎意外的是，被試者們所使用的看似非常簡單的線性閾值規則，獲得了與最優策略幾乎相同的收益——最優線性閾值策略的收益通常超過理論最優收益的95%以上。也就是說，如果精密的理論最優收益是100分的話，人們在試驗中不經過精細推導使用的線性閾值策略也能拿到95分以上的好成績。人們并不需要執行復雜的最優計算，只需遵循一種簡單、容易實施的經驗規則，就能夠獲得接近理論最優的結果。

當然，研究人員也在文章中承認，實驗中預設條件是比較理想化的。比如，餐廳評分總是一成不變的；被試者通過一次訪問就可以精準地知道餐廳的評分（現實生活中很難做到這一點）；在選擇餐廳的時候沒有考慮交通成本、時間成本、金錢成本，等等（日常生活中人們選擇餐廳，餐廳評分只是參考項之一，餐廳的距離、人均消費等因素往往對選擇起到關鍵作用）。此外，為了避免多次實驗對數據的影響，研究人員只允許被試者進行一次決策序列。換句話說，這項研究沒有把被試者的學習曲線考慮在內。盡管如此，上述這些限制都不影響這項研究本身深刻揭露了人們依靠直覺而非進行數學推導而做出策略的準確性。

結語

近50年前，費曼提出了餐廳選擇問題并使用簡單的模型進行了推算。多年過去，研究者使用概率論證實了費曼的結果，而真實情況下人們采用的是線性閾值策略，兩者差異并不大。這種簡單啟發式雖然偏離理論最優，卻能夠以極低的認知成本獲得幾乎接近的收益。

這項研究可以給我們一些慰藉：或者我們不像諾貝爾物理學獎獲得者一樣聰明，但憑借直覺選出來的餐廳也不會太差。

注釋

[1] 拉爾夫·萊頓（Ralph Leighton），1949年出生，美國傳記作家，也是物理學家理查德·費曼的朋友，他與費曼合著了《別逗了，費曼先生！》。萊頓還是一名業余鼓手，“圖瓦之友”團體的創始人。1991年，他出版了《理查德·費曼的最后旅程》（Tuva or Bust! Richard Feynman's Last Journey）。他的父親羅伯特·萊頓（Robert Benjamin Leighton，1919-1997）是加州理工的物理學教授，費曼的同事，也是著名《費曼物理學講義》的作者之一。

參考文獻

[1] Davide Castelvecchi,Feynman solved the ‘restaurant dilemma’ 50 years ago — now a study confirms his mathematics,https://www.nature.com/articles/d41586-026-00821-4

[2] Brian Christian, Evan M. Russek and Thomas L. Griffiths,Resolving Feynman’s restaurant problem reveals optimal solutions and human strategiesProc. Natl Acad. Sci.USA123, e2509612123 (2026).https://www.pnas.org/doi/epdf/10.1073/pnas.2509612123

[3] Thomas S. Ferguson. Who Solved the Secretary Problem?. Statist. Sci. 4 (3) 282-289, August, 1989. https://doi.org/10.1214/ss/1177012493

作者簡介

一根弦，中關村文理學院非優秀畢業生。博士期間主業發展原子核集體激發態理論，副業打聽八卦新聞。因帝都房價高企加上錯信IT高薪傳聞，誤入碼農行列，逃離北京來到卷都杭州。除全職工作外，分別在知乎以“一根弦”和在B站以“一根弦肥二”的網名挖掘和寫作物理學家，并以此為樂。

特 別 提 示

『返樸』提供按月檢索功能。關注公眾號，回復四位數組成的年份+月份，如“1903”，可獲取2019年3月的內容目錄，以此類推。

版權說明：歡迎個人轉發，任何形式的媒體或機構未經授權，不得轉載和摘編。