算法之美

内容简介

我们所有人的生活都受到有限空间和有限时间的限制，因此常常面临一系列难以抉择的问题。在一天或者一生的时光里，哪些事是我们应该做的，哪些是应该放弃的们对杂乱无序的容忍底线是什么的活动与熟悉并喜爱的活动之间如何平衡，才能取得令人愉快的结果些看似是人类特有的难题，其实不然，因为计算机也面临同样的问题，计算机科学家几十年来也一直在努力解决这些问题，而他们找到的解决方案可以给我们很多启发。

汤姆 · 格里菲思，加州大学伯克利分校心理学和认知科学教授，计算认知科学实验室主任。格里菲思发表过150多篇科学论文，内容涉及认知心理学、文化演进等，受到美国国家科学基金会、斯隆基金会、美国心理学会和心理环境学会等颁发的各类奖项。

本书内容

序言

假设你想租房子，正在旧金山四处寻找房源。旧金山可能是整个美国最难找房子的城市了。由于技术产业的蓬勃发展，再加上城市区划法律严格限制建造新住房，旧金山的房租已经与纽约不相上下，甚至比纽约还高。房源清单列出来几分钟，房子就会被人们一抢而空。通常情况下，只有第一个把定金支票塞到房东手里的人，才能拿到房子的钥匙。

理论上讲，认真调查、仔细斟酌是理性消费者的一大特征，但是旧金山的残酷市场并没有为他们留有权衡考虑的机会。在购物中心或者 上购物时，人们可以反复权衡再做出决定，但是将要入住旧金山的租客没有这个特权，他们必须迅速做出决定：要么舍弃其他所有可能的选择，就选定当前正在看的这套房子，要么掉头就走，再也不要回头。

简单起见，我们姑且假设，你唯一关心的就是尽最大可能增加挑中最理想公寓的机会。你的目标是把“看过的好房子被人挑走”与“还有好房子没来得及看”这两种遗憾的发生概率降至最低。于是，你立刻发现自己陷入了两难境地：如果没有衡量的标准，如何判断一套公寓是否是最合适的呢果你不先看一些公寓（这些公寓将被你放弃），又如何确定衡量标准收集的信息越多，越能在最合适的机会出现时准确地认出它，但是你已经与最合适的机会失之交臂的可能性也越高。

那么，到底该怎么办果收集信息的行为会危及结果，那么怎样才能在掌握足够多信息的基础上做出明智决定呢个令人极其为难的情境近乎于一个悖论。

在被问及此类问题时，大多数人凭直觉给出的回答可能大致如此：这需要在继续挑选与立刻下手之间达成某种平衡。也就是说，你必须先看足够多的房子，确定一个标准，然后接受符合这个标准的房子。事实上，平衡概念正是解决这类问题的关键。但是，大多数人根本无法确定这个平衡点在哪里。好消息是，这个平衡点已经被找出来了。

答案就是37%。

如果你希望选中最合适公寓的可能性达到最大，那么在看前37%的房子时不要做出任何决定（如果你准备花一个月的时间挑选房子，那么在前11天不要做出决定）。这段时间你是在为制定标准做准备，因此看房子时把银行卡放在家里吧。但是，过了这个时间点之后，你就要做好随时签约的准备（包括准备好定金等），一旦你对某套房子的满意程度超过之前看过的所有房子，就立刻下手。在继续挑选与立刻下手之间做出的这种妥协，并不仅仅是一种直觉，而是已经得到证明的最优解。

我们知道这个答案，是因为找房子问题属于数学上被称作“最优停止”（optimal stopping）的一类问题。37%法则明确了解决这些问题的一系列简单步骤（计算机科学称之为“算法”）。事实证明，找房子仅仅是最优停止问题在日常生活中的表现形式之一。在面临一连串选择时如何做出决定的难题，经常会改头换面，以不同的形式出现在我们的生活当中。在驶入停车位之前，需要绕整个停车场多少圈商业风险中何时套现脱身买房子或者停车时，何时是结束观望、做出决定的最佳时机/p>

在约会这个更加令人头疼的问题上，人们也经常要面对这样的难题。最优停止理论是一夫一妻婚姻制度催生的科学。

每天，人们都要面临最优停止问题的困扰（当然，诗人更愿意追逐的话题肯定是求婚带来的烦恼，而不是停车时的两难境地），有时甚至会因此而痛苦不堪。不过，我们大可不必如此，因为这类问题至少可以通过数学方法来解决。借助并不繁复的算法，我们不仅可以解决找房子的问题，生活中遭遇的所有最优停止问题都可以被妥善处理。

从本质上讲，我们身边经常出现因为租房子、停车、求婚而感到苦恼的人，这些人其实就是在自寻烦恼。他们需要的不是治疗师，而是一种算法。治疗师告诉他们要在冲动与多虑之间找到一个正确的、舒服的平衡点。

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

※—※—※

由于我们生活在有限的时间和空间之中，因此所有人都会面临一系列特定的问题，诸如在一天或者十年里，哪些事必须做，哪些事应当放手何在尝试新的体验与从事自己喜爱的活动中取得平衡，才能生活得惬意自在、心满意足/p>

