写在前面

为什么会读这本书？

• 起因听了「声东击西」最新一期《经济学家眼里的算法之蠢和治理难题》于洋老师的推荐来看看这本书
• 工作中会涉及到一些预测算法，想从底层了解下算法到底是什么？日常生活中有哪些常见的算法思维？

读完这本书后的期待是什么？

• 回答算法是什么？
• 常见的算法有哪些？如何利用书中的算法助力自己的工作和生活？

  读后感

读书笔记

序言

算法是什么？

算法指的就是解决问题的一系列步骤，其含义远不限于计算机，存在的历史也远远长于计算机。在计算机开始使用算法之前，人类早就将算法应用到生活当中了。

算法对生活的指引

计算机科学告诉我们：不要总是考虑所有的可选方案；不必每次都追求最佳结果；偶尔犯点儿错误；放下包袱，轻装前进；有的事情可以暂时放一放；相信自己的本能，不要过多思考；放松自己；采用抛硬币的方式；要体谅，但是不能忘记；忠于自我。

顺其自然，忠于自我

今天的算法设计不仅需要借助计算机科学、数学和工程技术，还需要得到统计学、运筹学等相关领域的帮助。此外，我们不仅需要考虑计算机算法设计与人类思维活动之间的关系，还需要认真研究认知学、心理学、经济学等学科。

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

秘书问题

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

正确的做法：观察期-行动期-遇到最合适的立即停止

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

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

利用这种最优方案，选中最优秀候选人的概率是37%。申请人总数越多，最优算法理论就越有价值。的确，在大多数情况下，大海捞针都会无功而返，但是，无论“海洋”多么辽阔，最优停止理论都是最理想的工具。

表 挑选秘书的最优方案

卖房子的时机

卖房子时，我们的目标其实不是得到最有利的报价，而是通过整个过程最终获取尽可能多的钱。由于等待是有代价的，是要付出真金白银的，因此当前的有利报价比几个月之后略高一点儿的报价更有吸引力。

掌握了这些信息之后，我们就可以省略确定阈值所需的观望阶段，直接确定一个阈值。然后，我们可以忽略所有低于这个阈值的报价，直接接受第一个高于阈值的报价。诚然，如果在某个时间之前不把房子出手，我们有限的积蓄就会消耗殆尽，或者我们只想考虑数量有限的几个报价，对随后的报价不感兴趣，那么在快要达到极限时，我们当然应该降低标准。

某种程度上来说，面试谈薪资也是这个逻辑，我们的目标其实并不是说得到理想状态下的最高报价，而是首先你要确定一个阈值，随后根据自己对所提供机会的offer进行评估：如果offer的薪资部分符合预期、且做的事情符合预期，几乎就可以做出合理的决策了。

因为等待也是需要付出时间成本的

如果拒绝当前的报价，预计出现更有利报价的可能性是多少？该报价与当前报价之间的差，乘以该报价出现的可能性，乘积是否大于继续等待的成本呢？数学计算的结果清楚地表明，停止价格是等待成本的一个显函数。

这里的理论是：（期望报价-当前报价）*期望报价出现的概率-等待成本>0，理想状态下是可以算出最佳报价的，当最佳报价超过等待成本时，是不划算的。

事实上，最优停止问题的这些变种还有一个更令人吃惊的特性。前面说过，在开普勒寻觅爱情的过程中，可以“复活”之前被自己拒绝的机会是一个非常重要的条件。但是，在卖房子或者找工作时，即使我们可以重新考虑之前的报价或工作邀请，即使我们可以肯定那个报价或工作邀请仍然有效，我们也绝不应该重新考虑它。如果之前它没有达到阈值的要求，那么现在它也不会高于阈值。在拒绝那个报价或工作邀请之后，我们的付出已经成为已支付成本。因此，不要妥协，不要试图亡羊补牢。坚持住，不要回头

随时准备停止的理由

1. 现实生活不像是理论模型中的那样，人的心态是会发生变化的：在寻觅工作持续了一段时间之后，我们人类通常就会感到厌烦，即使理性的人也难以避免。但是，模型很难精确地反映出这个变化。
2. 现实生活中的大部分决策只有1次机会：把握时间、做好决策的准备

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

2、 探索与利用：最新的还是最好的？

