读书笔记《算法之美》最优停止问题

在完全不知道信息时，如何做出最优的选择呢？数学家给出了完美答案，37%。

什么意思？就是在我们完全不知道信息时，先留出一段时间来收集信息，一旦过了这个时间，出现的比观察阶段还优秀的人，就毫不犹豫的选择他。数学家给出这个观察阶段是整个阶段的37%。这也就是所谓的“摸清情况再行动准则”。

比如，面试时，如果只有一位申请者，那面只能接受他，如果有两名申请者，你成功选到优秀人选的概率都是50%，如果有第三名申请人，情况就一下子变得有意思了。如果随机选择一名申请人，得到理想结果的概率是1/3，也就是33%。但是我们可以取得更理想的结果，而其中的关键就在第二场面试。在面试第一名申请人时，我们没有任何信息——她肯定是目前最优秀的申请人。在面试第三名申请人时，我们没有任何能动性——我们只能将工作机会交给这名申请人，因为我们已经拒绝了其他人的申请。但是，在面试第二名申请人时，我们既掌握了一些信息，又有一定的能动性——我们知道她与第一名申请人相比孰优孰劣，同时我们既可以接受她，也可以拒绝她。如果她比第一名申请人优秀，我们接受她，反之就拒绝她，那么会产生什么样的结果？事实上，在有三名申请人时，这是最理想的方案。令人吃惊的是，在有三名申请人时采用这个方法，与有两名申请人时选择半程最优秀人选的方法相比，效果不相上下。

随着申请人数不断增加，观察与行动之间的分界线正好处在全部申请人37%的位置，从而得出了37%法则：在考察前37%的申请人时，不要接受任何人的申请；然后，只要任何一名申请人比前面所有人选都优秀，就要毫不犹豫地选择他。

事实证明，利用这种最优方案，我们选中最优秀申请人的概率为37%。方案本身与出现理想结果的概率正好相等，这是这类问题表现出来的令人奇怪的数学对称性。

采用最理想的方案也会有63%的失败率，这是一个令人警醒的事实。在面对秘书问题时，即使我们采取了最理想的行动方案，在大多数情况下也会遭遇失败，也就是说，大多数情况下我们都无法选中所有人选当中最优秀的那名申请人。