algorithm - 访问多个城市的 TSP 的变化

Question

我希望通过多次访问来讨论 TSP 的分支和绑定解决方案。（也就是说，每个城市都需要至少访问一次，而不仅仅是一次）

编辑：

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

Answer 1

只需为每对节点 A 和 B 添加一条表示从 A 到 B 的最短路径的边来扩充图形。Floyd-Warshall 算法允许您在 O(n^3) 内完成此操作，这比任何 TSP 算法。完成此操作后，请使用标准 TSP 分支和绑定技术。 该站点包含Applegate 书中的一些信息，该书中根据Wikipedia TSP 条目讨论了 TSP 的分支和界限。

Answer 2

我宁愿将此作为对 Martin Hock 回答的评论提交，因为我正在解决一个可能的疏忽，这很容易实现他的建议。

给定 Floyd-Warshall 算法的输出，分支定界算法需要与重构最小成本路径的算法相结合。分支定界算法是外循环，它选择未访问的节点。然后，您使用最低成本路径重建算法将边和节点实际添加到您的循环中。节点应该被最小成本路径重建算法标记为已访问，而不仅仅是分支和绑定部分。