这些问题看起来似乎都是人类特有的，其实不然。半个多世纪以来，计算机科学家苦苦思考的问题（有很多已经得到妥善解决）与这些日常难题在本质上并无区别。例如，处理器在执行用户请求时应该如何分配自己的“注意力”，才能降低费用、节省时间什么情况下应该在不同任务之间来回切换开始应该接受多少任务量何利用有限的存储资源取得最佳效果该收集更多数据，还是根据已收集的数据采取行动人类而言，如何把握今天可能不是一件易事，但是我们身边的计算机可以轻轻松松地把握每一毫秒。显然，计算机有很多值得我们借鉴的地方。

将算法与人类生活相提并论似乎是一件很奇怪的事。在很多人看来，“算法”这个词意味着神秘莫测的谋划与操作，与大数据、大政府、大企业有密切的联系，正在逐渐变成现代 会基础架构中一个越来越重要的部分。其实，算法指的就是解决问题的一系列步骤，其含义远不限于计算机，存在的历史也远远长于计算机。在计算机开始使用算法之前，人类早就将算法应用到生活当中了。

“算法”（algorithm）一词得名于波斯数学家花拉子密。公元9世纪，这位数学家写过一本书，讨论用纸笔解决数学问题的技巧。［书名为“al-Jabr wa’l-Muqabala”，其中的“al-jabr”就是后来“algebra”（代数）这个词的前身。］不过，最早的数学算法早于花拉子密。在巴格达附近出土的4000年前的苏美尔人泥板文献上，就刻有一幅长除法示意图。

但是，算法不仅限于数学。在按照食谱介绍烤面包时，食谱上的所有步骤就是一个算法。按照图样编织毛衣时，这份图样就是一个算法。使用鹿角的末端连续精确地敲打，使石器形成锋利的刃的过程（这是制作精密石器的一个关键步骤），也遵循着一个算法。从石器时代开始，算法就已经是人类生活的一部分了。

※—※—※

本书将探讨人类事务算法设计这个概念，以帮助人们更好地处理日常生活中遇到的难题。将计算机科学的研究方法应用于日常生活，可以在多个层面上产生深远的影响。首先，它可以提供切实有效的建议，帮助我们解决具体问题。例如，最优停止理论可以告诉我们何时应该小心观察，何时应该果断行动；探索-利用平衡理论教会我们如何在尝试新事物与因循守旧之间找到平衡点；排序理论可以帮我们判断出是否需要以及如何整理办公室；缓存理论可以帮助我们合理地填充橱柜；日程安排理论则可以提供合理安排时间的高招。

其次，计算机科学还为我们理解这些领域的深层次运行规则提供了一套语汇。卡尔 · 萨根指出：“与其说科学是大量知识的汇总，不如说它是一种思考方式。”即使生活中的某些情况非常复杂，我们无法进行严格的数值分析，找不到任何现成的答案，我们也可以考虑这些问题的简单化表现形式，从而得出某些直觉和概念，帮助我们理解其中的关键环节并取得进展。

从更广泛的意义上看，借助计算机科学，我们可以了解人类思想的本质和理性的意义，学会回答如何度过一生这个最古老的问题。把认知视为一种解决周围环境所造成的问题（从本质上看，都是一些计算问题）的手段，并认真地加以研究，就有可能彻底改变我们对人类理性的理解。

认为研究计算机内部运行机制能够帮助我们学会思考与决策、判断某个事物是否可信、选择行为方式的观点，在很多人看来，不仅把问题过于简单化了，而且具有误导性。即使计算机科学告诉我们应该如何思考、应该采取哪些行动，我们愿意接受吗一读讲人工智能和机器人的科幻小说就会发现，那样的生活似乎都不是我们所向往的。

之所以如此，部分原因是我们把计算机看成了机械呆板的确定性系统——这些机器借助严谨的演绎逻辑，通过穷举所有可选方案，无论花费多少时间、问题难度如何，它都可以给出完全正确的答案。事实上，在阿兰 · 图灵当时的想象中，计算机就应该是这样。这位第一个设想出计算机的人通过类比的方式给出了计算的定义，而类比的原型就是认真钻研的人类数学家——他们通过长长的计算步骤，最终得出绝对正确的答案。

因此，当人们发现现代计算机处理难题的方式与他们对计算机的认识并不一致的时候，他们也许会大吃一惊。当然，简单的算术对现代计算机而言没有任何难度。目前，计算机科学面临的最难解决的问题其实是人机对话、修复破损文件、下围棋取胜，这些问题都具有规则不明确、所需信息不全，或者需要考虑无数种可能性才可以找出正确答案的特点。研究人员已经开发出各种算法，使计算机在解决难度极大的问题时不需要完全依赖穷举计算。要解决这些来自现实世界的任务，就必须正确处理好可能性问题，利用粗略估算，在时间与精确度之间做出某种妥协。

