我理解旅行商问题。假设我只想访问选定的城市并返回开始，该怎么做？
假设我的成本矩阵是，
A B C D
A 0 1 2 1
B 1 0 1 2
C 2 1 0 1
D 1 2 1 0
如果我想访问所有城市并返回 A。我的最短路径是 A->B->C->D，最小距离是 4.
假设我只想访问 B 和 D。我怎样才能找到最小距离？
这是修改后的旅行商问题？有人可以帮我为这个案例做暴力算法吗？
最佳答案
您可以先运行 Floyd-Warshall 来计算所有节点对之间的最短路径。参见 wikipedia article . 一旦您有了压缩成本矩阵，您就可以消除所有您不感兴趣的城市。从那里它就是标准的旅行推销员。
由于旅行推销员是 NP 完全的，因此在它之前运行 Floyd-Warshall 的复杂性并不重要。
如果您想要完整的路线(包括绕过无趣的城市以缩短路径，您将不得不返回 Floyd-Warshall 并重建路径。
关于c++ - 仅访问选定城市并返回开始的最低成本？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18095954/