01

问题的提出

1.1 麦穗问题

传说古希腊哲学大师苏格拉底的3个弟子曾求教老师，怎样才能找到理想的伴侣。于是苏格拉底带领弟子们来到一片麦田，让他们每人在麦田中选摘一支最大的麦穗，不能走回头路，且只能摘一支。

第一个弟子刚刚走了几步便迫不及待地摘了一支自认为是最大的麦穗，结果发现后面的大麦穗多的是。

第二位一直左顾右盼，东瞧西望，直到终点才发现，前面最大的麦穗已经错过了。

第三位把麦田分为三份，走第一个1/3时，只看不摘，分出大、中、小三类麦穗，在第二个1/3里验证是否正确，在第三个1/3里选择了麦穗中最大最美丽的一支。

要招聘一名秘书，有n人来面试。每次面试一人，面试过后便要即时决定聘不聘他，如果当时决定不聘他，他便不会回来。凭什么策略，才使选得到最适合担任秘书的人？

类似的还有相亲问题：相亲多少次就该做出决定？租房问题：看多少个房子就该下定决心租了？要解决这类问题，用到的都是最优停止理论，即如何选择停止观望的时机？

问题的解决

37%法则这个策略是：以秘书问题举例，先观察前1/e的面试者，每面试完一个人，都能知道其能力水平，然后选择后面遇到的第一个比前面所有面试者都优秀的人，否则就不选择。

1/e约等于37%，37%法则因此得来。

为什么是37%呢？

因为这已经变成了一个概率问题了，假设总共有N个人，在面试的前r个人中，我们记住一个最优秀的人为k，那么从第r+1个人开始，只要大于k的，就选择，那么我们要求的是能够最大化成功选中最优秀面试者的概率可以近似为：

设x=r/N ，那么上面的公式就可以写成：

p=-xln(x)

对它求导，可以解出x的最优值，即p在r/N等于1/e时取得最大值，1/e约等于0.368，也就是可以把前36.8%的人可以当做一个标准，后面63.2%的人中第一个达到标准的，即可录用。

也就是说，假如你要面试100个人，前37个人，看看就好，观望阶段默默记住一个最优秀的，从第38个人起，但凡超过了前面那个最优秀的，就可以下定决心录用他了。

按照这个方法，给日常生活中的选择困难恐惧症的小伙伴们提高了良好的理论指导，你觉得如何呢？

秘书问题得到的37%法则是一个非常理想的情况，且建立在“无信息”上，除了对面试者进行相互比较外，对其他信息一无所知，因此也是一个无信息博弈问题。

但真实生活中，尤其是买房、租房、相亲这类问题，肯定是想要掌握全部信息后再做决定的，因此也属于全信息博弈。

以租房举例，我们可以掌握候选对象的所有信息，比如房型、布局、地段、真实报价等，无需和37%法则一样留有一个观望阶段，可以直接通过已知信息确定租房价格的阈值，当有高于阈值的房子出现，则做出决定。

其实大家在租房时都会遇到的一个问题就是，假如我不在下个月交房租前把现在租的房子转租出去，那我就要多付一个月的房租，也就是说，在等待的时间里是有成本存在的。

很大的可能是，在时限快到来前，降价处理掉。然而最科学的方法是，一旦确定了最优停止价格，就不要妥协，不要回头。

关于这个最优停止理论的问题，其实在《算法之美》这本书的第一章里有详细地讲解，感兴趣的小伙伴可以看一下，我之前也写过这本书的读书笔记：如何用算法改变生活 | 算法之美，导图如下，图片传上来有压缩，如需高清大图，可加我微信：data_cola