问题标签 [hamiltonian-cycle]

令G(V,E)为无向图。哈密​​顿循环是一个循环，它只访问G的每个顶点v一次（第一个顶点除外，它也是循环中的最后一个顶点）。

假设：存在一种确定图是否具有哈密顿循环的有效算法（返回 True\False）。让我们将此 alg' D称为确定。

• 证明：存在一种返回哈密顿循环的有效算法。

我的回答尝试

我的问题

正如你所看到的，我有一个算法的想法来证明一个算法的存在。我觉得这是正确的方向......但是我如何证明这个算法实际上返回了哈密顿循环？

我正在与协和飞机合作解决 TSP 问题。这是我的代码

协和飞机已正确安装在我的系统上并且工作正常。当我运行 concorde_help() 时，我得到以下输出

这表明协和飞机安装正确。但是，当我尝试运行 R 代码（在顶部给出）时，有时我会得到答案，而有时我的程序会卡住。当程序执行成功时，我得到以下输出

在上述输出中，最优解为 0.00。谁能告诉我为什么这是零？有时代码不执行并给出以下输出

在这个输出之后，什么都没有发生，程序似乎进入了一个无限循环。谁能告诉我我做错了什么？

是我系统的错吗？我正在使用 Windows 10 和 R-studio 64 位开发核心 i3 系统。

编辑：这是我正在使用的数据集

编辑2：这是会话信息

我正在尝试解决哈密顿循环问题。

我的任务条件是：

该组由 N 人组成。在其中，每个人都有 N / 2 个朋友。友谊是对称的（如果 A 是朋友 B，那么 B 是朋友 A）。小组中的一个人有一本书（他的号码 X），每个人都想阅读，然后与其他一些人讨论。

需要确定转让书的方法，即它会访问每个人一次，只在朋友之间传递，最后归还给它的主人。

也就是说，它满足狄拉克定理的条件。

在小图上，我的解决方案可以正常工作，但在大图上，我的解决方案给出了时间限制例外。

有什么方法可以比 O(n!) 更快地解决它？

我试图编写一个函数，它将一个正整数 n 作为输入，并将整数 1 到 n 按顺序排列，使得每个相邻数字的总和是一个完美的平方（如果存在这样的顺序）。我意识到，如果我创建一个顶点是数字的图，并且如果它们的和是一个完美的平方，那么两个顶点之间有一条边，那么这个问题就相当于试图在图中找到一条哈密顿路径。因此，我正在尝试编写一个函数，该函数将在给定图中找到哈密顿图（如果存在）。这是我的代码：

“Moves”是图的字典（变量“graph”已经用过，我不擅长命名变量），其中每个顶点都是一个键，每个键的值是一个列表，其中包含相邻的其他顶点关键顶点。例如，当输入为 15 时，这是字典：

起点是哈密顿路径的起点。（我试图编写这个没有起点的函数，这样函数本身就会尝试每个点作为起点，但它变得复杂了。现在，我只是自己遍历所有顶点。）

我知道对于数字 15，它应该给我以下列表：

但是，它给了我这个列表：

思考这个函数是如何运作的，我意识到一旦它达到 1，它首先会添加 8 作为下一个数字。但是，8 在除 1 之外的顶点之间没有边。老实说，我不知道它接下来会做什么。我意识到一旦没有可能的候选者可以尝试，它就需要回溯并回到上一个正常位置。我不知道如何实现这一点。

我该如何解决这个问题？另外，如何改进我的代码？

我对 Python 很陌生，所以如果这个问题是微不足道的或者我的代码很糟糕，我深表歉意。

编辑：我想我解决了主要问题，现在它返回了正确的列表。这是新代码：

我认为问题在于，一旦我们走到了死胡同，错误的路径已经被附加到 list path，这就是为什么前面代码的输出中有一个 8 的原因。

现在，问题是函数None在返回列表后返回。因此，这是我为数字 15 运行此函数时的输出，即图表是我之前提到的字典：

