0

我目前正在尝试了解有关旅行商问题 (TSP) 的更多信息。我从互联网上找到了一些关于解决这个问题的启发式算法，例如蚁群优化、lin-kernighan、pairwise exchange 等。

另一方面，还有其他算法，如help-karp和分支定界算法。

他们提到他们解决了 TSP，但他们似乎正在通过中间的任何点找到从 A 点到 G 点的最短路径，这可以缩短路径。

在这种情况下，我认为它们与 Dijiktra 算法非常相似......

最重要的是，其中一些算法正在使用权重进行计算。他们通常使用的重量是多少？是距离吗？他们如何实际获得所有这些信息？

据我了解，TSP 是需要前往几个指定的地点，然后往返于同一个起点，不是吗？

诸如匈牙利算法之类的算法似乎更恰当地回答了 TSP，不是吗？

但是，我找不到太多关于这个算法的研究论文。

请指教。

4

1 回答 1

1

TSP 是一个著名的 NP 难（非多项式）问题。问题不在于我们不知道解决方案，而是所有解决方案都是 O(N!) 复杂度。许多算法做了很多聪明的事情来减少明显不好的解决方案，但最坏的情况（具有相等权重的完整图）将在 O(N!) 中运行。

Dijkstra 是一种多项式算法。如果您可以解决 TSP，您将获得世界范围的科学奖项（自 1930 年代以来都是如此）。

对于参考，您可以从 wikipedia 上的参考开始。

于 2017-10-13T09:35:44.737 回答