每天，我们都要做出各种各样的决定，都要在某个非常具体的方面做出选择：是进行新的尝试，还是继续选择我们喜欢的那个？直觉告诉我们，生活就是在新鲜事物和传统事物之间、在最新的和最棒的之间、在勇于冒险和安于现状之间取得平衡。但是，就像在公寓寻租过程中所面临的观望还是行动的两难困境一样，这里也有一个问题没有得到解决：如何平衡？

这个问题实际上可以定义为「探索or利用之间的取舍」

如何利用剩余时间？

1. 是探索新事物or利用已有的认知去享受，取决于你的剩余时间有多少？如果你的剩余时间充足，那么应该去大胆地探索；反之，可以尽情利用自己的探索成果，享受剩余的时间
2. 探索还是利用由剩余时间决定，我们也可以根据这个原则来研究其他人的决策逻辑——如果服务提供者想要利用口碑来大量获利说明剩余时间不多了；反之亦然
   1. 电影续集占比大代表电影业的潜在衰落
   2. 想要APP流失用户在流失前会大量兑现，也是类似的理论

基廷斯指数

基廷斯指数以一种正式、严谨的形式，证明了在有机会对探索结果加以利用时，我们应该倾向于选择未知的新事物。有一句古老的谚语说：“邻家芳草绿。”数学可以告诉我们其中的道理。尽管我们实际上认为未知事物可能差不多，甚至有可能更差，但是它也有可能更好。球队新球员没有经过检验，但是他的价值却高于能力似乎差不多的老手（至少在赛季初如此），原因正是我们对他知之甚少。探索行为本身就有价值，因为尝试新鲜事物可以增加我们发现最佳选择的机会。因此，不仅关注当前，同时还把未来纳入我们视野的做法，可以驱动我们不断尝试新鲜事物。

基廷斯指数只有在某些强假设条件下才是最优策略。

遗憾与乐观

1、 贝佐斯谈遗憾问题：充满激情与感染力

遗憾也可能给人以巨大的动力。在杰夫·贝佐斯决定创办亚马逊网站之前，他在纽约投资公司德劭集团的工作非常安稳，待遇也十分丰厚。在西雅图创办网上书店，这个步子迈得有点儿大，因此他的老板（也就是戴维·肖）劝他要小心。贝佐斯说：

我找到一个可以帮助我轻松做出重大决定的框架，并把它称作“遗憾最少化框架”（一个书呆子气十足的名称）。我把自己想象成80岁的模样，然后开始思考：“现在回望我的一生，我要把遗憾之事的数量降到最低。”我知道在我80岁时，我不会因这次尝试而后悔，我不会后悔参与到互联网这项我认为非常重要的事业中来。我知道，哪怕我失败了，我也不会遗憾，而我可能会因为没有尝试而感到遗憾，而且这种遗憾之情将永远萦绕在我的心头。想到这里，这个决定就变得非常容易了。

2、 采用遗憾最小化算法有望减少每年新增的遗憾数量

遗憾以对数速率增加，意味着前10次拉动老虎机拉把与后面90次所造成的遗憾同样多，意味着在10年时间里，第一年留下的遗憾数量等于其余9年留下的遗憾总和。（同理，在100年时间里，前10年犯下的错误等于后90年的错误总和。）这种情况让我们多少可以找到一点儿安慰。总的来说，我们不可能指望有朝一日我们将再也没有新的遗憾。但是，如果我们采用一种遗憾最少化算法，就有望减少每年新增的遗憾数量。

3、 乐观主义是防范遗憾的最有效措施：拥抱新事物

上限置信区间算法给出的推荐意见与基廷斯指数的推荐意见应该没有多大区别，但是前者的计算难度小得多，而且无须几何贴现这个前提条件。

上限置信区间算法的成功，是对怀疑者的一个正式回应。根据这些算法给出的建议，我们应该满怀激情地结识新人，尝试新鲜事物，因为在没有相反证据的时候，我们都应该假定可以取得最好的结果。从长远看，乐观主义是防范遗憾的最有效措施。

一般而言，我们对理性的直觉认识常常来源于利用，而不是探索。当我们谈论决策过程时，我们通常只关注某个决定的即时回报——如果你把每一个决定都当作人生的最后一个决定，那么只有利用才是有意义的。但在一生中，你会做出很多决定。实际上，在做很多决定时，理性的做法是强调探索的重要性，重视新的东西而不是最好的东西，重视令人为之兴奋的东西，而不是一味追求安全，重视随机选择，而不是深思熟虑的决定。在人生早期，更应该如此。孩子们的有些想法，在我们看来是任性，但是实际上，可能比我们想象的更明智。

