@ 2017.10.10 , 10:00
8

用算法找出最省钱的路线

用算法找出最省钱的路线
credit: 123RF

推销员要走遍美国所有的主要城市,如果要求每个城市恰好访问一次,然后返回总部,怎样才能找到开销最小的行程路线?这就是著名的旅行商问题,在规划理论和数值计算科学里一般缩写为TSP(Travelling Salesman Problem)。现今学界普遍认为,TSP最优路线的算法很有可能是不存在的(计算不可行的)。不过,好消息是计算机科学家早已发现了一条相当不错的路线——开销不超过理论最低成本的1.5倍的路线。

TSP假设在两个城市之间旅行,不管从哪座城市出发,成本都是一样的。但是真实情况并非如此。例如,也许从芝加哥飞往丹佛的航班比从丹佛飞往芝加哥的航班更便宜(或需要更少的时间)。在这些条件下找到最佳旅行路线——称为不对称TSP问题——显然也是计算上不可行的。但是,与解决经典的TSP不同的是,研究人员尚不知道如何找到一条近乎最优的路线通过大量城市。或者准确地说,是直到上个月,三位计算机科学家宣布他们设计了一种在所有情况下仍然有效的近似算法之前,尚不知道。

为什么不对称TSP如此艰难?简而言之,当行程在一个方向比另一个方向更昂贵时,就有更多路线要考虑。增加难度意味着,到目前为止,用于解决不对称TSP的所有算法或用时过久或导致不可用的路径。而新算法“解决了这个长期存在的开放性问题,是第一阶段的突破,”布法罗大学的George Regan和乔治亚理工大学的Dick Lipton在名为Gödel’s Lost Letter and P=NP博客上写到。这是一个专门发布当代算法研究成果的技术性博客。

“我最开始思考这个问题是在我读博的时候,2008年,”新文章的三位作者之一Ola Svensso说。与这个问题交手七年之后,Svensso转而去解决了一个简单点的问题,将一些城市集中在一起作为一个整体城市团,并且至少访问整体团中的一个城市。找到了访问所有城市团的最优路径算法。

然后Svensso招募了他后来的合作者Jakub Tarnawski和LászlóVégh,他们帮助他开发出一种崭新的算法,在一系列城市内反复形成较小的子群组,直到确定每个群组内的最佳路线。然后使用Svensson以前的研究,将组内的路线拼接在一起,以构建完整的路线。虽然以前也有人在尝试解决不对称TSP时采用过类似的方法,但是他们都没有成功地找到可以拼接到一起的低成本路线组。

虽然该论文尚未通过同行评审,但Regan认为,它有很大几率通过计算机科学界的审查。“证明中的想法很清楚,”Regan说,“有潜在的敏感技术点……但非常扎实,很有前途,结构良好,是很好地突破。”

Svensso说,他和他的合作者计划将其论文提交给即将举行的第五十届计算理论年度研讨会,以便正式的接受同行评议。

本文译自 quantamagazine.org,由译者 majer 基于创作共用协议(BY-NC)发布。


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

4.0
赞一个 (8)

TOTAL COMMENTS: 8+1

  1. Butters
    @2 months ago
    3582087

    非对称TSP问题,早就有各种算法获得其次优解,文章完全没把这个新算法的优越性(计算量减小程度、次优解质量提高程度)体现出来。

    [21] XX [1] 回复 [0]
  2. 虫合虫合
    @2 months ago
    3582116

    有次叫了个滴滴,要等10多分钟,结果公交车到了,于是先上去坐了一段路,正好到他堵着的位置下,省了几公里😀

  3. 3582169

    记得看过个漫画,说的是TSP有三种解法,DFS的时间复杂度是O(n!),动态规划是O(n*2^n),而Amazon是O(1)。。。

    [10] XX [1] 回复 [1]
  4. 3582225

    基本没收费站,省了一大笔费用

  5. 3582337

    遗传算法不算TSP的解法么

  6. To-Butters
    @2 months ago
    3582885

    @Butters: Quanta Magazine 就是科普文章啊。光给 layman 解释 approximation ratio、metric space、polynomial-time 就得半页纸。

  7. Butters
    @2 months ago
    3582891

    @Metro: 而EMS是 O(n^n^n)

  8. 3583633

    每个字都懂系列

发表评论


24H最赞