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
1700496693
无论是抖动、随机重启，还是偶然的恶化，随机性对于避免局部最大值都是非常有用的。随机不仅仅是处理棘手优化问题的可行方法，在许多情况下，它是必不可少的。然而，有一些问题挥之不去。你应该使用多少随机性？何时使用？考虑到像梅特罗波利斯算法这样的策略可以无限地改变我们的行程，你怎么知道你已经完成了？对于正在研究最优化的科研人员来说，这些问题有一个惊人的确定答案将来自另一个领域。
1700496694
1700496695
1700496696
1700496697
1700496698
算法之美：指导工作与生活的算法 [:1700494188]
1700496699
算法之美：指导工作与生活的算法 模拟退火算法
1700496700
1700496701
20世纪70年代末和80年代初，斯科特·柯克帕特里克认为自己是一名物理学家，而不是计算机科学家。柯克帕特里克对统计物理学尤其感兴趣，这门学科会用随机性来解释某些自然现象，例如与退火相关的物理学内容，以及材料在加热和冷却时改变状态的方式。退火过程中最有趣的特性或许是材料冷却的速度往往会对其内部结构产生巨大的影响。柯克帕特里克解释道：
1700496702