问题描述
我期待讨论分支限界解决方案的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.
这篇关于TSP的变化而访问多个城市的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！