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

文章插图

数学家喜欢做决定。周六商场打折，开车去购物，找车位的时候是一有空位就停进去，还是先转半圈，哪怕浪费点时间？是一看到加油站就加油，还是冒险跑更远一点，结果油价还更贵？如果收集球星卡，什么时候该停止整盒瞎买，转而去网上找单张？总之，在只能随机选择的时候，找来找去到什么时候才是个头？这都属于"最优停止问题"，其中最著名的就是"秘书问题" 。
作为英明的老板，你决定招个新人。传闻贵司只要优中之优，此言不虚。共有 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% 的可能选到最优者。