1700496630
算法之美：指导工作与生活的算法 三部分的权衡
1700496631
1700496632
约翰·济慈
1700496633
1700496634
这让我非常惊讶，品质决定一个人的成就，尤其是在文学领域，这是莎士比亚所大量拥有的。负面能力也如此，也就是，当一个人陷入不确定、神秘、怀疑时，在事实和理性之外没有任何急躁的行为。
1700496635
1700496636
约翰·斯图亚特·密尔
1700496637
1700496638
没有绝对的确定性，但对于人类生活的目的来说，却有足够的保证。
1700496639
1700496640
计算机科学通常是一个权衡利弊的问题。例如，在我们讨论第3章的计序时，我们注意到在计序前花费的时间和在搜索时花费的时间之间的权衡。在第4章讨论缓存时，我们探讨了占用额外空间的权衡（缓存的缓存进行缓存）来节省时间。
1700496641
1700496642
时间和空间是计算机科学中最常见的权衡的根源，但是最近，关于随机算法的研究表明，还有另一种需要考虑的变量：确定性。正如哈佛大学的迈克尔·米特增马赫所说：“我们要做的是想出一个答案来节省你的时间和空间，并权衡第三个维度：错误概率。”他被要求用最喜欢的例子来权衡不确定性，他并没有犹豫。“一位同事刚才说，应该做一个饮酒游戏，每当幻灯片上出现一次这个词，你就该喝一杯，你听说过布隆过滤器吗？”
1700496643
1700496644
米特增马赫说，要理解布隆过滤器，想想像谷歌这样的搜索引擎，它要覆盖整个网络并索引每一个可能的全球资源定位器（URL）。网页包含了超过一万亿个不同的全球资源定位器，平均每个定位器的长度大约为77个字符。当搜索引擎查看某个全球资源定位器时，它如何检查页面是否已经被处理了？仅仅存储访问过的所有定位器列表将会花费巨大的空间，并且反复搜索这个列表（即使已经完全排好序）都可能会成为一场噩梦。事实上，治疗后很有可能比疾病本身更糟糕：换句话说，每次检查都确保我们不会重新索引页面，这可能比直接索引两次页面更耗时。
1700496645
1700496646
但是，如果我们只需要确保这个全球资源定位器对我们来说是新的，那会怎么样呢？这就是布隆过滤器的用武之地。以其发明者伯顿·H.布隆命名，布隆过滤器的工作原理与拉宾-米勒-素性测试非常相似：这个全球资源定位器被输入一系列的方程式，这些方程式会对“实现向量”（witness）的新奇性进行检查。（这些方程不会说“n不是质数，”而是说“我没有见过n”。）如果你可容忍的错误率仅为1%或2%，那么就将结果存储在概率数据结构中，例如像布隆过滤器，它将会为你节省大量的时间和空间。这种过滤器的用处并不仅限于搜索引擎：布隆过滤器已经附带了许多最近的网络浏览器，用来检查一些已知的恶意网站的网址，而且它们也是比特币等加密货币的重要组成部分。
1700496647
1700496648
米特增马赫说：“那些错误权衡空间的想法，我认为问题在于人们不会把它与计算联系在一起。他们认为计算机应该给你答案。所以当你在算法课上听到这个的时候，‘它应该给你一个答案，这可能不是正确答案’（我乐意认为当学生听到这个的时候，就会把注意力集中在此）。我认为，人们在自己的生活中没有意识到他们做了多少事情，并接受了这一点。”
1700496649
1700496650
1700496651
1700496652
1700496653
算法之美：指导工作与生活的算法 [:1700494186]
1700496654
算法之美：指导工作与生活的算法 山、谷和陷阱
1700496655
1700496656
理查德·肯尼
1700496657
1700496658
这条河蜿蜒曲折，因为它无法思考。
1700496659
1700496660
随机性也已被证明是解决离散优化问题的一种强大武器，比如为美国全国大学篮球联赛安排比赛日程，或者为一个旅行推销员设计最短路线。在前一章中，我们看到了松弛可以在很大程度上减少这些问题，但是随机性的策略性运用已经成为一种可论证的，甚至是更重要的技术。
1700496661
1700496662
想象一下，你正在为一次游览世界10个城市的度假做准备，你自己遇到了旅行推销员问题：你将从旧金山出发并最终回到旧金山，中途要经过西雅图、洛杉矶、纽约、布宜诺斯艾利斯、伦敦、阿姆斯特丹、哥本哈根、伊斯坦布尔、德里和京都。你可能不太担心这条路线的总长度，但你可能确实想把旅行的资金花费降到最低。首先要注意的是，尽管10个城市听起来好像不是很多，但在这里，可选择的旅游线路的数量是10的阶乘：超过350万。换句话说，并没有实际的方法可以简单地检查每一种排列方法，并最终选择价格最低的一种。但你必须做得更聪明才行。
1700496663
1700496664
这是你第一次尝试设计一个行程，你可能会想着买从旧金山出发的（假设是西雅图）最便宜的航班，然后再买从那里到其他城市（假设为洛杉矶）最便宜的机票，然后再买（到纽约）最便宜的机票，以此类推，直到你到达第十个城市，再从那里飞回旧金山。这是一个所谓的“贪婪算法”的例子，你也可以把它看作是一种“近视算法”：一种目光短浅的算法预期在每一步中获得最好的东西。在调度理论中，正如我们在第5章看到的，一个贪婪的算法（例如，总是做最简单的工作，而不考虑长远）有时这可能是一个问题所需要的。在这种情况下，对于旅行推销员问题，贪婪算法给出的解决方案可能并不可怕，但它可能与你能做的最好的选择差很远。
1700496665
1700496666
一旦你完成了基本路线设计，你可能会对一些备选方案进行测试，方法是对城市的顺序进行轻微的调整，然后看看是否能有改进。例如，如果我们先去西雅图，然后去洛杉矶，我们可以试着用相反的顺序到这些城市：先去洛杉矶，再去西雅图。在任何给定的行程中，这11段路程的顺序都是可以前后调换的。那么我们都试一试，然后用最省钱的那一种。从这里开始，我们有了一个新的行程计划，我们可以开始改变这个计划，再次寻找最好的地方改进。这是一种被称为“爬山”的算法，因为通过搜索解决方案，发现有些方案更好，有些更糟，这通常被认为像是山和谷的风景，而你的目标是到达最高的山峰。
1700496667
1700496668
最终，你会得到一个比所有排列顺序都更好的解答。不管哪两个相邻的点互换，都不会再有任何一个排序能更胜于它。就在这里，爬山停止了。这是否意味着你可能只发现了一个所谓的“局部最大值”，而不是所有可能性的全局最大值。山顶的风景有时是骗人的。你可以知道你正站在山顶上，因为四周的地都会更低。但可能会有一座更高的山，就在另一个山谷的后面，隐藏在云之后。
1700496669
1700496670
1700496671
1700496672
1700496673
“错误风景”：描述了解决方案质量如何在不同的可能性之间变化
1700496674
1700496675
想想龙虾陷阱里的龙虾：可怜的动物，它并没有意识到离开笼子就意味着要回到笼子的中心，它需要到笼子中心才能出去。龙虾陷阱只不过是由线构成的局部最大值——一种致命的局部最大值。
1700496676
1700496677
在旅行计划一例中，幸运的是，局部最大值没有那么致命，但是它们具有相同的特点。即使我们找到了一个无法通过任何细小调整来改进的解决方案，我们仍然有可能遗漏了全局最大值。真正的最佳旅行路线可能需要对旅行方案进行彻底的修整：以不同的顺序来安排整个计划路线，例如，一路向西而不是向东。如果我们想继续寻求改进，我们可能需要暂时恶化我们的解决方案。随机性提供了一种策略（实际上有好几个策略）就是这么做的。
1700496678
1700496679