首页 趣味数学故事正文

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

xiawuyouke 趣味数学故事 2022-02-23 09:12:51 2760 10

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

数学家喜欢做决定。周六商场打折,开车去购物,找车位的时候是一有空位就停进去,还是先转半圈,哪怕浪费点时间?是一看到加油站就加油,还是冒险跑更远一点,结果油价还更贵?如果收集球星卡,什么时候该停止整盒瞎买,转而去网上找单张?总之,在只能随机选择的时候,找来找去到什么时候才是个头?这都属于"最优停止问题",其中最著名的就是"秘书问题"。

作为英明的老板,你决定招个新人。传闻贵司只要优中之优,此言不虚。共有 N(此数目已知)人来参加面试,面试顺序随机。每次面试之后,你只有两个选择:要么聘用此人,面试结束;要么请其回家,老死不相往来。要注意,两个选择必择其一。如果到最后也没有找到满意的人选,则必须聘用最后一人。万万不可让平庸之辈混进公司啊!那么问题来了:想让雇到精英的机会最大,该何时终止甄选呢?

选择的标准其实只有一个:此人比之前的候选人都好吗?我们假设所有候选人可以从优到差排序,且没有资质并列的情况。选到最优者的机会如何能达到最大呢?

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

A、B、C、D 这个 4 人看了招聘启事后,前来应聘数字项目主管的职位。他们的资质参差不齐:A 一般,B 良好,C 优秀,D 则是顶级。作为招聘者,你的目标就是把 D 招进来。

面试顺序随机,共 24 种可能:

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

即 4! 种排列

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

第一种策略是先到先得,不管其他人(即策略 0),选到最优者的概率为 1/4。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

策略0 - 先到先录取时, 录取 D 的所有可能

另一种同样莫名其妙的策略是把所有人都面试一遍,但就要最后一人(策略 3),选到最优者的概率也是 1/4。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

策略 3 - 只录取最后一个人时, 录取 D 的所有可能

但成功概率可以高过 1/4,没想到吧。可以先面试 1 人了解一下大致水平,但这人肯定不要,仅供参考,一出现比他水平高的就直接要了(策略 1)。

这种方法真的比策略 0 和策略 3 好吗?我们来分情况讨论,看选到最优者 D 的概率有多高。

● 第一个面试的是C:唯一比C强的就是D,D一出现就会被录取,有6/24的可能性。

● 第一个面试的是B:此时,C和D谁先出现,谁被录取。在24种可能中,B为第一有6种:BACD、BADC、BCAD、BCDA、BDAC和BDCA,只有3种情况会选到D,所以最终选D的可能性有3/24。

● 第一个面试的是A:此时,第二个面试者会被选中。经过检验发现,只有2/24的可能性会选到D。

● 第一个面试的是D:那就把他淘汰了,认倒霉吧。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

策略 1 - 参考第一个的水平, 然后马上录取时, 录取 D 的所有可能性

最终,按此法,有 11/24(即 46%)的可能性选到最优者。另外可知,选到 C 的概率为 7/24,选到 B 的概率为 4/24,选到 A 的概率为 2/24。

此策略的要点是放过第 1 人,只作参考。那放过更多人,成功概率会不会更高?比如前 2 人都不要(策略 2),如果第 3 人比前 2 人都好,就要第 3 人,否则只能选第 4 人。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

策略 2 - 参考前两名的水平, 然后马上录取时, 录取 D 的所有可能性

此时,如果前 2 人是 AC、BC、CA 或 CB,D 肯定中选。如果前2 人是 AB 或 BA,只有一半情况会选中 D。如果 D 是前 2 人之一,则被淘汰。由此可得 D 被选中的概率为 10/24(即 42%),而 C 被选中的概率为 6/24,B 和 A 被选中的概率只有 4/24。

放弃 k 个人,选择其后第一个比 k 个人都强的候选人,这样的策略称为"策略 k"。上文已验证,总数 N = 4 时,最佳策略是策略 1,约有 46% 的可能选到最优者。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

公司越做越大,该请人写写软文扩大影响了。这次有 5 人来面试,顺序依然随机,共 120 种。对每一种排列方式考虑策略 0 到策略 4, 看看哪种最好。

最后可知策略 0 和策略 4 都只有 20% 的成功率,而放弃第 1 人(策略 1)会将成功率增加到 41.7%。策略 2 最佳,成功率为 43.3%。策略 3 的成功率只有 35%。这些都交由读者去验证吧,推理或枚举都可以。总之,最佳策略是放弃前 2 人。

