资讯
首页  >  专题  >  环球科学  >  环球科学<前沿资讯>

逼近近似算法的极限


图片来源: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
本文来自:中国数字科技馆
特别声明:本文转载仅仅是出于科普传播信息的需要,并不意味着代表本网站观点或证实其内容的真实性;如其他媒体、网站或个人从本网站转载使用,须保留本网站注明的“来源”,并自负版权等法律责任;作者如果不希望被转载或其它相关事宜,请与我们接洽。
[责任编辑:环球科学]
分享到:
文章排行榜
©2011-2021 版权所有:中国数字科技馆
未经书面许可任何人不得复制或镜像
京ICP备11000850号-1 京公网安备11010502039775号
信息网络传播视听节目许可证0111611号
国家科技基础条件平台
./t20210512_1047625_taonews.html