访问多个城市的 TSP 变体
我希望讨论多次访问的 TSP 的分支和绑定解决方案。（即每个城市都需要至少访问一次，而不是只访问一次）
编辑：
消除了疑虑，因为它与 Jitse 指出的不相关。现在问题更清楚了。
I am looking to discuss branch and bound solution for TSP with multiple visits.(that is every city needs to be visited atleast once , instead of just once)
Edit:
Removed the doubt as it was not relevant as pointed by Jitse. Now the question is more clear.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
只需为每对节点 A 和 B 添加一条表示从 A 到 B 的最短路径的边来扩充图形即可。 Floyd-Warshall 算法 允许您在 O(n^3) 内完成此操作，这比任何 TSP 算法都要快得多。完成此操作后，请使用标准 TSP 分支定界技术。 此网站包含来自 Applegate 的书，根据 维基百科 TSP 条目。
Simply augment the graph by adding, for each pair of nodes A and B, an edge representing the shortest path from A to B. The Floyd-Warshall algorithm allows you to do this in O(n^3), which is much faster than any TSP algorithm. Once you've done this, use a standard TSP branch and bound technique. This site has some information from Applegate's book, which discusses branch and bound for TSP according to the Wikipedia TSP entry.
我宁愿将此作为对 Martin Hock 答案的评论提交，因为我正在解决一个可能的疏忽，这很容易实现他的建议。
分支定界算法需要与在给定 Floyd-Warshall 算法输出的情况下重建最小成本路径的算法相结合。分支定界算法是外层循环，它选择未访问过的节点。然后，您使用最低成本路径重建算法来实际将边和节点添加到循环中。节点应该被标记为通过最小成本路径重建算法访问，而不仅仅是通过分支定界部分。
I'd rather submit this as a comment on Martin Hock's answer because I'm addressing a possible oversight that would be easy to make implementing his suggestion.
The branch and bound algorithm needs to be combined with an algorithm for reconstructing least cost paths given the output of the Floyd-Warshall algorithm. The branch and bound algorithm is the outer loop, and it selects unvisited nodes. Then you use the least cost path reconstruction algorithm to actually add edges and nodes to your cycle. Nodes should be marked as visited by the least cost path reconstruction algorithm, not just by the branch and bound part.