问题标签 [hamiltonian-cycle]

我最近试图提出哈密顿路径的总数（基本上从起始顶点开始，准确地访问每个节点一次并到达结束顶点）。蛮力 dfs 在 7x8 的中等大小的网格上走了很长一段路。我想出了一些修剪策略。这些修剪技术的目标是不应该进一步扩展不能是哈密顿路径的部分路径。

DFS算法：从起始顶点开始，访问其邻居节点并递归。记录访问过的节点数，一旦到达结束顶点，检查访问过的节点总数是否与网格中的总节点数相同。这将是指数复杂度，因为对于每个顶点，您可以在 4 个方向上进行，这将是 O(4^n)。所以重点应该是尽快拒绝一条路径，而不是等到到达终点。

修剪技巧：

1）对于给定的部分路径，检查剩余的图是否连通。如果不是，那么这条部分路径就不能成为哈密顿路径。

2) 对于给定的部分路径，每个尚未访问的节点必须具有至少 2 度，以便一个邻居节点可以用于进入该节点，而另一个其他邻居用于退出。

我想知道这些修剪技术可以节省多少时间。我是否还缺少一些非常重要的修剪技术，因为我的加速并不显着。

提前致谢 ！！！

我正在阅读用于查找最小生成树（在加权图的情况下）和查找图是否具有汉密尔顿路径（取决于汉密尔顿循环的存在）的算法。我把一切都搞砸了。那么汉密尔顿路径和生成树有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有有效的算法来找到生成树（也许是最小生成树），但为什么我们不能有找到哈密顿回路的算法呢？我们可以继续一次添加和删除一条边，直到达到一个循环，也许我们可以找到一个哈密顿循环？

假设我们有一个随机图。如何以最少的步数删除或添加边，以使结果图中的每条边都位于汉密尔顿路径中？

如果有人可以分享任何想法，我将不胜感激。

我正在寻找一种有效的算法，该算法能够在双向 N*M 网格中找到尽可能随机的哈密顿路径。

有谁知道我在哪里可以找到，或者如何构建这样的算法？

我已经找到了一种有效的方法（见下图）。这里的最终结果是哈密顿循环。删除随机边将使其成为哈密顿路径。该算法是有效的，但没有提供足够的随机性。这种方法将始终使路径的起点和终点彼此相邻，而我希望它们位于随机位置。 空间填充曲线 http://img593.imageshack.us/img593/8060/sfc.png 图片取自http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type= pdf

我认为哈密顿循环问题可以概括为：

给定一个无向图G = (V, E)，哈密顿回路是一次G遍历每个顶点的G一次且仅一次。

现在，我想做的就是减少我的问题。我的问题是：

给定一个加权无向图G、整数k和 中的顶点u, v ，G是否有一条G从u到的简单路径v ，总权重至少为k？

所以知道哈密顿循环问题是NP完全的，通过将这个问题简化为哈密顿，这个问题也被证明是NP完全的。我的问题是将其简化为哈密顿量的功能。

1. 最大的问题是哈密顿问题不处理边权重，所以我必须将我的图转换为没有任何权重的图。
2. 最重要的是，这个问题有一个指定的开始和结束（u 和 v），而哈密顿量找到一个循环，所以任何开始都与结束相同。

对于（1），我正在考虑通过一个图表，其中所有总权重小于 k 的简单路径都被取出。对于（2），我认为这不是一个真正的问题，因为如果存在哈密顿循环，那么从 u 到 v 的简单路径可以从中切出。

所以，我真正的问题是：

1. 我的解决方案会给我正确的答案吗？
2. 如果是，那么我怎样才能取出将产生总重量小于 k 的简单路径的边缘而不影响实际解决方案可能需要这些边缘之一的可能性？因为如果一条边 e 被取出是因为它为 E 的一个子集产生了一个权重 < k 的简单路径，它仍然可以用于具有不同边组合的简单路径以产生一个权重 >= k 的路径。

谢谢！

给定一些单词，例如香蕉、猫、狗、大象、类型、中间、湖

找到一个序列使得

(1) 每个单词都在序列上

(2) 任何相邻的词不能有相同的字符。

如果找不到 seq，则返回 false。否则，返回 true 和 seq。

