[ 导读 ] 如果你的身边再出现因为租房子、停车、求婚而感到苦恼的人,你可以告诉他们:问问算法吧。而算法会告诉他们,这个平衡点就是37%。
股融易注:借助并不繁复的算法,我们不仅可以解决找房子的问题,生活中遭遇的所有最优停止问题都可以被妥善处理。
在很多城市和地区,租房都是困扰大多数人的难题。拿旧金山来说,旧金山可能是整个美国最难找房子的城市了。由于技术产业的蓬勃发展,再加上城市区划法律严格限制建造新住房,旧金山的房租已经与纽约不相上下,甚至比纽约还高。房源清单列出来几分钟,房子就会被人们一抢而空。通常情况下,只有第一个把定金支票塞到房东手里的人,才能拿到房子的钥匙。
如何确保自己找到最合适的房子?在被问及此类问题时,大多数人凭直觉给出的答案可能大致如此:这需要在继续挑选与立刻下手之间达成某种平衡。也就是说,你必须先看足够多的房子,确定一个标准,然后接受符合这个标准的房子。
平衡概念正是解决这类问题的关键,但是大多数人根本无法确定这个平衡点在哪里。
当然,租房要考虑的其他因素还有很多,比如周边环境、价格……我们姑且假设,你最关心的可能是增加选中令你最满意的房子的概率。那么,你的目标应该把以下两种遗憾的发生概率降到最低:看过的好房子被人挑走、还有好房子没来得及看。
这时候你会发现自己陷入了两难境地:如果没有衡量的标准,如何判断哪套最合适?没看过一些房子,又如何确定衡量标准?收集的信息越多,越能确定最佳选项是什么,但与最佳选项错过的可能性也越高。
到底该怎么办?如果收集信息的行为会危及结果,那么怎样才能在掌握足够多信息的基础上做出明智决定呢?这个令人极其为难的情境近乎于一个悖论。
好消息是,继续挑选与立刻下手之间的平衡点已经被数学家找出来了。
答案就是37%
作者布莱恩・克里斯汀和汤姆・格里菲思,在新书《算法之美》这本书中提到:如果你想让找到最合适的房子的可能性达到最大值,那么在看前37%的房子时不要做出任何决定。假如你打算花一个月的时间来挑房子,那么不要在前11天做出决定。因为这段时间是在制定标准,过了这个时间点之后,若你发现自己对某套房子的满意程度超过之前看过的所有房子,就可以立刻下手。在继续挑选与立刻下手之间做出的这种妥协,并不仅仅是一种直觉,而是已经得到证明的最优解。
租房问题属于数学上的“最优停止问题”(optimal stopping),即如何在面临一连串选择时做出最优决策。这类问题经常会改头换面,以不同的形式在生活中出现。而它最大的难点,不在于选择哪一种可选方案,而是确定自己需要考虑多少种可选方案。
“37%法则”源于最优停止问题中最著名的一类难题:“秘书问题”。秘书问题与我们之前讨论的租房难题十分相似。
假设一堆人申请一个秘书岗位,即使作为面试官的你不知道如何给每一名申请人评分,但还是可以轻松地判断哪一名申请人更优秀。(用数学语言来表述,就是说你只能看到序数,即申请人相互比较的排名,但是无法看到基数,即在一般性评分标准下的得分。)你按照随机顺序,每次面试一名申请人。你随时可以决定将这份工作交给其中一人,而对方只能接受,于是面试工作就此结束。但是,一旦你否决其中一名申请人,就不能改变主意再回头选择他。
在选择秘书时,遴选程序停止过早或者过晚都会导致不理想的结果。要取得最理想的结果,显然需要在两者之间找到最合适的平衡点。因为停止过早,最优秀的申请人还没有得到亮相的机会;停止过晚,就说明你在为一位根本不存在的更优秀的申请人保留这份工作。
如果找到最优秀申请人是你追求的唯一目标,那么在整个面试过程中,只要不是已有申请人当中的最优秀人选,你都不会接受。但是,仅仅达到“目前最佳”这个条件,还不足以说服面试官。比如说,第一名申请人毫无疑问就符合这个条件。
一般而言,我们有理由相信,随着面试程序不断进行下去,出现“目前最佳”申请人的概率将不断下降。例如,第二名申请人是截至目前最优秀申请人的可能性是50%,第五名的可能性只有1/5,第六名的可能性只有1/6,以此类推。
因此,随着面试工作的深入,目前为止最优秀申请人一旦出现,必然会令人眼前一亮(别忘了,根据定义,这名申请人比之前所有申请人都更加优秀),不过,这种可能性在不断降低。
所以说,看到第一个目前最优秀申请人就欣然接受(也就是说,面试第一名申请人之后就结束面试程序),显然是过于草率了。在一共有100名申请人时,也不能因为第二名申请人比第一名申请人更优秀就迫不及待地选择他,因为这种做法同样有些操之过急。那么,我们到底该怎么办?
凭直觉,我们可以找到几种应对的办法。例如,当第三次(或者第四次)出现胜过前面所有的申请人时,就把工作机会交给他。或者,在连续多个申请人都不理想的情况下,一旦出现一名目前为止最优秀的人选,就毫不犹豫地接受他。
但是,事实证明,所有这些相对来说似乎有道理的策略都算不上是最明智的做法。如果只有一名申请人,这个问题就非常简单——接受她的申请!如果有两名申请人,无论你如何选择,你成功选到优秀人选的概率都是50%。你可以接受第一名申请人(此时,她是半程最优秀申请人),或者拒绝她,而拒绝第一名申请人就意味着接受第二名申请人(她也是半程最优秀申请人)。
如果有第三名申请人,情况就一下子变得有意思了。如果随机选择一名申请人,得到理想结果的概率是1/3,也就是33%。有两名申请人时,我们没有办法取得比碰运气更好的结果。那么,在有三名申请人时,会怎么样?事实证明,我们可以取得更理想的结果,而其中的关键就在第二场面试。
在面试第一名申请人时,我们没有任何信息——她肯定是目前最优秀的申请人。在面试第三名申请人时,我们没有任何能动性——我们只能将工作机会交给这名申请人,因为我们已经拒绝了其他人的申请。但是,在面试第二名申请人时,我们既掌握了一些信息,又有一定的能动性——我们知道她与第一名申请人相比孰优孰劣,同时我们既可以接受她,也可以拒绝她。如果她比第一名申请人优秀,我们接受她,反之就拒绝她,那么会产生什么样的结果?事实上,在有三名申请人时,这是最理想的方案。
令人吃惊的是,在有三名申请人时采用这个方法,与有两名申请人时选择半程最优秀人选的方法相比,效果不相上下。
在有4名申请人时,穷举所有可能的情况之后就会发现,我们仍然应该在面试第二名申请人时采取行动;如果一共有5名申请人,我们应该等到面试第三名申请人时才采取行动。
随着申请人数不断增加,观察与行动之间的分界线正好处在全部申请人37%的位置,从而得出了37%法则:在考察前37%的申请人时,不要接受任何人的申请;然后,只要任何一名申请人比前面所有人选都优秀,就要毫不犹豫地选择他。
事实证明,利用这种最优方案,我们选中最优秀申请人的概率为37%。方案本身与出现理想结果的概率正好相等,这是这类问题表现出来的令人奇怪的数学对称性。上表列出了申请人数不同时的秘书问题最优解决方案。从中可以看出,随着申请人数不断增加,取得理想结果的概率(以及从观察期切换到行动期的时间点)在37%左右。(其实,应该是略低于37%。准确地说,考察申请人的最优比例是1/e,其中e是复利计算中经常出现的数学常数,等于2.71828……。但是,如果你记不住e的12个小数位,也无须着急。只要这个比例在35%与40%之间,取得最理想结果的可能性就非常接近于最高值。)
采用最理想的方案也会有63%的失败率,这是一个令人警醒的事实。在面对秘书问题时,即使我们采取了最理想的行动方案,在大多数情况下也会遭遇失败,也就是说,大多数情况下我们都无法选中所有人选当中最优秀的那名申请人。
对于把爱情视为寻觅“真命天子”的人来说,这确实是一个坏消息。不过,也不完全都是坏消息。直觉告诉我们,随着申请人数的不断增加,选中最优秀申请人的可能性将稳步下降。例如,如果采用随机选择的方式,在申请人总数为100时,我们得到理想结果的可能性是1%,在总人数为100万时,可能性就会降到0.0001%。但是,令人意想不到的是,秘书问题的计算结果不会发生变化。
如果采用最优停止理论,在100人当中选中最优秀申请人的可能性是37%。而总人数是100万时,无论你相信与否,你得到理想结果的可能性仍然是37%。因此,申请人总数越多,最优算法理论就越有价值。的确,在大多数情况下,大海捞针都会无功而返,但是,无论“海洋”多么辽阔,最优停止理论都是最理想的工具。
《算法之美》强调,最优停止问题经常会改头换面,以不同的形式出现在我们的生活当中。比如,在驶入停车位之前,需要绕整个停车场多少圈?在商业风险中何时套现脱身?在择偶上,何时观望,何时步入婚姻殿堂?当你再次面对这类问题时,至少可以通过数学方法来解决。借助并不繁复的算法,我们不仅可以解决找房子的问题,生活中遭遇的所有最优停止问题都可以被妥善处理。
因此,如果你的身边再出现因为租房子、停车、求婚而感到苦恼的人,你可以告诉他们:问问算法吧。而算法会告诉他们,这个平衡点就是37%。