java - 寻找哈密顿路径和哈密顿循环

Question

我在 JGraphT 中有一个 SimpleGraph，想知道是否有

1. 哈密顿路径

2. 哈密顿循环

如果存在的话我也想得到它。

我只找到TwoApproxMetricTSP和 HamiltonianCycle .

但两者都需要完整的图表。

一个明显的解决方案是向我的图表添加边，并使其成为加权图表，添加的边的权重如此之高，以至于它们不会在路径中使用。

但这会增加很多边缘，我想避免这种情况。

有没有更好的方法来获得哈密顿路径/循环，而无需自己实现算法？

Answer 1

决策问题“该图是否包含哈密顿循环(HC)”是 NP 完全问题。 JGraphT 不包含处理不完整图的算法，因此唯一的解决方案是通过添加具有足够大权重的边来使图完整。那么，当且仅当您找到一个没有您添加的任何昂贵优势的旅行时，HC 才存在。请注意，在下一个版本 (1.1.1) 中，有一个新的精确算法(请参阅 master 分支，Held Karp 动态规划方法)。该算法不会扩展到超过 32 个顶点。如果您有一个大图，我的建议是使用 TwoApproxMetricTSP。如果您确实需要解决(合理大小的)图形，则必须求助于线性规划。另请查看 TSP 求解器 Concorde。对于大多数 TSP 应用程序，我会实现一个专用的、高效的数据结构，例如将边/邻居存储在整数数组中。