1700496376
算法之美：指导工作与生活的算法 [:1700494175]
1700496377
算法之美：指导工作与生活的算法 最优化的难度
1700496378
1700496379
美国内战之前，亚伯拉罕·林肯在起草《解放奴隶宣言》或发表葛底斯堡演说之前，在伊利诺伊州的斯普林菲尔德当过一段时间的“草原律师”，他每年都要去第八巡回审判庭两次，这样坚持了16年。作为一名巡回律师，这意味着要在14个不同郡县的城镇里进行巡回审理，在数周内要骑行数百英里。规划这些线路带来了一个自然的挑战：如何在尽可能少的英里数内到达所有要去的城镇，而不重复经过任何一个城镇。
1700496380
1700496381
这是一个数学家和计算机科学家所熟知的“约束优化”问题：如何找到一组变量的最佳排列，并给出特定的规则和记分法。事实上，这是最著名的优化问题。如果它在19世纪被研究过，它可能会被称为“草原律师问题”，如果它在20世纪初出现的话，它可能会被戏称为“投递无人机问题”。但就像秘书问题一样，它出现在20世纪中期，一个明确的名称是“旅行推销员问题”。
1700496382
1700496383
路线规划问题直到20世纪30年代才得到数学界的关注，但后来发展迅猛。数学家卡尔·门格尔在1930年谈到了“邮政信使问题”，他指出，没有比直接简单地尝试每一种可能性更容易的解决办法了。哈斯勒·惠特尼在1934年的普林斯顿大学演讲中提出了这个问题，当时数学家梅里尔·弗勒德（你可能记得第1章中所提到的，他也被认为是第一个提出解决秘书问题方法的人）已经开始思考这个问题了。20世纪40年代，当弗勒德搬到加州时，他把它介绍给兰德研究所的同事，这个问题的标志性名字最早出现在数学家茱莉亚·鲁宾逊1949年发表的论文中。当这个问题席卷数学圈时，它似乎并不容易普及。虽然许多当时最伟大的人都痴迷于它，但似乎没有人能够真正在这方面取得进展。
1700496384
1700496385
在旅行推销员这一例子中，问题不在于电脑（或数学家）是否能找到最短的路径：理论上，一个人可以简单地列出并测量所有的可能性。更确切地说，问题在于随着城镇数量的增加，连接它们的可能路线也会越来越多。路线仅仅是城镇的一个命令，所以用蛮力去一一尝试是可怕的“阶乘时间”——在计算上相当于把一副牌扔在空中从而进行分类，直到它们按顺序落到地上。
1700496386
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
