《算法之美》精妙书摘

生活中很多看似复杂的问题都可以用算法解决，这本书给我们的启发是，与其浑浑噩噩地接受命运的安排，不如有点儿理性决策的精神，把决策变成一个数学问题，在这个充满不确定的时代，给咱们自己增加一点儿底气。
——万维钢

下文节摘自亚马逊《算法之美》左其盛老师所写书摘.

全书是算法入门，从生活中的各种问题说起：租房、谈恋爱、老虎机、拍电影、面试、买彩票、各种排序、找停车位、寻找新药、临床试验、奥巴马拉赞助、预估电影票房，讲数学家对这些问题的解决办法（也就是算法），一般从算法的由来开始说起，到现在的实际应用情况，还有各种变化与争议，比较有意思。

租房与谈恋爱在书中都被归入“最优停止”问题，算法的答案是在37%的时候做选择。细节可以看书。

涉及到一些技术细节，我估计高中毕业就能看明白。

我认为全书的内容还是比较有帮助的，比鸡汤类读物要有用一个数量级。

以下是书中一些内容的摘抄，#号后面是kindle电子版中的页码，【】中是我根据上下文补充的信息：

1：如果你希望选中最合适公寓的可能性达到最大，那么在看前37%的房子时不要做出任何决定（如果你准备花一个月的时间挑选房子，那么在前11天不要做出决定）。#145

2：我们知道这个答案，是因为找房子问题属于数学上被称作“最优停止”（optimalstopping）的一类问题。37%法则明确了解决这些问题的一系列简单步骤（计算机科学称之为“算法”）。#150

3：舒普指出，当停车位占用率从90%升至95%时，尽管仅多停了5%的车，但是大家寻找停车位的时间就会翻一番。#526

4：事实证明，探索与利用的取舍问题在网页设计与临床试验（以及其他领域）中占有核心地位——正常情况下，这两个名词不会出现在同一个句子中。#688

5：《经济学人》杂志指出：“在成本上升、收益下降的双重压力下，大型电影公司的应对之策是制作续集、前传或者邀请名演员担纲主演，因为他们相信这些电影肯定会火起来。”换句话说，在被淘汰出局之前，他们正争分夺秒，在他们发现的最容易吐钱的“老虎机”上进行赌博游戏。#727

6：基廷斯把这个问题【制药公司筛选药品】变成了尽可能简单的形式：有多个可选方案，每个可选方案得到回报的概率不同，可分配的精力（金钱或时间）是确定的。于是，这个问题变成了多臂老虎机问题的另外一个化身。

7：西罗克在奥巴马捐赠页面上完成的A/B测试反映了一些问题。对于第一次访问竞选网站的用户，“捐赠并领取礼物”按钮取得了最好的成绩，即使把发放礼物的成本剔除之后，仍然效果最佳。#906

8：优化网站配置的实验会造成成千上万美元的影响，但是在临床试验中，寻找最有效治疗方案的实验直接关乎病人的生死。越来越多的医生和统计人员认为我们的做法是不正确的。他们主张，我们应该把医疗方案选择问题视为多臂老虎机问题，在实验正在进行的同时努力寻找更好的治疗方法。#967

9：1969年，马文·泽伦（现在是哈佛大学的一名生物统计学家）建议采用“自适应性”试验。他提出的一个建议是随机化“胜者优先”算法——另外一个版本的赢留输变算法。根据这个算法，使用某个特定治疗方案的可能性随着每次成功治愈有所增加，反之则会减少。#969

10：也就是说，我们在招聘秘书时会过早地递出橄榄枝，但是在放弃新航空公司这个方面，我们的决定又往往来得过晚。#1046

11：探索者为了获得知识，付出的代价是心情愉悦。我们已经知道，因为意外惊喜有可能带给我们多倍补偿，所以基廷斯指数和上限置信区间都夸大了对未知选择方案吸引力的期望值。但是，与此同时，这也意味着在大多数情况下，探索必然会让人失望。#1126

12：这种方法现在被称作“合并排序”，是计算机科学中的传奇算法之一。正如1997年的一篇论文所指出的：“合并排序在排序历史中的重要地位与排序在计算历史中的重要地位旗鼓相当。”#1312

13：一些动物很幸运，也建立了非常明确的优势等级。诺依曼说：“比如说鱼。它们的关系就非常简单，大鱼居于优势地位。”正因为简单，所以鱼类可以和平相处。与鸡和灵长类动物不同，鱼可以在不流血的情况下建立秩序。#1595

14：在直接应用之外，约翰逊的研究还揭示了更深层次的两点内容：第一，时序安排可以通过算法表达；第二，存在最优时序安排方案。这引发了一项庞大的研究，为大量假定工厂中不同数量和种类的机器运行提供策略。#2026

15：【1997年】当喷气推进实验室团队的工程师将探路者号的这一问题识别为优先级反转的情况后，他们立即编写了一个修正代码，并将新代码数传送到百万英里之外的探路者号上。他们穿越太阳系发射的解决方案是什么呢？那就是优先级继承。#2147