3、 排序：建立秩序

排序理论

• 规模越大，难度越大
  • 最大限度减少痛苦的办法是在排序时尽可能减少排序对象的数量
• 衡量算法复杂度：大O符号
  • 常数时间O(1)
  • 平方时间O(n2)
  • 阶乘时间O(n!)
  • 线性对数时间O(n·logn)
• 常见的排序算法
  • 冒泡排序（每次都从头开始比较）：效率低
  • 插入排序（从中间开始，然后比较大小）：速度比冒泡排序要快一些，但是复杂度还是高, O(n2)
  • 分治算法-合并排序：将两副牌合并之后比较排序
  • 桶排序：在桶排序中，排序对象按照排序类别分成若干组，类别之间更精细的排序问题会被留到后面解决，在分组时不予考虑。
  • 比较计数法：每个排序对象都与其他对象作比较，从而统计出比该排序对象小的对象有多少个
• 排序是搜索的准备工作
  • 如果你从来不在某些物品中搜索某个目标，那么为这些物品排序就纯粹是一种浪费。如果你从来不为某些物品排序，那么你在其中搜索的效率就会很低。
  • 随着搜索成本的下降，排序的价值也会随之降低。（为电子邮件排序是一件浪费时间的事情）
  • 有序还是混乱取决于我们如何使用信息

    计算机科学表明，混乱的危害和秩序的危害是可以量化的，他们的成本都可以用时间这个“货币”来衡量。杂乱无序可能会被认为是一种拖延的行为——把责任推给未来的自己，而且还要连本带息偿还我们不愿意提前支付的债务。但是，详细情况还要更加微妙。有时，混乱不仅仅是轻松的选择，还是一个最优选择。

• 排序与体育
  • 排位赛：对运动员进行线性排序，每个球员直接向前一位球员发起挑战，获胜交换排序；这种方式相当于是冒泡排序
  • NCAA分组淘汰赛：先让球员无序配对，之后逐轮比较；是合并排序（不是严格的合并排序）
  • 如果只是想要决出第一名，只需要用线性时间；如果想要决出严格的排序，需要耗费平方时间；体育比赛通常是在线性时间和平方时间之中取平衡，以获得时间和商业利益的最大化
• 噪声与健壮性
  • 冒泡排序的效率低，但是对抗噪声的能力比较强，远胜于合并排序等速度更快的算法；排位赛的意外失利只会让运动员下降一个位置而已
  • 合并排序的效率高，而健壮性不足；在早期出错，就像首轮淘汰赛意外失利后，不仅丢失了夺冠的希望，也会永久性地降到半数球队之后
  • 比较计数排序算法的容错能力最强

在所有已知的算法中，包括平方时间算法和其他更优秀的算法，比较计数排序是最健壮的排序算法。了解这个事实应该可以帮助体育迷们正确面对某些具体情况。如果球队没有进入季后赛，就不要怨天尤人了。采用合并排序的季后赛有运气的成分，但是采用比较计数排序的常规赛是无法碰运气的。冠军戒指也许不是那么可信，但是分区的排名货真价实。换句话说，如果一支球队在季后赛早早出局，那是运气太差。但是如果一支球队不能进入季后赛，那这就是一个严酷的事实了。失望的球队球迷可能会在运动酒吧里向他们表示同情，但是计算机科学家不会心生任何怜悯。

看到这里真的想自己写一篇文章，解释下赛制与公平性、成本收益之间的关系，真是太有趣了。

NBA的常规赛就是非常公平的，比如湖人进不了季后赛就是代表了自己很弱；但如果在季后赛中，其实只能决出总冠军，并不能说谁是第二名

• 竞争替代争斗
  • 争斗尽管更公平和客观，但是对参与者的伤害更大，理想的方式是用竞争来替代争斗，所谓竞争就是大家按照某一个共识的标准来比较，得出一个排序

    尽管我们抱怨现代社会的快节奏、高压生活把我们变成了一只只仓皇四顾的老鼠，但是，正因为现代社会以竞争取代争斗，才使人类脱颖而出，与猴子、鸡和老鼠划清了界限。

