最优停止问题——理工宅的择偶算法
一、停车场和麦田
此刻你正在电影院的地下停车场，身边坐着你今天的约会对象。你想把车停得尽量靠近电梯间，但那里的好车位可能已经被别的车占了。这时约会对象示意你旁边就有一个空车位，这里离电梯已经不算远了，但也不太近。你应该停这儿么？还是应该继续往前开？选择前者，你要承担失去更好车位的风险；选择后者，一旦前面并没有空车位，等你再绕一大圈回来，现在这个车位可能也没有了。你该何去何从？
另一个更常见的比喻是这样的：你将要穿过一片麦田，在不能回头的前提下，如何摘下一株最大的麦穗？
在“停车问题”里，你知道越往前开车位会越好，但不保证有空车位等着你。而在“麦田问题”里，你出手必中，但你不知道前面的麦穗会更大还是更小。这类问题还可以衍生出很多变种，我们把这类在某种规则约束和信息不确定的条件下，需要选择“落袋为安”或是“继续寻找”的场景统称为“最优停止问题”。
在布莱恩·克里斯汀的《算法之美》一书里，对最优停止问题做了很多有趣的讨论。我们先从最基本的“麦田问题”开始。
二、麦田问题
1、基本麦田模型
用“麦田模型”来类比“择偶问题”其实相当粗糙，它相当于假设了：
1、你只能定性而不能定量的评价每个约会对象的优劣。就是说，对任意两个对象甲和乙，你能够判断出哪个更好，但不能明确说出到底好多少。
2、只要你愿意，对方必须拿爱与你回应。
3、好马不能吃回头草。
4、当然不能脚踏两只船。
在这些规则之下，麦田问题的最优解是“37%法则”。假如你计划相亲十次，那即使前面三次里有个刘德华，你都不要动心，只用记住条件最好的那个。然后继续相亲，只要后面遇到一个超过刘德华（前三个对象中的最优者）的对象，马上拿下。如果没有，就选最后一个。用这套算法，选中最优秀对象的概率是39.87%。
37%法则的精髓在于把候选者划分成两个部分：前一部分是考察区，用来摸情况，后一部分是行动区，用来做选择。这里我们忽略掉具体的计算和证明过程，只需要记住“37%法则”就是此类最优停止问题的最佳方案，选中最佳对象的概率约为37%。
我们已经定性地划分出了观察和行动两个阶段，接下来就要回答一个定量的问题：该如何配置这两个阶段的比例？在37%法则中，面对不同数量的候选人，观察区与行动区的比例大致在1:1.86至1:1.5之间。那么在其他情况下，该把分界点设在哪儿呢？
2、不同约束下的麦田
我们还是忽略数学上的推导，试着从常识的角度来理解这个问题。相比“上帝视角”模式，最优停止问题面对的障碍主要有两个：信息不确定、规则有约束。而观察区的设置就是为了解决信息的不确定，行动区主要用来对付规则的约束。因此当信息披露更充分时，可以缩短观察区，加长行动区。相反地，当规则更宽松时，就应该缩短行动区，把更多的资源分配给观察区。我们先来看看后一种情况。
如果把麦田模型里的第三条规则改成：好马可以吃回头草，但是回头草会有50%的概率拒绝你。显然这样的规则更加宽松了，因此应该加长观察区，沉住气不急于出手。根据数学分析，这种情况下我们在观察前61%的人选时都不应该表态，等到剩余39%的人选中出现目前最优秀人选时再出手。你选中最优秀人选的概率也从37%上升到了61%。
相反的，如果规则更加严苛，比如不仅不能吃回头草，而且就算是面前草也有一半的可能会拒绝你。那就应该把行动区的占比加长到75%，而把选择区的占比缩短为25%——你等不起了。运用这个策略，选中最佳对象的概率也下降到了25%。
上面讨论了不同的规则约束导致的观察和行动之间的分配策略变化。规则越宽松，观测区可以越长，选中最佳对象的概率也越高。下面我们再来看看如果能获得更高质量信息的情况。
3、全信息版本麦田
在前面的基本麦田模型里，我们假设“对任意两个对象甲和乙，你能够判断出哪个更好，但不能明确说出到底好多少。”那么如果你能获得更精确的信息呢？你不仅能比较两个对象的优劣，即使只面对一个对象，你也能给他打出一个绝对的分数，比如“这是一个80分男。”
在这种情况下，问题就从“面对十次相亲机会，该用前几次来观察？”变成了“该接受多少分以上的候选人？”
显然，如果你已经“面试”到了最后一名对象，那根据规则，无论多少分你都只能选择他。所以当你面对倒数第二名候选者时，如果他在50分以上，你就应该接受（假设候选人的素质在0～100分之间平均分布）。因为倒数第二名在50分以上，就意味着剩下那个候选人不如他的可能性大于50%。以此类推，当剩下的候选人越多时，你能接受的门槛分数就越高。计算表明，当后面还有25位候选人时，即使你面前是个95分的对象，你都应该拒绝他，把相亲继续进行下去。当还剩10位候选人时，你的录取线应该设在90分附近。
上面这类情况叫做“全信息版本的最优停止问题”，选中最优对象的概率是58%，远高于“基本麦田问题”中37%的成功率，这21点的提高就是由更优质的信息带来的。
三、择偶黄金法则
至此，我们已经讨论了四种麦田模型及其变种，从中可以总结出哪些“择偶黄金法则”呢？
第一、打铁还需自身硬。如果以你自身的条件能够吃到一些“回头草”，那你拿下最佳对象的概率就会上升。相反，如果你的条件不好，被“面前草”拒绝的可能性都较高，那即使你采用了数学上的最优方案，你择偶的成功率也不会高。
极端地说，如果你的条件好到了人挡杀人、佛挡杀佛的程度，你就可以面试完所有的候选人，再从中挑选出最好的那个，择偶成功率100%。相反，如果你的条件差到了人见人厌、狗见狗嫌的地步，那你的孤老一生率也是100%。
第二、评判标准要清晰。在自身条件相同的情况下，能够对候选人给出定量评价的人，比纯靠感觉的人的择偶成功率要高得多。所以，你应该把相亲当成一项系统工程来对待，要事先制定严肃的评价体系，不能懵懵懂懂地上场。
由这条还可以延伸出另一条法则：人贵有自知之明。打分不光是对别人，也要对自己。比如你判断自己的条件大概是70分左右，相应的潜在有效择偶区间在60分～90分，那你就可以把这个区间进一步细分，提高有效段的分辨率，以获得更精确的信息。相反，你本来只有70分，却认为自己有90分，然后把择偶区间定到90～100分，就好像一个二本大学把调档线定得和清华北大一样高，这样能招到生么？
第三、进场不能太晚。因为需要付出各种成本，所以当然不能说谈恋爱越早越好，相亲越多越好。但一个人进入婚恋市场的时间点也绝对不能太晚。从前面的图中可以看到，前半段的“调档线”可以设得很高，而且随着时间缓慢下降，但是进入尾部区域后“调档线”会断崖式下跌，所以千万不要等到尾部时才入场。
第四、寻找高分候选人群体。这条无需多言，平均而言，你在一块示范田里摘到的麦穗就是要比病虫害田里的要大得多。相亲前的各种硬性指标就是为了筛选出优秀的“生源”。如果自己的分数不够高，报考名牌大学隔壁的大学也是一个好选择。
四、停车问题
麦田模型的场景有点像你坐在房间里，候选人鱼贯而入接受你的面试，这是一个“一对多”的映射。现在把镜头拉高，你的周围还有许多房间，每间里面都有一个“面试官”。候选人在各个房间之间流动。这是一个“多对多”的映射，就像是…停车场。
我再把开篇的停车场问题换一种方式来描述。全身心投入学习和工作能提高一个人的素质，而高素质的人一旦进入婚恋市场，可以匹配到同等素质的伴侣。不过这些优秀伴侣的数量有限，先到先得。那么你应该在什么时间点上将跑道从天天向上切换到婚恋市场？
如果切换得太早，进入婚恋市场也只能选择“偏远的停车位”。如果进入得太晚，可能会落得“A女配D男”的高处不胜寒。
影响停车策略的关键因素是车位的占有率。援引《算法之美》中的解释：为了实现最优停止这个目标，在距离目的地一定路程之外，即使看到空车位也不要停车；一旦进入一定距离之内，就应该从观望阶段转变为行动阶段，看到空车位后立刻停车。这段距离的长短，取决于停车位可能被占用的百分比，即停车位占用率。下表列出了与某些有代表性的停车位占用率相对应的转变距离：
简单地说：如果发现停车场很挤，就要尽早停车，如果停车场挺空，那大可以多开一段距离。这里的占有率是个常数，也就是假设高分潜在配偶的数量少但是同一级别的竞争对手也少，两者的比值和低分段的潜在配偶和竞争对手数量的比值相同。
五、第五条法则
从中我们可以总结出第五条“择偶黄金法则”：选择空旷的停车场。比如女生选择理工院校，或者男生去上护理系。总之寻找那些和自身素质匹配的适龄异性比例较高的圈子。
更准确的比方可能应该这样打：如果你是个研一的女生，第一次去见导师，发现教研室全都是单身状态的师兄和同级男生，那你不用着急个人问题，停车场还很空，你可以先读个博再说…吗？
当然没这么简单，因为从他们的角度看停车场很挤，应该尽快停车，或者寻找其他停车场…一旦他们这么行动，你的停车场就变挤了，那你也应该尽快停车。婚恋市场是个动态变化的市场。
写到最后，已经非常理工宅和政治不正确了，必须得拨乱反正回来。在数学模型层面，择偶策略的背后肯定需要算法来支撑，但爱情不只是算计、婚姻更不是买卖。你在某年某月的某一天，在某个停车场或是某片麦田，遇见属于你的那张脸。然后你们互相帮助、共同进步、终成眷属，这难道不是一个更美的故事吗？
最后祝愿每个人都能在找寻幸福的道路上…适可而止。
参考文献：
1、布莱恩·克里斯汀《算法之美》
2、万维钢 《精英日课》
更多内容欢迎关注微信公众号《周工讲理》：用理工思维生活育儿。
