1700496387
问题是：是否有希望做得更好？
1700496388
1700496389
几十年的研究几乎都没能很好地解决旅行推销员问题。例如，弗勒德在第一次遇到此问题后的20多年（也就是1956年）写道：“在处理这个问题时，很有可能需要采取一种完全不同的方法。事实上，可能不存在解决这个问题的通用方法，而且那些看似不可能的结果也是有价值的。”10年之后，这种情况更加糟糕。“我猜想，”杰克·埃德蒙兹写道，“对于旅行推销员问题，没有好的算法。”这些话是有预见性的。
1700496390
1700496391
1700496392
1700496393
1700496394
算法之美：指导工作与生活的算法 [:1700494176]
1700496395
算法之美：指导工作与生活的算法 定义的难度
1700496396
1700496397
20世纪60年代中期，国家标准与技术研究所的埃德蒙兹和IBM（国际商业机器公司）的艾伦·科巴姆一起定义了一个可行的解决方案。他们断言，所谓的科巴姆——埃德蒙兹论断表明：如果一种算法运行在所谓的“多项式时间”，即O（n2）、O（n3），或者n的任意次方，那么该算法应该被认为是“有效的”。如果我们知道如何使用一种有效的算法来解决问题，那么该问题就会被认为是“可处理的”。相反，我们不知道如何解决的问题，被认为是“不可处理的”。“除了最小的尺度以外，最棘手的问题是电脑无法处理的问题，无论电脑多么强大。
1700496398
1700496399
这相当于计算机科学的核心洞察力。量化一个问题的难度是可能实现的。但有些问题就是……很难。
1700496400
1700496401
旅行推销员的问题在哪里？奇怪的是，我们还不太确定。1972年，在伯克利的理查德·卡普证明了旅行推销员问题与一个有争议的边缘性问题有关联，而这个问题还没有被明确证明是可解决的（或者是不可解决的）。但到目前为止，还没有找到解决这些问题的有效方法，大多数计算机科学家认为其中没有什么可找的。因此，在20世纪50年代所设想的旅行推销员问题的“不可能解决的结果”很可能就是它最终的命运。更重要的是，许多其他的寻找最优化问题，从政治战略到公共卫生到火灾安全等，都是同样棘手的问题。
1700496402
1700496403
但是对于那些与此类问题搏斗的计算机科学家来说，这个结论并不是故事的结局。相反，它更像是对武器的召唤。认定一个问题是不可解决的，你不能只是举手投降。正如日程安排专家简·卡雷尔·伦斯特拉告诉我们的：“当问题很困难时，并不意味着你就可以忘记它，这意味着它只是处于不同的状态。即使这是一个很厉害的敌人，你还是要打这场仗。”这就是这个领域所发现的无价之宝，我们也可以从中学到：如何最好地解决那些最佳答案似乎遥不可及的问题，如何学会放松。
1700496404
1700496405
1700496406
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