最优停止理论——如何适“可”而止

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 3.8k | 阅读时长 ≈ 3 分钟

摘要

本文主要从最优停止问题出发，介绍了麦穗问题和经典的秘书问题以及面对此类问题采取的策略。本文还根据该策略推导并验证了37%法则的正确性，并且简单分析了该法则的适用性。

理论介绍

中国有一句古话，叫做适可而止，其意思是到适当的程度就停下来，不要过头。生活中处处需要抉择判断，像是买衣服，挑选伴侣等，而这些问题都需要运用适可而止的思想，否则将确定最终选择，因为我们永远不知道最好的将什么时候出现。但是适可而止的“可”又是什么呢？当我们面对无穷无尽的选择时，有如何知道当前选择是否为“可”呢？在进入正文之前，先让我们听一个小故事。

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

面对老师的要求，三个弟子分别做出了不同的举动。第一个弟子刚刚走了几步便迫不及待地摘了一支自认为是最大的麦穗，结果发现后面的大麦穗多的是；第二位一直左顾右盼，东瞧西望，直到终点才发现，前面最大的麦穗已经错过了；第三位弟子把麦田分为三份，走第一个1/3时，只看不摘，分出大、中、小三类麦穗，在第二个1/3里验证是否正确，在第三个1/3里选择了麦穗中最大最美丽的一支，这就是所谓的麦穗理论。

为什么第三位弟子能够获得比较满意的结果呢？因为他在选择的过程中采用了一定的策略，即将决策过程分为两段：前2/3的路程用于确定“最基本的满意标准”，最后1/3选择满足“最基本的满意标准”的第一个方案。这里的两段可以是把全部可选方案在数量上分成两段来考察，也可以是把选择时间分成两段。

麦穗理论实际上要解决的是一种“最优停止问题”。这种问题一般有两个特点：我们并不清楚我们会遇到什么样的可选方案，只有看过了才知道，即未来不可知，但一个可选方案一旦被错过了不能再回头去选，即不能反悔。生活中其实很多事情都是类似的问题，麦穗理论里的找到理想伴侣、买房子、换工作等等。

所以有一个观望的“最优停止”的时间点，也因此这类问题被称为“最优停止问题”。

秘书问题（Secretary problem）是最优停止问题中最著名的一类难题，在不同的地方它也被称作相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题等。该问题的内容是这样的：假设你是面试官，要聘请一名秘书，一共有 n 个应聘者来面试。你按照随机顺序，每次面试一名申请人。你随时可以决定将这份工作交给其中一人，而对方只能接受，于是面试工作就此结束。但是，一旦你否决其中一名申请人，就不能改变主意再回头选择他。面试后总能清楚了解应聘者的合适程度，并能和之前的每个人做比较。问什么样的策略，才使最佳人选被选中的概率最大。

面对这类问题，Merrill M. Flood在1949年首次提出37%法则。他所采取的的策略类似于上述苏格拉底的第三位弟子的决策：首先对前面一部分面试者，无论优秀与否都直接拒绝，只考察目标，收集数据，用于确定“最基本的满意标准”。然后对剩下的人进行面试，如果遇到一位比之前面试的人都优秀的面试者，那么就立即出手，直接聘请这个人，否则就继续面试。

在麦穗问题中，那位弟子选择将前2/3的麦穗用于确定“最基本的满意标准”。但是这不一定是最优秀的决策。为了提高我们获得最优结果的概率的时候，我们需要找到最合适的样本量用于制定比较的标准。通过计算，Flood发现37%是一个最优停止点，也就是说选择前37%的人直接拒绝时，得到最适合担任秘书的人的概率最大。

理论证明

那么37%是如何推导出来的呢？

假设事件为第 k 个人被选中，事件为第 k 个人是最优秀的，事件为前 r 名面试者用于确定标准时选到最优秀应聘者，其中。则选到最优秀的应聘者的概率：

因为前 r 个人必然会被拒绝，所以 。又因为当第 k 个人被选择时，第 k个人前最优秀的人必然在前 r 个人当中，所以 。因此式（1）可化简为：

因为我们需要选出最优的决策，所以前 r 名面试者用于确定标准时选择到最优秀的应聘者的概率必须为最大，即。

通过计算机程序枚举 n 为 1~10000 时，选取的 r 的值，并选取部分数据记录于下表。

n r
3 1 0.333333 0.5
4 1 0.25 0.458333
5 2 0.4 0.433333
10 3 0.3 0.39869
100 37 0.37 0.371043
1000 368 0.368 0.368196
10000 3679 0.3679 0.3679

当 n 无限接近于时， 变为积分形式，即式（2）变为：

令函数 ，所以我们需要所求的为的最大极值点，即 ，此时可得。已知，因此计算结果符合要求。

验证代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<stdio.h>
#define oo 1e9+7
using namespace std;
int main(){
	freopen("test.txt","w",stdout);
	for(int i=1;i<=10000;i++){
		double maxp=0,temp=0;
		int maxr=1;
		for(int j=1;j<i;j++)temp+=1.0/j;
		for(int j=1;j<=i;j++){
			double pj=1.0*j/i;
			pj*=temp;
			if(pj>maxp){
				maxp=pj;
				maxr=j;
			}
			temp-=1.0/j;
		}
		cout<<i<<" "<<maxr<<" "<<1.0*maxr/i<<" "<<maxp<<endl;
	}
	fclose(stdout);
	return 0;
}

结语

37%法则还可以用于生活中有很多类似于秘书问题的问题，像是如何选择自己的伴侣，如何决定投资的项目，如何选择停车位等可化简为最优停止问题的问题。在所有最优停止问题中，最大的难点不在于选择哪一种可选方案，而是确定自己需要考虑多少种可选方案。

最优停止问题的权威教科书开宗明义地指出:“最优停止理论关注的是如何选择时机以执行特定行动的问题。”秘书问题最基本同时也最令人难以置信的前提条件——严格的连续性，即有进无退的单向行进，正好是时间自身属性的一个体现。生活中我们做出决定的时候，往往具有时间上的不可挽回性，你永远无法回到过去去重新做出选择，我们没有二次选择机会，如何适可而止，在合适的时间停止观察做出选择，这是非常重要的问题。

需要注意的是，37%法则选到的并不一定是最优方案，而是接近于最优的满意方案。还有的时候可能找到最优并不可能，或者代价极大。在这种情况下，我们要能接受“满意”。而且当最优的方案出现在前37%的时候，你会发现37%法则也无法找出满意的方案。因此在生活中，我们需要灵活的应用37%法则，结合自己的经验，寻找到那个令人满意的“可”之所在。

参考文献

[1] 约翰尼斯·开普勒 算法之美：指导工作与生活的算法
[2] 维基百科 秘书问题
[3] 听风临山 生活中一定会用到的数学常识：37%法则