Geek
用算法找出最省钱的路线
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 编辑发布。