最优停止问题：天文学大师开普勒如何处理恋爱问题

文章插图

公司越做越大，该请人写写软文扩大影响了。这次有 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 年代起，针对以上每一种方法都有数十篇研究文章。对"最优停止问题"的探索远没有停止，因为它在金融领域有很多（太多）应用。什么时候应该停止不假思索就生搬硬套数学模型的行为呢？这也是一个尚待解答的"最优停止问题"……

最优停止问题：天文学大师开普勒如何处理恋爱问题｜数学也荒唐( 二 )