秘書問題

秘書問題(類似名稱有相親問題、止步問題、見好就收問題、蘇丹的嫁妝問題、挑剔的求婚者問題等)內容是這樣的:要聘請一名秘書,有n人來面試。

秘書問題,解決方法,

秘書問題

每次面試一人,面試過後便要即時決定聘不聘他,如果當時決定不聘他,他便不會回來。面試時總能清楚了解求職者的適合程度,並能和之前的每個人作比較。問憑什麼策略,才使選得到最適合擔任秘書的人的機率最大?

解決方法

基本解決策略如下:對於某些整數r,其中1≤r<n。先面試首r人,都不聘請他們,在之後的n-r人中,如果任何一人比之前面試的人都更佳,便聘請他。
r的最佳值應該是r≈n/e≈0.368n。其中e是自然對數的底。基於這個r值得到最佳選項(如例中的“秘書”)的成功率是1 / e (大約 36.8%)。
此問題的變化包括:
選擇者可選多於一人
求職者的數目未知
求職者之間的關係可影響選擇
被拒絕的求職者有一定機率能被叫回來
選擇者滿足於次好的人

相關詞條

熱門詞條

聯絡我們