问题标签 [hamiltonian-cycle]

我真的在为这个证明而苦苦挣扎，非常感谢详细的解释：

显示一个包含 n 个顶点的完整图，MST 的权重小于或等于通过所有顶点的循环的最小权重（也称为哈密顿循环）？

有许多谜题是经典的“柯尼斯堡 7 桥”谜题的变体，您必须在不使用两次门的情况下找到穿过一组房间的路线。

这是一个没有解决方案的例子。

...并且是一个稍微修改的难题，确实有解决方案，如您在此处看到的。

我对解决这类问题的编程方法很感兴趣，虽然有很多方法可以确定房间和门的特定配置没有解决方案，但我有兴趣计算要访问的门列表以解决谜。查看问题的一种方法是将其配置转换为图形并求解哈密顿量。然而，由于禁止“掉头”的约束，这类问题需要处理不雅的逻辑。

我在几分钟内破解了一个解决方案来显示问题。这是一种蛮力解决方案，将“房间”分组，并增加了不变量，即您不能在同一个房间中从一个“门”移动到另一个“门”（因为这需要进行 U 形转弯）。

我觉得必须有一个更好的抽象来表示这个问题，而不是诉诸以下“技巧”：

1. 当路径刚刚来自那个房间时，有额外的逻辑来移除同一个房间中的门作为有效选择。

2. 生成与输入房间配置不同的图形。

3. 过滤所有不满足 U 形转弯约束的配置。（#1 的变体）

是否存在解决此类问题的现有文献，如果有，他们的结论是什么？房间问题是否与最著名的图算法所采用的方法根本不一致，以至于它需要这种特殊的逻辑？如果有更好的解决方案不是转换为图表，我也很想听听。

这是有效的现有代码，组代表第一个问题，注释掉的组代表后一个问题。：

门的标签如下：

我在 C 中有一个程序，它从文件中读取图形的定义，搜索哈密顿循环（只有一个），如果找到，则将其打印在屏幕上。问题是当我试图在具有 30 个或更多顶点的图中找到循环时，程序崩溃（对于 30 个顶点，它有时会显示循环结束崩溃（具有不同的饱和度），更多会立即崩溃）。当我尝试调试时，它会在 free() 函数处停止并显示 SIGTRAP 信号。我能做些什么来解决这个问题？这是我的代码：

我在准备“图论导论”课程的考试时遇到了这个问题。如果有人提供解决此类问题的方法（您指定顶点数和哈密顿或欧几里得路径并询问图形的结构），我将不胜感激。

我正在尝试这个 Google Codejam 问题，它说如果我们从完整图中删除 k 条边，可以找出汉密尔顿路径的数量

链接到问题

https://code.google.com/codejam/contest/32004/dashboard#s=p2

我发现我们可以使用包含排除原则来找出数字

但我的问题是当我们考虑从完整图中删除了一些“x”个边时如何确定路径数（给出了删除的边）

我玩哈密顿路径已经有一段时间了，并发现了一些很酷的用途。一个是一种谜题，其目标是连接所有节点以形成哈密顿路径。

所以，作为一个新手程序员，我创建了一个非常基本的蛮力图生成器，它可以创建具有哈密顿路径的图。但是当我尝试将图形大小增加到 10x10 时，问题就出现了。不用说，通过蛮力在那里不起作用。

我了解哈密顿路径是一个 NP 完全问题，但有没有一种方法可以优化图形生成过程。任何可以在合理时间内创建 15x15 网格的技巧。

非常感谢。

我知道如果拓扑排序具有排序顺序中所有连续顶点对由边连接的属性，那么拓扑排序顺序是唯一的。我的问题是我无法在 C++ 中实现它，尤其是在比较中。最后，我想看看 vetorTop 邻接列表中是否是拓扑排序中它旁边的数字。但似乎 in_degree 并没有给我这个结果。下面是我的代码：

我很乐意接受任何提示和/或建议！

假设您有一个预言机，可以（在多项式时间内）确定某个图中是否存在汉密尔顿路径。（提醒：汉密尔顿路径问题在 NPC 中）。

描述如何使用预言机在多项式时间内在图中找到一条汉密尔顿路径。

有任何想法吗？

背景我正在研究一个优化问题，并设法将问题简化为检查图形是否包含哈密顿路径。减少的问题如下：

问题我们得到一系列边（示例：e[1,5], e[3,4], ..., e[2,3]）。我们需要找到从这个序列开始的边数，以便使用这些边形成的图包含哈密顿路径。我们还需要返回路径。

我的算法这个问题可以从一个没有边的图开始解决。我们一个接一个地插入边，并在每次迭代中检查图是否包含哈密顿路径。通过使用哈密顿路径存在的必要条件，可以使这种方法更快一些。尽管如此，该算法仍然非常低效。

大问题有没有办法以更有效的方式解决这个问题（也许通过使用在早期迭代中完成的计算来加速以后的迭代）？

我一直在研究这段代码，我需要创建一个动态完整图，并尝试通过访问每个顶点一次来找到从开始顶点到结束的最短路径。经过一番研究，我找到了哈密顿循环问题的代码并将其添加到我的代码中。运行这段代码后，我得到了这个：

请注意，第一行打印生成的随机数，之后我打印边缘的权重以进行检查，最后在“从开始到结束的最短路径”之后打印 (vertices.size() * (vertices.size() - 1) / 2) 和 g.edgeSet().size() 检查图形是否完整。

这是我的代码：

编辑：我对这段代码的唯一问题是 hamiltoniancycle 方法中的 getedgeweight 方法