TSP的变化而访问多个城市 [英] Variation of TSP which visits multiple cities

问题描述

我期待讨论分支限界解决方案的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的<从A的最短路径A HREF =htt​​p://en.wikipedia.org/wiki/Floyd-Warshall%5Falgorithm>弗洛伊德算法可以让你做到这一点为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的变化而访问多个城市的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！