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

Question

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

1. 哈密顿路径

2. 哈密顿循环

如果存在，我也想得到它。

我只找到了TwoApproxMetricTSP和HamiltonianCycle.

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

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

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

有没有更好的方法可以在不自己实现算法的情况下获得哈密顿路径/循环？

Answer 1

决策问题"图是否包含哈密顿循环(HC("是NP-Complete。JGraphT 不包括处理不完整图的算法，因此唯一的解决方案是通过添加具有足够大权重的边来使图完整。然后，当您找到没有添加任何昂贵边缘的游览时，HC 存在。请注意，在下一个版本(1.1.1(中，有一个新的精确算法(请参阅主分支，Held Karp 动态规划方法(。此算法不会扩展到超过 32 个顶点。如果你有一个大的图形，我的建议是使用TwoApproxMetricTSP。如果你真的需要解决(合理大小的(图，你将不得不求助于线性规划。另请查看 TSP 求解器协和式飞机。对于大多数 TSP 应用程序，我将实现一个专用的、高效的数据结构，例如将边缘/邻居存储在整数数组中。