Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming
本文在约束逻辑编程框架内提出了新的过滤算法，这些算法利用来自欧几里得坐标的几何信息，以实现对欧几里得旅行商问题及其变体（如广义旅行商问题）更强的约束传播能力和更高的计算性能。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下你是一名快递员，手里拿着一张写满停靠点的地图。你想访问每一个站点且仅访问一次，最后回到家中，但你还希望尽可能少地消耗燃油。这就是经典的“旅行商问题”（Traveling Salesperson Problem），这个谜题几十年来一直让数学家和计算机科学家感到头疼。这不仅仅关乎货运卡车；它还涉及从智能车辆路径规划到计算机芯片上数据组织等方方面面。棘手之处在于，随着停靠点数量的增加，可能的路径数量会呈爆炸式增长，以至于即使是世界上最快的计算机也会在迷宫中迷失方向。
为了解决这个问题，计算机通常使用一种叫做“约束规划”（Constraint Programming）的方法。可以把它想象成一位超级聪明的侦探，他并不只是随机猜测路径，而是建立了一系列规则（约束）来立即排除不可能或愚蠢的选项。例如，“你不能两次访问同一个城市”或者“你不能开出一个跳过了剩余行程的圆圈”。通常，当问题涉及平面地图上的距离（科学家称之为“欧几里得”情况）时，计算机仅仅将地图视为一组通用的数字列表，忽略了这些停靠点实际上是画在纸上的带有直线和角度的点。这就像是在试图通过只看街道名称列表来导航一座城市，而从未看过地图本身。
这篇论文提出了一个简单但功能强大的问题：如果我们停止忽略地图会怎样？作者 Alessandro Bertagnon 和 Marco Gavanelli 决定为他们的计算机侦探建立一套能够理解几何结构的全新“规则”。他们创建了特殊的算法，这些算法知道在一条完美的、最短的路径中，道路不应该像天空中的“X”那样相互交叉，并且外围边缘应当按照整齐的圆形顺序被访问。通过教会计算机“看见”问题的形状，他们发现了一种比以前更快地剔除数百万个错误猜测的方法。他们还展示了这些几何技巧在问题变得更复杂时依然有效，比如当你需要访问一组城市但只需停靠其中之一时。
该论文的核心发现
这项工作的核心发现是，通过利用旅行商问题（TSP）特定的几何属性——特别是平面上的最短路径永远不会自我交叉，并且会按照特定顺序遵循形状的外边缘——计算机可以显著加快解决这些路径规划问题的速度。作者在一种叫做约束逻辑编程（CLP）的编程语言中实现了这些新规则。
他们将这种全新的“几何过滤”与现有最优秀的方法进行了对比测试。结果令人瞩目：对于多达 100 个点的随机地图，他们的新方法平均减少了约 70% 的寻找最优解所需时间。在计算机的“思考步骤”（搜索节点）方面，他们将工作量减少了大约 59% 到 75%，具体取决于所使用的策略。这意味着计算机不仅每一步都思考得更快，而且在找到答案之前需要思考的步骤也大大减少了。
他们排除了什么，以及是如何做到的
论文明确反对将欧几里得 TSP（即点在平面上呈直线距离）与普通 TSP 完全等同对待的标准做法。常见的方法是计算每对点之间的距离，创建一个巨大的数字表，然后应用通用规则。作者指出，这种“盲目”的方法忽略了已经存在的宝贵信息：点的坐标。他们证明了忽略几何结构会导致更大的搜索空间和更慢的求解速度。
他们还澄清了他们的方法“不是”什么。他们并不声称自己完全解决了 TSP，也没有声称创造了一个适用于每一种路径规划问题的“万能钥匙”。例如，他们指出，他们的“无交叉”规则不适用于那些道路必须交叉的问题，例如具有单行道或桥梁的现实世界城市网格，或者在可能需要绕路的情况下存在严格时间窗口的问题。他们的工作专门针对“完全欧几里得实例”，即点位于平面上且可以避免交叉的情况。
“无交叉”与“凸包”的魔力
为了让计算机变得更聪明，作者引入了两个主要的几何概念：
无交叉规则： 想象你在桌子上用一根绳子连接着一些点并画出一个圈。如果你的绳子自己交叉了，你总是可以把绳子拉紧，从而形成一个不交叉的更短的圈。作者在数学上证明了，最优（最短）路径永远不会有交叉线。他们在计算机程序中构建了一个特殊的“过滤器”，能够立即删除任何会导致交叉的路径选项。这就像是一个俱乐部的保镖，会立即踢走那些试图通过错误入口进入的人，从而省去了保镖稍后检查他们身份证件的麻烦。
凸包顺序： 想象用一根橡皮筋套住木板上的一组钉子。橡皮筋形成的形状被称为“凸包”。作者表明，在最短路径中，这个橡皮筋边缘的钉子必须按特定顺序（顺时针或逆时针）被访问。他们创建了强制计算机遵守这一顺序的规则，防止计算机浪费时间去检查那些在边缘来回穿梭的路径。
将魔力扩展到分组问题
论文还探讨了一个更难的版本，即“广义旅行商问题”（GTSP）。在这个版本中，你不需要访问每一个城市，而是需要访问一系列“簇”（即城市组），但你只需要在每个组中停靠一个城市。这就像一名快递员需要向三个不同的社区投递包裹，但只需在每个社区访问一户人家。
作者展示了他们的几何规则也可以被改编用于这个更难的问题。他们基于簇的几何结构定义了“邻居”，并应用了相同的无交叉和排序逻辑。在针对这些分组问题的测试中，新的几何方法在簇状地图中减少了高达 76% 的平均求解时间，在网格状地图中减少了 67%。
总结
作者谨慎地指出，虽然他们的方法比之前的约束规划技术有了巨大进步，但对于基础 TSP 而言，它尚未达到世界上最强大的专用求解器（如 Concorde）那样的速度。然而，那些超级求解器通常无法处理作者成功应对的更复杂的“广义”版本问题。
论文得出结论：通过仅仅关注问题的形状——利用线条不交叉以及边缘遵循曲线这一事实——计算机可以更高效地剪掉错误的答案。这不仅提高了计算速度，还改变了搜索的本质，使得计算机能够解决以前在合理时间内难以破解的更大、更复杂的路径规划问题。作者建议，只要道路不会发生不可避免的交叉，这种几何方法可以启发其他路径规划问题的改进。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。