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
1700496680
1700496681
1700496682
算法之美：指导工作与生活的算法 [:1700494187]
1700496683
算法之美：指导工作与生活的算法 局部最大值之外
1700496684
1700496685
其中一种方法就是用所谓的“抖动”来增大爬山算法。如果你看起来像是被卡住了，那就把它混合起来。做一些随机的小调整（即使它们的情况更糟），然后再回到爬山算法，看看你最后是不是在一个更高的山顶上。
1700496686
1700496687
另一种方法是，当我们达到一个局部最大值时，要完全地打乱我们的解决方案，然后从这个随机的新起点重新开始。这种算法被称为“随机重复爬山法”，或者，更鲜明的叫法是“猎枪爬山法”。他说：“当一个问题中遇到很多局部最大值时，这一策略被证明非常有效。例如，计算机科学家在尝试破译密码时使用了这种方法，因为有很多方法可以解密一条看起来很有用的消息，但最终无疾而终。在解密过程中，有一段看起来接近于合理的文本并不意味着你肯定是在正确的轨道上。因此，有时最好不要过于依赖一个既定的初始方向，而只是从头开始。
1700496688
1700496689
但还有第三种方法：当你用于某个问题时，不要变成全量的随机性，每次你做决定时都要使用一点儿随机性。这是由洛斯阿拉莫斯的团队开发出来的一种技术，它采用了蒙特卡罗法，被称为“梅特罗波利斯算法”。梅特罗波利斯算法就像爬山算法一样，都尝试在解决方案上进行不同的小规模调整，但它们有一个重要的不同之处：在任何一个给定的点上，它都有可能接受坏的调整和好的调整。
1700496690
1700496691
我们可以想象把这个应用到我们的假期计划问题上。之后，我们再次试图通过对不同城市位置上的调整来改变提出的解决方案。如果一个随机生成的结果会给我们旅行路线的调整带来改进，那么我们可以一直接受它，并继续在此基础上进行调整。但是，如果这种改变会让事情变得更糟，我们还是有机会将事情继续下去（尽管，越糟糕继续的机会就越小）。这样，我们就不会在任何地方停滞太长时间了：最终我们会尝试另一种解决方案，尽管它花费更大，同时有可能在路上提出一个新的更好的计划。
1700496692