4、 缓存：忘了它吧

分级存储器体系

• 什么是缓存？就是把信息先存储在一边，要用的时候专门查这一块，而不是去整个图书馆去检索，提高信息检索效率
• 摩尔定律与内存墙：摩尔定律预测出了信息处理速度每过一段时间会翻一翻，但存储器性能无法按照这个速度提升，这就意味着会有闲置，这种现象叫做「内存墙」
  • 通过缓存机制可以缓解内存墙的问题

缓存清理机制

• 随机清理算法：将新数据插入到缓存中，随机覆盖旧数据
• 先进先出（FIFO）：最早进入缓存的数据最先被清除
• 最近最少使用（LRU）：将闲置时间最长的内容清理掉
  • 最近最少使用法的高效性得益于计算机科学家所谓的“时间局部性”：如果一个程序曾经调用过某个信息，那么在不久的将来它可能会再次调用这个信息。

    本地需求

    工程师在设计电脑硬件时，考虑的是一个微小尺度上的地理位置：速度更快的内存通常更靠近处理器，这将最大限度地减少信息传输的线路长度。

将热门文件储存在就近的位置，这样能够大幅提升信息获取效率

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

1. 最近最少使用法：当你决定物品该扔还是该留时，最近最少使用原则可能是一个有效的指导原则，其效果比先进先出原则好得多。
2. 合理利用地理位置：尽可能把物品的“缓存”建立在它们通常使用的位置附近。
3. 多层次分级存储器体系：目前，人们还没有把它变成壁橱管理的指导意见。拥有缓存可以取得一定的效果，但是建立多个缓存级别，包括从体积最小、速度最快的到体积最大、速度最慢的各种缓存，可能会有更好的效果。从你的所属物品这个角度看，你的衣柜是一级缓冲，地下室是另一级，而自助存储柜是第三个。
   1. 从实用角度来看，尽管把衣服堆在床上是一件高效的方法，但不够有格调，所以一位学者建议在床边放一个衣物架。虽然衣物架现在已经不多见了，但是它在本质上就是一个一件套壁橱，可以挂夹克、领带和裤子的复合衣架，是你的家庭缓存必备的完美物件。

自组织列表的数学计算会为我们提供一些激进的建议：你根本没有必要因为案头文件成堆而自责，因为这不是杂乱无序的标志，而是最精心设计和最有效的组织形式之一。在别人看来，这是一种没有组织的混乱局面，但是实际上，它是一个自组织混乱。把东西扔回成堆物品的顶部，是你在无法预测未来时可以采取的最有效的做法。在前一章中，我们发现，在某些情况下，花时间排序之后，效率不升反降。这里，我们同样建议，在某些情况下不需要考虑如何管理的问题，不过理由有所不同：因为你其实已经组织得很好了。

听起来很反常识，但从算法角度看，这种方式某种程度上恰恰是最高效的。

经验暴政

因此，如果随着年龄增长，你开始经历这种延迟现象，你也不必沮丧。延迟的长度可以表明你的阅历是否丰富，信息检索耗费的精力则可以检验你的知识是否渊博，从延迟发生的频率则可以看出你的组织管理是否合理，有没有将最重要的东西储存在最近的位置。

随着年龄的增长，名字等信息记不住有的时候并不是记忆衰退，也可能是信息过载导致的检索效率降低导致的。解决方法是把最重要的东西储存在最近的位置。

5、 时间调度理论：要事先行

处理时限：考虑最后时限

如果你要降低最大延迟时间，那么最佳策略就是你先从截止日期最近的任务开始，再以此类推逐渐执行。这一策略被直观地称为最早到期日原则。

最早到期日是为了更好地减少最大延迟，这就意味着，它将最大限度地减少你吃到过期食物的概率，但这也许不是从最可口这个标准来衡量的。

把事情做好

有时，最后期限并不是我们主要的考虑因素，我们只是想要把事情都做好：在尽可能少的时间里完成尽可能多的事情。

将完成时间总和最小化可以引申出一个非常简单的优化算法——最短加工时间：总是先做能最快完成的任务。

追求完成的数量并不是收益最高的时间调度算法，对事务进行优先级排序，在此基础上关注完成质量、将事情做好更重要。

面对不确定性

每接到一件新工作时，通过其将耗费的时间来对其进行重要性的划分。如果该重要性高于当前正在执行的任务，就切换到新任务，不然就坚持当前任务。

