java - 在 Java 中使用动态规划解决 TSP

Question

我在网上找到了很多资源，讨论了这个和相关主题，但我没有找到任何真正帮助我知道从哪里开始实现这个解决方案的东西。

澄清一下，从城市 0 开始，我需要每隔一个城市访问一次，然后返回城市 0。

我有一个这样的数组:

   0 1129 1417 1240 1951
1129    0 1100  800 2237
1417 1100    0 1890 3046
1240  800 1890    0 1558
1951 2237 3046 1558    0

除了找到最优路线，我还需要找到沿途的最优部分路线。例如，我将从长度为 2 的路线开始，并最终打印出如下内容:

S = {0,1}
C({0,1},1) = 1129

S = {0,2}
C({0,2},2) = 1417

S = {0,3}
C({0,3},3) = 1240

S = {0,4}
C({0,4},4) = 1951

然后我将转到长度为 3 的路由，并打印如下内容:

S = {0,1,2}
C({0,1,2},1) = 2517
C({0,1,2},2) = 2229
and so on...

为了使其成为一个动态规划解决方案，我假设我应该保存任意 n 个节点之间的最短距离，而我认为这样做的最佳方法是使用 Hashmap，其中键是一个整数值该路径中包含的每个节点按升序排列(从节点 0>1>3>4 或 0>1>4>3 开始的路径可以存储为“134”)，每个键将包含一对可以存储路径顺序为列表，总距离为整数。

在这一点上，我想我想计算距离为 2 的所有路径，然后是距离为 3 的所有路径，然后取最小的几个并使用 hashmap 为每个路径找到返回的最短路径，并进行比较。

这看起来可行吗？还是我完全走错了路？

Answer 1

你有点走上正轨了。动态规划不是计算 TSP 的方法。你有点接近于计算最小生成树。这是一棵使用尽可能短的边和连接所有节点的树。有两种经常使用的算法:Primm's 和 Kruskal's。他们产生类似于您的最佳部分路线列表的东西。我建议您查看 Primm 的算法:https://en.wikipedia.org/wiki/Prim%27s_algorithm

解决 TSP 的最简单方法是找到最小生成树，然后对树进行预序树遍历。这为您提供了近似的旅行商解决方案，称为三角不等式近似。它保证不超过最佳 TSP 的两倍，但可以更快地计算。这个网页解释得相当好http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm

如果你想要一个更优的解决方案，你需要看看 Christofide 的方法，它更复杂。