现在的位置: 首页 > 综合 > 正文

秘书问题

2013年05月21日 ⁄ 综合 ⁄ 共 600字 ⁄ 字号 评论关闭

在概率及博弈论上,秘书问题的描述如下:

  要聘请一名秘书,有n个应聘者.每次面试一人,面试后就要及时决定是否聘化,如果当时决定不聘他,他便举回来.面试后总能清楚了解应聘者的合适程度,并能和之前的每个人做比较.问什么样的策略,才使最佳人选被选中的概率最大.

  这个问题最优解是一个停止规则.在这个规则里,面试官会拒色头k个应聘者(令他们中的最佳人选为应聘者M),然后选出第一个比M好的应聘者.

具体分析如下:

  对于某个固定的k,如果最佳人选是第i个应聘者(k < i ≤ n),要想选中这个最佳应聘者,就必须得满足前i-1个应聘者最好的人在前k个应聘者中,概率为k/(i-1).考虑所有可能的i值,可计算出最佳人选被选中的概率是:

令n趋近无穷大,把x表示为k/n的极限,令t为i/n,上述公式可近似为如下积分:

令P(x)对x的导数为0,解出x,我们得到最优的x等于1/e.从而,当n增大时,最优的k值趋近于n/e,最佳人选被选中的概率为1/e.

1/e大约等于0.37,因而这类问题应参取37%策略,即以备选的人选总数的前37%的人选作为参考

类似的问题:

最大概率选择到"最好女孩"问题

最大概率选择到"最大宝石"问题

启发:抽象问题,分析问题的能力,利用数学知识解决问题.

参考资料:

http://zh.wikipedia.org/wiki/%E7%A7%98%E6%9B%B8%E5%95%8F%E9%A1%8C

 

抱歉!评论已关闭.