当未来充满迷雾的时候，原来你不需要日程表，只需要一个待办事项清单。

中断合并

使实时调度变得如此复杂和有趣的部分原因是，它本质上是两个完全不兼容的原则之间的协调。这两个原则被称为反应速度和吞吐量：是指你能多快地进行反应，以及你可以做多少。

….这一章的最后一节有点读不下去，略过，总的来说，这一章讲时间调度的，写的有些晦涩

6、 贝叶斯法则：预测未来

媒体不断告诉我们，我们生活在一个“大数据时代”，计算机可以筛选这数十亿的数据点并发现一些肉眼看不到的细节。但跟日常生活联系最密切的问题往往是另一种极端。我们的生活充满“小数据”，我们就像看到柏林墙的戈特一样，也就是通过一个单一的观察，做一个推论。

贝叶斯论证的关键所在：从假设的过去向前推理，并奠定了理论基础，让我们可以向后找到最大的可能性。

拉普拉斯定律

如果买n张彩票共w张中奖，那么中奖率就是中奖数加1，除以所购买的数目加2，即w+1/n+1。

贝叶斯法则与先验信念

• 贝叶斯法则：将我们先前持有的观念和我们眼前的证据结合起来
• 先验：在你看到任何数据之前，每个假设的概率都是真实可能的，这就是所谓的先验概率

• 贝叶斯法则的一个实证：哥白尼原则

  • 哥白尼原则就是用过去的经验来预测将来要发生的事情的概率（过去和未来都是50%）
  • 哥白尼原则具有明显的简单性，但也有其合理之处，它是应用贝叶斯法则并使用了所谓的无信息先验的结果
    • 无信息先验意味着对预测的时间一无所知
  • 我们给贝叶斯法则带来的先验信息越丰富，我们便能从中得到越有用的预测。（什么都不知道的时候就用哥白尼原则）

    真实世界的先验

• 世界上有两种类型的事物

  • 倾向于/围绕某种自然价值的事 → 正态分布
  • 与之相反的事 → 幂律分布
    • 大部分是低于均值的，少部分是超过的
• 良好的预测最开始要有良好的直觉，要能感觉到我们何时在处理一个正态分布，何时在处理一个幂律分布。

几种分布的预测规则

• 幂律分布
  • 对于任何幂律分布，贝叶斯法则表明，一个合适的预测策略就是相乘法则：将迄今观察到的数量乘以一些常数。对于无信息先验，这个常数一般是2，哥白尼预测的方法由此得来；在其他幂律的情况下，所乘的数将取决于你工作的精确分布。
• 正态分布
  • 当我们将正态分布作为贝叶斯法则的先验时，我们会得到一个非常不同的指导。我们会得到一个“平均”规则：使用分布的“自然”平均数作为指导
• 厄兰分布：那些不具有更大或更小可能性结束的事物，只因为他们已经持续存在了一段时间。有时候事情是简单的、不变的。
  • 相加法则：总是预测事物只会再持续一个常量

• 人们对三种分布预测结果的认知【做出预测时，只要这件事是什么分布至关重要】

  • 在幂律分布中，某个事物已经存在的时间越长，我们可以预测它继续存在的时间也就越长。因此，幂律事件让我们等待的时间越长，就会让我们更加惊奇，尤其在它发生前的一刻。一个国家、一个公司或一个机构，年复一年地变得更加强大，所以当它崩溃时总是令人震惊。
  • 在正态分布中，如果事件提前发生就会令人惊讶，因为我们期望它们达到平均水平，但当它们推迟发生时不会如此。
  • 厄兰分布：通过定义的事件无论何时发生都不会给我们带来更多或更少的意外。任何事情的状态都有可能结束，不管它已经持续了多久。

    小数据与思维

• 在我们没有良好先验的情况下，我们就无法很好地预测。

• 我们的判断背叛了我们的预期，我们的期望又背叛了我们的经验。我们对未来的计划揭示了我们生活的世界以及我们自己经历过的方方面面。

你对这个世界的认知、对某件事情的认知，决定了你对其先验信息的判断，了解越多、得到的预测则越准确。

机械复制时代的先验

正如贝叶斯法则告诉我们的，做出准确预测的最好方法就是准确地了解你所预测的事情。这就是为什么我们能很好地预测人类的寿命，但是当被问及预测法老的统治时间时却不尽如人意。

