这是我的第 200 天分享
全文共约 1800 字，阅读完共需约 5 分钟
前段时间，我看了一本书，叫《算法之美》。书中的第一章，讲的就是37%法则（也叫最优停止理论）。
37%法则是什么意思呢？
假设有一只猴子，面前有100只香蕉。每当它看到一只香蕉，它可以选择要这只香蕉，或者丢弃它（一旦选择丢弃，就不能再捡回来了）。
我们如何帮助这只猴子做出最心仪的选择呢？
（注：今日分享所列举的例子情景，均指的是“要么选择这个，要么放弃这个，无法回头重新选择”）
01 37%法则
当我们遇到这种类似“选择或丢弃”的情景时，总是会犯纠结症，心里想，我到底是该选择这一个，还是再看看下一个呢？万一下一个更差，我该怎么办呢？
这其实就是一种和未知的博弈。
下一个情况如何，我们无法知道。如果直接选择了第一个，我们可能会因为错过大片更好的可能性而一直惦念；如果选择了最后一个，可能它并不是最合适的。
在开头的那个故事里，猴子每看到一个香蕉，心里就想着，下一个一定会更大，于是不断地重复“丢弃”的动作。结果到最后，他拿到的香蕉竟然是最小的。
在备选方案大于两个的情况下，直接选择第一个和最后一个，或许都不是特别明智。
我们可以从样本中，先选择一小部分，作为“参考范围”。从参考范围中，找到一个最优选择。然后把这个选择作为参考值，只要后面的数值，有一个数字比这个大，我们就选择它。
你大概能看出来，37%法则更适用于没有足够时间权衡考虑、必须立刻做出决定的情况。
假设你正在找合适的租的房子。你手里有一系列清单，这些房子都很抢手，只要你选择PASS掉，那么很快就会被别人占有。
为了尽可能地增加自己找到理想公寓的几率，你可以使用37%法则。前37%的房子作为样本范围，从中选择一个分数最高的作为参考值，从下一个开始，只要感觉前面那个参考值好，就直接拿下。
02 为什么是37%？
为什么37%法则叫37%法则，而不是36%法则，或者38%法则呢？这个数字，究竟是怎么来的呢？
在接下来的这一部分，我会用数学语言，向你解释37%的由来。
（前方比较费脑，高能预警！！！）
首先我们要清楚一点，我们要计算的是，前面的“参考范围”取多少，能让我们后续获得较优情况的概率更大。
假设总样本数为 n，前面的参考范围截止点为 k（即前 k 个数据作为参考范围）。
在这里，我们还要引入一个字母，假设在整个数据中，最优解的位置为第 i 个。
字母准备好了，我们就要开始计算啦。
第①步，我们要先找到第一个概率：在[0,i-1]中，较优解恰好在前面“参考范围”的概率为 k/(i-1)。
我来解释一下上面这句话，[0,i-1]中，最优解在前k个中，是为了保证这个较优解正好在参考范围，因此这个较优解，就可以作为参考值。
相反，如果这较优解是在第 k 个值之后（[k,i-1]）出现的，那么最优解就是这个较优解，而不是第 i 个值了。
这就和我们的初衷相悖，因为我们想让第i个值是最优解，这样我们算出来的概率，就是最优解的概率。
为了方便理解，我画了一张示意图，如下。
第②步，最优解的位置恰好在第i处的概率为1/n。我们要把上面的那个概率再乘以一个1/n。因为最优解的位置是随机的，就好像有十个苹果，第i个位置恰好是最大值的概率是十分之一一样。
因此，这个概率描述就进一步丰富：最优解位置在第i处（1/n），且在[0,i-1]中，较优解恰好在前面“参考范围”的概率为（1/n） k/(i-1)*。
这里要记得，i的取值范围不能小于k，因为那样i就只能作为“参考值”而不是“最优解”了。也就是说i的范围应该在[k+1,n]之间。
胜利就在眼前，我们就差最后一步啦！
因为i的位置从[k+1,n]之间有很多，因此我们要对概率做一个累加，公式如下。
当n足够大时，我们可以做一个积分，假设x=k/n，t=i-1。得出的结果如下：
为了找出概率的最大值，我们对x求导数，最后算出，当x=1/e时，P(k)最大（e为数学中一个常数，是一个无线不循环小数，其值约为2.718281828459045）。
1/e的值为0.367879...，因此就约等于37%。
这就是37%的由来。怎么样，你掌握了吗~
以上就是我今天的分享。我是润东，我们一起，向上生长。
参考资料：
-
布莱恩·克里斯汀,汤姆·格里菲斯.算法之美[M],北京:中信出版社,2018
-
https://blog.csdn.net/qq_37822951/article/details/104072409(关于37%法则的公式推导)
网友评论