如果面试人数更多呢?肯定有最佳策略,是哪一个?能找出来吗? 完全可以!

已知 N = 4 时,最佳策略为策略 1,N = 5 时,最佳策略为策略 2。经过验证还可发现,N = 6 和 7 时,最佳策略依然是策略 2,N = 8、9 和 10 时,最佳策略是策略 3。推而广之,可以证明 A 对于 N 个候选人, 策略 k(k > 0) 的成功概率为:

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

当 N 值较小时,我们毫不费力就能算出哪个是最佳策略(图 14.1)。

实际上,有一种简单的算法,可以算出任意(足够大)N 值的最佳策略是策略 N/e。这里的 e 是自然常数,即自然对数的底数,这是最重要的数学常数之一[1],约等于 2.71828,许多数学领域都要用到它, 我无法一一列举。N 足够大时,策略 N/e 选到最优者的概率在 36.8% 左右(即 1/e)。

[1] 数学界为了 e 和 π 哪个才是最重要的数学常数争论不休。还有人推举虚数单位 i 或者整数 0,但这两个常数的影响力较小。唯一确定的是,大家都嘲笑黄金比例 φ 的拥戴者。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

图 14.1 不同策略的成功概率

当 N = 5、10 和 50 时,不同策略的成功概率不同。用积分可以证明,N 越大,策略 k 的成功概率越接近 P(N , k ) = (k/N)ln(N/k),即图中橙色曲线所示。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

假如你要招聘一个会计,有 10 万人来面试,根据以上理论应该采用策略 100000/2.71828 = 36 788,即面试前 36 788 人,但不录取,仅作参考,待到之后出现比这 36 788 人都好的候选者时,就直接录取。这时,你选到 10 万人中最优者的概率约为 36.8%。

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐

当了一回人力资源经理,是不是很过瘾?"最优停止问题"最早出现在 1960 年 2 月号的《科学美国人》杂志中。马丁·加德纳在其专栏"数学游戏"中提出了一种"古戈尔游戏":玩家在 100 张纸上随便写下一些数字,正面朝下让另一玩家猜;这些数字可大可小,可能大如古戈尔(查看第10章 教你数数),即 10^100,游戏由此得名;第二个玩家一页页翻,觉得找到最大数时就停止。

"古戈尔游戏"的最佳策略与之前讨论的一样,如果有 100 张纸, 则应采取"策略 36"。加德纳在下月的专栏中就公布了这个解。

"最优停止问题"还有很多其他名称,如"结婚问题"——花花公子让女生一个个从面前走过,从中选一个做妻子,此外还有"嫁妆问题""选美问题"等,总是有些歧视女性的倾向……

这风气的源头可追溯到 17 世纪。德国天文学家开普勒的第一任妻子死于霍乱,他决定再娶一个,又不想要之前那样的包办婚姻,于是就组织了史上最漫长的相亲。2 年内共有 11 位女性回复他,开普勒仔细比较了每个人的优缺点,最后娶了苏珊娜·罗伊廷厄。她是 11 位候选人中的第 5 位,二人婚后生了 7 个孩子。实际上,不能说开普勒提出了"秘书问题",大部分假设他都没有遵守,而且他还可以反悔。但开普勒处理恋爱问题的方式,让他成了"最优停止"的先驱。

"秘书问题"的模型并不切实际,称职的人力资源经理事先知道要找什么样的人,而应聘的总人数也许不能预知。面试需要时间,而时间就是金钱,不仅要找到最优者,还要避免拖拉。错过就不能反悔? 只要候选人还未另谋高就,当然可以反悔。人力资源经理还可降低预期标准,不一定非要追求完美,在最优的两者之间择其一即可。

数学家对于好问题总是不厌其烦。从 20 世纪 60 年代起,针对以上每一种方法都有数十篇研究文章。对"最优停止问题"的探索远没有停止,因为它在金融领域有很多(太多)应用。什么时候应该停止不假思索就生搬硬套数学模型的行为呢?这也是一个尚待解答的"最优停止问题"……

最优停止问题:天文学大师开普勒如何处理恋爱问题|数学也荒唐


版权说明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

本文链接:http://www.allfloor.org/38666.html

发表评论

评论列表(10人评论 , 2760人围观)
  • 2022-04-17 00:04:52

    铰惨礁在2022年4月17日0时4分50秒发表了广东专升本http://www.sdzsb8.cn/sbrx/166.html

小学趣味数学题及答案_教案「免费下载」_小故事-阿尔法趣味数学网

http://www.allfloor.org/

|

Powered By Z-BlogPHP 阿尔法趣味数学网