问题标签 [hamiltonian-cycle]

不久前，作为概念证明（并且因为我和自闭症儿子一起使用 Logo），我在 Logo 中编写了一个程序，使用回溯方法在图中（如果存在）找到哈密顿回路。我使用的基本回溯模式是：

你可以在这里看到一个讨论。OUTPUT我可以在 Logo 中轻松地做到这一点，因为它允许使用命令从函数中获得多个退出点。

但是，Racket 不允许多个退出点（至少，不容易）。所以我希望指出一些材料的方向，这些材料可以解释（a）如何管理一个函数的多个退出点（我有一个模糊的概念，我可以用延续来做到这一点，如let/ec）或（b）如何以更适合该语言的方式管理 Racket 中的递归回溯。

作为 Racket 的新手，我相信这可以由专家在眨眼间完成，甚至可以由比我更初级的任何人完成。但现在我为自己感到困惑。谢谢！

我有 fun1 电话foo1()，需要O(n^6 + m^4). 你觉得时间复杂度是fun1多少？我的猜测是它会是O(2n^6 + m^4)！

fun2 还调用 foo2()，它需要 O(n^3 + m^2)。你觉得 fun2 的时间复杂度是多少？我的猜测是 O(n^3 + m^2 + 2n^2) ！

我对吗？

给定一个有向图，什么是只访问图的每个顶点一次的算法。这与哈密顿循环不同，因为我不需要在同一顶点开始和结束的路径。

回溯算法 想到的一种算法是回溯，它使用递归实现，在每一步中，您都探索所有可能的连接/路径，并保留一个布尔访问数组，以确保不会多次访问顶点。向后回溯时，此布尔值将设置为 false（回溯中的基本步骤）。基本情况是比较访问顶点的数量，并查看它是否与图中的节点数匹配，在这种情况下，它将返回 true。如果尚未访问所有顶点，但不存在其他连接以继续递归，则另一个基本情况将返回 false。

但是，这样做的时间复杂度O(n!)是不可取的。

有没有更好的算法来找到有向图的路径/遍历，它恰好覆盖图中的每个顶点一次。

我的问题：找到从节点A到节点的最短路径，该路径B通过未加权直接图的所有其他节点。我知道存在这样的路径。

我相信这是 NP-Hard，但我无法解释。我的教授喜欢让算法在 的运行时执行O(|V| + |E|)，其中V是节点E集和边集。

好像和这个问题差不多，但是Graph的属性不一样，有区别吗？

我正在寻找一些正确方向的建议/指导。

我的要求是生成一个图表，而不是解决一个解决方案。

我正在寻找一种算法来生成一个只有 1 个哈密顿循环的图（NxN 网格）。请注意，只有一种独特的解决方案至关重要。该图将是一个 NxN 节点网格，每个节点只有 4 个相邻节点，即顶部、右侧、底部、左侧。节点只能访问一次。除此之外，还可以有一些特殊的节点。

1. 死节点，即它们没有边缘连接
2. 固定入口和出口节点，即入口和出口节点已经定义，没有其他节点可以与给定节点连接。它可以是一个。相邻节点 b. 直节点

一些例子：

我的方法：

我采用*n 网格并首先在图表上放置随机死节点。在此之后，我放置随机的特殊节点。然后我运行一个遍历整个网格的 dfs 搜索，以查看是否存在满足特殊节点条件的有效循环，并且只访问每个节点一次（起始节点除外）并在起始节点处结束，使其成为一个完整的循环。

我的问题：

我在这里要问的是如何确保图表只有 1 个有效循环。我可以做的一件事是通过在每个循环之后添加更多死节点和特殊节点来递归迭代级别，直到有效哈密顿循环的数量减少到一个。这就是我计划实施的。

你会如何理想地解决这个问题？

我最近一直在开发一个类来查看给定的无向图有一个哈密顿循环。我发现了这篇有趣的文章
http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/。

我已经相应地开发了我的代码。但问题是算法无法返回哈密尔顿循环。

图.java：

Hamiltoninan.java：

有人可以指出问题出在哪里以及如何解决问题。

谢谢，卡尔蒂。

我已经完成了自己的研究，但是我找不到适合我需求的解决方案。

