最优停止问题
作者： 半场零射门
| 发布于: | Android | 转发：0 | 回复：0 | 喜欢：1 |
一、 秘书问题
你有10次相亲机会，候选人的品质范围从0分到100分，录取名额只有一个，每次相亲你需要当场决定是否录取。请问，什么样的策略能够让你最大概率地选中最优秀的那个候选人，这个最大的概率是多少？
这个问题和著名的“麦田问题”（不回头地走过一片麦田，只能出手一次，如何摘到最大的麦穗?）类似：
1、一个确定的候选序列
2、只要你愿意，对方必须拿爱与你回应
3、严禁脚踏两只船
4、好马不吃回头草
区别在于：
1、在前一个场景里，你可以定量地评估每个候选人的绝对水平。
2、在后一个场景你，你只能定性地比较候选人之间的优劣。
前者叫做“全信息秘书问题”，（最开始提出的场景是如何通过面试挑选出最好的秘书），后者也叫做“零信息秘书问题”。
二、零信息策略
“零信息秘书问题”或者说“麦田问题”已经被讨论得很多了，它的最优策略叫做“37%”法则：把候选序列划分成两个部分，前一部分是考察区（大概占总长度的37%），用来摸情况，后一部分是行动区，用来做选择。
在考察区里，即使遇到金城武你也不要动心，只用记住考察区里最佳候选者的水平。在进入行动区后，遇到第一个超过金城武的对象，马上拿下。如果彭于晏一直没出现，就选最后一个候选人。采用这个套路，选中最优对象的概率大概是37%。
不难看出，零信息问题里考察区的作用其实就是刺探候选序列的信息。那么对于全信息问题，问题就从“面对10次相亲机会，该用前几次来考察？”变成了“该当场录取多少分以上的候选人？”
三、全信息策略
我们再用数学语言描述一遍问题：对于一个经过归一化处理后的包含有n个连续型随机变量的集合，集合的每个成员均服从概率分布函数F(x)=x，0≤x≤1（以百分制举例就是得分不超过60分的概率为60%）。获胜的条件是选中集合中的最高分。请问胜率最大的策略是什么，最大的胜率是多少？
我们先来考虑一种极端的情况：如果当前面试者得分100分，你肯定应该马上录取他。那么如果是99分、98分…或者90分呢？直觉上，如果后面还有很多候选人，那可以再等等看。如果候选人已经所剩无几，则应该当机立断。
也就是说对于每一个候选者都对应了一条录取分数线S，而这条分数线的高低取决于剩余候选人的数量k。
我们用Sk表示后面还剩k个候选人（也就是序列里的倒数第K+1位）时的录取分数线，那么Sk应该是k的某种函数，而且Sk会随着k的减小而降低。我们的策略就是：依次比较每个候选人的得分和他这个位置所对应的录取线，当遇到序列里第一个大于或等于录取线的对象时就拿下他。该怎么确定录取线和剩余选项数之间的关系呢？
1、k=0
我们倒着来想这个问题，如果相亲到了最后一个对象(k=0)，那你只能录取他，如果他正好是那个佼佼者你就赢了，否则就输了(前面定义过：获胜=选中集合中的最高分)。所以此时的录取线为0(S0=0)。
2、k=1
对于倒数第二个对象，假设他的得分是x，录取他从而获胜的条件是：剩余的候选者都比他差。此时只剩一个候选者，根据前面定义的概率分布函数F(x)=x，0≤x≤1，这种情况发生的概率P1=P(剩余的都比当前差|当前得分x，还剩1人)=x。
而放弃得分为x的倒数第二名候选人而获胜的条件是：最后一人的得分比x更高，P2=1-x。
当P1≥P2时，我们就应该录取当前候选人，即x≥1-x，解出x≥0.5，所以倒数第二位置的候选人对应的录取线是0.5，换算成百分制就是50分(S1=50)。
3、k=2
对于倒数第三个候选人，假设他的得分是x，录取他从而获胜的条件还是：剩余的候选者都比他差。这种情况发生的概率P1=P(剩余的都比当前差|当前得分x，还剩2人)=x^2。
而如果放弃当前这个候选人，按我们的既定策略（当遇到序列里第一个大于或等于录取线的对象时就拿下他）继续相亲，还能获胜（选中集合中的最高分）的条件是：剩下的候选者里至少有一个得分大于等于x，而且我们还能选中里面的最高分。
前面我们已经讨论过，序列的录取线肯定是递减的，所以后面位置的录取线肯定＜x（因为x求解出来后，就是倒数第三位置的录取线S2），所以一旦在后面遇到一个得分≥x的候选人，按照“当遇到序列里第一个大于或等于录取线的对象时就拿下他”的策略，必然会选中他。
这就要求后面候选人里大于x中的最高分，要恰好排在大于x的所有候选人的第一个。由于还剩2名候选人，满足上述条件的情况一共有两种：
情况1：2人里只有1人得分≥x，发生的概率是P(情况1)=C(2，1)·(1-x) ·x
情况2：2人里有2人得分≥x，而且其中更高分者排在前面（1/2的可能），发生的概率是P(情况2)=C(2，2)·(1-x)^2·(1/2)
所以放弃得分为x的倒数第三名候选人而获胜的概率P2=P(情况1)+P(情况2)
当P1≥P2时，我们就应该录取当前候选人，解出x≥(1+√6)/5≈0.69，所以倒数第二位置的候选人对应的录取线是0.69，换算成百分制就是69分(S2=69)。
4、k=i
推而广之，对于倒数第i+1个对象，假设他的得分是x，录取他从而获胜的条件还是：剩余的候选者都比他差。这种情况发生的概率P1=P(剩余的都比当前差|当前得分x，还剩i人)=x^i。
而放弃当前这个候选人还能获胜的条件仍然是：剩下的候选者里至少有一个得分≥x，而且其中的最高分要恰好排在最前面。一共有i种情况：
情况1：i人里只有1人得分≥x，发生的概率是P(情况1)=C(i，1)·(1-x) ·x^(i-1)
情况2：i人里有2人得分≥x，而且其中更高分者排在前面（1/2的可能）……
……
把以上所有情况加起来得到P2的表达式：
最后通过求解下列方程(P1=P2)，得出倒数第i+1位置的候选人对应的录取线。
这个方程的解析解难以求得，可以用它的一阶近似解代替：Sk≈1/(1+0.8044/k)
最终求得全信息秘书问题中各个位置候选人对应的录取线表如下：
“全信息秘书问题”和“零信息秘书问题”这类尝试在某些约束条件下选中给定序列中最大值的问题，统称为最优停止问题。在John P.Gilbert和Frederick Mosteller于1966年发表的论文《Recognizing the Maximum of a Sequence》中对各种变体做了详细的讨论。
根据论文的推导（373～378页），在“全信息秘书问题”中采用上述最优策略选中最优对象的概率见下表：
可以看到，随着候选序列长度的增加，获胜概率收敛到58%左右。
四、启迪
通过前面的讨论，可以看到，在都采用最优策略的情况下，零信息问题的获胜概率为37%，全信息问题的获胜概率是58%。这21%的胜率优势告诉我们：
第一、找对象是一项系统工程，不能打无准备之仗。上场之前首先要有清晰的判断标准。在自身条件相同的情况下，能够对候选人给出定量评价比只能定性比较的胜率要高得多。
第二、进场不能太晚。下面是一张25人相亲序列的录取线图。从图中可以看到，前半段的分数很高，然后缓慢下降，进入尾部区域后会断崖式下跌，所以千万不要最后才入场。
五、停车问题
我们再换一个场景：想象此刻你正在商场的地下停车场，你想把车停得尽量靠近电梯间，但那里的好车位可能已经被占了。这时你旁边就有一个空车位，这里离电梯间已经不算远了，但也不太近。你应该停这儿么？还是应该继续往前开？选择前者，你可能会错失更好的车位；选择后者，你可能会越开越远。你该何去何从？
在“秘书问题”里，你出手必中，但你不知道后面候选人的水平。在“停车问题”里，你知道越往后（在到达电梯间之前）车位会越好，但不保证有空车位等你。
DeGroot在《Optimal Statistical Decisions》一书中对上述停车问题进行了讨论（384页，33题）。影响停车策略的关键因素是停车场的占用率。
Brian Christian在《算法之美》一书中的解释：在距离目的地一定路程之外，即使看到空位也不要停车；一旦进入这个距离之内，看到空车位后要马上停车。这段距离的长短，取决于停车位的占用率。下表列出了不同占用率所对应的距离：
定性的说，就是越拥挤的停车场就要越早停车。定量的计算：设停车场内任一车位空置的概率为p，那么决策距离r= −log 2 / log(1−p) ，最优策略是当离目的地的距离＜r时，有空车位就停。
可以把停车问题换一种表述：全身心投入学习和工作能提高一个人的素质，而高素质的人一旦进入婚恋市场，可以匹配到同等素质的伴侣。不过这些优秀伴侣的数量有限，先到先得。那么你应该在什么时间点上将跑道从天天向上切换到婚恋市场？
如果切换得太早，进入婚恋市场也只能选择“偏远的停车位”。如果进入得太晚，可能会落得“A女配D男”的高处不胜寒。
在DeGroot推导的最优策略中，整个停车场的车位占用率是个常数。相当于假设在婚恋市场里，高分潜在匹配对象的数量少但是同一级别的竞争对手也少，两者的比值和低分段的潜在匹配对象和竞争对手数量的比值相同。Tamaki在一系列论文中，对车位占用率服从不同概率分布和不同规则的各种衍生停车问题进行了研究。基本的结论是相同的：越拥挤的停车场就要越早停车。
停车问题带给我们的启迪是：尽量选择空旷些的婚恋市场。比如女生选择理工院校，或者男生去上护理专业。总之寻找那些适龄异性比例较高的圈子。
如果你是研一的女生，第一次去见导师，发现组里全都是单身状态的师兄，那你不用着急个人问题，停车场还很空，你可以先读个博再说…吗？
当然没这么简单，因为从他们的角度看停车场很挤，应该尽快停车，或者寻找其他停车场…一旦他们这么行动，你的停车场就变挤了，那你也应该尽快停车。这是个动态变化的战场。
本文讨论了最优停止问题在婚恋市场的应用，在数学模型层面，择偶策略的背后肯定需要算法来支撑。但爱情不是算计、婚姻更不是交易。最后祝天下有情人都能在找寻幸福的道路上…适可而止。
文中图片来自《算法之美》一书以及论文《Recognizing the Maximum of a Sequence》