1700496407
1700496408
算法之美：指导工作与生活的算法 [:1700494177]
1700496409
算法之美：指导工作与生活的算法 放松吧
1700496410
1700496411
伏尔泰
1700496412
1700496413
完美就是遇到优秀的敌人。
1700496414
1700496415
当别人告诉你要放松的时候，可能是因为你紧张，对要做的事情过于在意。当计算机科学家们面对一项艰巨的挑战时，他们的头脑也想放松，他们会传阅《放松方法或分散放松技巧介绍》（An Introduction to Relaxation Methods or Discrete Relaxation Techniques）一书。但是他们不会放松自己，他们只能会放松问题本身。
1700496416
1700496417
在计算机科学中最简单的放松形式之一就是约束松弛。在这项技术中，研究人员消除了一些问题的约束，并着手解决他们希望得到解决的问题。然后，在他们取得一定的进展之后，他们试图再将约束添加进去。也就是说，在把问题带回现实之前，他们会让问题暂时更容易处理。
1700496418
1700496419
例如，你可以让销售人员多次访问同一个城市，让他自由地来回，从而松弛旅行推销员问题。在这些宽松的规则下找到最短路径会产生所谓的“最小生成树”。（如果你喜欢的话，你也可以把最小生成树看成是连接每个城镇到至少另一个城镇所需的最少里程。以下是最短的旅行路线和最小生成树路线。）事实证明，解决这个更宽松的问题对于计算机来说基本上不需要时间。虽然最小生成树不一定能直接解决真正的概率问题，但它还是相当有用的。首先，生成树可以自由回溯，它制定的路线将永远不会比真正的解决方案路线要长，因为它必须遵循所有的规则。因此，我们可以使用轻松的问题——幻想，作为对真实的更低的约束。如果我们计算出某一组特定城镇的最小生成树距离为100英里，那我们便可以确定，旅行推销员所走的距离一定不会小于这个数。如果我们找到一条110英里长的路线，那我们可以确定它比最好的解决方案最多长10%。这样我们就能明白，我们离真正的答案有多近（即使不知道它到底是什么）。
1700496420
1700496421
更好的是，在旅行推销员的问题上，最小生成树实际上是开始寻找真正解决方案的最佳起点之一。类似这样的方法甚至可以让解决旅行推销员最大的问题成为可能——找到最短的路线，让地球上的每一个城镇都能在不到0.05%的（未知的）最佳解决方案中得到解决。
1700496422
1700496423
虽然我们大多数人都没有遇到过正式的约束松弛的算法版本，但它的基本内容对几乎所有在人生中遇到过重大问题的人来说都是很熟悉的。如果你不害怕，你会怎么做？这可能是你在指导顾问办公室或激励性研讨会上听到的话。如果你不能失败，你会怎么做？同样，在考虑工作或职业问题时，我们会问你，如果你中了彩票，你会怎么做？或者，换个策略，如果所有工作收入都一样，你会做什么？这种思想练习背后的想法正是约束松弛的过程：为了使棘手问题具有可伸缩性，为了在理想的世界中取得进展，这都可以被移植到真正的世界中。如果你不能解决你面前的问题，就去解决一个简单点儿的问题，然后看看这个解决方案是否能让你在一个成熟的问题中找到一个起点，或者一盏指路明灯。也许它可以。
1700496424
1700496425
1700496426
1700496427
1700496428
林肯1855年司法巡回最短旅行路线（上）和最小生成树路线（下）
1700496429
1700496430
松弛不能为你提供完美答案的捷径。但是计算机科学也可以量化松弛在时间和解决方案质量之间产生的比例权重。在很多情况下，这个比例是戏剧性的、没有头脑的，例如，一个答案跟一个1×10-15的完美答案相比，至少有一半好。这个道理简单而深刻：如果我们愿意接受足够接近的解决方案，那么即使是一些最严重的问题也可以用正确的技术来解决。
1700496431
1700496432
临时移除约束，如最小生成树和“如果你中了彩票会怎么办？”等例子，是最直接的算法松弛形式。但还有另外两种更微妙的松弛形式在最优化研究中反复出现，它们被证实在解决这一领域最重要、最棘手的问题时具有重要作用，例如从城市规划和疾病控制到体育竞争的培养，都有直接的现实意义。
1700496433
1700496434
1700496435
1700496436
1700496437
算法之美：指导工作与生活的算法 [:1700494178]
1700496438
算法之美：指导工作与生活的算法 无数灰色地带：持续的松弛
1700496439
1700496440
旅行推销员问题，就像梅根·贝洛斯寻找最佳座位安排的问题一样，是一种特殊的最优化问题，称为“离散优化”，即在解决方案中没有平滑的连续统一体。推销员要么到这个镇子，要么到那个镇，你要么在5号桌，要么在6号桌。两者之间没有灰色地带。
1700496441
1700496442
这样的离散优化问题就在我们身边。例如，在城市里，规划者试图把消防车放置在一个能在同样固定时间内（比如5分钟），到达区内不同住宅的地方。从数学上讲，每辆消防车都能在5分钟内从所处位置到达任何可以到达的区内住宅。挑战在于找到最小的地点集合，这样所有的房子都能被覆盖。威斯康星大学麦迪逊分校的劳拉·艾伯特·麦克莱说：“整个火灾和紧急情况领域都采用了这种覆盖模型，而且效果很好。”“这是一个很好的、很清晰的模型。”但由于一辆消防车要么存在于某个地点，要么不在这个地方，因此计算最小集就涉及离散优化。正如麦克莱所指出的，“这就是很多问题在计算上变得困难的地方，因为你不能这样做一半，那样做一半”。
1700496443
1700496444
离散优化的挑战也出现在社会环境中。想象一下，你想为你所有的朋友和熟人举办聚会，却不想花邀请信所需要的信封和邮票的钱。因此，你可以决定向几位关系好的朋友发出邀请，告诉他们“把我们认识的人都带过来”。你最理想的发现是，你的最小朋友圈认识你社交圈子里的所有人，这可以让你“舔”最少的信封，还能让每一个人都能参加。当然，这听起来似乎是为了省买邮票的几块钱，但这恰恰是政治竞选活动经理和企业营销人员想要解决的问题，即最有效地传播他们的信息。这也是流行病学家研究的问题，例如，给人口中最低数量的人接种疫苗，以保护整个社会免受传染病的威胁。
1700496445
1700496446
正如我们所指出的，离散优化对整数的要求（例如一个消防部门只可以有一辆、两辆、或三辆车在车库里，而不是两辆半或π辆消防车）使离散优化问题难以解决。事实上，消防车问题和派对邀请问题都是难以解决的：没有普遍有效的解决方案。但是，事实证明，确实存在许多有效的策略来解决这些问题的连续版本，其中任何分数或小数都是可能的解决方案。研究人员面对一个离散优化问题，可能会很羡慕地盯着这些策略，但他们可以做的还很多。他们可以试着把离散问题放宽到一个连续问题，然后看看会发生什么。
1700496447
1700496448
在邀请问题上，将其从离散优化松弛到连续优化，意味着一个解决方案可能会告诉我们向某一人发送一个1/4的邀请，问另外一个人发2/3。这到底是什么意思？很明显，这不是最初问题的答案，但是，就像最小生成树一样，它确实给了我们一个起点。有了轻松的解决方案，我们可以决定如何将这些分数转换回现实。例如，我们可以选择在必要的时候简单地把它们围起来，向每个收到“半个邀请”或以上的人发出邀请。我们也可以把这些分数当作概率来解释，例如在松弛的解决方案告诉我们要放半辆消防车的地方分别扔硬币，然后实际上，只在最后扔出硬币头像一面的地方放置消防车。在这两个例子中，随着这些分数转化为整数，在原始的离散问题中，我们便会有一个有意义的解决方案。
1700496449
1700496450
最后一步，和任何松弛方式一样，那就是问自己，与我们可能想出的最好的解决方案相比，这个解决方案有多好，我们可能会用详尽的方法检查每一个可能的答案。事实证明，对于邀请函问题，连续松弛与凑整将给我们一个容易计算的不错的解决方案：数学保证你能邀请到所有你想要邀请的人，而最多发出计算机通过直接计算所给出的最佳解决方案两倍的邀请。同样，在消防车问题上，连续松弛问题很可能很快地让我们在一个舒适的范围内得到最佳答案。
1700496451
1700496452
持续松弛并不是一颗神奇的子弹：它仍然没有给我们提供有效的方法以得到真正的最佳答案，只能得出它们的近似值。但是，提供最佳邮寄或接种方案的两倍选择仍远比未优化的选择要好。
1700496453
1700496454
1700496455
1700496456