问题是，我有一辆卡车需要花费它的负载（比如说垃圾）。有 city(node) 和 edges(way) 可以是正边或负边。虽然卡车采取一种方式，但它可能会松动或必须获得更多（浪费）取决于所选方式（边缘）。如果它选择了正边沿，它会丢失与选择的方式值完全相同的浪费量。反之亦然。

因此，卡车司机必须走一定的步数（无论边缘的值如何，每一步都需要一个恒定的时间）并且司机有有限的时间回到他的家（原点）（时间将是一个给定的参数）

所以在这个图中，我们有节点，我们有一个方向的边，这条边可以有负值或正值，并且在图中可以有允许驱动程序使用或不使用的循环。并且节点可以用不同的边相互指向。（从 A 到 B 边缘 val 是 5 ）（从 B 到 A 边缘 val 是 -3 等等..）

所以我想给司机最好的办法，在最短的时间内用尽最大的负荷。

所以，问题是这样的。

我想要的是，注意实际的代码。

如果您知道可以指定的问题的名称，不客气。如果您想用伪代码或文字分享您自己的算法。也欢迎你。如果您想分享一个您认为有类似问题的链接。也欢迎你。

如果您认为无法解决。请分享您的想法或证明的链接。

提前致谢。

我SimpleGraph在 JGraphT 中有一个，想知道是否有

1. 哈密​​顿路径

2. 哈密​​顿循环

如果存在，我也想得到它。

我只发现TwoApproxMetricTSP和HamiltonianCycle。

但两者都需要完整的图表。

一个明显的解决方案是在我的图中添加边，并使其成为加权图，添加边的权重如此之高，以至于它们不会在路径中使用。

但这会增加很多边缘，我想避免。

有没有更好的方法来获得哈密顿路径/循环而不自己实现算法？

我正在尝试用机票解决旅行推销员问题，所以主要想法是从一个机场开始，只访问所有机场一次，然后返回原点。

例如：从 LAX 出发访问 LV、CA、NY 结束 LAX。

这是一个经典的图问题，我们可以将机场表示为节点，将路线表示为边，价格作为边权重。

所以这是最简单的部分，真正让我困惑的是用户希望旅行的日期。例如，我想让用户选择他/她希望旅行的日期，比如从 01 开始到 15 结束。所以我想找到一种最便宜的方式来做到这一点。例如输出将是这样的：

01 - LAX - LV; 04 - LV - CA; 08 - CA - NY; 15 - NY - LAX

所以我知道我可以在边上添加额外的属性，但问题是算法将如何区分如何遍历图形，例如不选择过去权重最小的边。

所以你可以看到我有两条边从 CA 出来（注意边的格式是 DD - 价格，01 - 20 表示日期的第一个和成本 20），以及当多个边相同时如何处理这种情况节点存在。

它也可以被视为三维图，其中第三维是用户旅行的日期。所以主要问题是如何处理这些日期？

希望我明白了，任何建议表示赞赏

提前感谢。

我正在尝试做很多编程练习来理解概念并通过解决它们来获得实践经验。

我偶然发现了一个练习，它给出了一组关于图形是什么样子的条件，并要求你找出哈密顿循环是否可能，如果有，打印出一个可能性。

由于该练习使用的是我的母语，因此我已尽我所能翻译，内容如下：

假设有一个图形G=(V,E)，具有顶点数V和边数E。我们将N(v)表示为连接到 v 的顶点集。一个顶点的相邻顶点的数量称为 rank，我们用rank(v)表示它。

如果图形 G 是 conex 并且对于图形的每个顶点都满足以下条件，我们说图形 G 很奇怪：

1. 等级(v)>=2
2. 如果rank(v)=2则其他两个顶点不通过边相互连接。
3. 如果rank(v)>2则 v 的相邻顶点集合存在一个顶点u ( u ∈ N(v) )，所以以下性质为真： I. Rank(u)=2 AND II。v的相邻顶点的每隔两个不同的顶点(w1,w2 ∈ N(v)-{u} )相互连接，因此(w1,w2) ∈ E。

需要解决的每个图都被认为是一个“奇怪的”图。

如何解决这个问题？您需要借助条件大大减少计算时间，但我想不出用它们搜索哈密顿循环的技巧/模式。提前致谢。