随着计算机处理现实任务的能力不断增强，计算机算法不仅对于人类自己的生活具有借鉴意义，同时还为人们理解人类认知提供了一个更好的比较标准。在过去的一二十年里，行为经济学对人类进行了非常具体的研究，结果发现，人类是不理性的，很容易犯错误，而问题的源头在很大程度上就是大脑这个古怪而独特的硬件。这种自我贬低的认识越来越普遍，却无法解释某些令人困惑的问题。例如，在完成包括想象、语言、因果推理在内的大量认知任务时，4岁儿童的能力仍然超过成本高昂的超级计算机，这到底是什么原因/p>

从计算机科学为日常问题提供的解决方案可以看出，人类思维具有另外一种特点——人生充满了难以解决的问题。人经常犯错误，虽然这可以说明人类大脑容易出错，但是也表明这些问题具有难以解决的本质特点。通过算法来思考我们周围的世界，了解我们所面临问题的基本结构以及计算机给出的解决方案的特性，可以帮助我们真实地了解我们自己，更好地理解我们所犯的那些错误。

事实上，人类需要不断面对计算机科学所研究的一些高难度问题，在不确定性及时间有限、信息不全、情况瞬息万变等不利因素的干扰下做出决定。针对一些问题，即使最前沿的计算机科学也没能开发出永远不会犯错误的有效算法，有的情形似乎是任何算法都无法解决的。

不过，尽管有的现实问题异常复杂，人们还没有开发出完善的算法，但是一代代计算机科学家一直在与这些难题斗争，并且在这个过程中得出了深刻而独到的见解。这些来之不易的真知灼见与我们对理性的直觉认识并不一致，与数学家对周围世界的精确描述也迥然不同——数学家一心想要把这个世界变成整齐划一的线条。计算机科学告诉我们：不要总是考虑所有的可选方案；不必每次都追求最佳结果；偶尔犯点儿错误；放下包袱，轻装前进；有的事情可以暂时放一放；相信自己的本能，不要过多思考；放松自己；采用抛硬币的方式；要体谅，但是不能忘记；忠于自我。

用计算机科学的智慧指引自己的人生之路，这似乎是一条不错的建议。毕竟，与大多数建议不同的是，这条建议有据可依。

※—※—※

当初，算法设计在各学科的夹缝中找到了立足之地，它是数学与工程技术糅合而成的怪异混合体。现在，为人类设计算法的工作也面临相同的境遇——找不到一个现成的归属学科。今天的算法设计不仅需要借助计算机科学、数学和工程技术，还需要得到统计学、运筹学等相关领域的帮助。此外，我们不仅需要考虑计算机算法设计与人类思维活动之间的关系，还需要认真研究认知学、心理学、经济学等学科。

接下来，我们就将开始引领大家游览这个神秘的领域。首先，我们将讨论计算机与人类大脑都需要面对的巨大挑战：如何应对有限空间、有限时间、有限注意力、未知的未知事物、不完整的信息与不可预见的未来给我们造成的麻烦，如何镇定自若、充满自信地面对这些麻烦，如何与其他人一起，共同面对这些麻烦，我们将讨论这些难题的基本数学结构，了解计算机解决大多数难题的设计原理（有时，这些设计甚至与我们的想象背道而驰）。此外，我们还将了解人脑的工作原理，了解人脑在解决相同类型问题、应对相同限制条件时有哪些独特且密切相关的处理方式。最终，我们不仅将得到有助于解决身边问题的一系列具体建议，学会在面临最复杂人类困境时有助于我们看清其脉络结构的新方法，还可以清醒地认识到人与计算机深度融合过程中的痛苦与艰辛。此外，我们还会有一些意义更加深刻的收获：一套描述周围世界的全新语汇以及一个从全新角度了解自己的机会。

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

约翰尼斯 · 开普勒

所有的基督徒都会在结婚请柬的最前面郑重宣布，他们走进婚姻的殿堂是遵从上帝的特别安排。但是，我要站在哲学的角度，详细地探讨这个问题……

简 · 奥斯汀，《爱玛》

如果你觉得马丁先生是最优秀的人选，如果你觉得与他相处最为融洽，那么你还犹豫什么呢/p>

对于在中学时代就建立了恋爱关系的大一新生而言，感恩节就是一个严峻的考验：因为回家度过短短4天的假期之后，很多恋人就劳燕分飞了。大学辅导员把这个普遍现象称作“放弃火鸡”。

大一新生布莱恩就面临着这个问题。他中学时的女友在另外一所大学，天各一方的两个人不仅需要解决空间距离造成的麻烦，还需要认真思考一个问题：他们两人之间的感情到底有多深们从来没有考虑过这个具有哲学深度的问题。由于没有类似的感情可以参考，他们无从回答这个问题。于是，焦虑不安的布莱恩找到辅导员，向她寻求帮助。辅导员知道这是新生经常遭遇的一个典型难题，所以她用一种极其冷淡的语气给出了自己的建议：“先收集一些数据吧。”

显而易见，在连续性单配偶的生活方式中，人们不可避免地会遇到一个非常重要的问题：接触多少人之后，才可以确定自己的理想伴侣果在收集数据的过程中与自己的“真命天子”失之交臂，那该怎么办似乎成了感情问题上无解的“第22条军规”。

我们知道，这个令大一新生忧心忡忡、牢骚满腹的“第22条军规”其实就是数学界的“最优停止问题”，它的答案其实很简单，就是37%。

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

