寻找哈密顿路径和哈密顿循环
Finding Hamiltonian path and Hamiltonian cycle
我在 JGraphT 中有一个 SimpleGraph，想知道是否有
哈密顿路径
哈密顿循环
如果有的话我也想得到。
我只找到了 TwoApproxMetricTSP and HamiltonianCycle.
但两者都需要完整的图表。
一个明显的解决方案是向我的图添加边并使其成为加权图，添加的边的权重非常高，以至于它们不会在路径中使用。
但这会增加很多边缘，我想避免这种情况。
有没有更好的方法来获得哈密顿量 path/cycle 而无需自己实现算法？
决策问题 "does the graph contain a hamiltonian cycle (HC)" 是 NP 完全问题。 JGraphT 不包括处理不完整图的算法，因此唯一的解决方案是通过添加具有足够大权重的边来使图完整。然后，当且仅当您找到没有您添加的任何昂贵边的游览时，HC 才存在。
请注意，在下一个版本 (1.1.1) 中有一个新的精确算法（请参阅主分支，Held Karp 动态编程方法）。该算法不会扩展到超过 32 个顶点。如果你有一个大图，我的建议是使用 TwoApproxMetricTSP。如果你真的需要解决（合理大小的）图形，你将不得不求助于线性规划。另请查看 TSP 求解器 Concorde。对于大多数 TSP 应用程序，我会实现一个专用的、高效的数据结构，例如将 edges/neighbors 存储在整数数组中。
我在 JGraphT 中有一个 SimpleGraph，想知道是否有
哈密顿路径
哈密顿循环
如果有的话我也想得到。
我只找到了 TwoApproxMetricTSP and HamiltonianCycle.
但两者都需要完整的图表。
一个明显的解决方案是向我的图添加边并使其成为加权图，添加的边的权重非常高，以至于它们不会在路径中使用。
但这会增加很多边缘，我想避免这种情况。
有没有更好的方法来获得哈密顿量 path/cycle 而无需自己实现算法？
决策问题 "does the graph contain a hamiltonian cycle (HC)" 是 NP 完全问题。 JGraphT 不包括处理不完整图的算法，因此唯一的解决方案是通过添加具有足够大权重的边来使图完整。然后，当且仅当您找到没有您添加的任何昂贵边的游览时，HC 才存在。 请注意，在下一个版本 (1.1.1) 中有一个新的精确算法（请参阅主分支，Held Karp 动态编程方法）。该算法不会扩展到超过 32 个顶点。如果你有一个大图，我的建议是使用 TwoApproxMetricTSP。如果你真的需要解决（合理大小的）图形，你将不得不求助于线性规划。另请查看 TSP 求解器 Concorde。对于大多数 TSP 应用程序，我会实现一个专用的、高效的数据结构，例如将 edges/neighbors 存储在整数数组中。