问题标签 [hamiltonian-cycle]

我在这个网站上阅读了很多关于完整加权图和哈密顿之旅主题的内容，这些主题是由一位用户提出的，问了我大学的很多工作人员，但无法得到一个好的答案，我将这个问题的一个重要部分更改为如下：

问题 A：给定一个完整的加权图 G，找到weights具有最小权重的 Hamiltonian Tour。

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

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

1. 我们不能这样做，因为存在不可数状态。

2. O(|E|) 次

3. O(lg m) 次

4. 因为 A 是 NP-Hard，这是无法做到的。

我读了这个文件，在第 2 页他写道：

a) 优化问题（严格意义上）：找到最优解

b) 评估问题：确定最优解的值

c) 有界问题：给定一个有界 B，确定最优解的值是高于还是低于 B。

在接下来的两段

为了利用 c) 解决 b)，我们使用组合问题的可能值通常是离散的并且可以被视为整数的事实。假设我们可以在时间 T 内解决有界问题 c)。对于相应的评估问题 b)，人们通常先验地知道该值位于整数的某个范围 [L，U] 内。使用二分查找，我们用 log | 解决了评估问题。U - L | 调用有界问题 c)，因此在时间 T log | U - L |。

接下来他写道：

例如：加权图上的 TSP Kn = (V, E, w: E -> Reals), |V| = n, |E| = n-选择-2。使用 c) 解决 b)。n 个顶点的图中的环或哈密顿循环恰好有 n 条边。因此，n 条最长边的总和 S 是最优路径长度的上限。另一方面，n 条边的所有 m 个选择-n 个子集的总和是一组有限的数字，其中两个数字之间的最小非零差 d 定义了旅行长度的粒度。两个不同的旅行要么具有相同的价值，要么它们的长度至少相差 d。因此，计算 log(S / d) 界限问题的二分搜索确定了最佳游览的长度（值）。

我的问题是我们可以调整这个解决方案来以这种方式选择（3）吗？

我正在尝试创建一个本地搜索启发式来解决 TSP，这个过程似乎失败了。我生成了一个随机哈密顿循环并将其存储在传出 [] 中，传出 [i] 表示源自 i 的边之一指向的顶点。distances[a][b] 表示从顶点 a 到顶点 b 的距离。但是，每当我运行此代码时，算法并没有优化我传入传出的哈密顿循环，而是简单地创建新循环 0->numcities-2->1->numcities-1。如果它可以提高顶点到其输出顶点的距离，它应该简单地重复切换输出顶点。我可能忽略了一些小事，但我根本无法弄清楚我做错了什么。顺便说一句，我将运行多次，这就是布尔值更改的用途。

让 G 是一个简单的图，它不是森林并且周长≥5。证明 G 的补码是哈密顿量。周长是图中最短的循环。森林是一个没有任何循环的图。所以 G 至少有一个循环，最小长度为 5 。我想证明 G 的补码是哈密顿

我正在准备考试和我的算法课程，我们一直需要涵盖 NP 完整性，但我们从来没有任何真正的教程，只是为考试提供了一堆“练习题”。除了最后一个，我已经完成了所有工作，我真的不知道如何解决它（到目前为止，询问互联网已经返回了我不理解的已发表论文）。

前两个问题表明哈密顿路径问题属于 NP 类，然后通过显示哈密顿循环问题简化为它来证明它是 NP 完全的。

这就引出了我似乎无法取得进展的第三个问题：

图的度数约束生成树是某个固定 k 的最大度数 k 的生成树（树中的每个顶点最多与 k 个边相邻）。确定图 G 是否包含度数受 k = 2 约束的生成树是哈密顿路径问题，这是一个 NP 完全问题，如您刚刚所示。证明决定图 G 是否包含度受 k 约束的生成树，对于一般 k，也是一个 NP 完全问题。

我目前回答这个问题的尝试是这样的：

对于 k = 2，对于任何顶点 V，我们可以将图拆分为 2 个不同的子图，它们仅共享顶点 V，并且对于哈密顿路径返回 true。也就是说，对于 k=3，有一个顶点 V，我们可以将图分成 3 个不同的子图，这些子图都具有哈密顿路径。

我知道这不正确，但我觉得它走在正确的道路上，但根本不知道如何达到最终目标。任何帮助，将不胜感激。

我有一个有 562 个顶点和 3961 个边的有向图（如果你好奇，边是http://a3nm.net/share/raw_graph_284374.txt），我想在这个图中找到一个不会经过两次的循环相同的顶点并且尽可能长。

我知道这个问题是 NP 难的（通过减少哈密顿循环问题），但我并不真正关心找到最长的循环，只是一个相当长的循环。一个简单的 DFS 实现可以找到长度为 100-200 的循环，但我确信有许多启发式方法和改进可以用来找到更长的循环。

是否有任何（开源）程序或库可用于在这种大小的图中找到更长的周期？

这是我在图中找到哈密顿循环的算法：

我能够找到一个第一个哈密顿循环。是否可以对其进行调整以找到图中所有可能的哈密顿循环？

输入是一个非对称矩阵（节点之间的一些链接是一种方式），一些节点可能有 2 或 3 个链接到其他节点。

谢谢

编辑：

澄清一下，该算法已经可以找到解决方案，但找不到第二个解决方案，依此类推。从阅读中，使用 bactracking 的 A* 可能会解决问题，但我不确定它是否可以添加到我已有的内容中。

我需要证明给定无向图 G，哈密顿路径和哈密顿循环是多项式时间可相互约简的。这是我的减少，这是正确的吗？

对于循环到路径对于属于 V 的顶点 v，添加一个顶点 v' 并且对于所有 e(v,u) 添加边 e(v' ,u)。现在如果存在从 v 到 v' 的哈密顿路径，则存在 v 的哈密顿循环。

对于循环路径对于顶点 s 和 t，对所有边 e(t,u) 添加一条边 e(s,u)（如果此边不存在）并且对于所有边 e(s,u) 添加一条 endge (t,u)（如果这条边不存在）。最后添加一条边 e(s,t)。现在，如果 s 或 t 存在哈密顿循环，则存在从 s 到 t 的哈密顿路径。

有减少正确吗？这是否足以表明这两个问题是多项式时间可相互约简的？

有人可以向我解释受限哈密顿循环的定义吗？
我知道什么是哈密顿路径（和哈密顿循环），但我在理解什么是受限哈密顿循环时遇到了问题。

谢谢你。

我正在尝试使用 C# 中的遗传算法解决旅行推销员问题。但在我的应用程序中，最佳值变化如此缓慢。我尝试过不同的交叉方法，例如经典、贪婪和 pmx，但我从来没有得到我想要的。在遗传算法中导致缓慢逼近局部最小值的最有效原因是什么？不是交叉方法吗？

我认为我的 CO 方法是正确的，不是吗？我的代码：

就像问题在链接中的图片中所说的那样。

hamilton circuit上图中有a吗？

我发现了一些hamilton path像：

但不是hamilton circuit

我不能在这里添加图片，因为stackoverflow不允许我