美文网首页读书笔记
读书笔记《算法之美》最优停止问题

读书笔记《算法之美》最优停止问题

作者: 熙文说 | 来源:发表于2020-06-16 20:25 被阅读0次

在完全不知道信息时,如何做出最优的选择呢?数学家给出了完美答案,37%。

什么意思?就是在我们完全不知道信息时,先留出一段时间来收集信息,一旦过了这个时间,出现的比观察阶段还优秀的人,就毫不犹豫的选择他。数学家给出这个观察阶段是整个阶段的37%。这也就是所谓的“摸清情况再行动准则”。

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

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

事实证明,利用这种最优方案,我们选中最优秀申请人的概率为37%。方案本身与出现理想结果的概率正好相等,这是这类问题表现出来的令人奇怪的数学对称性。

采用最理想的方案也会有63%的失败率,这是一个令人警醒的事实。在面对秘书问题时,即使我们采取了最理想的行动方案,在大多数情况下也会遭遇失败,也就是说,大多数情况下我们都无法选中所有人选当中最优秀的那名申请人。

相关文章

  • 读书笔记《算法之美》最优停止问题

    在完全不知道信息时,如何做出最优的选择呢?数学家给出了完美答案,37%。 什么意思?就是在我们完全不知道信息时,先...

  • 《算法之美》读书笔记-如何获得平衡的生活-1

    《算法之美—指导工作与生活的算法》我的wordpress博文链接:《算法之美》读书笔记-如何获得平衡的生活-1 –...

  • 算法之美---最优停止问题(在37%处抽身而退)

    算法不仅可以指导生产,还可以用来解决生活问题 是因为找房子问题属于数学上被称作“最优停止”(optimal sto...

  • “算来算去”

    “算来算去” ——《算法之美》读书笔记 最初听到《算法之美》时,作为一个纯度百分之百的文科生是拒绝的,单算法两字就...

  • 启发式算法

    启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例...

  • 最优停止问题——理工宅的择偶算法

    一、停车场和麦田 此刻你正在电影院的地下停车场,身边坐着你今天的约会对象。你想把车停得尽量靠近电梯间,但那里的好车...

  • 卡片思想记录31

    最近看一些算法书籍,除了程序上代码的实现,生活很多东西也是一套算法, 1、最优停止问题 或者说秘书问题,一个经典的...

  • 人生的算法(一)-最优停止算法

    前面看过一本书《算法之美》,讲的是人生处处充满算法,利用算法可以更好的解决生活中的问题。比如选择,比如搜索,比如缓...

  • 简单贪心(2020-01-11)

    贪心算法是指,在对问题求解中,对问题的每一步决策都采取当前意义下最优策略的算法,即问题的整体最优性可以由局部最优性...

  • 思想 / 贪心算法

    适用贪心算法的场合 问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。这种子问题最优解被称为最优...

网友评论

    本文标题:读书笔记《算法之美》最优停止问题

    本文链接:https://www.haomeiwen.com/subject/apxdxktx.html