在機率及賽局理論上,秘书问题(Secretary problem),类似的名称有相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题等,屬於最佳停止問題(英语:Optimal stopping)。内容是这样的:要聘请一名秘书,有 n 个应聘者。每次面试一人,面试后就要及时决定是否聘他,如果当时决定不聘他,他便不会回来。面试后总能清楚了解应聘者的合适程度,并能和之前的每个人做比较。问什么样的策略,才使最佳人选被选中的概率最大。
求解最优策略编辑
这个问题的最优解是一个停止规则。在这个规则里,面试官会拒绝头 r - 1 个应聘者(令他们中的最佳人选为 应聘者 M),然后选出第一个比 M 好的应聘者。可见最优策略包含于这个系列的策略中。(如果M在所有n个应聘者中也是最好的一个,那么这个策略将选不出任何人选)对于任意的截断值 r,最佳人选被选中的概率是:
求和符号内概率的计算是基于:如果应聘者 i 是(所有应聘者中的)最佳人选,他被选中当且仅当头 i - 1 个应聘者中的最佳人选处在头 r - 1 个被拒绝的应聘者中。令 n 趋近无穷大,把 x 表示为 r/n 的极限,令 t 为 i/n,dt 为 1/n,总和可以近似为如下积分:
令 P(x) 对 x 的导数为 0,解出 x,我们得到最优的 x 等于 1/e。从而,当 n 增大时,最优截断值趋近于 n/e 最佳人选被选中的概率为 1/e。
秘書問題, 在機率及賽局理論上, 秘书问题, secretary, problem, 类似的名称有相亲问题, 止步问题, 见好就收问题, 苏丹的嫁妆问题, 挑剔的求婚者问题等, 屬於最佳停止問題, 英语, optimal, stopping, 内容是这样的, 要聘请一名秘书, 个应聘者, 每次面试一人, 面试后就要及时决定是否聘他, 如果当时决定不聘他, 他便不会回来, 面试后总能清楚了解应聘者的合适程度, 并能和之前的每个人做比较, 问什么样的策略, 才使最佳人选被选中的概率最大, 求解最优策略, 编辑这个问题的. 在機率及賽局理論上 秘书问题 Secretary problem 类似的名称有相亲问题 止步问题 见好就收问题 苏丹的嫁妆问题 挑剔的求婚者问题等 屬於最佳停止問題 英语 Optimal stopping 内容是这样的 要聘请一名秘书 有 n 个应聘者 每次面试一人 面试后就要及时决定是否聘他 如果当时决定不聘他 他便不会回来 面试后总能清楚了解应聘者的合适程度 并能和之前的每个人做比较 问什么样的策略 才使最佳人选被选中的概率最大 求解最优策略 编辑这个问题的最优解是一个停止规则 在这个规则里 面试官会拒绝头 r 1 个应聘者 令他们中的最佳人选为 应聘者 M 然后选出第一个比 M 好的应聘者 可见最优策略包含于这个系列的策略中 如果M在所有n个应聘者中也是最好的一个 那么这个策略将选不出任何人选 对于任意的截断值 r 最佳人选被选中的概率是 P r i 1 n P applicant i is selected applicant i is the best P applicant i is the best i 1 r 1 0 1 n i r n P the best of the first i 1 applicants is in the first r 1 applicants applicant i is the best 1 n i r n r 1 i 1 1 n r 1 n i r n 1 i 1 displaystyle begin aligned P r amp sum i 1 n P left text applicant i text is selected text applicant i text is the best right times P left text applicant i text is the best right amp left sum i 1 r 1 0 times frac 1 n right left sum i r n P left left begin array l text the best of the first i 1 text applicants text is in the first r 1 text applicants end array right text applicant i text is the best right times frac 1 n right amp sum i r n frac r 1 i 1 times frac 1 n quad quad frac r 1 n sum i r n frac 1 i 1 end aligned nbsp 求和符号内概率的计算是基于 如果应聘者 i 是 所有应聘者中的 最佳人选 他被选中当且仅当头 i 1 个应聘者中的最佳人选处在头 r 1 个被拒绝的应聘者中 令 n 趋近无穷大 把 x 表示为 r n 的极限 令 t 为 i n dt 为 1 n 总和可以近似为如下积分 P x x x 1 1 t d t x ln x displaystyle P x x int x 1 frac 1 t dt x ln x nbsp 令 P x 对 x 的导数为 0 解出 x 我们得到最优的 x 等于 1 e 从而 当 n 增大时 最优截断值趋近于 n e 最佳人选被选中的概率为 1 e 对于较小的 n 值 最优的 r 也可以通过动态规划方法得到 下表给出了一些最优的 r 值 n 1 2 3 4 5 6 7 8 9r 1 1 2 2 3 3 3 4 4P 1 000 0 500 0 500 0 458 0 433 0 428 0 414 0 410 0 406此問題的变种 编辑選擇者可選多於一人 求職者的數目未知 求職者之間的關係可影響選擇 被拒絕的求職者有一定機率能被叫回來 選擇者滿足於次好的人參考 编辑譯自本頁英文版 T S Ferguson Who solved the secretary problem Statistical science volume 4 pp 282 296 1988 數學傳播第二卷第三期 海外學人相親記 1 页面存档备份 存于互联网档案馆 本版未標示充足內容請見英文版 取自 https zh wikipedia org w index php title 秘書問題 amp oldid 74903492, 维基百科,wiki,书籍,书籍,图书馆,