1700494322
算法之美：指导工作与生活的算法 [:1700494103]
1700494323
算法之美：指导工作与生活的算法 秘书问题
1700494324
1700494325
在所有最优停止问题中，最大的难点不在于选择哪一种可选方案，而是确定自己需要考虑多少种可选方案。这些问题往往会引发不同的后果，不仅陷入爱河的人和需要租房的人必须慎重考虑，司机、房主、入室行窃者等也常常面临同样的抉择。
1700494326
1700494327
“37%法则”[1]源于所谓的“秘书问题”——最优停止问题中最著名的一类难题。秘书问题的情境与我们前面考虑过的租房难题十分相似。假设一堆人申请一个秘书岗位，而你是面试官，你的目标是从这堆申请人中遴选出最佳人选。你不知道如何给每一名申请人评分，但是可以轻松地判断哪一名申请人更加优秀。（用数学语言来表述，就是说你只能看到序数，即申请人相互比较的排名，但是无法看到基数，即在一般性评分标准下的得分。）你按照随机顺序，每次面试一名申请人。你随时可以决定将这份工作交给其中一人，而对方只能接受，于是面试工作就此结束。但是，一旦你否决其中一名申请人，就不能改变主意再回头选择他。
1700494328
1700494329
普遍认为，秘书问题第一次出现在出版物中是在1960年2月，那一期的《科学美国人》杂志在马丁·伽德纳最喜欢的栏目——“趣味数学”专栏中刊登了几个难题，其中之一就是秘书问题，不过当时没有明确地提到“秘书”这个词。但是，这个问题到底从何而来，这是一个非常神秘的谜。除了一些推测以外，初期的调查没有任何确凿的结论。随后，我们风尘仆仆地赶到斯坦福大学，查阅伽德纳的文书档案。伽德纳在20世纪中期留下来的那一盒盒书信，出乎意料地把我们的调查变成了侦探工作。阅读书信有点儿像偷听别人打电话，你只能听到通话一方所说的话，因此需要推断另一方到底说了什么。从这些回信看，大约50年前，伽德纳本人似乎正在调查秘书问题的来源。但是，看完这些书信，我们更是一头雾水了。
1700494330
1700494331
哈佛大学数学家弗雷德里克·莫斯特勒回忆说，1955年，他听同事安德烈·格里森提到过这个问题，而格里森又是从其他人那里听说的。阿尔伯塔大学的里奥·莫泽在信中说，他曾经在波音公司R.E.加斯克尔的“笔记”中看到过这个问题，而加斯克尔本人则说他是从一位同事那里听说这个问题的。罗格斯大学的罗杰·平克汉姆称，他是1955年从杜克大学数学家J.舍恩菲尔德那里第一次听说秘书问题的，他还说：“我记得，他说他是从密歇根大学的某个人那里听说的。”
1700494332
1700494333
几乎可以肯定，“密歇根大学的某个人”其实就是梅里尔·弗拉德。尽管在数学界以外几乎没有人知道弗拉德，但是他对计算机科学的影响很难被忽略。他把“旅行商问题”（我们将在第8章深入讨论）变成了一个广为人知的内容，还设计了“囚徒的困境”（参见第11章），甚至“软件”（software）一词也可能是他造出来的。1958年，他成了已知的第一个发现37%法则的人，同时他宣称，他从1949年就开始考虑这个问题了。但是，在说到最初来源时，弗拉德本人提到了另外几名数学家。
1700494334
1700494335
秘书问题是一个近乎完美的数学难题：问题本身表述简单，解题难度非常高，答案简洁明了，而影响力又足以让人产生浓厚的兴趣。因此，通过人们的口口相传，这个问题以燎原之势在20世纪50年代的数学界迅速蔓延开来。1960年，在伽德纳专栏的推波助澜之下，它又大大地激发了普通大众的想象力。至20世纪80年代，秘书问题已经变成了一个研究分支，无数人撰文讨论这个问题及与其相关的变体。
1700494336
1700494337
至于这个问题是如何与秘书产生联系的，这是一个非常有意思的过程——每种文化的社会偏爱都会对社会的形式系统产生影响。例如，在我们的心中国际象棋是中世纪欧洲人的象征，但是实际上国际象棋起源于8世纪的印度。15世纪，粗暴的“欧洲化”过程把沙阿（即国王）变成了王，维齐尔（即高官）变成了王后，而大象则成了基督教主教的形象。最优停止问题同样有多种不同化身，每种化身都是当时关注热点的某种反映。19世纪，最优停止问题的典型形式是巴洛克彩票和女性挑选求婚者的行为；20世纪初，常见的表现形式是驾车度假的人挑选宾馆、男性选择约会对象；在官僚作风盛行、男性占主导地位的20世纪中叶，最典型的最优停止问题是讨论男性老板如何挑选女性助手的问题。第一次明确提出“秘书问题”的是发表于1964年的一篇论文，自此之后，这个名称就再也没有发生变化。
1700494338
1700494339
[1]正文加粗字体在本书中指的是算法。
1700494340
1700494341
1700494342
1700494343
1700494344
算法之美：指导工作与生活的算法 [:1700494104]
1700494345
算法之美：指导工作与生活的算法 37%从何而来？
1700494346
1700494347
在选择秘书时，遴选程序停止过早或者过晚都会导致不理想的结果。停止过早，最优秀的申请人还没有得到亮相的机会；停止过晚，就说明你在为一位根本不存在的更优秀的申请人保留这份工作。要取得最理想的结果，显然需要在两者之间找到最合适的平衡点，在甄选时既不可迟迟不决，又不可草草收手。
1700494348
1700494349
如果找到最优秀申请人是你追求的唯一目标，那么在整个面试过程中，只要不是已有申请人当中的最优秀人选，你都不会接受。但是，仅仅达到“目前最佳”这个条件，还不足以说服面试官。比如说，第一名申请人毫无疑问就符合这个条件。一般而言，我们有理由相信，随着面试程序不断进行下去，出现“目前最佳”申请人的概率将不断下降。例如，第二名申请人是截至目前最优秀申请人的可能性是50%，第五名的可能性只有1/5，第六名的可能性只有1/6，以此类推。因此，随着面试工作的深入，目前为止最优秀申请人一旦出现，必然会令人眼前一亮（别忘了，根据定义，这名申请人比之前所有申请人都更加优秀），不过，这种可能性在不断降低。
1700494350
1700494351
所以说，看到第一个目前最优秀申请人就欣然接受（也就是说，面试第一名申请人之后就结束面试程序），显然是过于草率了。在一共有100名申请人时，也不能因为第二名申请人比第一名申请人更优秀就迫不及待地选择他，因为这种做法同样有些操之过急。那么，我们到底该怎么办？
1700494352
1700494353
凭直觉，我们可以找到几种应对的办法。例如，当第三次（或者第四次）出现胜过前面所有的申请人时，就把工作机会交给他。或者，在连续多个申请人都不理想的情况下，一旦出现一名目前为止最优秀的人选，就毫不犹豫地接受他。
1700494354
1700494355
但是，事实证明，所有这些相对来说似乎有道理的策略都算不上是最明智的做法。事实上，效果最佳的做法是接受所谓的“摸清情况再行动准则”（look-then-leap rule）：事先设定一个“观察”期，在这段时间里，无论人选多么优秀，都不要接受他（也就是说，你的任务就是考察目标，收集数据）。“观察”期结束之后，就进入了“行动”期。此时，一旦出现令之前最优秀申请人相形见绌的人选，就立即出手，再也不要犹豫了。
1700494356
1700494357
考虑申请人数极少时的秘书问题，“摸清情况再行动准则”就会自动显露出来。如果只有一名申请人，这个问题就非常简单——接受她的申请！如果有两名申请人，无论你如何选择，你成功选到优秀人选的概率都是50%。你可以接受第一名申请人（此时，她是半程最优秀申请人），或者拒绝她，而拒绝第一名申请人就意味着接受第二名申请人（她也是半程最优秀申请人）。
1700494358
1700494359
如果有第三名申请人，情况就一下子变得有意思了。如果随机选择一名申请人，得到理想结果的概率是1/3，也就是33%。有两名申请人时，我们没有办法取得比碰运气更好的结果。那么，在有三名申请人时，会怎么样？事实证明，我们可以取得更理想的结果，而其中的关键就在第二场面试。在面试第一名申请人时，我们没有任何信息——她肯定是目前最优秀的申请人。在面试第三名申请人时，我们没有任何能动性——我们只能将工作机会交给这名申请人，因为我们已经拒绝了其他人的申请。但是，在面试第二名申请人时，我们既掌握了一些信息，又有一定的能动性——我们知道她与第一名申请人相比孰优孰劣，同时我们既可以接受她，也可以拒绝她。如果她比第一名申请人优秀，我们接受她，反之就拒绝她，那么会产生什么样的结果？事实上，在有三名申请人时，这是最理想的方案。令人吃惊的是，在有三名申请人时采用这个方法，与有两名申请人时选择半程最优秀人选的方法相比，效果不相上下。[1]
1700494360
1700494361
在有4名申请人时，穷举所有可能的情况之后就会发现，我们仍然应该在面试第二名申请人时采取行动；如果一共有5名申请人，我们应该等到面试第三名申请人时才采取行动。
1700494362
1700494363
随着申请人数不断增加，观察与行动之间的分界线正好处在全部申请人37%的位置，从而得出了37%法则：在考察前37%[2]的申请人时，不要接受任何人的申请；然后，只要任何一名申请人比前面所有人选都优秀，就要毫不犹豫地选择他。
1700494364
1700494365
表1-1 挑选秘书的最优方案
1700494366
1700494367
1700494368
1700494369
1700494370
事实证明，利用这种最优方案，我们选中最优秀申请人的概率为37%。方案本身与出现理想结果的概率正好相等，这是这类问题表现出来的令人奇怪的数学对称性。上表列出了申请人数不同时的秘书问题最优解决方案。从中可以看出，随着申请人数不断增加，取得理想结果的概率（以及从观察期切换到行动期的时间点）在37%左右。
1700494371