由网友(姓亲名爹)分享简介：我期待讨论分支限界解决方案的TSP多个访问。（也就是每一个城市需要的只是一次被访问ATLEAST一次，代替）I am looking to discuss branch and bound solution for TSP with multiple visits.(that is every city needs...

我期待讨论分支限界解决方案的TSP多个访问。（也就是每一个城市需要的只是一次被访问ATLEAST一次，代替）

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)

编辑：

删除了怀疑，因为它是不相关的箭头Jitse。现在的问题是更清晰。

Removed the doubt as it was not relevant as pointed by Jitse. Now the question is more clear.

推荐答案

简单地通过增加扩大图，每对节点A和B，边缘重presenting到B的弗洛伊德算法可以让你做到这一点为O（n ^ 3），这是远远快于任何TSP算法。一旦你做到了这一点，使用一个标准的TSP分支定界技术。 本网站具有的阿普尔盖特的书，根据维基百科TSP项，其中讨论了分支定界的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.