16：事实证明，即使你不知道什么时候会开始工作，最早到期日和最短加工时间仍然是最佳的策略，这能够保证你在面对不确定性时表现出最佳状态（平均来说）。#2227

17：事实上，如果买n张彩票共w张中奖，那么中奖率就是中奖数加1，除以所购买的数目加2，即(w+1)/(n+2)。这种令人难以置信的简单的方法估计概率的简单方法被称为拉普拉斯定律，它很容易就能适用于任何你需要通过历史事件来评估概率的情况。#2459

18：戈特看到柏林墙时已经建成8年了，所以他最好的猜测是，它将再存在8年。（最终，这个数字是20年。）这个简单的推理，被戈特称为哥白尼原则，它可以得出一个简单的算法，能为各类事件做出预测判断。#2515

19：20世纪20年代中期，贝叶斯统计学家哈罗德·杰佛利曾考虑仅仅通过一辆城市有轨电车的序号来确定一个城市有轨电车的数量，并得出了相同的答案：该数字的双倍。#2551

20：在第二次世界大战期间，同盟国试图估计由德国制造的坦克数量。他们通过所捕获的坦克的序列号，在纯数学估计的基础上进行预测，得出的结果是德国每月生产246辆坦克，而通过广泛的（高度危险的）空中侦察所获得的估计表明，这个数字更接近于1400。而战后，德国记录显示的真实数字是：245。#2553

21：对于任何幂律分布，贝叶斯法则表明，一个合适的预测策略就是相乘法则：将迄今观察到的数量乘以一些常数。对于无信息先验，这个常数一般是2，哥白尼预测的方法由此得来；在其他幂律的情况下，所乘的数将取决于你工作的精确分布。例如，对于电影票房，它正好是1.4。#2596

22：丹麦数学家瓦格纳·厄兰研究了这种现象，他将独立事件之间的间隔形式化并推导出带有他名字的函数：厄兰分布。这条曲线的形状不同于正态分布或幂律分布：它有一个类似翅膀的形状，峰值上升较缓，尾部下降的趋势比幂律分布得快，但比正态分布得缓。#2617

23：厄兰分布给出了第三种预测法则——相加法则：总是预测事物只会再持续一个常量。我们经常听到的“只需5分钟！#2624

24：这三个非常不同的最佳预测模式——相乘法则、平均法则和相加法则都是通过将贝叶斯法则应用到幂律、正态和厄兰分布上得出结果的。#2633

25：事实证明，人们所做的预测与贝叶斯法则所得出的预测非常接近。直觉上，人们做出不同类型的预测也是遵循在现实世界中的不同分布——幂律、正态和厄兰分布。#2665

26：对于布冯来说，推导出这个公式就已经足够了。但在1812年，皮埃尔-西蒙·拉普拉斯（也就是我们在第6章提到的英雄）指出，这个结果还有另一层含义：一个人可以仅通过针掉在纸上来估计π的值。#3273

27：但是，对这种基于类比的方法的不信任很快便会消失：在IBM公司，柯克帕特里克和盖拉特使用模拟退火算法设计出比那些专家设计的更好的芯片布局。#3556

28：从1971年开始，指数退避算法就成为阿罗哈网络成功运作的一个重要组成部分，20世纪80年代，它被应用于传输控制协议，并成为互联网的一个重要组成部分。几十年后的现在，它仍然是如此重要。#3803

29：事实上，在美国，过去的十年见证了一场悄无声息的革命的开始，这场革命让司法系统本身就能处理好对毒品犯罪者的社会监控。这场革命是由一个名为“希望”的试点项目发起的，该项目采用了阿罗哈网络的指数避退原则。而这也是一个惊人的巧合，它也始于阿罗哈网络的诞生地——檀香山。#3830

30：缓冲膨胀的感觉就像是需要在互联网上查看每一件东西，要阅读所有可能的书籍，或要看所有可能的节目。你错过了你最喜欢的连续剧的一集，然后看了一小时，一天，十年。你去度假，回到家看到一大堆信件。之前若有人敲你家的门，没人应答，他就走了。现在，当你回家时，他们已经在门外排队等待。#4011

31：令人惊讶的是，蒂姆·拉夫加登和康奈尔大学的伊娃·塔多斯在2002年证明了“自私路由”方法的调和率仅仅是4/3。也就是说，完全公开只比组织严密的完美的协调差33%。#4186

32：的确，自动驾驶汽车应该减少交通事故的数量，并且能够使汽车更紧密地往前行驶，实现这两方面都能加快交通速度。但从拥塞的角度来看，调和率只有4/3，而完美的协调意味着完全协调的通勤只能是现在的3/4。#4193

33：对于博弈理论家来说，维克瑞拍卖有很多吸引人的地方。特别是对于一个算法博弈理论家来说，这其中有一种特性尤其突出：鼓励参与者诚实。#4451(完)