访问多个城市的 TSP 变体

Question

我希望讨论多次访问的 TSP 的分支定界解决方案。（即每个城市至少需要访问一次，而不是只访问一次）

编辑：

消除了疑虑，因为它与 Jitse 指出的不相关。现在问题更清楚了。

Answer 1

只需为每对节点 A 和 B 添加一条表示从 A 到 B 的最短路径的边来扩充图即可。这 Floyd-Warshall 算法 允许您在 O(n^3) 内完成此操作，这比任何 TSP 算法都要快得多。完成此操作后，请使用标准 TSP 分支定界技术。 这个网站 有一些信息来自 阿普尔盖特的书, ，根据下式讨论 TSP 的分支定界 维基百科 TSP 条目.

Answer 2

因为我解决一个可能的监督，这将是容易使实施他的建议，我宁愿提交此作为马丁·福的回答评论。

在分支定界算法需要与用于重构给出的Floyd-Warshall算法的输出最小成本路径的算法相结合。分支定界算法是外循环，并且它选择未访问的节点。然后你用最少的成本路径重建算法实际的边沿和节点添加到您的周期。由最小成本路径重建算法为已访问，而不是仅仅由分支定界一部分的节点应被标记。