0

我有一个很大的加权图。我想计算一条近似最短的哈密顿路径，它以最低的成本通过所有节点。我的图表非常大，不适合我的记忆。所以我决定随机忽略一些边缘并将其余的加载到内存中。但问题是大多数 java TSP 实现都需要一个完整的图表，在我的情况下需要大量内存，而我没有那么多内存。有没有在 imcpmlete 图上计算 TSP 的 java 库？我的staretegy是我将初始顶点集分成更小的部分。我为每个计算了最短的哈密顿路径，然后我连接了所有最短的哈密顿路径。它是 TSP 的一个很好的近似值吗？有谁知道大图的 TSP 更好的近似算法？

4

1 回答 1

1

问题在于，随着图变得不那么完整，找到哈密顿路径可能相当困难。有许多启发式方法可用于寻找近似解，例如最近邻法。虽然，您遇到了无法找到有效路径的机会。

于 2013-11-12T19:30:23.600 回答