作为贝叶斯法则的一种好方法，它以正确的比例表现世界——具有充分合理的先验，并适当校准。然而，当一个物种学会使用语言时，一切就开始瓦解。我们所谈论的并不是我们所经历的事情——我们主要谈论的是有趣的事情，而这些事往往也是不寻常的

如果你想成为一个具有准确直觉的贝叶斯主义者——如果你想自然地做出准确的预测，而不必考虑什么样的预测规则是适当的，你就需要保护你的先验。相反，这可能意味着要关闭消息来源渠道。

7、 过度拟合：不要想太多

1. 若模型中包含更多的因素，从定义上来说，会更拟合我们已经现有的数据。但更好地拟合现有数据并不一定意味着会得出更好的预测结果。
   1. 单因素模型过于简单，面对曲线走向无法应对
   2. 多因素模型对于数据点过于敏感
2. 从根本上说，过度拟合就是对数据的一种偶像崇拜，产生的原因是将重心放在我们能够测量的数据而不是真正重要的问题上。
3. 生活中的过度拟合无处不在
4. 如何检验过度拟合——交叉验证
   1. 比如标准化考试中为了验证学生不是只擅长笔试，还可以通过口语测试的方式进行综合的测评
5. 如何应对过度拟合——惩罚复杂性
   1. 如果我们引入复杂性惩罚，那么更复杂的模型需要做的不仅是做得更好，更重要的是解释数据以证明其更大复杂性的合理性。计算机科学家将这个原则——使用约束来惩罚模型的复杂性，称为正则化。
   2. 套索算法
      1. 然而语言又是另一种自然的套索：复杂性受到更长时间的说话和对听众注意力时限的惩罚。商业计划被压缩到电梯营销，生活忠告只有在足够简洁易懂的情况下才能成为谚语般的智慧之语。需要记住的东西都必须经过固有的记忆套索。
   3. 对模型的终极复杂性进行处罚并不是减轻过度拟合的唯一途径。你还可以通过控制输入数据的适应速度来推动模型走向简单化。
6. 启发法：
   1. 面对现实生活的复杂性，他放弃了理性的模型，转而遵循一个简单的启发法则。但正是由于现实生活的复杂性，一个简单的启发法实际上可能是理性的解决方案。
   2. 支持启发式思想的人更喜欢简单的答案，用更少的因素，或更少的计算，这正展现出“少即是多”的效果。
7. 何时应该想得更少？——不确定性高&数据有限
   1. 当你真正处于黑暗中，最好的计划将是最简单的。当我们对预期不确定，而且得到的数据杂乱无章时，最好的办法就是用一支粗的画笔来画画，用宽大的笔触来思考。有时候，照字面意思来处理就行。
   2. 记号笔不会局限住我们。你只能画出形状、线条和盒子。这很好。你最开始应该担心的是大局。

      8、 松弛：顺其自然

      在计算机科学中最简单的放松形式之一就是约束松弛。在这项技术中，研究人员消除了一些问题的约束，并着手解决他们希望得到解决的问题。然后，在他们取得一定的进展之后，他们试图再将约束添加进去。也就是说，在把问题带回现实之前，他们会让问题暂时更容易处理。

为了使棘手问题具有可伸缩性，为了在理想的世界中取得进展，这都可以被移植到真正的世界中。如果你不能解决你面前的问题，就去解决一个简单点儿的问题，然后看看这个解决方案是否能让你在一个成熟的问题中找到一个起点，或者一盏指路明灯。也许它可以。

松弛的几种方法：

• 约束松弛，简单地消除一些约束，在回到现实之前，先在更宽松的问题上取得进展。
• 持续松弛，将离散的或二进制的选择变成连续体：当决定是选冰红茶还是柠檬水时，先想象一个50：50的“阿诺德·帕尔默”混合，然后再向上或向下延展。
• 拉格朗日松弛，把不可能的变成仅仅是惩罚，要学会扭曲规则的艺术（或打破规则，并接受后果）

  每当我们遇到一个故障时（除非我们愿意花无数时间去追求完美），难题就会要求我们不许躲避，想象更简单的版本，并首先解决这些问题。当应用正确时，这不仅是一种个人想法，也不是幻想或白日梦。这是我们取得进步的最好方法之一。

9、 随机性：何时应用随机？