没有重复。没有单词的排列。

我的想法：

建立一个图，并使用哈密顿路径找到序列。

但是，它是一个NP完全。

如何避免哈密顿路径？

有更好的主意吗？

谢谢

我正在实现一种算法，该算法在有向图中找到最佳哈密顿路径。我已经实现了一个看起来运行良好的算法，但是我不完全确定在某些情况下是否存在细微的错误或其他问题。因此，我需要一些已知解决方案的不同网络，以检查我的实现是否也在按应有的方式解决它们。

由于 Wikipedia 暗示哈密顿路径只是无向图的适当术语，因此假设“哈密顿路径”是指在给定网络上访问每个节点一次且恰好一次的路径，无论是有向的还是其他的。

为简单起见，我们可以假设每个连接（或“边”）都有一个正整数值（或“长度”）。我们还可以假设没有节点与自身相连，并且在任何两个节点之间的每个方向上都不能有超过一条边。

我碰巧对总长度最长的路径感兴趣，因此“最佳”意味着最长，尽管如果我想要最短的总长度（如在传统 TSP 中），它可能没什么区别。我也碰巧使用了贪心算法。

我可以在哪里或如何获得已解决 TSP 的定向网络？如果实际解决方案和贪婪（或其他启发式）解决方案可用，那就更好了。网络应该足够大以进行信息测试，但足够小以供我手动检查解决方案（如果解决方案最初未知）。它们应该在拓扑上足够多样化，以涵盖“简单”和“有问题”的网络。

对于其他寻找相同的人；我最好的是以下网络：

这是一个邻接列表，行是边缘起点，列是终点。数字是每条边的长度，0 表示“无边”。例如，4 表示从D到A 的边的长度为 4，从A到D没有连接（长度为 0）。

该网络中的最大路径长度为 E->D->A->C->B。它的总长度是2+3+3+3=11。我相信贪心算法能够在这种情况下找到最佳解决方案，而且很明显它是最好的解决方案。

我有一个随机的无向社交图。

如果可能的话，我想找到一条哈密顿路径。或者如果不可能（或者不可能在多项式时间内知道是否可能）一系列路径。在这个“路径系列”（所有 N 个节点只使用一次）中，我想最小化路径的数量并最大化路径的平均长度。（因此单个节点的 N 条路径没有平凡的解决方案）。

我已经为节点和边生成了一个邻接矩阵。

有什么建议么？指向正确方向的指针？我意识到这将需要启发式方法，因为问题的 NP 完全（？）性质，我可以接受“足够好”的答案。我也想在Java中做到这一点。

谢谢！

从昨天开始我就被这个问题困住了。不幸/幸运的是，这个问题只占我的超级巨大（对我来说，一个 c++ 新手）算法的 0.5%，因此需要一个现有代码库，一个人可以适应并让事情正常工作。

我想检测并给出无向图中的所有圆圈。我的边缘没有加权。是的，我真正需要的是所有循环，即类似于有向图的所有哈密顿循环

我一直在玩 boost 图形库，DFS 算法似乎很有前途，但是，它只访问顶点一次，因此不能给出所有的哈密顿圆。

目前，我只需要代码工作，这样我就可以继续我的算法设计，之后我可能会考虑性能问题。甚至欢迎使用 5 嵌套 for 循环的解决方案。

这是我从 boost 中获得并使用的代码，但我不知道如何记录和访问我的 back_edges 前辈，即使解决了，boost DFS 也只会访问一次顶点：

上面的例子说通常只有 3 个循环，我预计会超过 4 个，单个顶点可能会出现在多个循环中。其次，我什至无法back_edge()像这样访问 boost 给我的所有三个周期std::vector<uInt32> fCycle1, fCycle2,fCycle3。我得到back_edge()的只是源顶点和目标顶点。

我将不胜感激任何帮助和提示。到目前为止，这里的所有示例都只是检测循环的存在或其数量，但没有一个示例显示如何列出所有存在的循环。

该算法解决了哈密顿路径问题。G是一个无向图，v起始顶点， G.size()图的大小，G.get(v).gV当前顶点的所有邻居顶点。

我可以说这个算法的复杂度是 O(n!) 吗？