秘书问题

在所有最优停止问题中，最大的难点不在于选择哪一种可选方案，而是确定自己需要考虑多少种可选方案。这些问题往往会引发不同的后果，不仅陷入爱河的人和需要租房的人必须慎重考虑，司机、房主、入室行窃者等也常常面临同样的抉择。

“37%法则”[1]源于所谓的“秘书问题”——最优停止问题中最著名的一类难题。秘书问题的情境与我们前面考虑过的租房难题十分相似。假设一堆人申请一个秘书岗位，而你是面试官，你的目标是从这堆申请人中遴选出最佳人选。你不知道如何给每一名申请人评分，但是可以轻松地判断哪一名申请人更加优秀。（用数学语言来表述，就是说你只能看到序数，即申请人相互比较的排名，但是无法看到基数，即在一般性评分标准下的得分。）你按照随机顺序，每次面试一名申请人。你随时可以决定将这份工作交给其中一人，而对方只能接受，于是面试工作就此结束。但是，一旦你否决其中一名申请人，就不能改变主意再回头选择他。

哈佛大学数学家弗雷德里克 · 莫斯特勒回忆说，1955年，他听同事安德烈 · 格里森提到过这个问题，而格里森又是从其他人那里听说的。阿尔伯塔大学的里奥 · 莫泽在信中说，他曾经在波音公司 R. E. 加斯克尔的“笔记”中看到过这个问题，而加斯克尔本人则说他是从一位同事那里听说这个问题的。罗格斯大学的罗杰 · 平克汉姆称，他是1955年从杜克大学数学家 J. 舍恩菲尔德那里第一次听说秘书问题的，他还说：“我记得，他说他是从密歇根大学的某个人那里听说的。”

秘书问题是一个近乎完美的数学难题：问题本身表述简单，解题难度非常高，答案简洁明了，而影响力又足以让人产生浓厚的兴趣。因此，通过人们的口口相传，这个问题以燎原之势在20世纪50年代的数学界迅速蔓延开来。1960年，在伽德纳专栏的推波助澜之下，它又大大地激发了普通大众的想象力。至20世纪80年代，秘书问题已经变成了一个研究分支，无数人撰文讨论这个问题及与其相关的变体。

至于这个问题是如何与秘书产生联系的，这是一个非常有意思的过程——每种文化的 会偏爱都会对 会的形式系统产生影响。例如，在我们的心中国际象棋是中世纪欧洲人的象征，但是实际上国际象棋起源于8世纪的印度。15世纪，粗暴的“欧洲化”过程把沙阿（即国王）变成了王，维齐尔（即高官）变成了王后，而大象则成了基督教主教的形象。最优停止问题同样有多种不同化身，每种化身都是当时关注热点的某种反映。19世纪，最优停止问题的典型形式是巴洛克彩票和女性挑选求婚者的行为；20世纪初，常见的表现形式是驾车度假的人挑选宾馆、男性选择约会对象；在官僚作风盛行、男性占主导地位的20世纪中叶，最典型的最优停止问题是讨论男性老板如何挑选女性助手的问题。第一次明确提出“秘书问题”的是发表于1964年的一篇论文，自此之后，这个名称就再也没有发生变化。

37%从何而来/h3>

在选择秘书时，遴选程序停止过早或者过晚都会导致不理想的结果。停止过早，最优秀的申请人还没有得到亮相的机会；停止过晚，就说明你在为一位根本不存在的更优秀的申请人保留这份工作。要取得最理想的结果，显然需要在两者之间找到最合适的平衡点，在甄选时既不可迟迟不决，又不可草草收手。

如果找到最优秀申请人是你追求的唯一目标，那么在整个面试过程中，只要不是已有申请人当中的最优秀人选，你都不会接受。但是，仅仅达到“目前最佳”这个条件，还不足以说服面试官。比如说，第一名申请人毫无疑问就符合这个条件。一般而言，我们有理由相信，随着面试程序不断进行下去，出现“目前最佳”申请人的概率将不断下降。例如，第二名申请人是截至目前最优秀申请人的可能性是50%，第五名的可能性只有1/5，第六名的可能性只有1/6，以此类推。因此，随着面试工作的深入，目前为止最优秀申请人一旦出现，必然会令人眼前一亮（别忘了，根据定义，这名申请人比之前所有申请人都更加优秀），不过，这种可能性在不断降低。

所以说，看到第一个目前最优秀申请人就欣然接受（也就是说，面试第一名申请人之后就结束面试程序），显然是过于草率了。在一共有100名申请人时，也不能因为第二名申请人比第一名申请人更优秀就迫不及待地选择他，因为这种做法同样有些操之过急。那么，我们到底该怎么办/p>

凭直觉，我们可以找到几种应对的办法。例如，当第三次（或者第四次）出现胜过前面所有的申请人时，就把工作机会交给他。或者，在连续多个申请人都不理想的情况下，一旦出现一名目前为止最优秀的人选，就毫不犹豫地接受他。

