问题标签 [hamiltonian-path]

有人可以告诉我汉密尔顿路径和欧拉路径之间的区别。它们看起来很相似！

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

1. 哈密​​顿路径

2. 哈密​​顿循环

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

我只发现TwoApproxMetricTSP和HamiltonianCycle。

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

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

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

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

我的问题是 - 如果我们考虑旅行推销员问题而不返回起点部分，贪心（最近邻）算法是否正确解决了这个问题？在之前的帖子中有人说这个问题相当于最短哈密顿路径，但我认为我们不需要对每个节点只访问一次的限制，所以我想要一个更好的解释。

谢谢，

我正在尝试解决一个问题，该问题在图表中为我提供了一条汉密尔顿路径。我知道用于它的算法，但它们都适合命令式风格。我的困惑是，如果我必须在 scala 中使用动态编程来解决问题，那么最好的方法是什么。还有比 DP（内存和空间）效率更高的算法吗？近似值是我能想到的，但据我所知，它需要一个完整的图表。请赐教。谢谢！

从这个问题- 哈密顿路径和欧拉路径之间的差异，每条哈密尔顿路径都不是欧拉路径。我怎样才能准确地覆盖每个顶点一次并穿过边缘两次？

我正在学习算法：设计与分析 II课程，其中一个问题是：

假设 P ≠ NP。考虑具有非负边长的无向图。以下哪个问题可以在多项式时间内解决？

提示：哈密顿路径问题是：给定一个具有 n 个顶点的无向图，判断是否存在一条（无环）路径具有 n-1 条边，并且恰好访问每个顶点一次。您可以使用哈密顿路径问题是 NP 完全的事实。从哈密顿路径问题到以下 4 个问题中的 3 个问题相对简单。

• 对于给定的源 s 和目标 t，计算恰好具有 n - 1 条边的最短 st 路径的长度（或 +∞，如果不存在这样的路径）。路径允许包含循环。
• 在图的所有生成树中，计算具有最小可能叶数的一棵。
• 在图的所有生成树中，计算具有最小可能最大程度的一棵。（回想一下顶点的度数是入射边的数量。）
• 对于给定的源 s 和目标 t，计算恰好具有 n - 1 条边的最短 st 路径的长度（或 +∞，如果不存在这样的路径）。路径不允许包含循环。

请注意，哈密顿路径是图的生成树，并且只有两个叶节点，并且恰好具有两个叶节点的图的任何生成树都必须是哈密顿路径。这意味着确定图中是否存在哈密顿路径的 NP 完全问题可以通过找到图的最小叶生成树来解决：当且仅当最小叶生成树正好有两个叶时，路径才存在. 因此，问题 2 是 NP 完全的。

问题 3 是 NP-Hard；这是证明这一点的论文。

这意味着，在 1 和 4 之间，一个是 NP-Complete，另一个是 P。似乎问题 4 可以简单地简化为哈密顿路径问题，但我无法理解循环如何使其可解决？还是相反？

我正在尝试实现 Held-Karp 算法以在未加权的有向图上找到哈密顿路径。为了实现这一点，我创建了一个内部类 Combination ，它存储一个 Stack ，它表示所采用的路径的顺序，以及一个 Set ，它存储当前在路径中的元素。

哈密​​顿路径的定义是只访问图中每个顶点一次的路径

我还使用队列来存储算法尚未完全探索或折扣的路径。

最初，这个队列充满了组合，每个组合在图中都包含一个顶点。这满足了 Held-Karp 的基本情况，其中平凡的哈密顿路径是通过单个顶点的路径。

当队列不为空时，队列前面的元素被出列。其堆栈中的顶部元素被窥视，因为该元素表示添加到路径的最后一个顶点。循环遍历最后一个顶点的相邻顶点，如果其中任何一个不在当前路径集中，则使用先前的路径 Stack 和路径 Set 创建一个新的 Combination 对象，并将新顶点添加到 Stack 和 Set 中。这个新的组合对象被添加到队列的后面以供以后分析。如果无法将另一个顶点添加到路径，则循环继续并且对此组合对象的引用丢失 - 组合被打折。

如果在出队时我们遇到一个具有与图中顶点数相同长度的 Stack 的 Combination 对象，那么我们返回该 Stack 的数组表示，因为它是哈密顿路径。

我正在针对这个Graph测试这个算法。

我的代码为此图生成的邻接列表如下：

矩阵索引和顶点值之间的键映射是：

ids HashMap 只是顶点的整数 ID 与其实际 String 值之间的映射。

由于该图不包含哈密顿路径，我希望输出是一个空字符串数组。但是我实际得到的输出是：

F -> A -> B -> D -> C -> E

这很奇怪，因为在图形或矩阵中 B 和 D 之间没有边。

我有一个包含 1000 个节点的完整加权图，需要在图中找到最长的哈密顿路径（更准确地说是节点序列）。我应该适合 5 秒（对于 Java），内存限制足够大。寻找最长的哈密顿路径看起来与寻找 TSP（旅行推销员）的解决方案没有太大区别。当然，最佳解决方案是不可能的，所以我正在寻找一个好的启发式方法。到目前为止，我最好的解决方案是使用最近邻算法，该算法易于实现并在多项式时间内运行（1000 个节点图大约需要 0.7 秒）。虽然它离最佳解决方案有点远。所以我正在寻找一种运行速度相对较快的更好的启发式算法。我看到提到禁忌搜索、模拟退火、蚁群、遗传学、分支和绑定，基于 MST 的算法等。问题是，由于它们的实现并不是微不足道的，因此很难找到它们的时间复杂度来决定哪些可以在 5 秒内完成。时限; 例如在多项式时间内运行。对于像 Christofides' 这样的一些算法，我看到复杂度是 O(V^4)，其中 V 是顶点数，这显然使得它无法拟合。

我遇到了 Bitonic Tour 解决方案，通常用于在欧几里得图中找到最短的哈密顿路径，但似乎也可以在非欧几里得图中找到最长的路径：

标准算法包括坐标的初始排序，我跳过了它，因为显然没有坐标要排序（图是非欧几里得）。这个动态编程解决方案在 O(V^2) 中运行，所以它可能很好。问题是它输出哈密顿路径长度，我需要节点序列。我真的不明白如何从上述算法中恢复路径（如果可能的话）。

TL DR 版本： 上面的双调游算法能否用于在完整加权图中查找最长哈密顿路径上的节点序列？如果没有，您能否为该任务推荐具有相似（多项式）时间复杂度的算法？

考虑不相交哈密顿路径问题：

输入：可以有向或无向的图

输出：该图是否存在至少 2 个边不相交的哈密顿路径？边不相交意味着两条路径不共享一条边。

证明不相交哈密顿路径是 np 完全的。

有人告诉我这个问题是 np-complete，但我无法证明它是 np-hard。我尝试将原始的哈密顿路径和哈密顿循环简化为这个问题，但我想不出解决方案。

我正在尝试在一个简单的 DAG 中实现对哈密顿路径的递归搜索。这是我的玩具数据和代码：

边缘列表格式的 DAG

转换后字典格式的 DAG

代码：G是图，size是图中的顶点数，v是当前顶点，v_next是邻居顶点。

当我遍历顶点（从 1 到 4）并在每个循环中运行函数时，结果有点奇怪。

我希望从 4 开始时结果将是 [4, 3, 1, 2]。之前提到的一篇文章是因为“可变默认参数”问题。但我不知道在这种情况下如何解决。有什么提示吗？