图片来源：Pixabay
计算机很擅长解决问题。比如像这些问题，例如从我家到美国51区怎么走最近？8675309是素数吗？一汤匙有多少茶匙？计算机都能很好地帮你解答。
但是，计算机科学家们相信一些听起来天马行空的问题，计算机永远都无法给出答案，至少是在我们的人生结束以前。这就是P对NP问题，即答案可以被快速检验的问题是否可以被快速解答。
我最喜欢的难题是旅行商问题。这个问题给定一个城市集合，问经过所有城市而后回到起点城市的最有效路径是哪一条？为了得到在现实世界中有实际意义的答案，计算机科学家们使用近似算法，这些算法不能完全解决这些问题，但又足够接近最优解，从而能在一定程度上解决实际问题。到目前为止，最好的算法是在1976年被提出的，能够保证其结果与最优解的误差最高为50%。
我也是一位研究近似算法的计算机科学家。我和合作者Anna Karlin、Shayan Oveis Gharan一起想出了一个办法去解决剩下的50%的问题。我们证明有一种特殊的近似算法，它能给这一停滞已久的研究带来一丝曙光，同时为更具实质性的进展铺平道路。
这一发现的重要性不仅仅局限于路线规划问题。任何这类难题都可以被抽象为旅行商问题。反过来，解决其中一个问题就能够解决所有问题。你可能会觉得这些难题就像是算出怎样让一群小精灵戴不同的帽子。
很难找到最佳路径
旅行商问题经常被表述为“找到最短路径”。但是，最有效率的方案在现实世界中会受到许多因素的影响，比如时间、花费和距离。
为了直观地感受该问题有多么困难，想象如下场景：有人给了你一张有100座城市的清单，以及两两城市之间航空、铁路、公路的旅行费用表。你认为你能找到游遍100座城市同时花费最少的路线吗？
可以算一算一共有多少种可能路径。如果你想要游遍这100座城市，那么可能的旅行顺序就是100的阶乘，即100×99×98……×1。这一数字比宇宙中所有原子的总数还大。
图片来源：Pixabay
够好就行
很遗憾的是，这一问题难以解决的事实无法阻碍它们出现在现实中。除了为旅行商（或者更现代一点，送货卡车）寻找最佳路径，旅行商问题还广泛存在于许多领域，例如基因组图绘制和电路板设计。
为了解决现实生活中的这类问题，实践者们做了很多人经常做的事情：找到未必是最佳但已经是足够好的解决方案。对旅行商来说，解决方案虽然比最佳路径长了几英里，但也可以接受。没人会特别在意一块电路板的加工尺寸长了一点或者Uber司机多花了几分钟才把乘客送到家。
计算机科学家们已经能接受“足够好”，并且大约50年来一直致力于研究所谓的近似算法。这些算法能被快速运行并得到结果，虽然不是最佳结果，但是可以证明它们接近最佳结果。
近似算法中的常胜将军
最早并且最著名的近似算法之一是用于解决旅行商问题的Christofides-Serdyukov算法。20世纪70代，Nicos Christofides和Anatoliy Serdyukov分别独立提出这一算法，但后者的工作最近才广为人知。
Christofides-Serdyukov算法相当简单，至少算法运行起来很简单。你可以把旅行商问题想象成是一个网络，每座城市就是一个节点，两两城市之间的路径就是一条边。每条边对应一定的成本，比如城市之间的旅行时间。Christofides-Serdyukov算法首先选择能够连接所有城市同时花费最小的边集。
可以证明这做起来不难：只需不断添加新城市，且满足花费最少即可，但这不是最终解。连接完所有城市后，有些城市可能会出现奇数条边，这是错误的，因为每次通过一条边进入一个城市，那么也一定会通过另一条对应的边离开它。因此，算法随后会添加成本最低的边集，使得每座城市都有偶数条边，据此产生最终路径。
这一算法运行速度快，并且产生的结果最多只会比最优解差50%。如果Christofides-Serdyukov算法给出的路径长150英里，那么最佳路径不可能短于100英里。
当然，如果无法真正知道最优解，那么也无法得知近似算法在某个具体算例中，究竟有多接近最优解；并且一旦知道了最优解，那么也没必要使用近似算法。但是，有办法能证明算法的下限是多少。举例来说，Christofides-Serdyukov算法能够保证其产生的路径最多是连接所有城市最短边集总长度的1.5倍，那么其结果最多是最优解的1.5倍。
图片来源：Pixabay
确实微小却也重要的进步
自Christofides-Serdyukov算法于1976年被提出以来，计算机科学家们根本无法对其进行改进。不过，去年夏天我和合作者们证明了存在一个特殊的算法，平均来说其产生的路径只比最优解差49.99999%。虽然我觉得写出这么多个9很惭愧（实际上后面还有很多9），但是这的确跨越了长期以来存在的50%鸿沟。
我们分析的算法与Christofides-Serdyukov算法非常相似。唯一的不同是第一步选择了连接所有城市的随机边集，平均来看像是巡回的旅行商问题。我们用这种随机性表明我们并不总是被困在和先前算法一样的地方。
虽然我们的进步很微弱，但我们希望其他的研究者能受此启发，从其他角度看待这一问题并取得进一步的成果。在一个研究领域中，类似50%的阈值通常会存在很长时间，但一旦被推翻，阈值就会更快地降低。我们最大的期望之一就是理解我们从旅行商问题中所得到的结果，同时证明这一结果能够带来更大的进步。
趋近完美
我们乐观地认为在未来几年内将能看到更多进展的另一个理由是：我们所分析的算法于2010年提出，我们认为该算法的性能比我们能够证明的要好得多。与Christofides算法不同，我们怀疑该算法可能只会比最优解差33%。
的确，比较近似算法结果和已知的最优解的实验结果表明，该算法在实践中表现优异，常常得到仅比最优解差几个百分比的结果。
目前的理论界限大约在1%，这意味着没有算法能够只比最优解差1%。理论学家们希望回答这么一个问题：我们究竟能多接近最优解？
翻译：常灏杰
审校：曾小欢
引进来源：theconversation
本文来自：betway官网
特别声明：本文转载仅仅是出于科普传播信息的需要，并不意味着代表本网站观点或证实其内容的真实性；如其他媒体、网站或个人从本网站转载使用，须保留本网站注明的“来源”，并自负版权等法律责任；作者如果不希望被转载或其它相关事宜，请与我们接洽。
[责任编辑：环球科学]
京公网安备11010502039775号
