问题标签 [hamiltonian-cycle]

我试图在给定的网格中找到任何哈密顿路径，其中包含各个节点的障碍。我的问题是我的代码已经运行了好几天，还没有结束。虽然这个问题出现在 NP-Complete 区域，但从我所看到的情况来看，我不确定是否缺少足够的时间是我的问题。

我的方法是，在 python 中，使用递归来执行深度优先搜索，通过网格可以进行的所有可能的左、右、上和下移动顺序。我研究了哈密顿路径问题的其他方法，但是对于我所做的来说它们更复杂，我认为小网格不需要它们

以下是我正在搜索的网格。0 是开放节点，1 是障碍物，S 是起点。

这是正在运行的函数当前网格的示例输出，其中 1 现在也代表访问过的节点。

然而，即使每秒大约 50000 步，代码似乎也从未停止检查右下角。例如，从未到达节点 (3,1) 和 (3,2) 处的两个 0。

所以这给我留下了一些问题：这是否只是 NP-Hard 的标准症状，即使我只尝试 13x9 网格？我是否达到了 python 递归限制，导致我的代码无休止地重新运行相同的 DFS 分支？还是我还缺少其他东西？

这是我的搜索方法的简化版本：

因此，代码应该遍历网格中所有可能的路径，直到形成哈密顿路径。这里是我正在运行的实际代码供参考：

下面是使用回溯查找图中是否存在哈密顿路径的代码。根据下面的代码，时间复杂度是O(V^2)，其中V是顶点总数。但是哈密顿问题是 NP 完全的。根据我的理解，这是一个无法在多项式时间内解决的问题n^k，其中n输入k是一些常数。我已经测试了下面的代码并且工作正常。那么我计算时间复杂度是否错误？

节点类：

假设有一个有向图由以下命名的顶点组成：

这些是 4 个不同字母的 3 个字母排列。( total = 4*3*2=24) 顶点的名称也描述了它们之间的边。如果源的最后两个字符等于目标的前两个字符，则任何两个顶点相互连接，例如

A BC -> BC D

或者

D CB -> CB A

该图与 De Burjin 或 Kautz 的图非常相似，但并不相同。它是强连接的，我知道它有哈密顿循环。

为了解决这个问题，我不是算法专家，我只是浏览了最新的 boost 图形库并找到了枚举所有循环的 hawick_unique_circuits() 函数，这是我的示例代码：

hawick_visitor 类只是检查找到的循环是否具有与 Graph 相同的顶点。如果有，这意味着我们找到了我们需要的哈密顿循环之一。

它适用于 24 个顶点，即从 4 个唯一字符中选择的 3 个字符，这是输出之一：

但是当我尝试解决类似的图形时，从 10 个唯一字符中选择了 5040 个名为 4 个字符的顶点，这个函数永远不会返回。应该有比 hawick_unique_circuits() 更好的算法来做到这一点。因为我知道有人在不到一分钟的时间内对 10,000 个顶点进行类似的计算，但我不知道怎么做。任何想法都受到高度赞赏。

这是该图有 5040 个我需要解决的顶点：

我有一个数据框，其中点的 X 和 Y 坐标如下：

我只想找出连接所有这些点的最短路径，并返回它的总距离。没有其他条件：每个点都可以连接到任何其他点，没有特定的开始或结束点，没有权重等......我发现了很多关于 igraph 包的主题，但我不知道如何提供我的数据进去。也发现了这个，但不是在 R 语言中。也许一个“蛮力”脚本会很好，因为我得到的分数不超过 20 分。谢谢

在一个有向无环图中，要找到一条汉密尔顿路径，首先要找到拓扑排序，然后再从拓扑排序中找到汉密尔顿路径。

我们如何证明这一说法的合理性？

如果我的问题被重复，请原谅，但我找不到完整的答案来证明所有顶点度数 = 2 的连通图是哈密顿图。

我读过这个和这个

组元素是由它生成的，对于某些 p，g^p = 1(g, 1, 1, ...), (1, g, 1, ... ), (1, 1, g, ...) ...的形式。(g^i1, g^i2, ... )

在组中的元素之间存在一条边，其中某个索引处的元素具有 g 的幂，与 p 模相差 1，即 g^1 和 g^2 在 p = 4 时具有双向边，但 g^1 和 g^3不要。

在这样的组中是否总是存在哈密顿循环？它有什么样的结构？

例子

对于 g = 1 在加法模 2 下(0, 0, ... 1, 0, 0, 0)生成超立方体的顶点。所以问题是超立方体中是否存在哈密顿循环。

我正在尝试创建一种算法，该算法创建一条以最短/最有效的方式将点图连接在一起的路径，确保所有点都已连接，并且每个点最多有两个连接。

经过一些研究，这似乎是一条（无向）哈密顿路径。我当前的算法只是创建网络中所有可能连接的列表，然后按顺序选择最短的连接，检查它与一个点的连接不超过两次。但是，它无法检查阻止它将整个图形连接在一起的闭环。

我的方法是完全错误的，还是有一种简单的方法来检查闭环并忽略创建它们的连接？

我无法找到一种从相关元组列表中构建树路径的方法？我只想要每个节点被访问一次的每个路径的列表，也就是哈密顿路径。

我不断靠近，但错过了一些路径。

例如，假设我们有这个连接列表：

所需的输出：

所以每个可能的路径都被存储，每个节点只被访问一次：

这是我所拥有的，但它缺少很多路径：

我在期中考试时遇到了一个问题。任何人都可以澄清答案吗？

问题 A：给定一个完整的加权图 G，找到一个具有最小权重的哈密顿环。

问题 B：给定一个完整的加权图 G 和实数 R，G 是否有一个权重最多为 R 的哈密顿游程？

假设有一台解决 B 的机器。我们可以调用 B 多少次（每次给定 G 和实数 R）来用这台机器解决问题 A？假设 G 中的边的总和到 M。

1）我们不能这样做，因为有不可数的状态。

2) O(|E|) 次

3) O(lg m) 次

4) 因为 A 是 NP-Hard 的，所以这是做不到的。