首先，从爬山算法可以得知：即使你有执行坏主意的习惯，你也应该坚持执行那些好的想法。

第二，从梅特罗波利斯算法可知：你有执行一个坏主意的可能性与该想法的糟糕程度成反比。

第三，从模拟退火算法可知：你应该提前实现随机性，在完全随机的状态下迅速冷却，随着时间的推移，使用越来越少的随机性，当接近冰点时，持续的时间最长。再让自己回火（照字面意思理解）。

10、 网络：我们如何联系？

流量控制和拥塞避免

• 在AIMD算法下，任何完全接收到的数据包会让飞行中的包数不是增加一倍，而是仅仅增加一个，而丢失的数据包会导致传输速率减少一半（由此得名和式增加积式减少算法）
• 和式增加积式减少算法就可以提供一种选择，因为它是明确用来处理不稳定环境的

这一章读的比较快，内容不是特别感兴趣

11、 博弈论：别人的想法

纳什均衡

数学家分析这些游戏的目的是寻找所谓的均衡：即，这是一套双方都能遵循的策略，因为他们的对手都不愿意改变自己的游戏。它被称为均衡，因为它是稳定的，没有任何一个玩家的进一步的想法可以让他们做出不同的选择。

纳什均衡可以帮助人们预测任何一套规则或激励制度的长期稳定结果。

像石头剪刀布这样简单的游戏，随意一瞥就可以看到其中的均衡，但是我们现在很清楚，在现实世界的复杂性游戏中，我们不能想当然地认为参与者能够发现或者达到游戏的均衡。反过来，这意味着游戏的设计者不能用均衡来预测玩家的行为。

占优策略

一个占优策略避免了递归，因为它是对你对手所有可能策略的最佳反应，所以你甚至不需要麻烦自己了解他们的想法。占优策略是强有力的。

这已成为传统博弈论的主要见解之一：一组游戏玩家的均衡，所有人都玩得很理性，这对那些玩家来说可能不是最好的结果。

德扑桌上如果所有人实力相当且都非常理性，那么大部分玩家可能都无所谓获利；股票市场也类似，但这只是理想状态下。

• 调和率衡量合作（集中设计或协调的解决方案）和竞争（每个参与者都各自试图最大化利于自己的结果）之间的差距。
• 低调和率意味着，无论好坏，系统本身就会像它被精心管理的那样良好。另一方面，高调和率意味着在谨慎地协调的情况下，事情有可能会最终变好，但如果没有某种形式的干预，我们就会陷入灾难。囚犯困境的游戏显然是属于后者。不幸的是，许多这个世界必须玩的最关键的游戏也都是这样的。

世界上的大部分游戏都是高调和率的，也就是脆弱的、需要谨慎协调的。

机制设计：改变游戏

如果游戏规则促使一个坏策略产生，也许我们不应该尝试改变策略。也许我们应该试着改变游戏规则。

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

1. 在正确的环境下，一群行为完全理性、完全正确的行为者，仍然可以成为有效的无限错误信息的牺牲品。这被称为“信息瀑布”。
2. 为什么市场会出现信息瀑布：
   1. 大家关注的不是事实本身，而转向了关注其他人的决策逻辑、关注的是自己的判断是否符合共识，而不是事实。盯着对手去制定策略
   2. 当误解别人想法时就会产生瀑布反应
   3. 游戏本身的规则就非常糟糕，一旦陷入其中，可能什么也做不了

关注事实、理解游戏规则、远离不靠谱的游戏

你自己的计算

• 比「最高价拍卖」更优的「维克瑞拍卖」：鼓励参与者诚实
  • 事实上，没有比直接以你估的“真正价值”（你认为这个拍品值多少）来竞标更好的策略了。
  • 在维克瑞拍卖会上，诚实是最好的政策。
• 如果改变策略没有帮助，你可以尝试改变游戏。如果无法改变，你至少可以控制你选择玩的游戏。通往地狱的道路是由棘手的递归、糟糕的平衡和信息瀑布铺成的。寻找那些诚实充当占优策略的游戏。然后，就是做你自己。

结语：计算善意

从算法中得到的几个智慧道理：

• 37%的规则
• 区分过程与结果：尽全力遵循最好的流程，即便结果不顺心，也不应责备自己
• 鉴别问题的复杂性，在可处理的问题中寻找局部最优解