但是，事实证明，所有这些相对来说似乎有道理的策略都算不上是最明智的做法。事实上，效果最佳的做法是接受所谓的“摸清情况再行动准则”（look-then-leap rule）：事先设定一个“观察”期，在这段时间里，无论人选多么优秀，都不要接受他（也就是说，你的任务就是考察目标，收集数据）。“观察”期结束之后，就进入了“行动”期。此时，一旦出现令之前最优秀申请人相形见绌的人选，就立即出手，再也不要犹豫了。

考虑申请人数极少时的秘书问题，“摸清情况再行动准则”就会自动显露出来。如果只有一名申请人，这个问题就非常简单——接受她的申请！如果有两名申请人，无论你如何选择，你成功选到优秀人选的概率都是50%。你可以接受第一名申请人（此时，她是半程最优秀申请人），或者拒绝她，而拒绝第一名申请人就意味着接受第二名申请人（她也是半程最优秀申请人）。

如果有第三名申请人，情况就一下子变得有意思了。如果随机选择一名申请人，得到理想结果的概率是1/3，也就是33%。有两名申请人时，我们没有办法取得比碰运气更好的结果。那么，在有三名申请人时，会怎么样实证明，我们可以取得更理想的结果，而其中的关键就在第二场面试。在面试第一名申请人时，我们没有任何信息——她肯定是目前最优秀的申请人。在面试第三名申请人时，我们没有任何能动性——我们只能将工作机会交给这名申请人，因为我们已经拒绝了其他人的申请。但是，在面试第二名申请人时，我们既掌握了一些信息，又有一定的能动性——我们知道她与第一名申请人相比孰优孰劣，同时我们既可以接受她，也可以拒绝她。如果她比第一名申请人优秀，我们接受她，反之就拒绝她，那么会产生什么样的结果实上，在有三名申请人时，这是最理想的方案。令人吃惊的是，在有三名申请人时采用这个方法，与有两名申请人时选择半程最优秀人选的方法相比，效果不相上下。[2]

在有4名申请人时，穷举所有可能的情况之后就会发现，我们仍然应该在面试第二名申请人时采取行动；如果一共有5名申请人，我们应该等到面试第三名申请人时才采取行动。

随着申请人数不断增加，观察与行动之间的分界线正好处在全部申请人37%的位置，从而得出了37%法则：在考察前37%[3]的申请人时，不要接受任何人的申请；然后，只要任何一名申请人比前面所有人选都优秀，就要毫不犹豫地选择他。

表1-1 挑选秘书的最优方案

全信息秘书问题中的最优停止阈值

因此，全信息博弈往往会产生令人意想不到，有时甚至会让人感到奇怪的结果。如果追求的目标是金钱，而不是爱情，则成功的可能性更高。在根据某种客观标准（例如收入排名情况）评判合作伙伴时，可供使用的信息比较多。如果评判标准是模糊不清的情感反应（“爱情”），则可能需要我们根据经验以及比较结果不断做出调整，同时可供使用的信息也相对较少。

当然，选择对象的“资产净值”与我们权衡的标准不一定一致。任何标准，只要可以全面反映申请者与其他人对比的情况，就会导致我们弃用摸清情况再行动准则，转而采用阈值准则，同时我们成功找出最优秀申请者的可能性也会大大增加。

此外，人们还经常修改秘书问题的其他前提条件，使之与现实生活中寻觅爱情（或挑选秘书）等难题更为相似，结果形成了更多的秘书问题变种。不过，最优停止问题给我们的启发不仅限于约会与招聘这两个方面。事实上，在租房子、找停车位、见好就收的时机选择等问题中，我们同样需要面对一个又一个的可选方案，做出最有利的选择。从一定程度上说，这些问题已经得到了解决。

卖房子的时机

只需修改经典秘书问题的两个特征，就可以从浪漫的爱情跳进不浪漫的房地产领域。在前文中，我们说过租公寓的过程属于最优停止问题，但是真的拥有房产之后，你仍然难免要与最优停止问题打交道。

假设你想卖房子。在咨询了几个房地产中介之后，你将粉刷一新、带有园林景观的房子推向市场，然后静等有意者上门。每个看房人提出有意购买时，你基本上都要做出决定，要么接受，要么拒绝。但是，拒绝是有代价的，因为在下一个有意购买者上门之前，你需要再支付一周（甚至一个月）的抵押贷款，而且下一个购买者的 价未必更高。

卖房子与全信息博弈比较相似。我们知道有意者愿意付出的具体金额，不仅可以看出谁 出的价格更高，而且可以看出彼此之间的具体差额。此外，我们还掌握有关房地产市场行情的更多信息，至少可以对预计的 价变化幅度做一个大致的预测。（有了这样的预测，就相当于掌握了上述打字测试中的信息。）两者之间的差别在于目标不同。卖房子时，我们的目标其实不是得到最有利的 价，而是通过整个过程最终获取尽可能多的钱。由于等待是有代价的，是要付出真金白银的，因此当前的有利 价比几个月之后略高一点儿的 价更有吸引力。

