算法之美

    [美]布莱恩·克里斯汀 汤姆· 格里菲思 著

    万慧 胡小锐 译

    中信出版集团目录

    序言

    01 最优停止理论 如何选择停止观望的时机？

    秘书问题

    37%从何而来？

    情场上的出手时机

    掌握候选对象的完整信息

    卖房子的时机

    最优停车位置

    见好就收的时机

    随时准备停止

    02 探索与利用 要最新的还是要最好的？

    什么是探索与利用

    如何利用剩余时间？

    赢留输变

    基廷斯指数

    遗憾与乐观网上“土匪”

    试验中的临床试验

    不安分的世界

    探索——孜孜不倦

    走出探索和利用的两难困境

    03 排序 建立秩序

    排序狂潮

    排序带来的苦恼

    大O符号：衡量最坏情况的标准

    平方时间：冒泡排序与插入排序

    打破平方时间的魔咒：分治算法

    超越比较法：比对数更好的算法

    排序是搜索的准备工作

    排序与体育

    发牢骚的权利：噪声与健壮性

    杀戮排序：啄食顺序与优势等级

    以竞争取代争斗

    04 缓存 忘了它吧

    分级存储器体系

    缓存清理与未卜先知重整图书馆藏书

    本地需求

    家庭生活中的“高速缓存”

    归档与堆存

    遗忘曲线

    经验暴政

    05 时间调度理论 要事先行

    安排时间是一门科学

    处理时限

    把事情做好

    找出问题所在

    优先级反转和优先约束

    减速带

    放弃所有：抢占和不确定性

    抢占并不是随意的：关联转换

    颠簸状态

    中断合并

    06 贝叶斯法则 预测未来

    贝叶斯牧师的倒推理

    拉普拉斯定理贝叶斯法则与先验信念

    哥白尼原则

    贝叶斯与哥白尼

    真实世界的先验……

    他们的预测规则

    小数据与思维

    我们的预测体现出我们自己

    机械复制时代的先验

    07 过度拟合 不要想太多

    反对复杂性案例

    数据崇拜

    过度拟合无处不在

    检测过度拟合：交叉验证

    如何应对过度拟合：惩罚复杂性

    启发法

    人类进化中的过度拟合

    何时应该想得更少？

    08 松弛 顺其自然

    最优化的难度

    定义的难度放松吧

    无数灰色地带：持续的松弛

    只是一张超速罚单：拉格朗日松弛算法

    学会松弛

    09 随机性 何时应用随机？

    抽样

    随机算法

    抽样的优势

    三部分的权衡

    山、谷和陷阱

    局部最大值之外

    模拟退火算法

    随机性，进化和创造力

    10 网络 我们如何联系？

    分组交换

    信息确认

    指数退避算法：宽恕的算法

    流量控制和拥塞避免

    反馈语：语言学的流量控制

    缓存膨胀：这就是延时，傻瓜迟到不如永远不到

    11 博弈论 别人的想法

    递归

    达到均衡

    占优策略，无论好坏

    公地悲剧

    机制设计：改变游戏

    机制设计的演变

    信息瀑布：泡沫的悲剧理性

    你自己的计算

    结语 计算善意

    版权页序言

    假设你想租房子，正在旧金山四处寻找房源。旧金山可能是整个美

    国最难找房子的城市了。由于技术产业的蓬勃发展，再加上城市区划法

    律严格限制建造新住房，旧金山的房租已经与纽约不相上下，甚至比纽

    约还高。房源清单列出来几分钟，房子就会被人们一抢而空。通常情况

    下，只有第一个把定金支票塞到房东手里的人，才能拿到房子的钥匙。

    理论上讲，认真调查、仔细斟酌是理性消费者的一大特征，但是旧

    金山的残酷市场并没有为他们留有权衡考虑的机会。在购物中心或者网

    上购物时，人们可以反复权衡再做出决定，但是将要入住旧金山的租客

    没有这个特权，他们必须迅速做出决定：要么舍弃其他所有可能的选

    择，就选定当前正在看的这套房子，要么掉头就走，再也不要回头。

    简单起见，我们姑且假设，你唯一关心的就是尽最大可能增加挑中

    最理想公寓的机会。你的目标是把“看过的好房子被人挑走”与“还有好

    房子没来得及看”这两种遗憾的发生概率降至最低。于是，你立刻发现

    自己陷入了两难境地：如果没有衡量的标准，如何判断一套公寓是否是

    最合适的呢？如果你不先看一些公寓(这些公寓将被你放弃)，又如何

    确定衡量标准？你收集的信息越多，越能在最合适的机会出现时准确地

    认出它，但是你已经与最合适的机会失之交臂的可能性也越高。

    那么，到底该怎么办？如果收集信息的行为会危及结果，那么怎样

    才能在掌握足够多信息的基础上做出明智决定呢？这个令人极其为难的

    情境近乎于一个悖论。

    在被问及此类问题时，大多数人凭直觉给出的回答可能大致如此：这需要在继续挑选与立刻下手之间达成某种平衡。也就是说，你必须先

    看足够多的房子，确定一个标准，然后接受符合这个标准的房子。事实

    上，平衡概念正是解决这类问题的关键。但是，大多数人根本无法确定

    这个平衡点在哪里。好消息是，这个平衡点已经被找出来了。

    答案就是37%。

    如果你希望选中最合适公寓的可能性达到最大，那么在看前37%的

    房子时不要做出任何决定(如果你准备花一个月的时间挑选房子，那么

    在前11天不要做出决定)。这段时间你是在为制定标准做准备，因此看

    房子时把银行卡放在家里吧。但是，过了这个时间点之后，你就要做好

    随时签约的准备(包括准备好定金等)，一旦你对某套房子的满意程度

    超过之前看过的所有房子，就立刻下手。在继续挑选与立刻下手之间做

    出的这种妥协，并不仅仅是一种直觉，而是已经得到证明的最优解。

    我们知道这个答案，是因为找房子问题属于数学上被称作“最优停

    止”(optimal stopping)的一类问题。37%法则明确了解决这些问题的一

    系列简单步骤(计算机科学称之为“算法”)。事实证明，找房子仅仅是

    最优停止问题在日常生活中的表现形式之一。在面临一连串选择时如何

    做出决定的难题，经常会改头换面，以不同的形式出现在我们的生活当

    中。在驶入停车位之前，需要绕整个停车场多少圈？在商业风险中何时

    套现脱身？在买房子或者停车时，何时是结束观望、做出决定的最佳时

    机？

    在约会这个更加令人头疼的问题上，人们也经常要面对这样的难

    题。最优停止理论是一夫一妻婚姻制度催生的科学。

    每天，人们都要面临最优停止问题的困扰(当然，诗人更愿意追逐

    的话题肯定是求婚带来的烦恼，而不是停车时的两难境地)，有时甚至

    会因此而痛苦不堪。不过，我们大可不必如此，因为这类问题至少可以通过数学方法来解决。借助并不繁复的算法，我们不仅可以解决找房子

    的问题，生活中遭遇的所有最优停止问题都可以被妥善处理。

    从本质上讲，我们身边经常出现因为租房子、停车、求婚而感到苦

    恼的人，这些人其实就是在自寻烦恼。他们需要的不是治疗师，而是一

    种算法。治疗师告诉他们要在冲动与多虑之间找到一个正确的、舒服的

    平衡点。

    算法告诉他们这个平衡点就是37%。

    ※—※—※

    由于我们生活在有限的时间和空间之中，因此所有人都会面临一系

    列特定的问题，诸如在一天或者十年里，哪些事必须做，哪些事应当放

    手？如何在尝试新的体验与从事自己喜爱的活动中取得平衡，才能生活

    得惬意自在、心满意足？

    这些问题看起来似乎都是人类特有的，其实不然。半个多世纪以

    来，计算机科学家苦苦思考的问题(有很多已经得到妥善解决)与这些

    日常难题在本质上并无区别。例如，处理器在执行用户请求时应该如何

    分配自己的“注意力”，才能降低费用、节省时间？在什么情况下应该在

    不同任务之间来回切换？刚开始应该接受多少任务量？如何利用有限的

    存储资源取得最佳效果？应该收集更多数据，还是根据已收集的数据采

    取行动？对人类而言，如何把握今天可能不是一件易事，但是我们身边

    的计算机可以轻轻松松地把握每一毫秒。显然，计算机有很多值得我们

    借鉴的地方。

    将算法与人类生活相提并论似乎是一件很奇怪的事。在很多人看

    来，“算法”这个词意味着神秘莫测的谋划与操作，与大数据、大政府、大企业有密切的联系，正在逐渐变成现代社会基础架构中一个越来越重要的部分。其实，算法指的就是解决问题的一系列步骤，其含义远不限

    于计算机，存在的历史也远远长于计算机。在计算机开始使用算法之

    前，人类早就将算法应用到生活当中了。

    “算法”(algorithm)一词得名于波斯数学家花拉子密。公元9世

    纪，这位数学家写过一本书，讨论用纸笔解决数学问题的技巧。[书名

    为“al-Jabr wa’l-Muqabala”，其中的“al-jabr”就是后来“algebra”(代数)

    这个词的前身。]不过，最早的数学算法早于花拉子密。在巴格达附近

    出土的4000年前的苏美尔人泥板文献上，就刻有一幅长除法示意图。

    但是，算法不仅限于数学。在按照食谱介绍烤面包时，食谱上的所

    有步骤就是一个算法。按照图样编织毛衣时，这份图样就是一个算法。

    使用鹿角的末端连续精确地敲打，使石器形成锋利的刃的过程(这是制

    作精密石器的一个关键步骤)，也遵循着一个算法。从石器时代开始，算法就已经是人类生活的一部分了。

    ※—※—※

    本书将探讨人类事务算法设计这个概念，以帮助人们更好地处理日

    常生活中遇到的难题。将计算机科学的研究方法应用于日常生活，可以

    在多个层面上产生深远的影响。首先，它可以提供切实有效的建议，帮

    助我们解决具体问题。例如，最优停止理论可以告诉我们何时应该小心

    观察，何时应该果断行动；探索-利用平衡理论教会我们如何在尝试新

    事物与因循守旧之间找到平衡点；排序理论可以帮我们判断出是否需要

    以及如何整理办公室；缓存理论可以帮助我们合理地填充橱柜；日程安

    排理论则可以提供合理安排时间的高招。

    其次，计算机科学还为我们理解这些领域的深层次运行规则提供了

    一套语汇。卡尔·萨根指出：“与其说科学是大量知识的汇总，不如说它

    是一种思考方式。”即使生活中的某些情况非常复杂，我们无法进行严格的数值分析，找不到任何现成的答案，我们也可以考虑这些问题的简

    单化表现形式，从而得出某些直觉和概念，帮助我们理解其中的关键环

    节并取得进展。

    从更广泛的意义上看，借助计算机科学，我们可以了解人类思想的

    本质和理性的意义，学会回答如何度过一生这个最古老的问题。把认知

    视为一种解决周围环境所造成的问题(从本质上看，都是一些计算问

    题)的手段，并认真地加以研究，就有可能彻底改变我们对人类理性的

    理解。

    认为研究计算机内部运行机制能够帮助我们学会思考与决策、判断

    某个事物是否可信、选择行为方式的观点，在很多人看来，不仅把问题

    过于简单化了，而且具有误导性。即使计算机科学告诉我们应该如何思

    考、应该采取哪些行动，我们愿意接受吗？读一读讲人工智能和机器人

    的科幻小说就会发现，那样的生活似乎都不是我们所向往的。

    之所以如此，部分原因是我们把计算机看成了机械呆板的确定性系

    统——这些机器借助严谨的演绎逻辑，通过穷举所有可选方案，无论花

    费多少时间、问题难度如何，它都可以给出完全正确的答案。事实上，在阿兰·图灵当时的想象中，计算机就应该是这样。这位第一个设想出

    计算机的人通过类比的方式给出了计算的定义，而类比的原型就是认真

    钻研的人类数学家——他们通过长长的计算步骤，最终得出绝对正确的

    答案。

    因此，当人们发现现代计算机处理难题的方式与他们对计算机的认

    识并不一致的时候，他们也许会大吃一惊。当然，简单的算术对现代计

    算机而言没有任何难度。目前，计算机科学面临的最难解决的问题其实

    是人机对话、修复破损文件、下围棋取胜，这些问题都具有规则不明

    确、所需信息不全，或者需要考虑无数种可能性才可以找出正确答案的

    特点。研究人员已经开发出各种算法，使计算机在解决难度极大的问题时不需要完全依赖穷举计算。要解决这些来自现实世界的任务，就必须

    正确处理好可能性问题，利用粗略估算，在时间与精确度之间做出某种

    妥协。

    随着计算机处理现实任务的能力不断增强，计算机算法不仅对于人

    类自己的生活具有借鉴意义，同时还为人们理解人类认知提供了一个更

    好的比较标准。在过去的一二十年里，行为经济学对人类进行了非常具

    体的研究，结果发现，人类是不理性的，很容易犯错误，而问题的源头

    在很大程度上就是大脑这个古怪而独特的硬件。这种自我贬低的认识越

    来越普遍，却无法解释某些令人困惑的问题。例如，在完成包括想象、语言、因果推理在内的大量认知任务时，4岁儿童的能力仍然超过成本

    高昂的超级计算机，这到底是什么原因？

    从计算机科学为日常问题提供的解决方案可以看出，人类思维具有

    另外一种特点——人生充满了难以解决的问题。人经常犯错误，虽然这

    可以说明人类大脑容易出错，但是也表明这些问题具有难以解决的本质

    特点。通过算法来思考我们周围的世界，了解我们所面临问题的基本结

    构以及计算机给出的解决方案的特性，可以帮助我们真实地了解我们自

    己，更好地理解我们所犯的那些错误。

    事实上，人类需要不断面对计算机科学所研究的一些高难度问题，在不确定性及时间有限、信息不全、情况瞬息万变等不利因素的干扰下

    做出决定。针对一些问题，即使最前沿的计算机科学也没能开发出永远

    不会犯错误的有效算法，有的情形似乎是任何算法都无法解决的。

    不过，尽管有的现实问题异常复杂，人们还没有开发出完善的算

    法，但是一代代计算机科学家一直在与这些难题斗争，并且在这个过程

    中得出了深刻而独到的见解。这些来之不易的真知灼见与我们对理性的

    直觉认识并不一致，与数学家对周围世界的精确描述也迥然不同——数

    学家一心想要把这个世界变成整齐划一的线条。计算机科学告诉我们：不要总是考虑所有的可选方案；不必每次都追求最佳结果；偶尔犯点儿

    错误；放下包袱，轻装前进；有的事情可以暂时放一放；相信自己的本

    能，不要过多思考；放松自己；采用抛硬币的方式；要体谅，但是不能

    忘记；忠于自我。

    用计算机科学的智慧指引自己的人生之路，这似乎是一条不错的建

    议。毕竟，与大多数建议不同的是，这条建议有据可依。

    ※—※—※

    当初，算法设计在各学科的夹缝中找到了立足之地，它是数学与工

    程技术糅合而成的怪异混合体。现在，为人类设计算法的工作也面临相

    同的境遇——找不到一个现成的归属学科。今天的算法设计不仅需要借

    助计算机科学、数学和工程技术，还需要得到统计学、运筹学等相关领

    域的帮助。此外，我们不仅需要考虑计算机算法设计与人类思维活动之

    间的关系，还需要认真研究认知学、心理学、经济学等学科。

    本书作者都有跨学科工作与研究的经历。布莱恩学习的是计算机科

    学和哲学，研究生阶段学习的是英语，毕业之后从事的是与这三个学科

    都相关的工作。汤姆学的是心理学和统计学，在加州大学伯克利分校从

    教期间，他主要研究人类认知与计算之间的关系。但是，人类算法设计

    涉及多个领域，任何人都不可能是所有领域的专家。因此，在探索研究

    方便人类生活的算法时，我们还与过去50年最著名的算法专家进行了交

    流，询问这些全世界最聪明的人，他们的研究对他们自己的生活(包括

    寻觅配偶、收拾衣帽鞋袜)到底产生了什么样的影响？

    接下来，我们就将开始引领大家游览这个神秘的领域。首先，我们

    将讨论计算机与人类大脑都需要面对的巨大挑战：如何应对有限空间、有限时间、有限注意力、未知的未知事物、不完整的信息与不可预见的

    未来给我们造成的麻烦，如何镇定自若、充满自信地面对这些麻烦，如何与其他人一起，共同面对这些麻烦，我们将讨论这些难题的基本数学

    结构，了解计算机解决大多数难题的设计原理(有时，这些设计甚至与

    我们的想象背道而驰)。此外，我们还将了解人脑的工作原理，了解人

    脑在解决相同类型问题、应对相同限制条件时有哪些独特且密切相关的

    处理方式。最终，我们不仅将得到有助于解决身边问题的一系列具体建

    议，学会在面临最复杂人类困境时有助于我们看清其脉络结构的新方

    法，还可以清醒地认识到人与计算机深度融合过程中的痛苦与艰辛。此

    外，我们还会有一些意义更加深刻的收获：一套描述周围世界的全新语

    汇以及一个从全新角度了解自己的机会。01 最优停止理论 如何选择停止观望的时

    机？

    约翰尼斯·开普勒

    所有的基督徒都会在结婚请柬的最前面郑重宣布，他们走进婚姻的

    殿堂是遵从上帝的特别安排。但是，我要站在哲学的角度，详细地探讨

    这个问题……

    简·奥斯汀，《爱玛》

    如果你觉得马丁先生是最优秀的人选，如果你觉得与他相处最为融

    洽，那么你还犹豫什么呢？

    对于在中学时代就建立了恋爱关系的大一新生而言，感恩节就是一

    个严峻的考验：因为回家度过短短4天的假期之后，很多恋人就劳燕分

    飞了。大学辅导员把这个普遍现象称作“放弃火鸡”。

    大一新生布莱恩就面临着这个问题。他中学时的女友在另外一所大

    学，天各一方的两个人不仅需要解决空间距离造成的麻烦，还需要认真

    思考一个问题：他们两人之间的感情到底有多深？他们从来没有考虑过

    这个具有哲学深度的问题。由于没有类似的感情可以参考，他们无从回

    答这个问题。于是，焦虑不安的布莱恩找到辅导员，向她寻求帮助。辅

    导员知道这是新生经常遭遇的一个典型难题，所以她用一种极其冷淡的

    语气给出了自己的建议：“先收集一些数据吧。”

    显而易见，在连续性单配偶的生活方式中，人们不可避免地会遇到一个非常重要的问题：接触多少人之后，才可以确定自己的理想伴侣？

    如果在收集数据的过程中与自己的“真命天子”失之交臂，那该怎么办？

    这似乎成了感情问题上无解的“第22条军规”。

    我们知道，这个令大一新生忧心忡忡、牢骚满腹的“第22条军规”其

    实就是数学界的“最优停止问题”，它的答案其实很简单，就是37%。

    当然，前提条件是你愿意在爱情问题上做出各种假设。秘书问题

    在所有最优停止问题中，最大的难点不在于选择哪一种可选方案，而是确定自己需要考虑多少种可选方案。这些问题往往会引发不同的后

    果，不仅陷入爱河的人和需要租房的人必须慎重考虑，司机、房主、入

    室行窃者等也常常面临同样的抉择。

    “37%法则”[1]

    源于所谓的“秘书问题”——最优停止问题中最著

    名的一类难题。秘书问题的情境与我们前面考虑过的租房难题十分相

    似。假设一堆人申请一个秘书岗位，而你是面试官，你的目标是从这堆

    申请人中遴选出最佳人选。你不知道如何给每一名申请人评分，但是可

    以轻松地判断哪一名申请人更加优秀。(用数学语言来表述，就是说你

    只能看到序数，即申请人相互比较的排名，但是无法看到基数，即在一

    般性评分标准下的得分。)你按照随机顺序，每次面试一名申请人。你

    随时可以决定将这份工作交给其中一人，而对方只能接受，于是面试工

    作就此结束。但是，一旦你否决其中一名申请人，就不能改变主意再回

    头选择他。

    普遍认为，秘书问题第一次出现在出版物中是在1960年2月，那一

    期的《科学美国人》杂志在马丁·伽德纳最喜欢的栏目——“趣味数

    学”专栏中刊登了几个难题，其中之一就是秘书问题，不过当时没有明

    确地提到“秘书”这个词。但是，这个问题到底从何而来，这是一个非常

    神秘的谜。除了一些推测以外，初期的调查没有任何确凿的结论。随

    后，我们风尘仆仆地赶到斯坦福大学，查阅伽德纳的文书档案。伽德纳

    在20世纪中期留下来的那一盒盒书信，出乎意料地把我们的调查变成了侦探工作。阅读书信有点儿像偷听别人打电话，你只能听到通话一方所

    说的话，因此需要推断另一方到底说了什么。从这些回信看，大约50年

    前，伽德纳本人似乎正在调查秘书问题的来源。但是，看完这些书信，我们更是一头雾水了。

    哈佛大学数学家弗雷德里克·莫斯特勒回忆说，1955年，他听同事

    安德烈·格里森提到过这个问题，而格里森又是从其他人那里听说的。

    阿尔伯塔大学的里奥·莫泽在信中说，他曾经在波音公司R.E.加斯克尔

    的“笔记”中看到过这个问题，而加斯克尔本人则说他是从一位同事那里

    听说这个问题的。罗格斯大学的罗杰·平克汉姆称，他是1955年从杜克

    大学数学家J.舍恩菲尔德那里第一次听说秘书问题的，他还说：“我记

    得，他说他是从密歇根大学的某个人那里听说的。”

    几乎可以肯定，“密歇根大学的某个人”其实就是梅里尔·弗拉德。

    尽管在数学界以外几乎没有人知道弗拉德，但是他对计算机科学的影响

    很难被忽略。他把“旅行商问题”(我们将在第8章深入讨论)变成了一

    个广为人知的内容，还设计了“囚徒的困境”(参见第11章)，甚至“软

    件”(software)一词也可能是他造出来的。1958年，他成了已知的第一

    个发现37%法则的人，同时他宣称，他从1949年就开始考虑这个问题

    了。但是，在说到最初来源时，弗拉德本人提到了另外几名数学家。

    秘书问题是一个近乎完美的数学难题：问题本身表述简单，解题难

    度非常高，答案简洁明了，而影响力又足以让人产生浓厚的兴趣。因

    此，通过人们的口口相传，这个问题以燎原之势在20世纪50年代的数学

    界迅速蔓延开来。1960年，在伽德纳专栏的推波助澜之下，它又大大地

    激发了普通大众的想象力。至20世纪80年代，秘书问题已经变成了一个

    研究分支，无数人撰文讨论这个问题及与其相关的变体。

    至于这个问题是如何与秘书产生联系的，这是一个非常有意思的过

    程——每种文化的社会偏爱都会对社会的形式系统产生影响。例如，在我们的心中国际象棋是中世纪欧洲人的象征，但是实际上国际象棋起源

    于8世纪的印度。15世纪，粗暴的“欧洲化”过程把沙阿(即国王)变成

    了王，维齐尔(即高官)变成了王后，而大象则成了基督教主教的形

    象。最优停止问题同样有多种不同化身，每种化身都是当时关注热点的

    某种反映。19世纪，最优停止问题的典型形式是巴洛克彩票和女性挑选

    求婚者的行为；20世纪初，常见的表现形式是驾车度假的人挑选宾馆、男性选择约会对象；在官僚作风盛行、男性占主导地位的20世纪中叶，最典型的最优停止问题是讨论男性老板如何挑选女性助手的问题。第一

    次明确提出“秘书问题”的是发表于1964年的一篇论文，自此之后，这个

    名称就再也没有发生变化。

    [1]正文加粗字体在本书中指的是算法。37%从何而来？

    在选择秘书时，遴选程序停止过早或者过晚都会导致不理想的结

    果。停止过早，最优秀的申请人还没有得到亮相的机会；停止过晚，就

    说明你在为一位根本不存在的更优秀的申请人保留这份工作。要取得最

    理想的结果，显然需要在两者之间找到最合适的平衡点，在甄选时既不

    可迟迟不决，又不可草草收手。

    如果找到最优秀申请人是你追求的唯一目标，那么在整个面试过程

    中，只要不是已有申请人当中的最优秀人选，你都不会接受。但是，仅

    仅达到“目前最佳”这个条件，还不足以说服面试官。比如说，第一名申

    请人毫无疑问就符合这个条件。一般而言，我们有理由相信，随着面试

    程序不断进行下去，出现“目前最佳”申请人的概率将不断下降。例如，第二名申请人是截至目前最优秀申请人的可能性是50%，第五名的可能

    性只有15，第六名的可能性只有16，以此类推。因此，随着面试工作

    的深入，目前为止最优秀申请人一旦出现，必然会令人眼前一亮(别忘

    了，根据定义，这名申请人比之前所有申请人都更加优秀)，不过，这

    种可能性在不断降低。

    所以说，看到第一个目前最优秀申请人就欣然接受(也就是说，面

    试第一名申请人之后就结束面试程序)，显然是过于草率了。在一共有

    100名申请人时，也不能因为第二名申请人比第一名申请人更优秀就迫

    不及待地选择他，因为这种做法同样有些操之过急。那么，我们到底该

    怎么办？

    凭直觉，我们可以找到几种应对的办法。例如，当第三次(或者第四次)出现胜过前面所有的申请人时，就把工作机会交给他。或者，在

    连续多个申请人都不理想的情况下，一旦出现一名目前为止最优秀的人

    选，就毫不犹豫地接受他。

    但是，事实证明，所有这些相对来说似乎有道理的策略都算不上是

    最明智的做法。事实上，效果最佳的做法是接受所谓的“摸清情况再行

    动准则”(look-then-leap rule)：事先设定一个“观察”期，在这段时间

    里，无论人选多么优秀，都不要接受他(也就是说，你的任务就是考察

    目标，收集数据)。“观察”期结束之后，就进入了“行动”期。此时，一

    旦出现令之前最优秀申请人相形见绌的人选，就立即出手，再也不要犹

    豫了。

    考虑申请人数极少时的秘书问题，“摸清情况再行动准则”就会自动

    显露出来。如果只有一名申请人，这个问题就非常简单——接受她的申

    请!如果有两名申请人，无论你如何选择，你成功选到优秀人选的概率

    都是50%。你可以接受第一名申请人(此时，她是半程最优秀申请

    人)，或者拒绝她，而拒绝第一名申请人就意味着接受第二名申请人

    (她也是半程最优秀申请人)。

    如果有第三名申请人，情况就一下子变得有意思了。如果随机选择

    一名申请人，得到理想结果的概率是13，也就是33%。有两名申请人

    时，我们没有办法取得比碰运气更好的结果。那么，在有三名申请人

    时，会怎么样？事实证明，我们可以取得更理想的结果，而其中的关键

    就在第二场面试。在面试第一名申请人时，我们没有任何信息——她肯

    定是目前最优秀的申请人。在面试第三名申请人时，我们没有任何能动

    性——我们只能将工作机会交给这名申请人，因为我们已经拒绝了其他

    人的申请。但是，在面试第二名申请人时，我们既掌握了一些信息，又

    有一定的能动性——我们知道她与第一名申请人相比孰优孰劣，同时我

    们既可以接受她，也可以拒绝她。如果她比第一名申请人优秀，我们接受她，反之就拒绝她，那么会产生什么样的结果？事实上，在有三名申

    请人时，这是最理想的方案。令人吃惊的是，在有三名申请人时采用这

    个方法，与有两名申请人时选择半程最优秀人选的方法相比，效果不相

    上下。[1]

    在有4名申请人时，穷举所有可能的情况之后就会发现，我们仍然

    应该在面试第二名申请人时采取行动；如果一共有5名申请人，我们应

    该等到面试第三名申请人时才采取行动。

    随着申请人数不断增加，观察与行动之间的分界线正好处在全部申

    请人37%的位置，从而得出了37%法则：在考察前37%[2]

    的申请人时，不要接受任何人的申请；然后，只要任何一名申请人比前面所有人选都

    优秀，就要毫不犹豫地选择他。

    表1-1 挑选秘书的最优方案事实证明，利用这种最优方案，我们选中最优秀申请人的概率为

    37%。方案本身与出现理想结果的概率正好相等，这是这类问题表现出

    来的令人奇怪的数学对称性。上表列出了申请人数不同时的秘书问题最

    优解决方案。从中可以看出，随着申请人数不断增加，取得理想结果的

    概率(以及从观察期切换到行动期的时间点)在37%左右。

    采用最理想的方案也会有63%的失败率，这是一个令人警醒的事

    实。在面对秘书问题时，即使我们采取了最理想的行动方案，在大多数

    情况下也会遭遇失败，也就是说，大多数情况下我们都无法选中所有人选当中最优秀的那名申请人。对于把爱情视为寻觅“真命天子”的人来

    说，这确实是一个坏消息。不过，也不完全都是坏消息。直觉告诉我

    们，随着申请人数的不断增加，选中最优秀申请人的可能性将稳步下

    降。例如，如果采用随机选择的方式，在申请人总数为100时，我们得

    到理想结果的可能性是1%，在总人数为100万时，可能性就会降到

    0.0001%。但是，令人意想不到的是，秘书问题的计算结果不会发生变

    化。如果采用最优停止理论，在100人当中选中最优秀申请人的可能性

    是37%。而总人数是100万时，无论你相信与否，你得到理想结果的可

    能性仍然是37%。因此，申请人总数越多，最优算法理论就越有价值。

    的确，在大多数情况下，大海捞针都会无功而返，但是，无论“海洋”多

    么辽阔，最优停止理论都是最理想的工具。

    [1]采用这个方案，最优秀申请人落选与得不到面试机会的概率分别是33%和16%。具体来

    说，三名申请人正好有6种可能的排序，即1-2-3、1-3-2、2-1-3、2-3-1、3-1-2和3-2-1。如果考察

    第一名申请人并选择比她优秀的那名申请人，这个方案会在3种情况下(2-1-3、2-3-1、3-1-2)

    取得成功，在另外三种情况下将得到不理想效果，其中两种情况(1-2-3、1-3-2)会导致过度挑

    剔的问题，一种情况(3-2-1)会导致挑选不够充分的问题。

    [2]事实上，应该是略低于37%。准确地说，考察申请人的数学最优比例是1e，其中e是复

    利计算中经常出现的数学常数，等于2.71828……。但是，如果你记不住e的12个小数位，也无

    须着急。只要这个比例在35%与40%之间，取得最理想结果的可能性就非常接近于最高值。情场上的出手时机

    托马斯·马尔萨斯

    两性之间的情欲几乎不会随着时代的变迁而发生改变。在代数学

    上，我们可以称之为给定量。

    芭芭拉·布什

    夺走我的初吻的男人后来成了我的丈夫。我把这些告诉孩子们时，他们的反应十分强烈。

    卡内基-梅隆大学的运筹学教授迈克尔·特里克也曾经为寻觅真爱而

    苦恼，当时他还是一名研究生。他回忆说：“我突然想起来，人们研究

    过这个问题，这不就是秘书问题吗？我身边有一个空缺，现在有若干人

    提出了申请，而我的目标就是从中选出最优秀的申请者。”于是，他进

    行了量化分析。他不知道他一辈子可以结识多少名女性，但是37%法则

    有一定的灵活性，既可以表示申请者的人数，也可以表示遴选过程持续

    的时间。假设遴选过程从18岁开始，至40岁结束，那么根据37%法则，在26.1岁时他就应该结束观察期，随时果断出手。碰巧的是，当时的特

    里克正好处于这个年龄。因此，当他发现某一名女性比之前所有约会对

    象都优秀的时候，他知道机会来了，于是他果断行动。他说：“我不知

    道她会不会是完美的妻子(模型的各种假设都无法帮助我做出这个判

    断)，但是毫无疑问，她符合算法为这个步骤开出的所有条件。于是，我向她求婚了。”

    “结果，她拒绝了我的求婚。”至少从17世纪开始，爱情问题就已经让数学家头疼了。现代人知道

    约翰尼斯·开普勒这个名字，或许是因为他发现行星轨道是椭圆形的，此外他还是“哥白尼革命”的重要成员，与伽利略、牛顿等人一起，颠覆

    了人类对自己在宇宙中所处位置的认知。不过，开普勒也不是不食人间

    烟火。1611年，在他的第一任妻子离世后，渴盼重建家庭的开普勒开始

    了漫长而艰苦的求爱经历，前后一共交往了11名女性。在前4名交往对

    象中，开普勒最喜欢第4个(“因为她身材高挑，英姿飒爽”)，但是他

    没有就此打住。开普勒回忆说：“如果不是爱情和理智把第5名女性强推

    给我，我应该已经安定下来了。但是，这名女性对我的爱，她的谦恭忠

    诚、勤俭持家以及她对继子继女的爱，一下子征服了我。”

    他接着说道：“不过，我仍然我行我素，继续与其他女性交往。”

    亲朋好友继续为开普勒牵线搭桥，开普勒也没有拒绝，不过兴致不

    是很高，因为他的心仍然被第5名交往对象占据着。在一共交往了11名

    女性之后，开普勒决定收手了。他回忆说：“就在我准备前往雷根斯堡

    的时候，我回过头来去找第5名交往对象并向她求婚，结果她同意

    了。”于是，开普勒和苏珊娜·罗伊特林格举行了婚礼。除了第一次婚姻

    留给他的几个孩子之外，开普勒和罗伊特林格又生了6个孩子。据说，开普勒之后的家庭生活十分幸福美满。

    开普勒和特里克在寻觅爱情上的亲身经历告诉我们(两者的结局正

    好相反)，秘书问题把情况想得过于简单了。在经典的秘书问题中，申

    请者肯定希望得到那份工作，像特里克那样遭遇拒绝的情况绝不会发

    生。此外，申请者一旦被否决之后，就不可以“复活”，因此开普勒采取

    的策略是行不通的。

    在秘书问题首次被提出后的几十年时间里，人们研究了各种各样的

    情境，并结合不同的条件提出了若干最优停止策略。例如，针对可能遭

    到拒绝的问题，他们提出了一个简单明了的数学答案：尽早向多名对象伸出橄榄枝。假如遭到拒绝的可能性是50%，那么得出37%法则的那个

    数学分析过程就会告诉你，遴选过程完成14后就应该随时准备求婚

    了。如果遭到拒绝，那么在发现下一个最佳人选时要再次求婚，直到求

    婚成功为止。运用这个策略，获得成功(即向所有人选中的最佳人选求

    婚并被接纳)的总概率仍然可以达到25%。根据自己的标准寻觅爱情本

    身就有难度，再加上遭到拒绝这个不利条件，25%的成功概率可以算是

    一个还不错的结果了。

    开普勒把自己没有及时出手的原因归咎于“不安现状、心存疑虑”。

    他在一封信中向自己的知己好友哀叹：“难道非得四处碰壁，所有欲望

    都落空之后，我的心才会平静下来，接受命运的摆布吗？”在这种情况

    下，最优停止理论同样可以起到一定的安慰作用。事实证明，不安现状

    和心存疑虑并不是道德沦丧或者心理退化的标志，而是在合适情境下捕

    捉二次机会的最有效策略的一个组成部分。如果可以复活之前被放弃的

    人选，最优算法就会对我们所熟悉的摸清情况再行动准则做一个小的调

    整：推迟表态时间，制订备用计划。

    例如，我们假设即时求婚肯定会被接受，而迟滞求婚则有一半的可

    能遭到拒绝。根据数学分析，我们在观察前61%的人选时都不应该表

    态，等到剩余39%的人选中出现目前最优秀人选时再出手。如果考察完

    了所有人选之后仍然没有找到合适对象(开普勒当时就面临这种情

    况)，就回过头，在你淘汰的人选当中选择最优秀的那个。在这种情况

    下，策略与结果之间再次表现出对称性，在允许二次选择这个条件下，你最终选中最优秀人选的概率仍然是61%。

    正因为现实与经典秘书问题有所不同，所以开普勒最终还是找到了

    自己的幸福。事实上，经典问题发生的那个小变化也没有导致特里克愿

    望落空。在遭到拒绝之后，特里克读完大学并在德国找了一份工作。特

    里克回忆说：“我在酒吧里遇到一位漂亮的姑娘，我们一见钟情，三周后就同居了。后来，我邀请她去美国‘暂住一段时间’。”姑娘接受了邀

    请。6年后，他们举行了婚礼。掌握候选对象的完整信息

    经典秘书问题的前提条件是，即时表态一定会被接受，而迟滞表态

    肯定会遭到拒绝，但是我们在前面讨论的第一组变量(拒绝与复活)则

    颠覆了这个前提。在这种情况下，最有效的应对办法没有任何变化，仍

    然是：不要急于表态，观察一段时间后及时出手。

    不过，秘书问题的一个更重要的前提，可能会引起我们的异议。在

    秘书问题中，除了可以相互比较之外，我们对这些申请者一无所知。对

    于优秀人员应该具有哪些特点，我们无法参考任何客观标准或者已有标

    准，而且在比较这些申请者时，我们只能知道孰优孰劣，但是无法了解

    彼此之间的确切差距。正因为如此，“观望”阶段是不可避免的。在前期

    阶段，我们冒着与优秀人选失之交臂的危险，不断调整我们的期望值与

    权衡标准。数学家把这种最优停止问题称作“无信息博弈”。

    这种情境可能与大多数寻租公寓、寻觅伴侣和招聘秘书的情况有天

    壤之别。假设我们可以参考某种客观标准。例如，安排所有秘书参加打

    字考试，然后像美国高考(SAT)、研究生入学考试(GRE)或者法学

    院入学考试(LSAT)那样按照百分制统计成绩。也就是说，根据得

    分，我们可以知道每名申请者的打字水平在所有人选中的位置。如果申

    请者得了51分，则表示她的打字水平略高于平均水平，如果得了75分，则表示她的水平高于34的申请者，以此类推。

    假设所有申请者可以代表全体人口样本，而且所有数据没有受到任

    何倾向性或者自选择的影响。同时，假设打字速度是我们判断申请者是

    否合适的唯一条件。此时，情况就完全不同了，因为我们拥有数学家所谓的“全信息”。1966年的那篇秘书问题研讨会论文指出：“不需要根据

    积累的经验设定判断标准。有时，我们可以立刻做出一个有益的选

    择。”换言之，即使得95分的申请者第一个接受评判，我们也可以信心

    满满地立刻与她签约。当然，前提是我们认为所有申请者中没有得96分

    的。

    问题来了。如果我们的目标是找到最适合这份工作的优秀人选，那

    么我们仍然需要小心斟酌，因为其余的申请者当中可能还有更加优秀的

    人选。不过，既然我们掌握了全信息，就可以直接计算这种可能性到底

    有多大。例如，下一个申请者得到96分或者更高分的可能性一定是

    120。因此，是否立刻停止的决定取决于还剩下多少申请者没有接受面

    试。全信息的意义在于我们无须观望就可以直接出手。此时，我们可以

    运用阈值准则，一旦发现某位申请者的分数高于某个值，就立刻接受

    她，而不需要先考察一批候选人并确定阈值。但是，我们需要密切关注

    可供选择的人还有多少。

    数学计算表明，如果还有很多人等待面试，那么你就不应该接受当

    前正在面试的那名申请者，即使她非常优秀，因为你有可能找到一个更

    优秀的人选。但是，随着可供选择的人数不断减少，你就应该做好准

    备，随时准备与优于平均水平的申请者确立雇佣关系。有一句我们都比

    较熟悉(尽管不是那么鼓舞人心)的话说得好：面对花哨的包装，还是

    降低你的期待吧。我们还可以找到另外一句话，用以说明与之相反的情

    况：天涯何处无芳草，何必单恋一枝花!重要的是，无论是哪种情况，数学都可以告诉我们临界点到底在哪儿。

    在这种情况下，最简单的方法是从后往前，反过来理解这些数字的

    含义。如果你一直面试到最后一名申请者，那么你就别无选择，只能接

    受他。如果你一直在观望，那么在面试倒数第二名申请者时你需要考虑

    的问题就变成了：他的分数是否高于50呢？如果是，就雇用她；如果不是，那么你可以考虑把宝押在最后一名申请者身上，因为她的分数高于

    50的可能性是50%。同理，如果倒数第三名申请者的高于69，倒数第四

    名的分数高于78，以此类推，那么你就应该立刻选择这名申请者。也就

    是说，剩余的申请者越多，在评判时就应该越挑剔。无论如何，你都不

    应该选择低于平均水平的申请者，除非你已经别无选择。(此外，既然

    你一定要在这些申请者当中挑出最优秀的，那么如果某名申请者不是目

    前为止最优秀的人选，就一定不要雇用他。)

    在这种全信息版本的秘书问题中，选中最优秀申请者的可能性是

    58%。这个概率远谈不上十拿九稳，但是已经大大优于无信息博弈中根

    据37%法则得到的37%的成功率。如果你掌握了所有信息，那么即使申

    请人数非常多，你多半也会取得成功。

    全信息秘书问题中的最优停止阈值因此，全信息博弈往往会产生令人意想不到，有时甚至会让人感到

    奇怪的结果。如果追求的目标是金钱，而不是爱情，则成功的可能性更

    高。在根据某种客观标准(例如收入排名情况)评判合作伙伴时，可供

    使用的信息比较多。如果评判标准是模糊不清的情感反应(“爱情”)，则可能需要我们根据经验以及比较结果不断做出调整，同时可供使用的

    信息也相对较少。

    当然，选择对象的“资产净值”与我们权衡的标准不一定一致。任何

    标准，只要可以全面反映申请者与其他人对比的情况，就会导致我们弃

    用摸清情况再行动准则，转而采用阈值准则，同时我们成功找出最优秀

    申请者的可能性也会大大增加。

    此外，人们还经常修改秘书问题的其他前提条件，使之与现实生活

    中寻觅爱情(或挑选秘书)等难题更为相似，结果形成了更多的秘书问

    题变种。不过，最优停止问题给我们的启发不仅限于约会与招聘这两个

    方面。事实上，在租房子、找停车位、见好就收的时机选择等问题中，我们同样需要面对一个又一个的可选方案，做出最有利的选择。从一定

    程度上说，这些问题已经得到了解决。卖房子的时机

    只需修改经典秘书问题的两个特征，就可以从浪漫的爱情跳进不浪

    漫的房地产领域。在前文中，我们说过租公寓的过程属于最优停止问

    题，但是真的拥有房产之后，你仍然难免要与最优停止问题打交道。

    假设你想卖房子。在咨询了几个房地产中介之后，你将粉刷一新、带有园林景观的房子推向市场，然后静等有意者上门。每个看房人提出

    有意购买时，你基本上都要做出决定，要么接受，要么拒绝。但是，拒

    绝是有代价的，因为在下一个有意购买者上门之前，你需要再支付一周

    (甚至一个月)的抵押贷款，而且下一个购买者的报价未必更高。

    卖房子与全信息博弈比较相似。我们知道有意者愿意付出的具体金

    额，不仅可以看出谁报出的价格更高，而且可以看出彼此之间的具体差

    额。此外，我们还掌握有关房地产市场行情的更多信息，至少可以对预

    计的报价变化幅度做一个大致的预测。(有了这样的预测，就相当于掌

    握了上述打字测试中的信息。)两者之间的差别在于目标不同。卖房子

    时，我们的目标其实不是得到最有利的报价，而是通过整个过程最终获

    取尽可能多的钱。由于等待是有代价的，是要付出真金白银的，因此当

    前的有利报价比几个月之后略高一点儿的报价更有吸引力。

    掌握了这些信息之后，我们就可以省略确定阈值所需的观望阶段，直接确定一个阈值。然后，我们可以忽略所有低于这个阈值的报价，直

    接接受第一个高于阈值的报价。诚然，如果在某个时间之前不把房子出

    手，我们有限的积蓄就会消耗殆尽，或者我们只想考虑数量有限的几个

    报价，对随后的报价不感兴趣，那么在快要达到极限时，我们当然应该降低标准。(购房者喜欢找“积极的”卖主，原因就在这里。)但是，如

    果没有被这两种情况逼到墙角，那么我们就可以通过成本效益分析，确

    定是否应该继续观望。

    接下来，我们分析一种非常简单的情况：假设我们清楚报价金额的

    变化幅度，并且在这个变化范围内各种报价出现的可能性是相同的。只

    要报价不会中断(我们的积蓄也不会花完)，我们就可以单纯地考虑我

    们对收获或损失的期望值，以决定是否继续等待更有利的交易。如果拒

    绝当前的报价，预计出现更有利报价的可能性是多少？该报价与当前报

    价之间的差，乘以该报价出现的可能性，乘积是否大于继续等待的成本

    呢？数学计算的结果清楚地表明，停止价格是等待成本的一个显函数。

    无论你出售的是价值高达数百万美元的豪宅，还是摇摇欲坠的棚

    屋，对这个数学结果都不会有任何影响。你唯一需要关心的是你可能接

    收到的最高报价与最低报价之间的差值。输入几个具体数字，就可以看

    出这个算法可以提供给我们大量清楚明了的指导意见。例如，假设我们

    预计报价金额在400000~500000美元之间。首先，如果等待成本非常

    低，那么在挑选买主时我们几乎无须有任何顾忌。如果等待下一个报价

    的成本仅为1美元，那么为了赚取尽可能多的钱，我们可以一直等到有

    人愿意支付499552.79美元时才出手。少一分钱，我们都不会卖给他。

    如果每次等待需要付出2000美元的代价，那我们就应该等待480000美元

    这个报价。如果面对的是一个不景气的市场，每次等待需要耗费10000

    美元时，那么只要报价高于455279美元，我们就应该立刻出手。最后，假设等待成本为预计报价范围的一半(在本例中，报价变化幅度的一半

    就是50000美元)或更高时，那么观望对我们来说不会有任何好处，最

    有利的做法是直接接受第一个报价，然后立刻成交。人在屋檐下，不得

    不低头。

    在这个问题中，阈值完全取决于搜寻成本，这也是这类问题需要注意的关键要点。下一个报价令人心动的可能性(以及搜寻成本)都不会

    发生任何变化，因此，无论运气如何，我们在搜寻过程中都无须降低最

    优停止价格。一旦确定最优停止价格之后(即使这是我们在将房子推向

    市场之前做出的决定)，我们就再也不要有任何动摇。

    卖房子问题的最优停止阈值

    威斯康星大学麦迪逊分校的优化专家劳拉·阿尔伯特·麦克莱回忆

    说，她在卖房子时，就用到了最优停止问题的相关知识。她说：“我们

    收到的第一个报价就非常高，但是他们希望我们比预计的搬离日期早一

    个月搬走。这个代价太大了。这时候，又有人报出了一个有竞争性的报

    价……但是我们一直不为所动，直到最后有人报出了令我们满意的报价

    为止。”对很多卖家而言，建议他们拒绝一两个优厚的报价都会让他们

    神经紧张，如果随后的报价比不上前者，那么他们就会更加紧张。但

    是，麦克莱很冷静，坚守立场没有动摇。她承认：“如果我不知道数学

    计算的结果，就很难坚持下来。”在任何情况下，只要你可以得到一系列报价，而寻找或等待下一个

    报价需要付出一定成本时，就可以应用上述准则。因此，除了卖房子，在很多情况下我们都可以考虑这条准则。例如，经济学家利用这个算法

    构建的找工作模型，可以轻而易举地解释失业工人与空缺岗位并存这个

    看似矛盾的事实。

    事实上，最优停止问题的这些变种还有一个更令人吃惊的特性。前

    面说过，在开普勒寻觅爱情的过程中，可以“复活”之前被自己拒绝的机

    会是一个非常重要的条件。但是，在卖房子或者找工作时，即使我们可

    以重新考虑之前的报价或工作邀请，即使我们可以肯定那个报价或工作

    邀请仍然有效，我们也绝不应该重新考虑它。如果之前它没有达到阈值

    的要求，那么现在它也不会高于阈值。在拒绝那个报价或工作邀请之

    后，我们的付出已经成为已支付成本。因此，不要妥协，不要试图亡羊

    补牢。坚持住，不要回头!最优停车位置

    克拉克·克尔，加州大学伯克利分校校长(1958—1967年)

    我发现，大学校园里有三个主要的行政管理问题：学生关心性爱，校友关心体育，教职员工关心停车问题。

    最优停止问题经常出现的另一个领域与汽车驾驶有关(在这个领

    域，回头同样是不明智的)。在某些早期文献中，秘书问题的主角是驾

    车者，而汽车只进不退的基本设定把驾车旅行中的所有决策过程(包括

    寻找饭店、寻找浴室，以及最令城市驾车者头疼的寻找停车位等过程)

    全部变成了停止问题。要讨论进出停车场的问题，加州大学洛杉矶分校

    著名的城市规划教授、被《洛杉矶时报》称作“停车场摇滚明星”的唐纳

    德·舒普显然是最合适的人选。我们从加州北部出发，驾车前往学校拜

    访舒普。我们告诉舒普，我们为这段行程预留了大量时间，让他不要担

    心我们会因为意外的交通情况而无法按时抵达。舒普回答说：“说到针

    对‘意外的交通情况’制订计划，我认为你们应该考虑的是预计的交通情

    况。”舒普的知名度或许大多归功于他的著作《免费停车的高昂代

    价》，此外他还做了大量工作，推动人们讨论、了解驾车旅行的真实情

    况。

    我们真应该同情那位可怜的驾驶员。根据舒普的模型，理想的停车

    位应该在停车位“标价”、行走所需时间及造成的麻烦、寻找停车位所需

    时间(随着目的地、一天中的时间不同而发生显著变化)以及整个过程

    所消耗的汽油等方面实现优化并达成精确平衡。因为车内乘客人数不

    同，上述等式会发生变化，因为乘客可以分担停车费用，但是无法分担搜寻时间，也无法分担步行的时间与麻烦。与此同时，驾驶者还需要考

    虑到的一个问题是：停车位最多的地方可能也是停车需求最大的地方。

    停车问题含有博弈论的成分，因为在你算计道路上其他驾车者的时候，他们也在算计你。[1]

    话虽如此，停车难题大多归根于一个数字，即停车

    位占用率——目前被占用的所有停车位占总停车位的比例。如果占用率

    很低，找到一个好的停车位并非难事；如果占用率很高，想为你的车找

    到一席之地就不是那么容易了。

    舒普认为，停车的很多难题都归因于城市政策，因为这些政策导致

    停车位占用率极高。如果某个地方的停车费用非常低(更糟糕的是，有

    的甚至免费)，就会刺激人们把车停在那里，而不是停到稍远的位置，然后步行。于是，大家都想在那儿停车，但是大多数人发现那里已经停

    满了车，因此他们只好开着车四处巡游，试图找到一个停车位，结果既

    浪费时间，又浪费汽油。

    舒普建议的解决办法是安装数字停车计时器，根据停车需求自动调

    整价格。(旧金山市区已经采用了这种计时器。)在设定价格时，需要

    先设定一个目标占用率。舒普认为，这个目标值应该在85%左右(对于

    路边停车率接近100%的大多数大城市而言，这个占用率已经非常低

    了)。舒普指出，当停车位占用率从90%升至95%时，尽管仅多停了5%

    的车，但是大家寻找停车位的时间就会翻一番。

    一旦意识到停车其实是一个最优停止问题，你就会发现占用率对停

    车策略有着关键的影响。行驶在大街上，每次看到一个空车位时，我们

    都必须做出决定：是停到这个车位上，还是试试运气，再往前开一点

    儿？

    假设你行驶在一条无限长的道路上，路边车位均匀分布，而你的目

    标是把车停到尽可能接近目的地的车位上，以便少走几步路。那么你应该采用摸清情况再行动准则。为了实现最优停止这个目标，在距离目的

    地一定路程之外，即使看到空车位也不要停车；一旦进入一定距离之

    内，就应该从观望阶段转变为行动阶段，看到空车位后立刻停车。这段

    距离的长短，取决于停车位可能被占用的百分比，即停车位占用率。下

    表列出了与某些有代表性的停车位占用率相对应的转变距离。

    表1-2 寻找停车位的最优策略

    如果这条无限长的街道与大城市一样，停车位占用率高达99%，只

    有1%的停车位是空闲的，那么在距离目的地大约70个停车位(略多于14英里[2])处开始，只要看到空车位，就应该停车。但是，如果舒普

    的办法奏效，将占用率降低到85%左右，那么在距离目的地半个街区之

    前，你都无须着急停车。

    我们行驶的道路大多不是笔直的，也不会是无限长的。因此，同其

    他最优停止问题一样，研究人员也在上述基本情况的基础上做出了各种

    调整。例如，他们考虑了若干不同情况，包括允许驾驶者调头、距离目

    的地越近停车位越少、驾驶者与目的地相同的其他驾驶者形成竞争关系

    等。但是，无论该问题的参数发生哪些变化，增加空闲停车位的数量都

    可以使我们的生活更加方便。从某种意义上讲，这是提示市政府的政策

    制定者：停车问题不是单纯靠增加资源(停车位)并最大化利用资源

    (占用)就可以解决的。停车还是一个进程(是一个最优停止问题)，消耗注意力、时间、汽油，还会导致污染和拥堵等后果。合适的政策可

    以彻底解决这个问题。而且，适宜居住的街区周围有空的停车位，可能

    是街区运行良好的一个标志，这正好与我们的直觉相反。

    我们问舒普，他在洛杉矶车流中穿行，前往加州大学洛杉矶分校上

    班的时候，他的研究是否可以为他提供优化方案。作为一名全世界顶尖

    的停车问题专家，他是否有什么秘密武器。

    舒普还真的拥有一个秘密武器：“我骑车上下班。”

    [1]第11章将详细讨论博弈论计算中的各种风险。

    [2]1英里≈1.61千米。——编者注见好就收的时机

    1997年，鲍里斯·别列佐夫斯基因拥有大约30亿美元的财产，被

    《福布斯》杂志确认为俄罗斯首富。仅仅10年前，他还是苏联科学院的

    一名数学家，靠工资度日。他利用在研究过程中建立的业界关系，创建

    了一家公司，帮助外国汽车制造商与苏联汽车制造商AvtoVAZ沟通交

    流。随后，他的公司变成了AvtoVAZ汽车的大型经销商，同时还通过分

    期付款的方法，利用卢布的恶性通货膨胀牟利。他还利用与AvtoVAZ的

    合作关系套取资金，用来购买这家汽车制造商及俄罗斯公共电视台、西

    伯利亚石油公司的部分股份。最终，他赚得了几十亿美元的身家，成为

    寡头阶层的新成员。随后，他开始参与政治。1996年，他支持鲍里斯·

    叶利钦连任；1999年，他又支持弗拉基米尔·普京成为叶利钦的继任

    者。

    但是，后来别列佐夫斯基的政治态度开始转变。普京当选总统之后

    不久，别列佐夫斯基公开反对普京提出的旨在扩大总统权限的宪政改

    革。他在公开场合不断批评普京，导致他与普京的关系开始恶化。2000

    年10月，在有人请普京就别列佐夫斯基对他的批评发表评论时，普京

    说：“政府手持大棒，只需一下，就能击碎其脑壳。目前我们还没有动

    用大棒……一旦我们真的动怒，就将毫不犹豫地砸下去。”当年11月，别列佐夫斯基就离开了俄罗斯，再也没有回来。流亡到英国之后，别列

    佐夫斯基继续批评普京。

    别列佐夫斯基如何做出离开俄罗斯的决定？是否可以通过数学方法

    考虑“见好就收”这条建议？多年前，别列佐夫斯基本人就是一名数学

    家，而且他研究的正好就是最优停止问题，他创作的第一本书(当然也是他的唯一一本书)全部关于秘书问题，因此他当时可能也考虑了这个

    问题。

    人们在分析见好就收这个问题时，为它披上了好几种伪装，但是最

    适合别列佐夫斯基这种情况的可能应该是“窃贼问题”(向俄罗斯寡头表

    示歉意)。在窃贼问题中，窃贼可以实施一系列盗窃活动。他们的每次

    盗窃都会有收获，并且每次都有机会带着战利品顺利脱身。但是，一旦

    被抓住，他们就会失去之前的所有收获。窃贼希望收获最大，那么什么

    样的算法可以给他提供合理建议呢？

    窃贼问题有解，对于盗窃题材的电影剧本而言不是好消息。当盗窃

    团队诱惑一位已经金盆洗手的老手，希望他复出并干最后一票的时候，这位狡猾的窃贼只需要认真分析那些数字就知道该怎么做了。凭直觉也

    可以得出结果。实施盗窃的次数应该大致等于顺利脱身的可能性除以被

    抓的可能性的值。如果你是一名有经验的窃贼，每次盗窃成功的可能性

    为90%(损失全部身家的可能性为10%)，那么在盗窃9次(90÷10=9)

    之后，你就应该洗手不干了。如果是一名笨手笨脚、成功率只有一半的

    生手，情况会怎么样？第一次去偷盗时，你本来就身无分文，因此无须

    担心有任何损失，但是之后就不要再去碰运气了。

    尽管别列佐夫斯基是最优停止问题方面的专家，但是他的结局仍然

    十分凄惨。2013年3月，一名保镖在他位于伯克郡的住所里发现了他的

    尸体。他死在锁着的浴室里，脖子上系着绳子。官方在尸检之后宣布他

    死于自杀。由于他在一系列高调的诉讼案中输给了俄罗斯对手，也失去

    大笔财富，因此他走上了上吊自尽这条不归路。或许他抽身而退的时间

    还应该更早一些，在积累几千万美元的财富之后就应该收手，而且不能

    介入政治。但是，遗憾的是，那不是他的做事风格。他在数学界的一位

    朋友里奥尼德·博古斯瓦夫斯基，曾经讲过别列佐夫斯基的一件往事。

    当时，他和别列佐夫斯基都还是年轻的研究员。他们前往莫斯科附近，准备进行湖上滑水活动。但是，他们计划使用的那条船出了故障。戴维

    ·霍夫曼在他的《寡头》一书中有这样一段文字：

    朋友们都跑上沙滩，点起了篝火，只有博古斯瓦夫斯基和别列佐夫

    斯基向船坞走去，准备修理那台发动机……三个小时之后，他们已经把

    发动机拆装了一遍，但是发动机仍然无法工作。尽管已经错过了聚会的

    大多数活动，但是别列佐夫斯基仍然坚持说，他们一定要继续尝试修理

    发动机。博古斯瓦夫斯基回忆说：“我们想尽办法，试图修好那台发动

    机。”别列佐夫斯基从来不会轻言放弃。

    令人吃惊的是，在最优停止的文献资料中也曾提到过不放弃(而且

    是永不放弃)。有的时序决策问题似乎没有最优停止准则，尽管从我们

    前面讨论的大量问题看，似乎不应该出现这种情况。“要么三倍，要么

    赔光”的博弈游戏就是一个简单的例子。假设你带着1美元去玩这个游

    戏。游戏规则对轮次没有限制，但是要求你每次都要押上所有的钱，你

    有50%的机会赢回三倍的钱，另外50%的机会全部赔光。那么你应该参

    与多少轮呢？尽管这个问题非常简单，但它没有合适的最优停止准则，因为每参加一轮游戏，你的平均收益都会略有增加。从1美元开始，你

    有一半机会赢回3美元，一半机会收回0美元，平均而言，第一轮结束之

    后，你装进口袋的现金期望值是1.5美元。那么，如果你在第一轮游戏

    中运气不错的话，第二轮游戏的两个可能结果就会将你刚刚赢回来的3

    美元变成9美元或者0美元，也就是说，第二轮的平均收益是4.5美元。

    数学计算结果表明，你应该一直玩下去。但是，果真如此的话，你最终

    必将输光所有的钱。可见，有的问题有解，反而会有损无益。随时准备停止

    斯蒂芬·格雷列特

    我的生命只有一次。因此，如果我能做点儿善事，或者可以向人们

    表示善意，让我现在就做吧!别让我拖延，别让我疏忽，因为我没有第

    二次生命!

    安妮·迪拉德

    用掉这个下午吧。你不可能把它带走。

    我们在前文讨论了人们在生活中遭遇停止问题的具体实例，很显

    然，我们大多数人每天都会遭遇这类问题，只不过表现形式各不相同。

    生活中最优停止问题无处不在，有时与秘书有关，有时又与未婚夫(或

    未婚妻)、公寓有关。因此我们难免会想到一个问题：进化、教育或者

    直觉到底能不能为我们提供最有效的策略？

    乍一看，答案似乎是否定的。十几项研究已经得出了相同的结果，人们往往在更优秀申请者还没亮相之前就已经草草停止。为了更深入地

    了解这些研究成果，我们拜访了加州大学河滨分校的阿姆农·拉波波

    特。他在实验室里从事最优停止实验工作已有40多年了。

    20世纪90年代，拉波波特与达里尔·希尔合作，完成了一项与经典

    秘书问题关系密切的研究。在这项研究中，人们需要无数次面对秘书问

    题，每次申请者的人数为40或者80。结果，人们找到最优秀申请者的总

    成功率相当不错，大约为31%，与最理想的37%相去不远。大多数人都

    遵循了摸清情况再行动准则，但是有超过45的人出现了出手过早的情况。

    拉波波特告诉我们，他本人在生活中遇到最优停止问题时，都会想

    到这个现象。例如，在寻租公寓时，他竭力控制自己希望迅速交易的冲

    动。他说：“尽管我天生是一个急性子，看到第一个公寓就想租下来，但是我还是竭力控制自己。”

    但是，这种不耐烦的表现说明经典秘书问题忽略了另外一个需要考

    虑的因素——时间。别忘了，在你寻觅秘书的全过程中，你没有秘书可

    用。此外，你把时间都花在面试上，自己的工作就无法完成了。

    在实验室里解决秘书问题时，停止时机的选择往往过早，原因可能

    就在于这种成本。希尔和拉波波特认为，如果我们假设面试每名申请者

    的成本等于发现最优秀秘书所产生价值的1%，那么最优策略就会与实

    验中人们从观望阶段转变为行动阶段的时间选择正好一致。

    令人难以理解的是，在希尔和拉波波特的研究中，寻觅是不需要付

    出任何成本的。那么，人们在实验室中的行为为什么与寻觅需要付出成

    本时一致呢？

    这是因为人们认为时间成本一定是存在的，而且时间成本是在人们

    的真实生活中产生的，与实验如何设计没有关系。

    因此，寻觅活动的“内在”时间成本(在最优停止模型中通常没有得

    到体现)也许可以解释人类做出的决策通常与模型的描述之间存在差异

    的原因。研究最优停止的科研人员尼尔·比尔登指出：“在寻觅工作持续

    了一段时间之后，我们人类通常就会感到厌烦，即使理性的人也难以避

    免。但是，模型很难精确地反映出这个变化。”

    不过，这并不意味着最优停止问题的重要性有所降低。事实上，它

    的重要性不降反升，因为时间的流逝会把所有决策活动变成最优停止问题。

    最优停止问题的权威教科书开宗明义地指出：“最优停止理论关注

    的是如何选择时机以执行特定行动的问题。”很难想出一种更好的方

    法，可以简明扼要地描述人类所面临的状况。显然，我们需要判断何时

    应该买进股票，何时应该将这些股票卖出，我们还要决定何时应该打开

    我们已经封藏了一段时间的葡萄酒，何时应该打断某人，何时应该亲吻

    某人。

    这样看来，秘书问题最基本同时也最令人难以置信的前提条件——

    严格的连续性，即有进无退的单向行进，正好是时间自身属性的一个体

    现。就此而言，最优停止问题的这个显性前提正好就是使其充满活力的

    隐性前提。这个前提迫使我们基于还没亲眼看到的可能结果做出决定，迫使我们在采取最优策略之后仍然愿意接受非常高的失败率。我们永远

    没有二次选择的机会。我们有可能得到类似的选择机会，但是绝不会得

    到完全相同的选择机会。犹豫不决(不作为)与行为一样不可改变。困

    在单行线上的驾车者与空间的相互关系就是我们与第四维度的关系：我

    们的生命真的只有一次。

    直觉告诉我们，合理的决策需要穷举所有选择，逐一权衡，然后从

    中找出效果最好的那个选择。但是实际上，在钟表嘀嘀嗒嗒的声音中，决策活动(或者更具一般性的思维活动)的其他方面都淡化了，进一步

    凸显出停止时机选择的重要性。02 探索与利用 要最新的还是要最好的？

    要最新的还是要最好的？

    饥肠辘辘时，你会去熟悉而且喜爱的那家意大利餐馆，还是新开张

    的泰国餐厅？你会带你最亲密的好友一同前往，还是邀请你新结识的熟

    人以便加深了解？这些都太难选择了。或许你宁愿待在家里吧。那么你

    准备做一道比较拿手的菜肴，还是上网搜索找到灵感后做一道新菜？还

    是很难选择？没关系，订一份比萨怎么样呢？那么，在选比萨时，你准

    备“照旧”，还是要一些特别的口味呢？在你吃第一口之前，这些难题已

    经让你筋疲力尽了。放唱片、看电影或者看书，同样也不是一件轻松的

    事，你也会面临如何选择的问题。

    每天，我们都要做出各种各样的决定，都要在某个非常具体的方面

    做出选择：是进行新的尝试，还是继续选择我们喜欢的那个？直觉告诉

    我们，生活就是在新鲜事物和传统事物之间、在最新的和最棒的之间、在勇于冒险和安于现状之间取得平衡。但是，就像在公寓寻租过程中所

    面临的观望还是行动的两难困境一样，这里也有一个问题没有得到解

    决：如何平衡？

    罗伯特·波西格在他于1974年出版的经典著作《禅与摩托车维修艺

    术》中对“有什么新鲜事吗？”这句寒暄语进行了公开谴责。他说：“只

    要认真地研究这个问题的话，得到的答案肯定是一堆琐碎的跟风事物，等到了明天它们就会失去新鲜劲儿。”他认为另一个问题就要好得

    多：“最好的是什么？”

    但是，现实生活没有那么简单。别忘了，你喜欢的每一首“最好的”歌、每一家“最好的”餐馆，在刚开始的时候，对你而言也不过是一

    个“新鲜”事物。这就说明或许还有一些最好的东西不为我们所知，因

    此，新鲜事物至少值得我们略加关注。

    一些古老的格言承认这种矛盾关系，但是没有给出应对之策。“结

    交新友，不忘旧友；新友是银，旧友是金”“无论生活如何丰富多彩，仍

    然留有结交新朋友的空间”等老话说的确实是真理，但是它们没有告诉

    我们，这些“金”“银”应该以什么样的比例混合，才可以高质量地打造出

    幸福生活这块合金。

    50多年来，计算机科学家一直埋头钻研，希望可以找到这个平衡

    点。他们的研究甚至还有一个专门的名称：探索与利用的取舍。什么是探索与利用

    英语为“explore”(探索)和“exploit”(利用)这两个词赋予了截然

    相反的含义，但是在计算机科学家眼中，它们有很多具体的中性含义。

    简单地说，探索的意思是收集信息，而利用则指利用所拥有的信息，以

    产生一个好的结果。

    凭直觉就知道，探索在人生中是不可或缺的。但是，我们同样应该

    知道，如果缺少了利用，人生也必然无比惨淡。根据计算机科学的定

    义，很多时候，利用其实是我们心目中的那些美妙时光的一个特征。节

    假日的家庭聚会就是一种利用。书迷安静地坐在椅子上，一边喝着热腾

    腾的咖啡，一边阅读自己心仪的书；乐队在狂热的歌迷面前演唱自己的

    畅销金曲；经受住岁月考验的夫妇在“属于他们的乐曲”中翩翩起舞。所

    有这些，都是一种利用。

    有时候，探索还有可能为我们埋下祸根。

    例如，音乐的魅力之一就是新的音乐作品层出不穷。但是，如果你

    是一名音乐记者，那么不断推出的新作品就会让你觉得头疼。选择音乐

    记者这个行业，就意味着把探索进行到极致，无时无刻不在接触新鲜事

    物。乐迷可能认为从事这个行业就像生活在天堂一样，但是，如果你一

    直忙于探索新的事物，就永远没有办法享受你的鉴赏成果，所以这与天

    堂般的生活相去甚远。音乐网站Pitchfork的前主编斯科特·普拉奇霍夫在

    这方面感慨颇深。他对批评家的生活是这样评价的：“在工作期间，你

    很难找到时间听自己想听的音乐。”由于长时间鉴赏那些质量不确定的

    新歌，因此他特别希望听一听自己喜欢的歌曲。为了抵制这种强烈愿望的诱惑，普拉奇霍夫会在他的iPod(苹果播放器)中存放新的音乐作

    品，通过这个物理障碍来保证自己不会忘记职责，即使他有的时候特别

    想听史密斯乐队的歌曲。音乐记者本着殉道者的精神，默默探索，为其

    他人的利用创造条件。

    在计算机科学中，探索与利用的矛盾通过“多臂***问题”的形式

    表现得淋漓尽致。这个奇怪的名称来源于赌场***的俗称——“独臂

    匪徒”。假设你走进一家赌场，里面全部是各种各样的***，但是每

    台机器吐钱的概率各不相同。问题是，你提前不知道这些概率到底是多

    少。在你开始游戏之前，你根本不知道哪台机器最喜欢吐钱，哪台机器

    只吞钱不吐钱。

    你自然希望赢的钱越多越好。显然，你肯定会在不同机器上亲自测

    试一番(探索)，然后专挑那些你认为最有可能吐钱的机器来玩游戏

    (利用)。

    为了弄明白这个问题的微妙之处，我们假设房间里只有两台老虎

    机。你在一台机器上玩了15次，其中有9次***吐出了一些钱，还有6

    次没有任何反应。你在另一台机器上只玩了两次，其中一次***吐出

    了钱，另一次则没有吐钱。哪一台机器更有可能让你赢钱？

    把赢钱的次数与总次数相除，就可以计算出各台机器的“期望值”。

    利用这个方法比较时，第一台机器显然更胜一筹。9-6这个游戏记录表

    明它的期望值是60%，而第二台机器的1-1记录只能得出50%这个期望

    值。不过，仅仅这样考虑还是不够的。毕竟，只玩两次，次数还是太少

    了。因此，从某种意义上讲，我们仍然不知道第二台机器的实际表现如

    何。

    选择餐厅或者唱片就等同于选择一台***，去玩生活这个游戏。

    但是，了解探索与利用的取舍问题，不仅可以帮助我们挑选餐厅和歌曲，还可以帮助我们深入了解如何随着年龄的增长调整我们的人生目

    标，了解最合理的做法为什么并不总是选择最好的。事实证明，探索与

    利用的取舍问题在网页设计与临床试验(以及其他领域)中占有核心地

    位——正常情况下，这两个名词不会出现在同一个句子中。

    人们往往将决策行为孤立开来，针对每一次决策活动寻找在结果中

    实现最高期望值的方法。但是，决策行为几乎都不是孤立的，期望值也

    不是最终目标。如果你考虑的不是下一个决定，而是在将来面对相同选

    择方案时你将做出的所有决定，探索与利用的取舍就会发挥重要作用。

    数学家彼得·惠特尔认为，从本质上看，***问题正是通过这种方

    式“体现了所有人类行为中显而易见的矛盾”。

    那么，你到底应该在那两台***中选择哪一台呢？这是一个带有

    陷阱的问题，因为答案完全取决于一个我们至今还没有讨论的内容：你

    准备在赌场玩多长时间？如何利用剩余时间？

    在1989年上映的电影《死亡诗社》中，一个令人难忘的场景是彼得

    ·威廉姆斯呼吁道：“抓住现在，孩子们，要抓住每一天，让你们的生活

    变得非凡起来。”

    这条建议非常重要，同时也有点儿自相矛盾。抓住一天与抓住一辈

    子的时光是完全不同的两个概念。的确，有人说：“吃喝享乐吧，因为

    明天我们就会死去。”但是，我们或许应该反过来说：“让我们学一门新

    的语言或者乐器，或者与陌生人随便聊聊吧。生命如此漫长，谁知道多

    年之后哪一朵快乐之花会绽放。”当我们在喜爱的体验与新鲜的体验之

    间取得平衡时，最重要的莫过于为享受这些体验制订计划的那个中间环

    节。

    数据科学家、博主克里斯·斯图吉奥解释说：“刚刚搬到一座城市

    时，我更有可能去尝试新的餐厅，但是当我准备从一座城市搬走时，这

    种可能性就会降低。”这位善于处理工作、生活中探索与利用这一取舍

    问题的老手说：“现在，我在大多数情况下都会去我熟悉、喜爱的餐

    厅，因为我知道我很快就会离开纽约了。但是，几年前刚到印度的浦那

    市时，我几乎吃遍了这座城市，只要看起来毒不死人的东西，我都会去

    尝试一下。当我准备离开那座城市时，我又开始吃我过去就喜欢吃的东

    西，而不是到处尝试新的食物……即使我发现某个地方还不错，我也只

    会去一两次。何必再冒那个险呢？”

    随着时间的推移，即使探索有所发现，我们可以认真品味这些新发

    现的机会也已经所剩无几，因此探索的价值随之降低。在你离开一座城市的前夜，你发现一家酒吧非常棒，但是你已经没有机会去第二次了。

    这一点可以让我们清醒下来，不至于一味地尝试新鲜事物。

    与之相反，利用的价值随着时间的推移反而会不断上升。本质上，现在你心目中最迷人的酒吧至少不逊于上个月你心目中最迷人的酒吧。

    (如果后来你发现你喜欢上了另一家酒吧，那就说明这家酒吧可能更

    棒。)因此，当你有时间使用探索带来的知识时，就大胆探索。当你准

    备兑现探索的成果时，就尽情利用。利用好剩余时间就是正确的应对之

    策。

    有趣的是，既然应对之策是利用好剩余时间，那么通过研究人们采

    用的策略，我们也可以推断出剩余时间的起始点与结束点。以好莱坞为

    例。1981年，票房排行榜前10名的电影中只有两部是续集；1991年，前

    10名中有三部续集；2001年，这个数字上升到了5部；2011年，票房前

    10名电影中有8部都是续集。事实上，续集在2011年各大公司电影作品

    中所占的比例创造了一个新纪录。但是，这个纪录在2012年就被打破

    了，到2013年又再次被打破。2012年12月，记者尼克·艾伦对来年的电

    影前景进行了展望。他的热情明显不是很高：

    观众将第6次看到X战警，还将看到《速度与激情6》《虎胆龙威5》

    《惊声尖笑5》和《鬼影实录5》。此外，他们还会看到《钢铁侠3》和

    《宿醉3》，以及《布偶大电影》《蓝精灵》《特种部队》和《圣诞坏

    公公》的续集。

    在电影公司看来，续集可以保证观众基础，是稳赚不赔的买卖，是

    可以享受的成果。但是，因为稳赚不赔就一拥而上，说明他们的目标非

    常不长远，这与斯图吉奥即将离开一座城市之前的行为非常相似。与全

    新的电影相比，续集更有可能成为当年的热门电影，但是未来深受观众

    喜爱的票房保证将从何而来呢？蜂拥而至的续集潮不仅令人感到遗憾

    (影评家肯定是这样想的)，在一定程度上甚至令人伤感。电影业已经进入了一个安于现状的阶段，这似乎是一个信号，告诉我们电影业已经

    日薄西山了。

    好莱坞的经济状况与这种预感似乎不谋而合。2007—2011年，各大

    电影公司的利润下降了40%；在过去10年里，有7年的票房收入走了下

    坡路。《经济学人》杂志指出：“在成本上升、收益下降的双重压力

    下，大型电影公司的应对之策是制作续集、前传或者邀请名演员担纲主

    演，因为他们相信这些电影肯定会火起来。”换句话说，在被淘汰出局

    之前，他们正争分夺秒，在他们发现的最容易吐钱的“***”上进行赌

    博游戏。赢留输变

    事实证明，要用优化算法来处理多臂***问题，难度非常大。彼

    得·惠特尔回忆说，“二战”期间，这个问题“令同盟国的分析人员身心俱

    疲……于是有人提议，把这个问题作为破坏智力的终极工具，交给德国

    人研究”。

    战后，人们通过几年的研究，取得了若干进展。哥伦比亚大学的数

    学家赫伯特·罗宾斯提出了一个简单的策略，并指出，尽管这个策略尚

    不完善，但是可以给出一些效果不错的建议。

    在具体考虑了只有两台***的情况之后，罗宾斯提出了赢留输变

    算法：随便选择一台***，只要它不断吐钱，就在这台机器上玩游

    戏。如果某次拉动拉把后，***没有吐钱，就换另一台机器。1952

    年，罗宾斯提出的这个简单策略虽然远不完善，但是效果肯定比碰运气

    好。

    在罗宾斯之后，不少人进一步研究了“赢留输变”原则，并发表了一

    系列论文。根据直觉，如果你本来就倾向于某台***，而且这台机器

    刚刚又让你赢了一些钱，那么你对这台机器的评估就会升值，肯定不介

    意在这台机器上再玩一次。事实证明，在很多情况下，赢就留下原则都

    是探索与利用平衡问题优化策略的一个组成部分。

    但是，输就走人这个原则就值得商榷了。不吐钱就换机器是一种非

    常草率的行为。假设你去一家餐厅用餐。你去过一百次，每次都感到非

    常满意。如果有一次你感到失望，会不会从此以后就再也不去这家餐厅了呢？正确的做法是不要对瑕疵惩戒过重。

    更重要的是，赢留输变不含任何剩余时间的概念，因此没有为优化

    行为留出时间。你去你喜爱的餐厅用餐，结果扫兴而归，那么这个算法

    就会建议你以后换一家餐厅，即使你明天就要离开这座城市了。

    不过，罗宾斯开启了多臂***问题研究的先河，在随后几年里，这个领域涌现出大量的文献资料，研究人员也取得了重大进展。美国兰

    德公司的数学家理查德·贝尔曼发现，当我们预先知道所有的可选方案

    以及赢钱机会时，就能求出这个问题的精确解。就如全信息秘书问题的

    解法一样，贝尔曼基本上也采用了逆向法。首先，他假设自己知道之前

    所有决策会产生的结果，然后考虑应该在哪一台***上最后一次拉下

    拉把。推算出结果之后，他再考虑倒数第二次的情况，然后是倒数第三

    次、倒数第四次，一直倒推到最开始。

    贝尔曼的这个方法肯定可以得到确定无疑的答案，但是，如果可能

    的选择与赌博的轮次都非常多时，工作量就会非常大(甚至大到无法完

    成的程度)。此外，即使我们可以计算出未来的所有可能情况，我们也

    不一定确切地知道我们到底有多少赢钱机会(甚至不知道有多少种选择

    方案)。因此，多臂***问题从本质上讲还没有得到解决。用惠特尔

    的话说：“它很快就变成了一个经典问题，同时也变成了永不妥协的代

    名词。”基廷斯指数

    特例往往是通往宇宙奥秘的大门，这种情况在数学中也经常发生。

    20世纪70年代，联合利华公司请年轻的数学家约翰·基廷斯帮助他们优

    化药物试验。令人意想不到的是，基廷斯竟然解开了一道难住了一代数

    学家的难题。

    基廷斯(牛津大学统计学教授)认真地思考了联合利华提出的问

    题：已知有几种不同的化合物，如何以最快的速度确定哪种化合物可能

    对哪种疾病有效？基廷斯把这个问题变成了尽可能简单的形式：有多个

    可选方案，每个可选方案得到回报的概率不同，可分配的精力(金钱或

    时间)是确定的。于是，这个问题变成了多臂***问题的另外一个化

    身。

    无论是追逐利润的制药公司，还是他们所在的医药行业，都经常需

    要面对探索与利用如何取舍的竞争需要。制药公司希望投入到研发部门

    的资金可以帮助他们发明新药，但是他们同时还希望现在正在帮助他们

    赚钱的生产线继续开足马力。医生在开处方时，肯定希望病人在现有条

    件下得到最好的治疗，但是他们也希望实验研究可以找到更有效的治疗

    手段。

    显而易见，在这两种情况中，我们都无法确定相关的剩余时间到底

    是什么。从某种意义上讲，制药公司和医生一样，都对不确定的未来感

    兴趣。制药公司希望可以永远存在下去，而医药行业则希望取得突破，甚至希望在人们出生之前就可以向他们提供帮助。不过，他们对当前时

    间的重视程度更高：今天就把病人治愈，其价值高于让病人一周以后，甚至一年以后才康复，利润方面当然同样如此。经济学家把这种重现

    在、轻将来的概念称作“贴现”。

    基廷斯在研究多臂***问题时采用的就是这些术语，这是他与之

    前的研究人员不同的地方。在他的构想中，他的目标不是在固定时间段

    里追求最大回报，而是在时间无限长但是价值被打折扣的未来追逐最有

    利的结果。

    这种贴现在我们自己的生活中并不鲜见。如果你准备在一座城市逗

    留10天，那么你在选择餐厅时就要记住逗留时间已经确定这个事实，但

    是，如果你居住在这座城市，时间就没有多大意义了。此时，你也许会

    想，时间越久，回报贬值的程度就越大：你更关心的是今天的晚餐，而

    不是明天的晚餐，并且对明天晚餐的关心程度又高于一年之后的晚餐。

    至于关心程度到底有多大差别，取决于你采用的“贴现函数”。基廷斯设

    置的条件是回报价值呈几何级数贬值，也就是说，每次去餐厅进餐的价

    值是上一次的分数倍。如果你认为每天被车撞的可能性为1%，那么在

    评估明天晚餐的价值时，就应该把它设定为今天晚餐价值的99%，因为

    你有可能根本没有机会享受明天的晚餐。

    设定了这种几何贴现条件之后，基廷斯提出了这样一个策略：分别

    考察多臂***的各个拉把，然后计算出各个拉把自己的价值。通过一

    个别出心裁的设想——贿赂，基廷斯完成了自己的研究，并且认为这个

    策略“至少可以给出一个效果不错的近似估计”。

    在《交易还是不交易》(Deal or No Deal)这个热门电视节目中，参赛者要从26个箱子中选择一个。箱子里装有奖金，金额1美元~100万

    美元不等。随着游戏的进行，一位被称作银行家的神秘人物就会时不时

    出现。他愿意支付给参赛者金额不等的一笔钱，条件是参赛者不要打开

    他选中的那只箱子。参赛者需要做出选择，或者接受这笔实实在在的

    钱，或者选择装在箱子里的数额不确定的奖金。基廷斯发现(尽管多年之后第一期《交易还是不交易》节目才播

    出)，多臂***问题与之并无区别。我们对每一台***都知之甚

    少，甚至一无所知，但是它们都有某个保底回报率。如果摆在我们面前

    的不是***，而是它的回报率，那么我们肯定不会去玩***游戏。

    这个数字(基廷斯称之为“动态分配指数”，现在全世界都把它叫作“基

    廷斯指数”)告诉我们一条显而易见的赌博策略：一定要选择指数最高

    的那个拉把。[1]

    事实上，基廷斯指数并不仅仅是一个效果不错的近似估计，还可以

    彻底解决回报按几何级数贴现的多臂***问题。探索和利用之间的矛

    盾可以被转化成一个比较简单的任务：用一个数量使两者达成平衡并求

    这个数量的最大值。在说到自己的成就时，基廷斯非常谦虚，笑着说

    道：“这又不是费马大定理。”但是，他的这个定理让一大堆涉及探索与

    利用这个两难选择的问题得到了解决。

    不过，即使知道以往的记录和贴现率，特定机器基廷斯指数的计算

    仍然非常复杂。但是，一旦我们知道某些特定条件下的基廷斯指数，我

    们就可以利用这些指数解决相同形式的任何问题。重要的是，由于每个

    拉把的基廷斯指数都是独立计算出来的，因此涉及的拉把个数不会产生

    任何影响。

    下表给出了0~9次输赢所对应的基廷斯指数值，条件是回报以90%

    的比例递减。利用这些数值，可以解决日常生活中的多种多臂***问

    题。例如，在这些条件下，你应该选择以往记录为1-1(即期望值为

    50%)的那台***，而不选择记录为9-6(即期望值为60%)的那台机

    器。在下表中查询这两台机器对应的坐标就可以发现，了解得不多的那

    台机器的基廷斯指数为0.6346，而玩得比较多的那台机器得分仅为

    0.6300。问题解决了：这一次可以碰碰运气，大胆探索。仔细观察表中的基廷斯指数，就会发现一些有意思的东西。首先，你会发现赢就留下这个原则在发挥作用：任选一排，从左向右看去，就

    会发现指数值一定在增长。如果在某个时候某个拉把是你的正确选择，而且你拉下那个拉把之后真的赢钱了，那么再次选择这个拉把就是一个

    明智的决定(沿着图表自左至右)。其次，你可以看出在什么情况下输

    就离开这个原则会误导你。先赢9次，然后输钱1次，对应的基廷斯指数

    为0.8695，仍然比表中的大多数指数高，因此你不要急于离开，至少再

    拉一次这个拉把。

    表2-1 基廷斯指数值与输赢的关系

    注：在回报以90%的比例递减时的情况。

    但是，该表最有意思的地方是左上角的那一格。0-0这个记录(表明我们对这个拉把一无所知)所对应的期望值是0.5000，但是基廷斯指

    数是0.7029。换句话说，一台你从来没有玩过的机器，比你玩了10次，其中有7次赢钱的机器更有吸引力!沿着对角线向右下方前进，就会发

    现1-1这个记录对应的指数是0.6346，记录2-2对应的是0.6010，等等。如

    果这个50%的赢钱率一直保持下去，基廷斯指数最终会驱近于0.5000，而经验证明，这台机器的确没有任何特别的地方，它最终会收走那些刺

    激我们进一步探索的“奖金”。但是，收敛过程进展非常缓慢，探索奖励

    的刺激作用非常大。的确，我们可以看到，即使第一次拉下拉把后输了

    钱，0-1这个记录所对应的基廷斯指数仍然高于50%。

    我们还可以看出改变贴现率后探索与利用会发生什么样的变化。下

    表列出的内容与前表相同，不过条件是回报递减的比例不是90%，而是

    99%。在未来与现在的权重几乎相同时，相对于十拿九稳的事情而言，偶然发现的价值上升得更快。从这张表可以看出，从未测试过、记录为

    0-0的机器可以确保有86.99%的赢钱概率!

    由此可见，基廷斯指数以一种正式、严谨的形式，证明了在有机会

    对探索结果加以利用时，我们应该倾向于选择未知的新事物。有一句古

    老的谚语说：“邻家芳草绿。”数学可以告诉我们其中的道理。尽管我们

    实际上认为未知事物可能差不多，甚至有可能更差，但是它也有可能更

    好。球队新球员没有经过检验，但是他的价值却高于能力似乎差不多的

    老手(至少在赛季初如此)，原因正是我们对他知之甚少。探索行为本

    身就有价值，因为尝试新鲜事物可以增加我们发现最佳选择的机会。因

    此，不仅关注当前，同时还把未来纳入我们视野的做法，可以驱动我们

    不断尝试新鲜事物。

    表2-2 基廷斯指数值与输赢的关系注：在回报以99%的比例递减时的情况。

    因此，基廷斯指数为我们指出了一个轻而易举地解决多臂***问

    题的方法。但是，这并不是说这个难题已经彻底得到解决，也不意味着

    基廷斯指数可以帮助我们处理日常生活中所有探索与利用的取舍问题。

    原因之一是基廷斯指数只有在某些强假设条件下才是最优策略。各种各

    样的行为经济学与行为心理学实验都不建议人们对未来奖励实行几何贴

    现(即每次拉动拉把的价值都是上一次的分数倍)的做法。此外，如果

    不同方案之间的转换需要付出成本，那么基廷斯指数就不再是最有效的

    策略。(邻居家的草地看起来可能真的更绿一些，但这并不是我们翻过

    篱笆的理由，更不用说通过二次抵押贷款把邻居家的房子买下来了。)

    更重要的是，在匆忙之间很难计算出基廷斯指数。如果随身携带一张指

    数表，你可以找到晚餐的最佳选择，但是你得到的好处可能还不足以弥

    补你需要付出的时间和精力。(“等一等，我可以解决这个问题。这家餐厅的好评率是2935，另一家的好评是1316，因此它们的基廷斯指数

    分别是……嘿，人呢？”)

    正是因为考虑到这些因素，从基廷斯指数被提出之日起，计算机科

    学家和统计学家就已经在寻找可以更方便、更灵活地解决多臂***问

    题的方法。这些新的策略不仅可以比较好地满足需要，而且人(及机

    器)在一系列情境下应用这些方法时，难度比用基廷斯指数计算最优方

    案小。同时，它们还可以用来解决最令人害怕的一类问题，帮助我们在

    面对机会时做出正确的选择。

    [1]尽管基廷斯指数有效，但还是远离赌场为妙。遗憾与乐观

    弗兰克·辛纳屈

    遗憾？我曾经有过，但是算不上太多，不值得一提。

    温斯顿·丘吉尔

    我本人是个乐观主义者，因为不乐观的话，似乎也于事无补。

    如果你认为基廷斯指数太复杂，或者你所处的情况并没有表现出几

    何贴现的特征，那么你还有另一个选择——关注遗憾。当我们选择吃饭

    地点、伙伴或者居住城市时，遗憾常常会笼罩在我们心头——面对一堆

    好的可选方案，结果却做出了一个错误的选择，我们往往难以原谅自

    己。令我们遗憾不已的常常是我们没有做的事情，或者是从来没有尝试

    过的选择方案。用管理理论学家切斯特·巴纳德的话来说就是：“尝试后

    即使遭遇失败，也至少是一个学习的过程；如果不去尝试，就会与机会

    失之交臂，造成无可估量的损失。”

    遗憾也可能给人以巨大的动力。在杰夫·贝佐斯决定创办亚马逊网

    站之前，他在纽约投资公司德劭集团的工作非常安稳，待遇也十分丰

    厚。在西雅图创办网上书店，这个步子迈得有点儿大，因此他的老板

    (也就是戴维·肖)劝他要小心。贝佐斯说：

    我找到一个可以帮助我轻松做出重大决定的框架，并把它称作“遗

    憾最少化框架”(一个书呆子气十足的名称)。我把自己想象成80岁的

    模样，然后开始思考：“现在回望我的一生，我要把遗憾之事的数量降

    到最低。”我知道在我80岁时，我不会因这次尝试而后悔，我不会后悔参与到互联网这项我认为非常重要的事业中来。我知道，哪怕我失败

    了，我也不会遗憾，而我可能会因为没有尝试而感到遗憾，而且这种遗

    憾之情将永远萦绕在我的心头。想到这里，这个决定就变得非常容易

    了。

    计算机科学也不可能让你一辈子没有遗憾，但是它有可能帮助你实

    现贝佐斯追求的目标：把人生当中的遗憾降到最少。

    遗憾是将我们的实际行为与事后认定的最佳行为进行比较后得到的

    产物。在多臂***问题中，巴纳德说的“无可估量的损失”其实是可以

    精确测量的，遗憾也可以被赋予一个数值：采用某个策略后获取的回报

    总额与每次都选对最有利拉把时(如果我们从一开始就知道拉下哪个拉

    把能赢钱，该有多好啊)，所获取的回报总额理论值之间的差。我们可

    以针对不同策略计算出这个差值，然后找出差值最小的那些策略。

    1985年，赫伯特·罗宾斯第二次尝试破解多臂***问题，此时，距离他提出赢留输变策略已经有30年了。他和同事、哥伦比亚大学数学

    家黎子良合作，提出了与遗憾有关的几个重要特点。第一，假设你不是

    全知全能，那么让你感到遗憾的事情可能就会不断增加，永远无法停

    止，即使你选择的是最有效策略，这是因为，即使最有效策略也不一定

    每次都是完美无缺的。第二，如果你选择的是最有效策略，那么遗憾增

    加的速度就会比你选择其他策略时的速度慢一些，在采用好的策略时，遗憾增加的速度将越来越慢，因为你对问题的了解程度在加深，做出更

    明智选择的能力在加强。第三，同时也是最具体的一个特点，数量最少

    的遗憾(同样需要假定你不是全知全能)就是每次拉下***把手时遗

    憾的数量以对数速率增加。

    遗憾以对数速率增加，意味着前10次拉动***拉把与后面90次所

    造成的遗憾同样多，意味着在10年时间里，第一年留下的遗憾数量等于

    其余9年留下的遗憾总和。(同理，在100年时间里，前10年犯下的错误等于后90年的错误总和。)这种情况让我们多少可以找到一点儿安慰。

    总的来说，我们不可能指望有朝一日我们将再也没有新的遗憾。但是，如果我们采用一种遗憾最少化算法，就有望减少每年新增的遗憾数量。

    自黎子良、罗宾斯之后，研究人员在过去几十年里一直致力于寻找

    可以确保遗憾最少化的算法。在他们提出的算法当中，最受欢迎的就是

    上限置信区间算法。

    直观表现的统计数据通常在数据点上方或下方添加所谓的误差条

    线，以表明该测量值是不确定的；误差条线表示的是被测量数量真实值

    所在的合理范围，即“置信区间”。随着我们收集的数据越来越多，置信

    区间将不断缩小，这说明测量值越来越精准。(例如，有两台***，你在一台***上玩了两次，其中有一次赢钱了，在另一台***上玩

    了10次，有5次赢钱了。这两台机器的期望值相同，但是前者的置信区

    间更宽。)上限置信区间算法告诉我们，多臂***问题非常简单，可

    以直接选择置信区间上限最高的那个方案。

    因此，上限置信区间算法与基廷斯指数一样，也为多臂***的每

    个拉把赋予了一个数值。在上限置信区间算法中，这个数值就是根据目

    前掌握的信息，计算该拉把在合理情况下可以产生的最高值。因此，该

    算法不关心截至目前已经取得最好成绩的是哪个拉把，相反，它会选择

    在合理情况下未来有可能取得最佳成绩的那个拉把。例如，如果你从未

    去某家餐厅就餐，那么就你了解的信息看，这家餐厅可能非常棒。即使

    你已经去过一两次并且品尝了两道菜，你获取的信息也不足以表明这家

    餐厅一定比不上你经常去的那些餐厅。同基廷斯指数一样，上限置信区

    间一定大于期望值，但是随着某个方案给我们的体验越来越多，两者之

    间的差就会越来越小。(只有一次中评的餐厅仍然有可能非常棒，但是

    收到过几百次中评的餐厅一定不会很好。)上限置信区间算法给出的推

    荐意见与基廷斯指数的推荐意见应该没有多大区别，但是前者的计算难度小得多，而且无须几何贴现这个前提条件。

    上限置信区间算法所采用的原理有一个绰号——“面对不确定性时

    的乐观主义”。他们指出这种乐观主义是有充分理由的。这些算法强调

    通过已知证据推断某个选择方案可能产生的最佳结果，而计算的结果倾

    向于我们了解程度较低的可能情况。因此，他们自然会在决策过程中增

    加探索的比重，满怀热情地选择新的事物，因为任何新鲜事物接下来都

    可能变得非常重要。麻省理工学院的莱斯利·基布灵就曾采用相同的原

    理，她设计的“乐观机器人”在探索周围空间时，赋予未知地形的值比较

    高。显然，这个原理对于人类生活同样有所启示。

    上限置信区间算法的成功，是对怀疑者的一个正式回应。根据这些

    算法给出的建议，我们应该满怀激情地结识新人，尝试新鲜事物，因为

    在没有相反证据的时候，我们都应该假定可以取得最好的结果。从长远

    看，乐观主义是防范遗憾的最有效措施。网上“土匪”

    2007年，谷歌的产品经理丹·西罗克向公司请假，去参加当时身为

    参议员的巴拉克·奥巴马在芝加哥举行的总统竞选活动。作为“新媒体分

    析”团队的负责人，西罗克把谷歌在网站上的一个做法移植到鲜红的总

    统竞选“捐款”按钮上。结果令人大吃一惊——他的这个举动直接促使捐

    款金额增加了5700万美元。

    西罗克到底对那个按钮做了什么呢？

    答案是AB测试。

    AB测试的步骤大概是这样的：某公司为某个网页设计了几个不同

    的草稿。他们可能想了解不同的颜色、图片、新闻报道标题或者屏幕上

    各项内容的不同排列有什么样的效果。于是，他们把登录网站的用户随

    机分配到这些排列不同的页面上，通常各页面的访问人数相等。一个用

    户可能看到按钮是红色的，另一个用户则可能看到按钮是蓝色的；一个

    用户可能看到的是“DONATE”(捐款)，另一个可能看到的

    是“CONTRIBUTE”(捐助)。然后，他们对相关的计量体系(例如点

    击率或者用户平均捐助金额)进行监视。一段时间之后，如果从统计数

    据可以观察到显著效果，“获胜”的版本通常就会站稳脚跟，或者成为另

    一轮实验的参考标准。

    西罗克在奥巴马捐赠页面上完成的AB测试反映了一些问题。对于

    第一次访问竞选网站的用户，“捐赠并领取礼物”按钮取得了最好的成

    绩，即使把发放礼物的成本剔除之后，仍然效果最佳。对于长期订阅新闻但是从来没有掏过腰包的访问者，“捐款”按钮效果最好，可能是因为

    这个表达可以唤起他们的负疚感。对于过去曾经捐过款的访问者，“捐

    助”按钮吸引追加捐款的效果最好，其中的道理可能是已经“捐款”的人

    随时可以进一步“捐助”。令竞选团队吃惊的是，在所有情况下，奥巴马

    的一张简简单单的黑白全家福照片所取得的效果竟然超过团队可以找到

    的任何其他照片及视频。所有这些独立的优化手段加到一起，产生了巨

    大的实际效果。

    如果在过去10年里你使用过互联网，那么你就已经成为其他人考虑

    的探索与利用问题中的一分子了。企业希望找到利润的主要来源，同时

    又希望尽可能赚取更多的利润，因此他们探索、利用。亚马逊、谷歌等

    大型科技公司在2000年前后开始在他们的用户身上进行实时AB测试，随后互联网在几年时间里就变成了全世界规模最大的对照实验。那么这

    些企业探索和利用的对象是什么？一言以蔽之，就是：让你移动鼠标、掏腰包。

    企业AB测试的内容包括站点导航、主题行和营销邮件的投送时

    间，有时甚至包括公司的某些实际要素和定价。除了公开的谷歌搜索算

    法和公开的亚马逊结账流程以外，现在的企业还会在不告知用户的情况

    下对网页进行一些神秘而微妙的变更。(2009年，谷歌就曾有测试41种

    蓝色以确定某个工具条颜色的行为。)在某些情况下，任何两个用户可

    能都不会得到完全相同的体验。

    数据科学家、脸书(Facebook)数据小组前负责人杰夫·哈默巴赫

    曾告诉《彭博商业周刊》：“我们这代人中最聪明的人正在想方设法让

    人点击广告。”艾伦·金斯堡在诗作《嚎叫》中用一句不朽的诗句形

    容“垮掉的一代”：我看见我们这一代人中最聪明的人毁于疯狂的行为。

    同样，我们也可以把哈默巴赫的这句话视为千禧年的“嚎叫”。对于这种

    情况，哈默巴赫的看法是“糟透了”。但是，无论人们如何利用网络，在网络上做实验以研究人们的点击行为都是可以的，而且链接可以指向过

    去的营销人员根本想不到的地方。

    当然，我们都知道2008年奥巴马的参选结果。但是，有人知道他的

    分析团队负责人丹·西罗克的去向吗？奥巴马就任总统后，西罗克回到

    了美国西部，与谷歌的同事皮特·库曼合作创办了网站优化公司

    Optimizely。2012年，当又一轮的总统选举拉开帷幕时，该公司的客户

    名单里不仅包含奥巴马竞选连任的团队，还可以看到奥巴马的挑战者、共和党候选人米特·罗姆尼的竞选团队。

    AB测试大约于10年前首次被使用，如今这个优化利器已经脱下了

    神秘的外衣，并且理所当然地植入到网络上的经营行为与政治活动之

    中。当你再一次打开浏览器时，你眼前的色彩、图片、文本甚至定价

    (当然还有广告)肯定都是探索与利用算法根据你的鼠标点击为你量身

    定制的。在这个特定的多臂***问题中，你不是那名赌徒，而是奖池

    中的累积奖金。

    几年来，AB测试的程序也越来越完善。AB测试最经典的做法是

    将流量均分给两个选择方案，测试一段时间之后，再将所有流量都分配

    给获胜一方。但是，这种做法将导致一半用户在测试的过程中只能接受

    较差的那个方案，因此它未必最有利于解决问题。如果可以找到更好的

    做法，就有可能得到丰硕的回报。在谷歌近500亿美元的年收入额中，超过90%的比例来自付费广告，而互联网商务一年的成交额为数千亿美

    元。这说明探索与利用算法是互联网的一个非常重要的经济技术动力来

    源。关于最优算法的争论一直甚嚣尘上，统计学家、工程师和博客作者

    就各种经营环境下探索与利用的最有效平衡方法这个问题争论不休。

    精确地区分人们在探索与利用问题上的不同观点似乎是一件晦涩难

    懂的事情，但是事实证明，区分这些观点非常重要，这不仅与总统选举

    和互联网经济有关，而且与人们的生活也有密不可分的关系。试验中的临床试验

    1932—1972年，亚拉巴马州梅肯县有数百名非裔美国人患有梅毒，但是医学专业人士故意不予治疗。这是美国公共卫生服务机构“塔斯基

    吉梅毒研究”40年实验的一部分。1966年，公共卫生服务部门的员工彼

    得·巴克斯顿提出抗议，并于1968年提出了第二次抗议。但是，直到他

    把这件事透露给媒体(1972年7月25日，《华盛顿星报》刊登了相关内

    容，第二天《纽约时报》也在头版头条上讨论了这件事)之后，美国政

    府才停止了这项研究。

    公众对此提出了强烈抗议，随后国会举行听证会，并裁决必须采取

    措施规范医学伦理的原则和标准。1979年，在马里兰州贝尔蒙特会议中

    心召开的委员会出台了一份被称作“贝尔蒙特报告”的文件。《贝尔蒙特

    报告》为医学实验的伦理实践奠定了基础，从此以后，塔斯基吉实验这

    种令人震惊的、明显不恰当的、违背卫生职业对病人应尽义务的行为永

    远不会重演。但该文件也注意到，在许多其他情况下，问题的性质很难

    精确界定。

    报告指出：“希波克拉底的格言‘不伤害’一直是医学伦理的基本原

    则，生理学家克劳德·伯纳德把它扩展到研究领域，指出一个人不应该

    伤害另一个人，无论他的行为可以给其他人带来何种好处。然而，即使

    避免伤害也需要知道什么是有害的。在获取这些信息的过程中，人们可

    能会有受到伤害的风险。”

    因此，《贝尔蒙特报告》承认，以自己掌握的最有效信息指导自己

    行动和收集更多信息之间存在矛盾，但是该报告没有给出解决办法。此外，它还表明，收集知识具有极高的价值，因此即使在某些方面违背正

    常医学伦理也是可以接受的。报告指出，新药和新疗法的临床试验经常

    会使某些病人面临受到伤害的危险，尽管这种危险可以通过某些措施降

    至最低程度。

    仁爱的原则并不一定非常明确。例如，儿科病研究给儿童带来的风

    险超出了最低限度，短期内却看不到让其他孩子从中受益的希望，这是

    儿科病研究面临的一个难以处理的伦理问题。一些人认为这样的研究是

    不可接受的，另一些人则指出，如果加以限制，很多有望在未来给孩子

    们带来巨大裨益的研究就会遭到禁止。同样，正如所有的困难案例一

    样，仁爱原则涵盖的不同主张可能相互矛盾，并迫使人们做出艰难的选

    择。

    人们在《贝尔蒙特报告》出台之后几十年里面临的重要问题之一就

    是临床试验的标准方法是否真的可以将病人面临的风险降至最低。某个

    传统的临床试验将病人分成若干小组，每个小组在研究过程中接受不同

    的治疗。(只有在极其特殊的情况下，实验才会提前终止。)这个程序

    关注的焦点是明确回答哪种治疗方案效果更好，而不是为接受实验的每

    一名病人提供最有效的治疗。一部分病人在整个实验期间接受的治疗最

    终被证明效果较差，这与网站的AB测试没有任何不同。但是，在实验

    进行的同时，医生(科技公司同样如此)就已经在收集有关各方案治疗

    效果的信息，这些信息不仅可以在实验结束之后用来改进未来病人的治

    疗，而且同样适用于正在实验中接受治疗的病人。

    优化网站配置的实验会造成成千上万美元的影响，但是在临床试验

    中，寻找最有效治疗方案的实验直接关乎病人的生死。越来越多的医生

    和统计人员认为我们的做法是不正确的。他们主张，我们应该把医疗方

    案选择问题视为多臂***问题，在实验正在进行的同时努力寻找更好

    的治疗方法。1969年，马文·泽伦(现在是哈佛大学的一名生物统计学家)建议

    采用“自适应性”试验。他提出的一个建议是随机化“胜者优先”算法——

    另外一个版本的赢留输变算法。根据这个算法，使用某个特定治疗方案

    的可能性随着每次成功治愈有所增加，反之则会减少。按照泽伦设计的

    程序，你首先在帽子里放两个小球，分别代表接受研究的两个治疗方

    案。从帽子中随机拿出一个小球，以确定第一名病人使用哪种治疗方案

    (随后将小球放回帽中)。如果所选的治疗方案成功地取得了疗效，就

    在帽子里再放一个代表这种治疗方案的小球。此时，帽子里一共有三个

    小球，其中有两个代表刚刚取得成功的治疗方案。如果所选的治疗方案

    失败了，就在帽子里再放一个代表另外一个治疗方案的小球，以增加将

    来选中该治疗方案的可能性。

    16年后，一项ECMO(体外膜肺氧合)研究在临床试验中首次使用

    了泽伦的算法。ECMO是密歇根大学的罗伯特·巴特莱特在20世纪70年

    代提出的一种治疗婴儿呼吸衰竭的大胆方法，它将流向肺部的血液导到

    体外，利用机器帮助它完成氧合，然后送回心脏。这是一个有风险的极

    端措施(甚至有形成栓塞的可能性)，但是在没有其他选择的情况下，它也不失为一种有可能行得通的方法。1975年，ECMO挽救了加州奥兰

    治县一个新生女婴的生命。这名即使安装呼吸机也会缺氧的女婴，如今

    已经40多岁，并且已经结婚生子。但是在早期，ECMO被认为是一种具

    有高度试验性的技术和程序，在成年病人身上进行的早期研究表明它的

    疗效并不优于传统治疗方法。

    1982—1984年，巴特莱特和他在密歇根大学的同事对患有呼吸衰竭

    的新生儿进行了一项研究。研究小组声称，他们知道自己希望解决“拒

    绝实施未经证实但有可能挽救生命的治疗方法所带来的伦理问题”，并

    且“不愿意仅仅为了满足传统的随机分配方法的需要，就拒绝为另外一

    组病人实施可以挽救他们生命的治疗方案”。因此，他们采用了泽伦的

    算法，并制订了一个试验策略。结果，一名被安排接受“常规”治疗的婴儿病情加重，濒临死亡，而11名接受试验性ECMO治疗的婴儿全部存活

    了下来。1984年4—11月，在官方研究结束后，另有10名婴儿符合实施

    ECMO疗法的标准。其中8名患者接受了ECMO治疗，结果8人全部存

    活。两名患者接受常规治疗，最后均不治而亡。

    这些数字非常引人注目，然而，在密歇根大学对ECMO的研究完成

    后不久，它就陷入了争论之中。试验中接受常规治疗的患者非常少，这

    与标准方法有很大的不同，而且这个程序本身具有高度的侵入性和潜在

    风险。在论文发表后，哈佛大学公共卫生学院生物统计学教授吉姆·维

    尔和他的卫生学院同事仔细研究了这些数据，并且断定“如果不进行进

    一步的研究，就无法证明应该将ECMO纳入常规疗法的名单之中”。因

    此，维尔和同事们设计了第二个临床实验。这一次，他们仍然努力在获

    取知识和对患者实施有效治疗这两者之间达成平衡，但是选择了使用更

    温和的设计方案。他们将为患者随机安排ECMO或常规治疗。等到在其

    中一个组中观察到预先指定的死亡人数之后，就会对所有病人提供更有

    效的治疗方法。

    在维尔研究的第一阶段，接受常规治疗的10名婴儿中有4人死亡，而接受ECMO治疗的9名婴儿全部存活。这4名婴儿的死亡足以促使研究

    进入第二阶段，于是全部20名患者都接受了ECMO治疗。最终，19人得

    以幸存。维尔和同事们终于信服了，并且断言“如果继续随机安排治疗

    方法，在伦理道义上是无法辩解的”。

    但是，在维尔实施这项研究之前，就已经有人完成了类似研究，并

    明确提出了相同的观点。批评者包括唐·贝瑞——世界上研究多臂老虎

    机问题的主要专家之一。贝瑞在发表于《统计科学》杂志上的一篇评论

    文章中写道：“像维尔研究那样为病人随机安排ECMO以外的治疗方

    法，是不道德的……在我看来，维尔当初就不应该实施那项研究。”

    然而，即使维尔的研究也没有让医学界的所有人都信服。20世纪90年代，有人又在英国招募了近200名婴儿，进行了另一项ECMO研究。

    他们没有采用自适应算法，而是遵循传统的方法，将这些婴儿随机分为

    人数相等的两个小组。研究人员称ECMO的有效性“是有争议的，因为

    现有证据有不同的解释”。结果，关于这两种治疗方法之间的差别，英

    国人宣布的结果与美国人在两项研究中得出的结论并不相同，但是英国

    人仍然宣称他们的研究结果“与先前的初步成果是一致的，即利用

    ECMO提供支持的治疗方案可以降低死亡风险”。为获取这些知识，他

    们付出了多大代价!“常规”组婴儿死亡人数比接受ECMO治疗的小组多

    24人!

    自适应临床试验的结果遭到了普遍抵制，这似乎是一个令人费解的

    现象。但是，我们可以想一想在20世纪初刚刚出现的统计学对医学产生

    的影响。本来，每次出现一个新疗法，医生们都需要说服其他医生接受

    该疗法。但是统计学出现之后，哪些证据可信、哪些证据不可信，就有

    了明确的标准。修改已经被广为接受的标准统计方法有可能打破这种平

    衡，至少会暂时打破平衡。

    在ECMO引发的争议平息之后，唐·贝瑞离开了明尼苏达大学的统

    计学系，来到位于休斯敦的MD安德森癌症中心，利用他在研究多臂老

    虎机问题时提出的方法，为各种癌症治疗法设计临床试验。他仍然会直

    言不讳地批评随机临床试验，而且跟他一样的批评者大有人在。近年

    来，他一直为之奋斗的理念终于逐渐变成一种主流观点。2010年2月，美国食品及药品管理局发布了一份《药物和生物制剂的自适应设计临床

    试验》的“指导”文件，这表明他们终于愿意探索其他选择了(尽管长期

    以来，他们一直坚持他们所信任的选择方案)。不安分的世界

    一旦你熟悉了多臂***问题，你就会发现这些问题随时会出现在

    你身边。我们做出的决定往往都不是孤立的，它们会给我们提供一些信

    息，在未来做其他决定时，我们可以加以利用。因此，我们自然会问，人们在解决这些问题时通常会有什么样的表现。我们在前面遇到最优停

    止问题时就提出了这样的问题，而心理学家和行为经济学家也已经在实

    验室里进行了广泛的研究。

    一般而言，人们似乎倾向于过度探索——对新鲜事物的青睐程度超

    过效果最佳的事物。1966年，阿莫斯·特沃斯基和沃德·爱德华兹在杂志

    上发表了一个关于这种现象的简单演示。他们先展示了一个盒子，盒子

    上面有两盏灯。然后，他们告诉实验参与者，每盏灯打开的时间比是固

    定的，但是没有告诉他们这个比例到底是多少。接着，他们给这些实验

    参与者1000个机会，让他们观察是哪盏灯打开了，或者在不观察的情况

    下对结果下注。(与传统***问题的设置不同，在这里，人们无法

    像“拉动拉把”那样在下赌注的同时就可以观察到结果，而是要等到实验

    结束，参与者才知道他们是否押中。)这个实验纯粹就是探索与利用之

    间的对抗，信息的获取与信息的利用正好矛盾。在大多数情况下，参与

    者都采取了一种明智的策略：先观察一段时间，然后把赌注押在看似最

    好的结果上，但是他们用来观察的次数总是太多了。到底多了多少？在

    一次实验中，两盏灯打开的时间比分别是60%和40%，两者之间的差别

    既不特别明显，也不至于难以察觉。在这种情况下，人们平均会选择观

    察505次，而其他495次的机会则被用来下注。但数学计算表明，他们只

    需观察38次，然后就应该开始下注，也就是说，可以留下962个机会，用来赢钱。

    其他研究也得出了类似的结论。20世纪90年代，沃顿商学院的研究

    人员罗伯特·迈耶和施勇进行了一项研究。他们让人们从两个选择方案

    中做出选择。一个选择方案的回报概率已知，另一个则未知。具体来

    说，就是两个航空公司，其中一个名声较响、准点率已知，另一个则是

    没有记录的新公司。数学给出的最优策略是：为了使一段时间内准点到

    达的次数达到最大，在刚开始时应该只选择那家新航空公司，除非那家

    知名公司的准点率明显高于前者。只要那家知名公司的服务明显更好

    (也就是说，只要新公司的基廷斯指数低于知名公司的准点率)，就应

    该立刻毫不犹豫地选择这家知名公司，而且再也不要回头。(在这种情

    况下，一旦你不再乘坐那家新公司的飞机，你就无法获得更多关于它的

    信息，因此它就没有了挽回信誉的机会。)但在实验中，即使新航空公

    司的服务非常好，选择尝鲜的人仍然很少；当这些尝鲜的人发现新航空

    公司服务不佳的时候，他们又往往不能及时调整自己的选择。而且，即

    使他们放弃其中一家航空公司，态度也不是十分坚决，而是继续来回变

    换自己的选择。在两家航空公司都不准点时，这种表现更加明显。所有

    这一切都与习惯性过度探索有关。

    最后，心理学家马克·斯蒂维尔思、迈克尔·李和E.J.瓦根梅克斯利用

    四臂***做了一个实验。在实验中，参与者有连续15次机会，从4个

    拉把中选择一个进行赌博游戏。然后，他们把参与者可能会使用的策略

    进行分类。结果表明，30%的策略接近于最优策略，47%的策略与赢留

    输变策略十分相似，22%的策略似乎是在新的拉把与目前为止成绩最好

    的拉把之间做出随机选择。研究结果再一次符合过度探索的特征，因为

    赢留输变以及偶尔随机尝试新拉把这两种行为都会导致人们尝试新鲜事

    物，即使在游戏快要结束、应该进入纯利用阶段的时候，他们也不愿意

    选择最佳方案。也就是说，我们在招聘秘书时会过早地递出橄榄枝，但是在放弃新

    航空公司这个方面，我们的决定又往往来得过晚。不过，正如没有秘书

    帮忙需要我们付出成本，过早地选定一家航空公司也是有代价的，因为

    这个世界可能会发生变化。

    标准多臂***问题假设各个拉把的回报概率不会随时间发生变

    化，但是航空公司、餐厅以及需要人们做出重复选择的其他环境未必满

    足这个条件。如果各个拉把的回报概率随时间发生变化(人们称之

    为“不安分的***”)，问题的难度就会显著提高。(事实上，不安分

    多臂***问题的难度非常高，目前还无法利用算法四平八稳地彻底解

    决这个问题。人们认为这样的算法永远也不会出现。)原因之一就是我

    们再也不能先探索一段时间，然后尽情地利用。既然世界是变化的，那

    么正确的选择可能就是继续探索。一家餐厅令你失望，于是你再也不愿

    意去那里用餐，但是过了几年之后，也许你应该再去一次，万一那里换

    了一名经理呢。

    亨利·大卫·梭罗在他的著名散文《散步》中，说他喜欢在离家近的

    地方旅行，他从不厌倦周围的环境，并且马萨诸塞州的风光总是能给他

    一些新奇的发现。他写道：“在方圆十英里或者午后散步所及范围内的

    景物与七十载人间岁月之间，其实可以发现一种和谐，一种你永远不会

    觉得非常熟悉的和谐。”

    生活在烦躁不安的世界里，我们也必须有一颗不安分的心。只要事

    物在不断变化，我们的探索就不能偃旗息鼓。

    不过，即使在一个动荡不安的世界里，针对标准版本多臂***问

    题精心打造的算法技术仍然可以找到用武之地。基廷斯指数、上限置信

    区间等策略可以提供相当优秀的近似解决方案及经验法则，在回报概率

    随时间变化的幅度不大时效果更加明显。今天，世界上很多事件的回报

    概率变化幅度比以前小得多。地里的果实这一周成熟了，到了下一周就会烂掉，但是，正如安迪·沃霍尔所说的，“一杯可乐就是一杯可乐”。

    通过进化来调整自己的直觉以适应不断变化的世界，在工业标准化时代

    未必有用。

    也许最重要的是，考虑有最优解的多臂***问题，不仅可以为我

    们提供各种算法，还可以让我们得到一些深刻的见解。在经典多臂老虎

    机问题研究中形成的一些语汇，诸如探索与利用的矛盾、剩余时间的重

    要性，0-0选择方案的高价值和最小遗憾值等，它们不仅可以帮助我们

    以全新的方式理解眼前的具体问题，还可以帮助我们以全新的视角看待

    整个人类生活。探索——孜孜不倦

    虽然实验室研究具有启发性，但是在人们面对的许多重要问题中，剩余时间都非常长，无法在实验室中加以研究。学习了解周围世界的组

    织结构、建立持久的社会关系都是伴随我们一生的任务。因此，了解早

    期探索、后期利用的一般模式可以给我们启发。

    所有发展心理学家都渴望理解和解释关于人类的一个奇怪现象：我

    们培养能力与自主性的过程往往需要持续好多年。北美驯鹿和瞪羚自出

    生之日起，就必须做好拼命奔跑以逃脱捕食者的准备，但是人类需要一

    年多的时间才能迈出自己的第一步。加州大学伯克利分校发展心理学教

    授、《摇篮里的科学家》一书的作者艾莉森·高普尼克在解释为什么人

    类有如此长的依赖期时说：“它让你学会以发展的方式来解决探索与利

    用之间的取舍。”我们已经看到，教我们玩多臂***的优秀算法往往

    在刚开始的时候倾向于探索，在后期则倾向于对所获取的知识加以利

    用。但是正如高普尼克指出的：“这种做法有一个缺点——在探索阶

    段，你无法获得充分的回报。”因此，童年是人生的探索阶段。“在童年

    时期，你可以尽情探索各种可能性，而不必担心回报的问题，因为爸

    爸、妈妈、奶奶和保姆会帮你处理好。”

    把童年看作是人生算法中短暂的探索阶段，可能会让学龄前儿童的

    父母感受到一些安慰。(汤姆有两个热衷于探索的学龄前女儿，他希望

    算法可以指引她们的人生，让她们感到遗憾的次数降至最低。)同时，也让我们对儿童的理性有了新的深刻认识。高普尼克指出：“仔细研究

    长期以来人们对孩子的看法，就会发现成人通常会认为孩子在认知上有

    各种各样的缺陷，因为孩子们在某个方面的表现有些糟糕。他们不会系鞋带，他们不擅长长期规划，他们不擅长集中注意力。孩子们在这些方

    面表现得非常差。”但是，随意按动按钮、对新玩具非常感兴趣、思维

    跳跃性强，这些都是孩子们的特点。如果他们的目标是探索，这些就正

    是他们应该做的事情。如果你是一个婴儿，那么你抓到家里所有东西都

    会往嘴里放的行为，与赌徒在赌场里小心翼翼地拉动***拉把的行为

    并没有本质上的不同。

    一般而言，我们对理性的直觉认识常常来源于利用，而不是探索。

    当我们谈论决策过程时，我们通常只关注某个决定的即时回报——如果

    你把每一个决定都当作人生的最后一个决定，那么只有利用才是有意义

    的。但在一生中，你会做出很多决定。实际上，在做很多决定时，理性

    的做法是强调探索的重要性，重视新的东西而不是最好的东西，重视令

    人为之兴奋的东西，而不是一味追求安全，重视随机选择，而不是深思

    熟虑的决定。在人生早期，更应该如此。

    孩子们的有些想法，在我们看来是任性，但是实际上，可能比我们

    想象的更明智。走出探索和利用的两难困境

    莉迪娅·戴维斯

    我的阅读生涯已经走到了一个十字路口，有过类似经历的人都熟悉

    我现在面临的难题：在我余下的时光里，我是应该不停地阅读新书，还

    是应该停止这种徒劳的行为(之所以徒劳，是因为新书永远读不完)，然后重读那些曾经令我无比愉悦的书呢？

    与学步的孩童相对应的另一个极端是已步入垂暮之年的老人。从探

    索与利用这个两难困境的角度去思考老年生活，也会为我们带来一些令

    人吃惊的洞见，让我们学会随着时间的推移调整我们对生活的期望。

    斯坦福大学心理学教授劳拉·卡斯滕森通过自己的研究，对人们在

    衰老这个问题上的成见提出了质疑。她特别研究了人们的社会关系随着

    年龄增长而发生变化的过程与原因。这种变化有一个明晰的基本模式：

    人们社交网络的规模(即与他们保持社交关系的人数)几乎总是随着时

    间的推移而减少。不过，卡斯滕森的研究表明，我们应该改变对这个现

    象的看法。

    传统观点认为，老年人的社交网络逐渐变小，恰恰说明生活质量会

    随着年龄的增长而逐渐下降，因为他们维系社会关系的能力在减弱，身

    体一天天衰弱，而且普遍与社会脱节。但是，卡斯滕森认为，老年人的

    社会关系越来越简单，是他们主观选择的结果。她说，这个变化是“一

    生的选择过程造成的结果。人们利用这个选择过程构建他们的社交网

    络，并且通过仔细谋划，适应调整，最大限度地提高社交和情感收益，同时最大限度地减少社交和情感风险”。卡斯滕森和他的同事发现，老年人“修剪”一些不重要的关系，以便

    把注意力高度集中在亲朋好友身上，这才是造成他们的社交网络逐渐变

    小的主要原因。这个过程似乎是一个深思熟虑的选择：当人们接近生命

    的终点时，他们希望更多地关注对他们来说最重要的人。

    卡斯滕森和合作伙伴芭芭拉·弗雷德里克森通过实验验证了这个假

    设。他们让人们从直系亲属、最近读过的一本书的作者和志趣相投的新

    交中选择一个人与自己共度30分钟。结果，年纪大的人往往选择家人，年轻人则希望与作者接触或者结交新朋友。但是，如果对实验做一个重

    要的修改，告诉年轻人他们即将搬到很远的地方，那么他们也会更愿意

    与家人待在一起。在另一项研究中，卡斯滕森和同事发现，同样的结果

    也发生在老年人身上：如果让老年人设想，由于医学上取得了突破，他

    们还可以再活20年，那么他们的选择就会和年轻人趋同。由此可见，社

    交偏好的这些差异与年龄本身无关，而是与人们对决策过程中剩余时间

    的认知有关。

    计算机科学同样认为，探索与利用的困境对剩余时间很敏感。我们

    通常认为年轻人喜欢推陈出新，而老年人的做事方式往往一成不变。事

    实上，两者的行为都与他们各自的剩余时间高度一致。把社交网络限制

    在精心挑选、对自己最重要的圈子里，是一种理性的反应，因为老年人

    尽情享受社交成果的时间已经越来越少了。

    认识到老年生活是充分利用前期积累的阶段，有助于我们以全新的

    视角看待一些经典的老年现象。举个例子，上大学时，你置身于一个新

    的社交环境之中，周围的人你都不认识，这对于你来说通常是一段催人

    向上、意气风发的时光，而老年公寓虽然也是一个新的社交环境，周围

    的人你也都不认识，但是这很可能会让你非常苦闷。这种差异在一定程

    度上是因为我们在人生各个阶段探索与开发这个连续统一体中所处的位

    置不同。探索与开发的权衡也告诉我们应该如何看待来自长辈的建议。如果

    祖父告诉你哪家餐厅好，你应该相信，因为这些都是几十年搜索活动的

    结果。但是，如果他每天下午5点都会去同一家餐厅，你就该毫不犹豫

    地探索其他选择，即使那些餐厅有可能更差。

    在探索了几十年之后，如果把晚年生活视为充分利用人生积累的良

    机，就可以加深我们对人生的认识，我们甚至将发现生活会随着时间的

    推移而越变越好。探索者为了获得知识，付出的代价是心情愉悦。我们

    已经知道，因为意外惊喜有可能带给我们多倍补偿，所以基廷斯指数和

    上限置信区间都夸大了对未知选择方案吸引力的期望值。但是，与此同

    时，这也意味着在大多数情况下，探索必然会让人失望。把注意力转移

    到自己喜欢的事情上，应该可以提高生活质量，事实似乎也确实如此。

    卡斯滕森发现，与年轻人相比，老年人通常对自己的社交网络更加满

    意，认为自己的情感状况更加健康。

    因此，傍晚常去的那家餐厅里有很多东西值得老年人期待。坐在那

    里，他们可以品尝毕生探索带来的成果。03 排序 建立秩序

    罗伯特·考德雷，《词汇表》

    如果你要查的单词的首字母是a，就在《词汇表》开头部分查找。

    如果首字母是v，就到靠后的位置查找。此外，如果开头的两个字母是

    ca，就在字母c项下的开头部分查找。如果是cu，则应到字母c部分的末

    尾处查找。以此类推。

    多年以前，丹尼·希利斯是麻省理工学院的一名本科生。当时他还

    没有创立“思维机器公司”，也还没有发明著名的“连接机器”并行超级计

    算机，而是住在学生宿舍里，目瞪口呆地看着室友的袜子。

    与许多大学生不同的是，希利斯关心的并不是室友的卫生状况。让

    他感到吃惊的，并不是他勤于洗袜子，室友却从来不洗，而是接下来发

    生的事情。

    室友从干净的洗衣篮中拿出一只袜子。接着，又随机抽出另一只袜

    子。如果两只袜子不配对，他就把第二只扔回去。然后继续这个过程，他把袜子一个一个地抽出来，然后把它们扔回去，直到为第一只袜子成

    功配对为止。

    洗衣篮里一共有10双不同的袜子。按照这个方法，配好第一对最多

    需要取19次，配好第二对又可能需要17次。如果要把20只袜子全部配成

    对，这个室友可能需要从洗衣篮里取110次袜子。

    任何未来的计算机科学家看到这幅情景，可能都会要求换宿舍。应该如何对袜子进行排序的问题引起了计算机科学家的热议。2013

    年，有人在“栈溢出”编程网站上贴出了一个关于袜子的问题，立刻引发

    了长达12000个单词的争论。

    当我们对传奇式密码学家、计算机科学家、图灵奖得主罗恩·李维

    斯特提起这个话题时，他向我们坦承：“我被袜子打败了!”

    当时，他穿着凉鞋。排序狂潮

    排序是计算机的核心内容。事实上，从很多方面看，如果没有排

    序，计算机就不会变成现实。

    19世纪末期，美国人口每10年就会增加30%。1870年，美国人口普

    查只有5个“调查科目”，到1880年，就增加到了200多个。1880年人口普

    查的制表工作花了8年，在1890年人口普查即将开始时才勉强完工。当

    时，有一位作家评论说：“调查人员整天埋头整理那些令人头皮发麻的

    统计数字，竟然没有失明，也没有发疯，这真是一大奇迹。”所有从事

    人口普查的工作人员都不堪重负，濒临崩溃。这个局面已经到了不得不

    改变的地步。

    发明家赫尔曼·霍尔瑞斯从当时使用的打孔火车票那里找到灵感，发明了一种可以存储信息的打孔统计卡和一种机器，用来完成计数与排

    序工作。他把这套系统称作“霍尔瑞斯计算机”。1889年，霍尔瑞斯获得

    专利，美国政府在1890年的人口普查中采用了霍尔瑞斯计算机。在这之

    前，从来没有人看到过这样的机器。一位惊叹不已的旁观者说：“这个

    装置就像众神的磨坊一样准确无误，速度则完胜对方。”然而，另一个

    人认为这项发明的用途十分有限：“除了政府以外，没有人愿意使用

    它，因此发明者不可能发财。”霍尔瑞斯把这个预言制成剪报并保存了

    下来，但是事实证明，这个预言并不完全正确。1911年，霍尔瑞斯公司

    与另外几家公司合并，变成了计算-制表-记录公司。几年之后，公司改

    名为国际商用机器公司，即IBM。

    从计算机诞生直到进入20世纪，排序一直是推动计算机发展的一大动力。为“存储程序”计算机编写的第一个代码是一个高效排序程序。事

    实上，正是因为计算机的能力超越了IBM的专用卡片分类机，所以美国

    政府相信它们在通用机器上投入巨额资金的决定是正确的。到20世纪60

    年代，一项研究估计，世界上超过14的计算资源被用于排序。难怪排

    序对于处理几乎任何类型的信息来说都是至关重要的。无论是查找最大

    值或最小值，最常见数据或最罕见数据，还是清点、索引、标记副本，或者根据你的要求进行查找，其核心工作通常都是排序。

    但是，排序不仅用于这些方面。毕竟，排序的主要原因之一是将内

    容变成方便人眼观察的形式，这意味着排序也是人类信息体验的关键。

    排序列表无处不在。就像鱼儿问“水是什么”一样，我们只有有意识地去

    感知，才会发现排序无处不在。

    即使电子邮件收件箱有数千封邮件，它也通常会根据收件时间显示

    排在前面的50封。利用点评网站Yelp寻找餐厅时，它也会将成百上千家

    餐厅根据邻近程度与用户评分排序，然后为你显示前十几名。博客按日

    期对博文进行排序，显示一个不是很长的博文清单。脸书的动态信息、推特的信息流和红迪网的主页都是根据某些属性对内容进行排序，然后

    以列表的形式显示出来。我们把谷歌和必应等网站称作“搜索引擎”，但

    是这个称呼并不是非常恰当，因为它们其实都是排序引擎。作为接收全

    球信息的一种手段，谷歌占有非常明显的优势，究其原因，与其说是它

    可以在成千上万的网页中找到我们需要的文本(20世纪90年代，谷歌的

    竞争对手同样可以出色地完成这个任务)，不如说是因为谷歌可以将这

    些网页进行有效地排序，然后只把关系最密切的前10个网页显示出来。

    从很多方面看，在庞大排序表的顶部截取一部分，就可以当作通用

    的用户界面。

    计算机科学可以帮助我们了解所有上述情况的深层次内容。当我们

    被账单、文件、书本、袜子等团团包围，希望厘出头绪(这种情况每天都会发生，而且比我们想象的还要多)时，这些知识又可以转化为一种

    深刻认识，帮助我们解决难题。通过量化混乱状况的缺点(和优点)，计算机科学还告诉我们，在一些情况下，我们其实根本不应该排出次

    序。

    此外，当我们开始看排序结果时，我们知道被排序的不仅是信息

    ——被我们排序的其实是人!建立先后次序的计算机科学最适合大展身

    手的舞台可能是运动场和拳击场，因此，学会排序有助于理解人类可以

    和谐相处、偶尔才会拳脚相向的原因。也就是说，排序可以为我们提供

    一些令人吃惊的线索，帮助我们了解社会的本质。所谓社会，就是我们

    维持的另外一种更重要、规模更大的秩序。排序带来的苦恼

    1955年，詹姆斯·霍斯肯在第一篇公开发表的关于排序的科学论文

    中写道：“为了降低单位产出的成本，人们通常会增加他们的业务规

    模。”这是任何一名商科学生都很熟悉的规模经济。但是，在排序这个

    问题中，规模往往会招致灾难：如果扩大排序的规模，“排序的单位成

    本就会不降反升”。排序往往呈现非常明显的规模不经济现象，这与普

    通人认为大批量处理问题有诸多好处的直觉正好相反。一般来说，做两

    个人的饭并不比做一个人的饭难，肯定比为一个人做两次饭要容易得

    多。但是，整理好装有100本书的书架，比整理两个各有50本书的书架

    更费时：因为你需要整理的东西是后者的两倍，而且每件东西可以放置

    的位置也是后者的两倍。需要整理的东西越多，难度就越大。

    这是排序理论的第一个，也是最基本的深刻见解：规模越大，难度

    越大。

    由此我们可以推断，在排序的过程中，最大限度地减少痛苦的办法

    就是在排序时尽可能减少排序对象的数量。的确，降低袜子排序计算难

    度的一个最有效的预防措施就是勤洗衣服。如果洗衣服的频率增加到原

    来的3倍，排序时的难度就会变为原先的19。如果希利斯的室友继续采

    用他的那套独特程序，那么把洗衣服的间隔时间从14天改为13天，为袜

    子配对时从洗衣篮中拿袜子的总次数就可以减少28次。(间隔时间增加

    1天，拿袜子的次数就会增加30次。)

    即使在14天这样一个不大不小的时间范围内，我们也可以看到排序

    的规模已经开始变得难以处理。然而，计算机通常需要一口气为数百万个项目排序。面对这种情况，我们可以借用电影《大白鲨》的一句台

    词：我们需要一艘更大的船以及更好的算法。

    但是，要回答如何排序、哪种排序方法效果最佳这个问题，就需要

    先弄明白另外一个问题：如何计分。大O符号：衡量最坏情况的标准

    根据《吉尼斯世界纪录大全》，为一副扑克牌整理次序的最快记录

    是捷克魔术师兹德涅克·布拉德克保持的。2008年5月15日，布拉德克仅

    用时36.16秒就把52张扑克牌排好了先后次序。[1]

    他是怎么做到的？是

    什么排序技术让他获得这项殊荣的？答案可能与一些有趣的排序理论有

    关，但是布拉德克拒绝置评。

    对于布拉德克的灵巧与技能，我们只能表示尊敬，但是我们百分之

    百地确定我们自己也可以打破他的纪录。事实上，我们非常确定，只要

    向这项殊荣发起

    80658175170943878571660636856403766975289505440883277824000000000000

    次挑战，就一定可以创造一个无法打破的纪录。这个数字比10的66次方

    的80倍略大一点儿，是52的阶乘，数学上记作“52!”——包含52张牌的

    一副扑克牌可以排出这么多不同的次序。在经过大约这么多次的尝试之

    后，我们迟早可以为经过洗牌变得杂乱无序的扑克牌快速排序，然后，我们可以自豪地让克里斯汀·格里菲斯这个名字载入《吉尼斯世界纪录

    大全》，然后在旁边标明一个不太难看的排序时间——0分00秒。

    公正地说，在宇宙进入热寂状态之前，我们可能都需要不停地尝

    试，才有可能创造出这个完美的纪录。尽管如此，我们从中可以清楚地

    看到纪录保持者和计算机科学家之间最大、最根本的区别。吉尼斯纪录

    的工作人员只关心最好的成绩(和娱乐性)。当然，他们的行为也无可

    厚非，因为所有的体育纪录也都只能反映出最佳表现。然而，计算机科

    学几乎从不关心最好的情况。相反，计算机科学家可能想知道像布拉德克等人的平均排序时间：让他对所有8×1066副扑克牌或者合理大小的样

    本进行排序，然后记录平均速度。(这下你知道他们为什么不会让计算

    机科学家来做这些事情了吧？)

    不仅如此，计算机科学家还希望知道最慢的排序速度。分析最糟糕

    的情况，可以让我们放心地做出硬性保证——确保关键程序可以及时完

    成，确保不会超出最后期限。因此，在本章剩余部分(事实上，是全书

    的剩余部分)里，除非另有说明，否则我们讨论的都是算法的最差表

    现。

    计算机科学有一种专门用来测量算法最坏情况的速记法，即所谓

    的“大O”符号。大O符号有一个非常奇怪的特点——设计这个符号的目

    的就是用来表示不精确性。也就是说，大O符号的目的不是使用分钟和

    秒钟来表示算法的性能，而是方便我们讨论问题规模和程序运行时间之

    间的关系。由于大O符号故意剔除了细枝末节的内容，所以展示在我们

    眼前的是将问题分成不同大类的概略情况。

    假设你准备邀请n名客人出席晚宴。在客人到来之前，打扫房间的

    时间与来客人数没有任何关系。这类问题最简单，被称为“O(1)”，也

    被称为“常数时间”。值得注意的是，大O符号根本不关心清理工作需要

    多长时间，只是要求它保持不变，与宾客名单没有任何关系。无论来几

    个客人，1个，10个，100个，或者n个，你都需要完成同样多的工作。

    接下来，烤肉在所有客人面前传递一圈所需的时间将是“O(n)”，也被称为“线性时间”——客人增加一倍，菜传递一圈所需的时间就会增

    加一倍。同样，大O符号根本不关心一共有多少道菜，也不关心这些菜

    是否会上第二遍。在这两种情况下，时间仍然取决于宾客数量，如果你

    画出客人数量和时间的关系图，就会得到一条直线。更重要的是，在大

    O符号中，任何线性时间因子的存在，都会掩盖掉所有常数时间因子。

    也就是说，将烤肉传递一圈，或者花三个月时间把餐厅重新装修一遍，再把烤肉在所有客人面前传递一遍，对计算机科学家来说，两者都是等

    效的。不要认为这个说法不可思议，记住计算机处理的是n的值，这个

    数值变成几千、几十万，甚至几十亿，也不是难事。换句话说，计算机

    科学家正在考虑举行一个规模非常大的聚会。在数百万的来宾当中传递

    一次烤肉，所需时间之多，真的足以让房屋重新装修所需的时间变得无

    足轻重。

    假设客人到来之后，你要与每个人热烈拥抱，情况又会怎么样？第

    一个到达你家的客人与你拥抱，第二个客人需要拥抱两次，第三个客人

    要拥抱三次。此时，拥抱一共发生了多少次？这种情况属

    于“O(n2)”，也称“平方时间”。此时，我们同样只关心n与时间的关系

    概貌。每个人拥抱两次不会是O(2n2)，拥抱加传递食物不会

    是O(n2+n)，拥抱加打扫房间也不是O(n2+1)。所有的时间都是平

    方时间，所以O(n2)将掩盖掉其他所有因素。

    注：常数时间，记作O(1)；线性时间，记作O(n)；平方时间，记作O(n2)

    从现在开始，情况就会变得越来越糟糕了。如果每增加一名客人都

    会让你的工作加倍，那么就会有“指数时间”，记作“O(2n)”。更糟糕的是，甚至还有“阶乘时间”，记作“O(n!)”。阶乘时间异常复杂，计

    算机科学家只有在开玩笑时(例如，我们设想通过洗牌这个方式为一副

    扑克牌排序)，或者真的希望自己是在开玩笑时，才会讨论这类问题。

    [1]除此以外，布拉德克还保持多项纪录。例如，他可以在水下打开三副手铐逃生，所耗时

    间与给扑克牌排序的时间差不多。平方时间：冒泡排序与插入排序

    2007年，时任参议员的奥巴马访问谷歌公司时，谷歌的首席执行官

    埃里克·施密特开了一个玩笑，以求职面试官的口气问了奥巴马一个问

    题：“为100万个32位整数排序，最好采用什么方法？”奥巴马诙谐一

    笑，回答道：“我认为用冒泡排序肯定是不对的。”谷歌的工程师们爆发

    出一阵欢呼。一位工程师后来回忆道：“他竟然知道冒泡排序，我一下

    子就被打动了。”

    奥巴马排除冒泡排序的回答是正确的。这个简单的直觉式算法效率

    低下，已经成为计算机科学专业的学生攻击的目标。

    假设你希望将杂乱无序的藏书按照字母顺序进行分类排序。那么你

    会很自然地想到一个方法，于是你在书架前巡视，看到有两本书颠倒了

    先后次序，就把它们调换过来(例如，将品钦的小说放在华莱士后

    面)。在将品钦放到华莱士前面之后，你继续巡视。走到书架最后端之

    后，你就会回过头来，从书架最前端重新开始。如果从头走到尾，都没

    有看到有哪两本书次序不对，就说明你完成了这项工作。

    这就是冒泡排序，它会把我们带进平方时间。有n本书放在不正确

    的位置，每次巡视书架最多可以为一本书调换位置。(也就是说，我们

    发现了一个小问题，然后完成了一个小的修正。)所以，在最坏的情况

    下，即书架上的书正好是倒序放置的，那么至少有一本书需要移动n个

    位置。因此，在最坏的情况下，n本书都需要移动最多的n个位置，就会

    得出O(n2)这个结果。[1]

    不过，这并不是一个最令人害怕的结果，比

    如，前面说过，要用洗牌的方法把一副牌理顺，就会得到O(n!)这个可怕的结果。与之相比，O(n2)并不可怕(无须运用计算机科学加

    以证明，我们也知道是这么回事)。但是，这个平方项很快就会让我们

    望而生畏。举个例子，这意味着整理5个书架所需要的时间不是整理单

    个书架的5倍，而是25倍。

    你可能会采取另外一种方法，即把所有的书都从书架上拿下来，然

    后一本一本放到合适的位置。你把第一本书放在书架中间，然后拿第二

    本书和第一本比较，根据比较结果把它插到第一本的右边或者左边。在

    放第三本书时，你先从左到右浏览书架，然后把它放到合适的位置。你

    不断重复这个过程，渐渐地所有的书都被按次序放到书架上，直到你最

    终完成这项工作。

    计算机科学家们给这种方法起了一个非常贴切的名称——“插入排

    序”。好消息是，它比冒泡排序更直观，而且名声也不是太差。坏消息

    是它实际上并不比冒泡排序快多少。每本书仍然需要一次插入，而且平

    均每次插入都需要你移动大约半个书架的距离，才能找到合适的插入位

    置。虽然在实践中插入排序比冒泡排序要快一些，但我们还是会被带进

    平方时间。为不止一个书架排序仍然是一项难以处理的任务。

    [1]其实，冒泡排序的平均运行时间并不好于这个结果。平均而言，书本与它们最终应该在

    的位置之间相差n2个位置。计算机科学家会告诉我们，将n本书分别传递n2个位置，约需要

    O(n2)次。打破平方时间的魔咒：分治算法

    看到两个完全合理的方法都会导致平方时间之后，我们不禁要问：

    真的有更快的排序方法吗？

    这个问题听起来像是一个关于生产力的问题。但是，与计算机科学

    家讨论这个问题，就会发现它更接近于空谈，类似于思考光速，时光之

    旅，超导体，或者热力学中的熵。宇宙的基本规则和极限是什么？哪些

    是可能的？哪些是允许的？计算机科学家就像粒子物理学家和宇宙学家

    一样，通过这种方式一点一滴地窥探上帝的蓝图。整理出秩序，至少需

    要付出多少努力？

    我们能否找到一种常数时间，也就是O(1)算法，无论规模大

    小，耗费的时间都不会有任何变化(就像在客人蜂拥而至之前打扫房间

    一样)？即使证实书架上的n本书已经排好序，也不可能在常数时间里

    完成，因为我们需要检查所有书的位置。因此，用常数时间完成图书分

    类排序工作其实是根本不可能的。

    线性时间O(n)呢？可不可以像在餐桌上传递一道菜那样高效，排序对象增加一倍，工作量也仅仅增加一倍？想一想上面的那些例子，就会发现很难有这样的方法。在各种情况下，n2都与你需要移动n本书

    这个事实有关，而且每次将书移动位置所需的工作量与n也成某种比例

    关系。怎么可以把大小为n、次数也为n的工作变得只剩下一个n？在冒

    泡排序中，运行时间O(n2)是因为我们需要逐本移动n本书的位置，而且每次移动时需要跨越n个位置。在插入排序中，之所以是平方时间，是因为我们需要逐本处理n本书，而且在插入之前还要将每本书与n

    本书进行比较。线性时间排序意味着每本书都需要常数时间，无须考虑

    有多少本书需要排位的问题。这好像也是不可能做到的。

    因此，我们知道我们至少可以在平方时间里完成任务，但是可能无

    法在线性时间里把所有书都排好序。我们的极限或许就在线性时间与平

    方时间之间的某个位置。在线性与平方之间，即n与n×n之间，是否可以

    找到合适的算法呢？

    答案是肯定的，而且这些算法近在眼前。

    前面说过，信息处理开始于19世纪的美国人口普查，是由赫尔曼·

    霍尔瑞斯及后来的IBM公司根据实体打孔卡排序设备开创形成的。1936

    年，IBM开始生产一系列名为“比较者”的机器，它可以将分别排序的两

    叠扑克牌合并到一起。只要两叠牌本身是排好序的，就可以在线性时间

    内，非常轻松地将它们合并到一起，并且排好序。该程序非常简单，首

    先把两叠牌最上面的那两张相互比较，将较小的那张放在新的那叠牌

    中。重复这个步骤，直到把所有牌都放好。

    1945年，约翰·冯·诺伊曼为了展示存储程序计算机的威力，编写了

    一个程序。在这个程序的最终结论中，就包含有比较的概念。为两张牌

    排序很简单，把较小的那张牌放在上面就可以了。如果有两叠牌，每叠

    包含两张排好序的牌，我们可以很容易地将这四张牌整理成排好序的一

    叠牌。重复几次，就可以整理出越来越多且排好序的牌垛。很快，你就

    可以把完整的一副牌整理得井然有序。在最后一次合并时，你可以通过

    与交错式洗牌非常相似的手法，将扑克牌整理出你需要的次序。

    这种方法现在被称作“合并排序”，是计算机科学中的传奇算法之

    一。正如1997年的一篇论文所指出的：“合并排序在排序历史中的重要

    地位与排序在计算历史中的重要地位旗鼓相当。”合并排序威力巨大，是因为它的复杂程度位于线性时间和平方时间

    之间。具体来说，O(n log n)被称为“线性对数”时间。每一次操作都

    会把有序牌叠的规模增加一倍，所以要对n张牌完全排序，你需要的操

    作次数就等于2通过自乘变成n时所需的次数，换句话说，就是以2为底

    的对数。你可以通过两次比较操作，为4张牌排序；第三次操作之后，排好序的牌就会有8张；第四次操作，16张。合并排序的分治法问世之

    后，人们很快受到启发，提出了一系列其他线性对数排序算法。把线性

    对数复杂程度说成对平方复杂程度的一个改进，远不足以体现出两者之

    间的差距。如果需要排序的项目数量与人口普查差不多，那么两者的差

    距就相当于对数据集进行29次操作和3亿次操作之间的差别。各行业在

    解决大规模排序问题时都青睐这种方法，原因就不难理解了。

    在家庭内部处理小规模排序问题时，合并排序也能找到合适的舞

    台。它之所以应用广泛，原因之一是它非常适合并行处理。如果你还在

    苦苦思索对付那个书架的办法，合并排序策略就会建议你订一个比萨，然后邀请几个朋友来分享。把书平均分配，并让每个人负责整理其中一

    堆。接着，让朋友们两两配对，把他们负责的书合并到一起。重复这个

    过程，直到最后剩下两堆书，再一次性地合并到书架上。需要注意的

    是，不要让比萨弄脏了那些书。超越比较法：比对数更好的算法

    在华盛顿州普雷斯顿镇附近有一个不起眼的工业公园，园内有许多

    不起眼的灰色入口，2011年和2013年美国国家图书馆分类排序冠军

    就“藏身”于其中一个入口的后面。一条长长的分段传送带以每分钟167

    本(每天85000本)的速度，运送图书从条形码扫描器前通过。随后，这些图书自动分流，进入投送舱门，被投送到96只不同的箱子中。

    合并排序示意图

    注：书架上有次序混乱的8本书。首先，把相邻两本书配成一对并

    排序，再通过比较将两对书合并成一组，而且这4本书的先后次序都是

    正确的。随后，通过比较将两组书全部按照正确次序放到书架上。普雷斯顿分类排序中心是世界上规模最大、效率最高的图书分类排

    序设施之一，主管单位是金县图书馆系统。金县图书馆与纽约公共图书

    馆的设施大致相仿，它们一直是竞争关系。由于势均力敌，4年来两个

    图书馆在竞争中打成平手。在2014年的最后决战打响之前，纽约图书馆

    图书运营服务部副主管萨尔瓦多·马加蒂诺说：“金县图书馆今年要打败

    我们？想都别想!”

    理论家也可以在普雷斯顿分类排序中心发现一些值得关注的东西，因为这套系统为图书排序所用的时间是O(n)，即线性时间。

    从某种非常重要的意义上看，合并排序算法给出的O(n log n)线

    性对数时间肯定是我们可以得到的最佳效果。已经有人证明，如果通过

    一系列面对面直接比较的方法对n个事物进行完全排序，比较的次数不

    可能少于O(n log n)。这是一条普世法则，是不可能违背的。

    但是，严格说来，这条法则并不能平息排序问题上的所有争议。有

    的时候我们并不需要完全排序，有的时候根本不需要逐项比较也能完成

    排序工作。正是因为有这两个原因，实践中的粗略排序速度也可以比线

    性对数时间快。桶排序算法非常漂亮地展现了这个特点，而普雷斯顿分

    类排序中心就是桶排序的一个完美实例。

    在桶排序中，排序对象按照排序类别分成若干组，类别之间更精细

    的排序问题会被留到后面解决，在分组时不予考虑。(在计算机科学

    中，“桶”这个术语仅表示一组未排序的数据，但是，金县图书馆系统等

    现实世界中最有影响力的桶排序用户则把这个表达按照字面含义来理

    解。)对于这一步骤，有人提出反对意见：如果你希望将n个对象分装

    到m个桶中，分组工作需要的时间是O(mn)，也就是说，时间一定与

    对象数量和桶数量的乘积成比例关系。但是，只要桶的数量与排序对象

    的数量相比显得比较小，大O符号就认为这个时间约等于O(n)，即线

    性时间。真正打破线性对数壁垒的关键，是了解排序对象的分布情况。如果

    桶选得不合适，排序的效果就不会太好。例如，如果所有的书都被投放

    到同一个箱子里，排序工作就没有任何进展。但是，如果桶选得非常合

    适，所有项目都被分到大小差不多的组里，就表明已经朝着完全有序前

    进了一大步(鉴于排序工作在本质上遵循“规模越大，难度越大”这条准

    则)。普雷斯顿分类排序中心的任务是按照目的地，而不是字母顺序，进行排序，因此在选桶的时候考虑的是流通统计数据。有的分支流通量

    比较大，因此他们就分配给这些分支两只箱子，有时甚至是三只箱子。

    人在完成排序工作时，如果对排序对象有类似的了解，也会对他们

    有利。为了现场观看专家的排序工作，我们前往加州大学伯克利分校的

    主图书馆和墨菲特图书馆，进行了一次实地考察。这些图书馆的书架长

    度 ......