我SimpleGraph在 JGraphT 中有一个，想知道是否有
哈密顿路径
哈密顿循环
如果存在，我也想得到它。
我只发现TwoApproxMetricTSP和HamiltonianCycle。
但两者都需要完整的图表。
一个明显的解决方案是在我的图中添加边，并使其成为加权图，添加边的权重如此之高，以至于它们不会在路径中使用。
但这会增加很多边缘，我想避免。
有没有更好的方法来获得哈密顿路径/循环而不自己实现算法？
问问题
835 次
1 回答
2
决策问题“图是否包含哈密顿循环 (HC)”是 NP-Complete。JGraphT 不包括处理不完整图的算法，因此唯一的解决方案是通过添加具有足够大权重的边来使图完整。然后，当且仅当您找到没有添加任何昂贵边缘的游览时，才存在 HC。请注意，在下一个版本 (1.1.1) 中有一个新的精确算法（参见 master 分支，Held Karp 动态编程方法）。该算法不会扩展到超过 32 个顶点。如果您的图表很大，我的建议是使用 TwoApproxMetricTSP。如果你真的需要解决（合理大小的）图，你将不得不求助于线性规划。还可以查看 TSP 求解器 Concorde。对于大多数 TSP 应用程序，我会实现一个专用的，
于 2018-01-13T20:53:20.310 回答