我怎样才能解决这个问题，所以它不会返回None？顺便说一句，我还是要自己尝试每一个数字作为起点。这就是我所做的：

换句话说，我必须手动尝试每个数字作为路径的开始。如何调整原始函数，使其不需要起点，并自行尝试所有可能的数字？

此外，即使对于小数字，此功能也需要很长时间。我怎样才能使它更有效率？

编辑：我意识到包含整个函数而不是仅包含哈密顿路径部分更有帮助，因为某些变量是未定义的。

该函数blueprint通过检查每个可能对的总和来创建图形。我已经解释过了hampath_finder。for之后，我尝试使用循环将每个数字作为路径的开始。

https://www.youtube.com/watch?v=3xeYcRYccro&list=PLoJC20gNfC2gmT_5WgwYwGMvgCjYVsIQg&index=32

12:10 指出该示例是汉密尔顿路径。这是一个说明汉密尔顿路径不能生成汉密尔顿图的例子。事实上，所有顶点都被红线覆盖。汉密尔顿路径是一次接触所有顶点。使满意。如果我们从右上到右下添加一条边，我们会不会有一个汉密尔顿循环。然后我们可以从一个顶点开始，运行所有其他 3 个并从头开始完成。一次。为什么不是汉密尔顿循环。

我知道如果图中存在负成本循环，则相对最短路径问题属于 np-complete 类。我需要通过使用哈密顿循环问题执行多项式归约来证明这一点。谁能解释一下？这将非常有帮助。

据我了解，哈密顿路径恰好访问图的每个顶点一次。是否有至少访问每个顶点一次的路径的名称？

一些图可能是这样的，一个循环访问每个顶点，必须多次访问某些顶点。我想谈谈最短的此类周期。

Ultra-Hamiltonian 自行车被定义为一种封闭的步行，它只访问每个顶点一次，除了最多一个顶点访问不止一次。

问题：- 证明确定给定图是否包含超哈密顿循环是 NP 难的。

我们可以从哈密顿循环问题中减少它，这是一个 NP 难题，但我没有从哪里开始将它减少到超哈密顿循环问题。

你能告诉我这样做的方法吗？

我最近在CodeBullet的 Snake AI 视频中发现了 Hamiltonian Path/Circuit，并决定亲自尝试一下。我编写了一个基本的深度优先搜索算法来访问图中的所有节点并在电路完成时存储路径。

下面是算法的伪代码：

这个实现在理论上是可行的，因为它确实为我提供了一个 6x6 及以下网格的解决方案，但问题是，它非常慢。在视频中，它甚至无法为 8x8 网格提供解决方案，并提到这是一种非常快速的算法，因为他已经计算了 50x50 网格的哈密顿电路，所以它也显示出来了。

我真的很想知道如何加快速度，因为我确信我的初学者技能不足以指出一些你可能很容易看到的明显缺陷。任何帮助表示赞赏。

如果我们看到这里介绍的算法：https ://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/threeSAT_to_hamiltonianCycle.html

它每级使用 2k 个节点，其中 k 是子句数或引用优化版本中特定变量的子句数。然而，路径的歧义似乎肯定是可能的，令人惊讶的是，一个学术网站会在归约证明中包含如此重大的错误。

此处介绍的算法版本：https ://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/08PolynomialTimeReductions-2x2.pdf

似乎是正确的，因为它在每个级别使用 3k+3 个节点，其中它的 2k 版本在子句/变量对之间添加了节点以用于额外的 k-1 个节点，然后在每行的开头和结尾额外增加 2 个节点. 这给出了 2k+k-1+2+2=3k+3 个节点。

似乎不仅 UNSAT 公式可能是可满足的，而且可以肯定的是，SAT 方程将有由 OpenDSA 上的方程产生的错误解。在一本制作精良的专业书籍中发现这样一个错误是相当令人惊讶的，所以我认为这值得一问。我已经就此通知了 OpenDSA。