Featured image of post 最佳停止时间理论

最佳停止时间理论

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

本文主要从最优停止问题出发,介绍了麦穗问题和经典的秘书问题以及面对此类问题采取的策略。本文还根据该策略推导并验证了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%的人直接拒绝时,得到最适合担任秘书的人的概率最大。

阅读原文

Licensed under CC BY-NC-SA 4.0
Laosji
Built with Hugo
主题 StackJimmy 设计