掌握了这些信息之后，我们就可以省略确定阈值所需的观望阶段，直接确定一个阈值。然后，我们可以忽略所有低于这个阈值的 价，直接接受第一个高于阈值的 价。诚然，如果在某个时间之前不把房子出手，我们有限的积蓄就会消耗殆尽，或者我们只想考虑数量有限的几个 价，对随后的 价不感兴趣，那么在快要达到极限时，我们当然应该降低标准。（购房者喜欢找“积极的”卖主，原因就在这里。）但是，如果没有被这两种情况逼到墙角，那么我们就可以通过成本效益分析，确定是否应该继续观望。

接下来，我们分析一种非常简单的情况：假设我们清楚 价金额的变化幅度，并且在这个变化范围内各种 价出现的可能性是相同的。只要 价不会中断（我们的积蓄也不会花完），我们就可以单纯地考虑我们对收获或损失的期望值，以决定是否继续等待更有利的交易。如果拒绝当前的 价，预计出现更有利 价的可能性是多少 价与当前 价之间的差，乘以该 价出现的可能性，乘积是否大于继续等待的成本呢学计算的结果清楚地表明，停止价格是等待成本的一个显函数。

无论你出售的是价值高达数百万美元的豪宅，还是摇摇欲坠的棚屋，对这个数学结果都不会有任何影响。你唯一需要关心的是你可能接收到的最高 价与最低 价之间的差值。输入几个具体数字，就可以看出这个算法可以提供给我们大量清楚明了的指导意见。例如，假设我们预计 价金额在400000~500000美元之间。首先，如果等待成本非常低，那么在挑选买主时我们几乎无须有任何顾忌。如果等待下一个 价的成本仅为1美元，那么为了赚取尽可能多的钱，我们可以一直等到有人愿意支付499552.79美元时才出手。少一分钱，我们都不会卖给他。如果每次等待需要付出2000美元的代价，那我们就应该等待480000美元这个 价。如果面对的是一个不景气的市场，每次等待需要耗费10000美元时，那么只要 价高于455279美元，我们就应该立刻出手。最后，假设等待成本为预计 价范围的一半（在本例中， 价变化幅度的一半就是50000美元）或更高时，那么观望对我们来说不会有任何好处，最有利的做法是直接接受第一个 价，然后立刻成交。人在屋檐下，不得不低头。

在这个问题中，阈值完全取决于搜寻成本，这也是这类问题需要注意的关键要点。下一个 价令人心动的可能性（以及搜寻成本）都不会发生任何变化，因此，无论运气如何，我们在搜寻过程中都无须降低最优停止价格。一旦确定最优停止价格之后（即使这是我们在将房子推向市场之前做出的决定），我们就再也不要有任何动摇。

如果这条无限长的街道与大城市一样，停车位占用率高达99%，只有1%的停车位是空闲的，那么在距离目的地大约70个停车位（略多于1/4英里[5]）处开始，只要看到空车位，就应该停车。但是，如果舒普的办法奏效，将占用率降低到85%左右，那么在距离目的地半个街区之前，你都无须着急停车。

我们行驶的道路大多不是笔直的，也不会是无限长的。因此，同其他最优停止问题一样，研究人员也在上述基本情况的基础上做出了各种调整。例如，他们考虑了若干不同情况，包括允许驾驶者调头、距离目的地越近停车位越少、驾驶者与目的地相同的其他驾驶者形成竞争关系等。但是，无论该问题的参数发生哪些变化，增加空闲停车位的数量都可以使我们的生活更加方便。从某种意义上讲，这是提示市政府的政策制定者：停车问题不是单纯靠增加资源（停车位）并最大化利用资源（占用）就可以解决的。停车还是一个进程（是一个最优停止问题），消耗注意力、时间、汽油，还会导致污染和拥堵等后果。合适的政策可以彻底解决这个问题。而且，适宜居住的街区周围有空的停车位，可能是街区运行良好的一个标志，这正好与我们的直觉相反。

我们问舒普，他在洛杉矶车流中穿行，前往加州大学洛杉矶分校上班的时候，他的研究是否可以为他提供优化方案。作为一名全世界顶尖的停车问题专家，他是否有什么秘密武器。

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

见好就收的时机

1997年，鲍里斯 · 别列佐夫斯基因拥有大约30亿美元的财产，被《福布斯》杂志确认为俄罗斯首富。仅仅10年前，他还是苏联科学院的一名数学家，靠工资度日。他利用在研究过程中建立的业界关系，创建了一家公司，帮助外国汽车制造商与苏联汽车制造商 AvtoVAZ 沟通交流。随后，他的公司变成了 AvtoVAZ 汽车的大型经销商，同时还通过分期付款的方法，利用卢布的恶性通货膨胀牟利。他还利用与 AvtoVAZ 的合作关系套取资金，用来购买这家汽车制造商及俄罗斯公共电视台、西伯利亚石油公司的部分股份。最终，他赚得了几十亿美元的身家，成为寡头阶层的新成员。随后，他开始参与政治。1996年，他支持鲍里斯 · 叶利钦连任；1999年，他又支持弗拉基米尔 · 普京成为叶利钦的继任者。

