模型描述

最优停止问题又称为秘书问题，相亲问题，衍生出了 37% 法则。

一组数据在单向流动过程中，你希望选择这组数据中较好的一个，但是这组数据一旦流动经过你的眼前，你需要在这一瞬间选取它或者让数据继续流动等待选取下一个数据，一旦你选取了这个数据，那么这一组数据就会消失，也就是不能更换已经做出的选择。

当我们在完全不了解这一组数据的情况下，我们在何时做出数据选取才能保证自己选取的数据总是比较好的呢？或者说我们在哪一个点做出反馈才能保证我们始终占有优势呢？

算法解析

假如程序员 abcnull 在 2020 年会遇到妹子 A，在 2021 年会遇到妹子 B，在 2022 年会遇到妹子 C，假设 abcnull 一生只会遇到这三个能让他心动的妹子，他该如何选择才能选到那个最好的老婆呢？

A，B，C 三个妹子都是随机的，所以 abcnull 随便选择的话，选到那个最好的妹子的概率是 1/3，选到最差的妹子也是 1/3，选到一般般的妹子还是 1/3

可惜 abcnull 是一名不喜欢不确定因素的程序员，他喜欢可控的事物，因此他打算采用一种自己可掌控的策略，这种策略如下：

2020 年遇到 A 时，不选她，在 2021 年遇到 B 时，观察 B 是否比 A 要更优秀，如果是就立马决定是她，若不是就只能等到 2022 年直接选择 C 了。

采取这种策略通过排列组合我们会有如下发现：（加粗表示采取上述策略之后的最终选择）

A(good) B(middle) C(bad)

A(good) B(bad) C(middle)

A(middle) B(good) C(bad)

A(middle) B(bad) C(good)

A(bad) B(good) C(middle)

A(bad) B(middle) C(good)

这样我们会发现，abcnull 选到最棒的女孩的概率是 1/2，选到次一点的女孩的概率是 1/3，选到最差的女孩的概率是 1/6，这种选择策略可比瞎选要好多了，因为瞎选可是有 1/3 的概率选择到最差的女生

按照这种策略，我们需要把人数稍微推广一下，因为 abcnull 这一生遇到的妹子可远比 3 人要多的多呢！我们采用排列组合的知识然后稍微做个统计：

abcnull 一生遇到心仪对象的人数	选到最棒的人的概率
3	50%
4	45.83%
5	43.33%
6	42.78%
7	41.43%
8	40.98%
9	40.59%
10	39.87%

可以看到随着 abcnull 一生遇到的妹子越多，他按照此策略选到的妹子的概率就越小。他是接近线性的吗？答案是否定，它是一条有下界的曲线，有工具的同学可以用 MATLAB 作图，也可以用 excel 做一个散点图分析一波，这里直接采用了在线作图工具，绘制了 10 个点如下所示：

数据还是不够多，不过也能看出近似是一条曲线，排列组合求这个最优解的概率太繁琐了，后续的数据我们打算使用高等数学的知识计算，测到 10000 人时已经近似是 37%。

现在我们已经知道了随着 abcnull 遇到的人数增加，他选到最棒的妹子的概率大约是 37%（实际上还要低一点），那他最好从前多少个人开始就需要做选取的决定呢？

现在我们打算 abcnull 这一生会遇到 n 个可爱的妹子，他先观察前 k 个妹子管她是白富美还是土肥圆全都直接 pass，从 k+1 人起，一旦遇到一个比前 k 个都赞的女孩就果断选择她，下面开始计算：

P(k) = 1/n × k/(n-1) + 1/n × k/n + 1/n × k/(n+1) + ··· + 1/n

然后我们提一个 k/n 化简，在 n 比较大时候，我们发现 P(k) 是 xy = 1 在 (k/n, 1) 分割成宽为 1/n 小区间后的黎曼和，最后求解 P(k) 约为 0.368，近似取整为 37%

我们可以发现，当 n 足够大时候采用最优停止算法选到的最棒女孩的概率永远近似 37%，若是瞎选那概率就会随人数的增加而下降，那 n 很小的时候呢？n 很小的时候，不管你怎么选概率差别就不大了，所以说宅男宅女们要是遇到的人太少了，就不用选了，感觉差不多就行了。

实际场景

一个程序员的一生会与 8w 人产生交集，中国绝大部分程序员都生活在国内，世界男女比例大致是 1:1，由于中国男多女少的局面，在男女比始终保持不变的前提下，中国男女比为 1:0.93，也就是会与大约 38549 名女性有交集，但实际上这其中还有一部分是亲属，假如一个男孩想在 20~40 岁这个年龄段找对象，由于中国男性平均年龄 72 岁，每年会遇到 535 个女孩左右，那么在 26 岁起这个年龄只要遇到一个比之前都好的就果断抓住她。如果一个男孩不想成为大龄剩男再去找对象他只想在 20~30 岁之间找对象，他就需要在 23 岁起开始找对象最好。对于女性来讲，由于存在育龄的缘故，最好得在 20~49 岁间找对象，如果一个女孩不考虑年龄大不好找或者不在意年龄大去找对象的话，她在 31 起就可以开始考虑找对象了。如果一个女孩也介意年龄太大去找的话，想在 20~28 岁间找对象，那么她就应该在 22 岁 4 月初开始就需要物色对象了，一旦找到一个比之前认识都好的人就果断抓住他，这就是最佳选择的策略。