|
数学家喜欢做决定。周六商场打折，开车去购物，找车位的时候是一有空位就停进去，还是先转半圈，哪怕浪费点时间？是一看到加油站就加油，还是冒险跑更远一点，结果油价还更贵？如果收集球星卡，什么时候该停止整盒瞎买，转而去网上找单张？总之，在只能随机选择的时候，找来找去到什么时候才是个头？这都属于“最优停止问题”，其中最著名的就是“秘书问题”。 作为英明的老板，你决定招个新人。传闻贵司只要优中之优，此言不虚。共有 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 年代起，针对以上每一种方法都有数十篇研究文章。对“最优停止问题”的探索远没有停止，因为它在金融领域有很多（太多）应用。什么时候应该停止不假思索就生搬硬套数学模型的行为呢？这也是一个尚待解答的“最优停止问题”…… 法国亚马逊数学类畅销书  《数学也荒唐》 编者著：杰罗姆.科唐索 译著者：王烈 出版社：人民邮电出版社图灵新知 出版年：2017年8月 该书用20个数学问题，探讨了代数、概率学、统计学、平面几何、图论、拓扑学等主题，分析角度十分独特，语言幽默风趣，内容充实，贴近生活，在意想不到的趣题中探讨数学知识. 本文选自第14章, 已获许可发布此章节, 特此感谢图灵新知的支持! 点击[阅读原文]跳转购买链接. 前言 01 早餐代表我的心 02 照（不）亮你的家 03 瓷砖铺法知多少 04 青梅竹马分披萨 05 如何平分有菠萝、奇异果和樱桃的蛋糕 06 创意桌上游戏 07 挂不上墙的神作 08 认识地球的形状 09 认识宇宙的形状 10 教你数数 11 争霸法国网球公开赛 12 你究竟有几个冷笑话 13 玩转《地产大亨》 14 如何选秘书 15 山无陵，天地合，乃敢与君绝 16 议会席位怎么分？ 17 如何选总统？ 18 走出迷宫 19 盖茨翻煎饼 20 小便器优选法 |
|
|