但是，后来别列佐夫斯基的政治态度开始转变。普京当选总统之后不久，别列佐夫斯基公开反对普京提出的旨在扩大总统权限的宪政改革。他在公开场合不断批评普京，导致他与普京的关系开始恶化。2000年10月，在有人请普京就别列佐夫斯基对他的批评发表评论时，普京说：“政府手持大棒，只需一下，就能击碎其脑壳。目前我们还没有动用大棒……一旦我们真的动怒，就将毫不犹豫地砸下去。”当年11月，别列佐夫斯基就离开了俄罗斯，再也没有回来。流亡到英国之后，别列佐夫斯基继续批评普京。

别列佐夫斯基如何做出离开俄罗斯的决定否可以通过数学方法考虑“见好就收”这条建议年前，别列佐夫斯基本人就是一名数学家，而且他研究的正好就是最优停止问题，他创作的第一本书（当然也是他的唯一一本书）全部关于秘书问题，因此他当时可能也考虑了这个问题。

人们在分析见好就收这个问题时，为它披上了好几种伪装，但是最适合别列佐夫斯基这种情况的可能应该是“窃贼问题”（向俄罗斯寡头表示歉意）。在窃贼问题中，窃贼可以实施一系列盗窃活动。他们的每次盗窃都会有收获，并且每次都有机会带着战利品顺利脱身。但是，一旦被抓住，他们就会失去之前的所有收获。窃贼希望收获最大，那么什么样的算法可以给他提供合理建议呢/p>

窃贼问题有解，对于盗窃题材的电影剧本而言不是好消息。当盗窃团队诱惑一位已经金盆洗手的老手，希望他复出并干最后一票的时候，这位狡猾的窃贼只需要认真分析那些数字就知道该怎么做了。凭直觉也可以得出结果。实施盗窃的次数应该大致等于顺利脱身的可能性除以被抓的可能性的值。如果你是一名有经验的窃贼，每次盗窃成功的可能性为90%（损失全部身家的可能性为10%），那么在盗窃9次（90÷10=9）之后，你就应该洗手不干了。如果是一名笨手笨脚、成功率只有一半的生手，情况会怎么样一次去偷盗时，你本来就身无分文，因此无须担心有任何损失，但是之后就不要再去碰运气了。

尽管别列佐夫斯基是最优停止问题方面的专家，但是他的结局仍然十分凄惨。2013年3月，一名保镖在他位于伯克郡的住所里发现了他的尸体。他死在锁着的浴室里，脖子上系着绳子。官方在尸检之后宣布他死于自杀。由于他在一系列高调的诉讼案中输给了俄罗斯对手，也失去大笔财富，因此他走上了上吊自尽这条不归路。或许他抽身而退的时间还应该更早一些，在积累几千万美元的财富之后就应该收手，而且不能介入政治。但是，遗憾的是，那不是他的做事风格。他在数学界的一位朋友里奥尼德 · 博古斯瓦夫斯基，曾经讲过别列佐夫斯基的一件往事。当时，他和别列佐夫斯基都还是年轻的研究员。他们前往莫斯科附近，准备进行湖上滑水活动。但是，他们计划使用的那条船出了故障。戴维 · 霍夫曼在他的《寡头》一书中有这样一段文字：

朋友们都跑上沙滩，点起了篝火，只有博古斯瓦夫斯基和别列佐夫斯基向船坞走去，准备修理那台发动机……三个小时之后，他们已经把发动机拆装了一遍，但是发动机仍然无法工作。尽管已经错过了聚会的大多数活动，但是别列佐夫斯基仍然坚持说，他们一定要继续尝试修理发动机。博古斯瓦夫斯基回忆说：“我们想尽办法，试图修好那台发动机。”别列佐夫斯基从来不会轻言放弃。

令人吃惊的是，在最优停止的文献资料中也曾提到过不放弃（而且是永不放弃）。有的时序决策问题似乎没有最优停止准则，尽管从我们前面讨论的大量问题看，似乎不应该出现这种情况。“要么三倍，要么赔光”的博弈游戏就是一个简单的例子。假设你带着1美元去玩这个游戏。游戏规则对轮次没有限制，但是要求你每次都要押上所有的钱，你有50%的机会赢回三倍的钱，另外50%的机会全部赔光。那么你应该参与多少轮呢管这个问题非常简单，但它没有合适的最优停止准则，因为每参加一轮游戏，你的平均收益都会略有增加。从1美元开始，你有一半机会赢回3美元，一半机会收回0美元，平均而言，第一轮结束之后，你装进口袋的现金期望值是1.5美元。那么，如果你在第一轮游戏中运气不错的话，第二轮游戏的两个可能结果就会将你刚刚赢回来的3美元变成9美元或者0美元，也就是说，第二轮的平均收益是4.5美元。数学计算结果表明，你应该一直玩下去。但是，果真如此的话，你最终必将输光所有的钱。可见，有的问题有解，反而会有损无益。

随时准备停止

斯蒂芬 · 格雷列特

我的生命只有一次。因此，如果我能做点儿善事，或者可以向人们表示善意，让我现在就做吧！别让我拖延，别让我疏忽，因为我没有第二次生命！

安妮 · 迪拉德

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

