TSP 3D之旅，穿越2,079,471颗星，距离最优距离不到0.0000074

要想让计算机界感到恐惧，只要低声说出旅行推销员问题就行了。如果我们想要找出28个城市的路线，那么在我们得到结果之前，宇宙就会消亡。

事实上，这个问题的名声如此之高，以至于在小实例上取得的进展(使用公认很酷的技术)具有新闻价值，比如最近有报道称，一款新的人工智能处理器可以解决22个城市的问题，或者一辆变形虫发现的8站之旅可能会永远改变计算的面貌。

我们的工作显然不那么奇特，但规模要大得多。与丹麦罗斯基勒大学的Keld Helsgun合作，我们的目标是通过200多万颗单独恒星的3D位置计算可能最短的旅行，这是一个基于欧空局GAIA数据发布1的点集。

从2017年10月到2019年10月，我们每周制作越来越短的3D星空之旅，采用了一系列启发式搜索技术和不断增加的计算能力。这项工作的基础是Keld'；的LKH软件包，这是一个强大的代码，用于获得TSP和相关路由问题的近似最优解。在LKH之上，我们添加了专门用于如此庞大的数据集的方法，将本地搜索和遗传算法与分解策略相结合，以允许并行计算。

搜索一直持续到去年年底，但是从2019年10月6日开始，我们没有发现解决方案的进一步改进。这就是运动图像中显示的巡视。它的总长度为28,884,352.4秒，或者，如果你愿意，也可以是94,208,157.5光年。

关键的一点是，这不是任何一条穿越星际的路线。我们的人提供了一个证据，证明它的长度，如果不是绝对最短的话，最多相差0.0000074倍。客观地说，这就像是从纽约到洛杉矶的公路旅行，保证在最佳越野驾驶的半个城市街区内。

我们的质量保证是由另一个困难的计算提供的。在过去的两年半里，我们一直在运行线性规划、割平面法，以慢慢缩小我们的解与通过点集的不可想象的许多可能的巡回中的每一次的长度下限之间的差距。我们在这里的工作建立在协和TSP求解器的基础上，再次进行了多次调整，以处理预期的大量点并允许广泛的并行计算。

我们知道没有比我们的路线短超过213.4秒的旅行了。也许对让-吕克·皮卡德来说已经足够接近了，但对缩小剩余差距的攻击可能会导致数学技术在《星际迷航》之外有广泛的应用。如果你认为你能帮上忙，我将提供50美元的赏金，让你通过重新安排穿越星际的航班，每一秒就能节省一秒。如果有更好的目标旅行，这将有助于我们的工作，所以我很高兴提供奖励，以鼓励更多的人关注这些数据集。这将有助于我们的工作，如果有的话，我会很高兴地提供奖励，以鼓励更多的人关注这些数据集。

别担心预算。凯尔德和我在去年的Kaggle比赛中赢得了17,000美元；我存了一些钱来支付任何捷径搜索者的费用。如果你想加入寻找Parsecs的行列，请查看“挑战”页面上的详细信息。

·威廉·库克(William Cook)，滑铁卢大学(University Of Waterloo)和约翰·霍普金斯大学(Johns Hopkins University)。

有关导航运动图像的指南，请单击页面右上角的I按钮。

在TSP主页和LKH网站上可以找到关于我们所采用的数学技术的大量信息的链接。

有关星形TSP实例点集的详细信息，请参见数据页面；有关更多图像，请参阅浏览页面。

这些计算是在罗斯基勒大学和滑铁卢大学的系统上进行的。支持由NSERC发现基金提供。

我们感谢迈克尔·博伊尔建议使用色调来指示恒星在我们的解决方案中出现的顺序。