1700494299
算法之美:指导工作与生活的算法 01 最优停止理论 如何选择停止观望的时机?
1700494300
1700494301
约翰尼斯·开普勒
1700494302
1700494303
所有的基督徒都会在结婚请柬的最前面郑重宣布,他们走进婚姻的殿堂是遵从上帝的特别安排。但是,我要站在哲学的角度,详细地探讨这个问题……
1700494304
1700494305
简·奥斯汀,《爱玛》
1700494306
1700494307
如果你觉得马丁先生是最优秀的人选,如果你觉得与他相处最为融洽,那么你还犹豫什么呢?
1700494308
1700494309
对于在中学时代就建立了恋爱关系的大一新生而言,感恩节就是一个严峻的考验:因为回家度过短短4天的假期之后,很多恋人就劳燕分飞了。大学辅导员把这个普遍现象称作“放弃火鸡”。
1700494310
1700494311
大一新生布莱恩就面临着这个问题。他中学时的女友在另外一所大学,天各一方的两个人不仅需要解决空间距离造成的麻烦,还需要认真思考一个问题:他们两人之间的感情到底有多深?他们从来没有考虑过这个具有哲学深度的问题。由于没有类似的感情可以参考,他们无从回答这个问题。于是,焦虑不安的布莱恩找到辅导员,向她寻求帮助。辅导员知道这是新生经常遭遇的一个典型难题,所以她用一种极其冷淡的语气给出了自己的建议:“先收集一些数据吧。”
1700494312
1700494313
显而易见,在连续性单配偶的生活方式中,人们不可避免地会遇到一个非常重要的问题:接触多少人之后,才可以确定自己的理想伴侣?如果在收集数据的过程中与自己的“真命天子”失之交臂,那该怎么办?这似乎成了感情问题上无解的“第22条军规”。
1700494314
1700494315
我们知道,这个令大一新生忧心忡忡、牢骚满腹的“第22条军规”其实就是数学界的“最优停止问题”,它的答案其实很简单,就是37%。
1700494316
1700494317
当然,前提条件是你愿意在爱情问题上做出各种假设。
1700494318
1700494319
1700494320
1700494321
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
1700494345
算法之美:指导工作与生活的算法 37%从何而来?
1700494346
1700494347
在选择秘书时,遴选程序停止过早或者过晚都会导致不理想的结果。停止过早,最优秀的申请人还没有得到亮相的机会;停止过晚,就说明你在为一位根本不存在的更优秀的申请人保留这份工作。要取得最理想的结果,显然需要在两者之间找到最合适的平衡点,在甄选时既不可迟迟不决,又不可草草收手。
[
上一页 ]
[ :1.700494298e+09 ]
[
下一页 ]