我们在前文讨论了人们在生活中遭遇停止问题的具体实例，很显然，我们大多数人每天都会遭遇这类问题，只不过表现形式各不相同。生活中最优停止问题无处不在，有时与秘书有关，有时又与未婚夫（或未婚妻）、公寓有关。因此我们难免会想到一个问题：进化、教育或者直觉到底能不能为我们提供最有效的策略/p>

乍一看，答案似乎是否定的。十几项研究已经得出了相同的结果，人们往往在更优秀申请者还没亮相之前就已经草草停止。为了更深入地了解这些研究成果，我们拜访了加州大学河滨分校的阿姆农 · 拉波波特。他在实验室里从事最优停止实验工作已有40多年了。

20世纪90年代，拉波波特与达里尔 · 希尔合作，完成了一项与经典秘书问题关系密切的研究。在这项研究中，人们需要无数次面对秘书问题，每次申请者的人数为40或者80。结果，人们找到最优秀申请者的总成功率相当不错，大约为31%，与最理想的37%相去不远。大多数人都遵循了摸清情况再行动准则，但是有超过4/5的人出现了出手过早的情况。

拉波波特告诉我们，他本人在生活中遇到最优停止问题时，都会想到这个现象。例如，在寻租公寓时，他竭力控制自己希望迅速交易的冲动。他说：“尽管我天生是一个急性子，看到第一个公寓就想租下来，但是我还是竭力控制自己。”

但是，这种不耐烦的表现说明经典秘书问题忽略了另外一个需要考虑的因素——时间。别忘了，在你寻觅秘书的全过程中，你没有秘书可用。此外，你把时间都花在面试上，自己的工作就无法完成了。

在实验室里解决秘书问题时，停止时机的选择往往过早，原因可能就在于这种成本。希尔和拉波波特认为，如果我们假设面试每名申请者的成本等于发现最优秀秘书所产生价值的1%，那么最优策略就会与实验中人们从观望阶段转变为行动阶段的时间选择正好一致。

令人难以理解的是，在希尔和拉波波特的研究中，寻觅是不需要付出任何成本的。那么，人们在实验室中的行为为什么与寻觅需要付出成本时一致呢/p>

这是因为人们认为时间成本一定是存在的，而且时间成本是在人们的真实生活中产生的，与实验如何设计没有关系。

因此，寻觅活动的“内在”时间成本（在最优停止模型中通常没有得到体现）也许可以解释人类做出的决策通常与模型的描述之间存在差异的原因。研究最优停止的科研人员尼尔 · 比尔登指出：“在寻觅工作持续了一段时间之后，我们人类通常就会感到厌烦，即使理性的人也难以避免。但是，模型很难精确地反映出这个变化。”

不过，这并不意味着最优停止问题的重要性有所降低。事实上，它的重要性不降反升，因为时间的流逝会把所有决策活动变成最优停止问题。

最优停止问题的权威教科书开宗明义地指出：“最优停止理论关注的是如何选择时机以执行特定行动的问题。”很难想出一种更好的方法，可以简明扼要地描述人类所面临的状况。显然，我们需要判断何时应该买进股票，何时应该将这些股票卖出，我们还要决定何时应该打开我们已经封藏了一段时间的葡萄酒，何时应该打断某人，何时应该亲吻某人。

这样看来，秘书问题最基本同时也最令人难以置信的前提条件——严格的连续性，即有进无退的单向行进，正好是时间自身属性的一个体现。就此而言，最优停止问题的这个显性前提正好就是使其充满活力的隐性前提。这个前提迫使我们基于还没亲眼看到的可能结果做出决定，迫使我们在采取最优策略之后仍然愿意接受非常高的失败率。我们永远没有二次选择的机会。我们有可能得到类似的选择机会，但是绝不会得到完全相同的选择机会。犹豫不决（不作为）与行为一样不可改变。困在单行线上的驾车者与空间的相互关系就是我们与第四维度的关系：我们的生命真的只有一次。

直觉告诉我们，合理的决策需要穷举所有选择，逐一权衡，然后从中找出效果最好的那个选择。但是实际上，在钟表嘀嘀嗒嗒的声音中，决策活动（或者更具一般性的思维活动）的其他方面都淡化了，进一步凸显出停止时机选择的重要性。

---

[1]正文加粗字体在本书中指的是算法。

[2]采用这个方案，最优秀申请人落选与得不到面试机会的概率分别是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）会导致挑选不够充分的问题。

[3]事实上，应该是略低于37%。准确地说，考察申请人的数学最优比例是1/e，其中 e 是复利计算中经常出现的数学常数，等于2.71828……。但是，如果你记不住 e 的12个小数位，也无须着急。只要这个比例在35%与40%之间，取得最理想结果的可能性就非常接近于最高值。

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

[5]1英里≈1.61千米。——编者注

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

03 排序 建立秩序

04 缓存 忘了它吧

05 时间调度理论 要事先行

06 贝叶斯法则 预测未来

07 过度拟合 不要想太多

08 松弛 顺其自然

09 随机性 何时应用随机

10 络 我们如何联系

11 博弈论 别人的想法

结语 计算善意

阅读全文: http://gitbook.cn/gitchat/geekbook/5b690598fa9fe34011ed8bcf

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33847 人正在系统学习中