问题标签 [hamiltonian-cycle]

什么是在无向图中找到哈密顿圈的动态规划算法？我在某处看到存在具有O(n.2^n)时间复杂度的算法。

我正在尝试在 java 中实现一个邻接矩阵，它将产生一个哈密顿循环的输出，然后可以用不同的算法来解决这个问题，例如 kruskurals、djikstras 和 2opt 方法。我知道我需要一个二维数组，但我不知道从哪里开始。我需要能够存储矩阵并将其应用于我拥有的图形，该图形目前是一个带有“n”个节点的圆圈（取决于矩阵）。欢迎所有帮助，谢谢

我有相对较小的（40-80 个节点）三次（3 正则）平面图，我必须确定它们的哈密顿性。我知道这个任务是 NP 完全的，但我希望渐近指数时间算法对于我感兴趣的图形大小来说仍然非常快。

这与旅行商问题有关。首先需要生成所有排列，然后附加目的地（与原点相同）。即：1）abcd abdc ....

2) abcda abdca ....a

我有所有的距离，只需要一个算法来总结它们。我想知道是否有一种算法（最好是 C）我可以使用它，或者某处是否有现成的解决方案。

嗨，我正在做一个需要解决 TSP 问题的项目。我需要的是如何在图中找到哈密顿电路。事实上，我知道如何在现实世界中做到这一点。但是在实现和源代码上我不知道如何做到这一点。我已经阅读了互联网上使用一些嵌套循环的文章，但我没有得到每个 for 的作用以及整个故事是如何进行的。如果有人可以帮助我，我将不胜感激。并给我一个简单的例子来说明如何实现这一点。我不需要工作模型。假设我们有一个顶点数组和一个路径数组（路径是指路径的开始和结束顶点）。我们如何解决这个问题。

这个问题实际上改写了那个问题。代码堵塞问题如下：

你得到一个完整的无向图，有N个节点和K个“禁止”边。N <= 300, K <= 15。找出图中不使用任何K个“禁止”边的哈密顿循环数。

的直接 DP 方法O(2^N*N^2)不适用于这样的N。看起来获胜的解决方案是O(2^K). 有谁知道如何解决这个问题？

我有这个项目，我必须提出实现哈密顿循环的 Java 源代码。我在谷歌上搜索，至少现在我知道哈密顿循环是什么，除了起始顶点之外只通过所有顶点一次的路径，因为它也是最后一个顶点（告诉我我是否错了）。问题是我不知道如何实现它。基本上，我的问题是：

1. 如何，在哪里实现哈密顿循环？
2. 哈密​​顿循环的应用是什么（有助于理解为什么它如此重要）

我想知道是否有一种算法可以在有向加权图中找到最长的循环路径（我认为这是找到最大哈密顿子图的问题）。

我需要从一个顶点开始并返回到同一个顶点，遍历最可能的节点。

谢谢

我知道以前有人问过这个问题，但我在任何帖子中都没有找到答案。有人可以建议我一种算法，它可以在图中枚举所有哈密顿路径吗？

一点背景知识：我正在研究一个问题，我必须枚举每个哈密顿路径，进行一些分析，然后返回结果。为此，我需要能够列举所有可能的汉密尔顿路径。

谢谢。

代码堵塞问题如下：

你得到一个完整的无向图，有 N 个节点和 K 个“禁止”边。N <= 300, K <= 15。找出图中不使用任何 K 个“禁止”边的哈密顿循环数。

不幸的是，这里在堆栈和整个网络上对此的解释都非常不充分。我可以找出某个'n'的HamCycles：（n-1）！/2。

我可以用动态编程做短集。

但我没有得到所有的博洛尼亚子集，如何让它 O^K？我在 Python 中，尚未破译可用的 C++。最终我确定我会花时间学习 C++，然后我会破译它。但与此同时，为什么有人不能在网络上的某个地方更好地解释这一点？它们总是一半的解释。