问题标签 [hamiltonian-cycle]

我想在大型（50 多个节点）图上测试我最近创建的算法。优选地，它们将特别具有挑战性的图，并且将存在已知的游览（至少对于其中的大多数）。

这个问题的问题集似乎不像 TSP 那样容易找到。我知道弗林德的挑战集可在http://www.flinders.edu.au/science_engineering/csem/research/programs/flinders-hamiltonian-cycle-project/fhcpcs.cfm

然而，他们似乎是被指挥的。我可能可以更改我的算法以适用于定向，但这需要时间并且可能会引发错误。我想知道它是否可以首先用于无向。

有谁知道哪里有问题集？谢谢你。

快速编辑：

现在我不确定弗林德的布景是否是定向的……它没有说。示例使它看起来可能实际上是无向的。

所以我被赋予了这项任务，我不知道如何使用有关成本的信息。这是要求，我没有其他信息。

我正在使用一个统一的成本网格，它只允许在正交方向上移动。这被用作游戏蛇的基地，蛇必须不断移动并尝试吃板上的苹果。食物的定位和防撞是使用经典的 AStar 算法完成的，以找到蛇头和食物之间的最短路径。然而，这种方法有时会导致蛇去寻找食物，导致它没有明确的路径去下一个食物。蛇最终卡在一个不规则形状的矩形中，此时没有未来的模拟。

我的问题是：有没有办法在不规则矩形内找到最长的移动链，以便最长地存活，并可能让蛇的尾巴停止阻挡通往下一个食物的路径？我查看了 Hamilton Algorithms 以尝试访问所有节点，但似乎没有针对不规则形状的解决方案。解决方案不一定是完美的，但它应该始终尝试让蛇有最好的机会从陷阱中逃脱。

有什么想法吗？

我发现这个算法只显示一个哈密顿循环，但我需要在无向图中打印所有哈密顿循环。

这是我尝试使用的代码：https ://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/

有人可以帮我实施吗？此外，这段代码向我展示了所有的汉密尔顿路径： http ://www.techiedelight.com/print-all-hamiltonian-path-present-in-a-graph/

对于一个完整的无向图 G，其中顶点由 索引[n] = {1,2,3,...,n} where n >= 4。我知道 G 中哈密顿回路的总数是(n-1)! / 2

1. 如果我们必须穿过边缘{1,2}，有多少个哈密顿回路？
2. 如果多个连续的边，例如{1,2} {2,3}必须被遍历呢？
3. 如果多个非连续边，例如{1,2} {3,4}必须被遍历怎么办？

直观地说，对于第 1 部分，答案似乎是，(n-2)! /2但我并不完全确定。对于其他部分，我完全被难住了。

任何帮助深表感谢！

我需要编写一个代码来判断一个循环是否是汉密尔顿。

首先我有两个文本文件：

1.file ：第一行包含顶点和边的数量，其余的是一对连接的两个顶点。像 0 1 表示这两者之间有一条边。

2.file：带有数字（顶点）的行，我们需要检查它是否是汉密尔顿循环。

首先，如何在没有无向循环的情况下写下图表？因为我无法得到它，所以它给了我错误。

正如我所尝试的：

第二个问题：

你如何检查循环是否是汉密尔顿？首先我打算检查它是否真的是一个循环，然后如果是，然后检查顶点是否只出现一个。
我还应该做些什么来获得我的答案、建议或更简单的方法吗？

谢谢你的回复。

我知道这是一个冗长的问题:) 我正在尝试在 Scala 2.11 中的数据集上实现哈密顿循环，作为其中的一部分，我正在尝试从值映射生成邻接矩阵。

解释：

键 0 到 4 是不同的城市，所以在下面的“allRoads”变量中

我需要生成adj Matrix，例如：如果城市是连接的，我需要生成1，否则我必须生成0，意思是

输入-

我的代码：

输出：

预期输出 - 像这样的东西，请建议是否有更好的东西来生成哈密顿循环的输入

不确定如何将上述输出存储为 Map 或 Plain 2D Array。

我必须使用邻接矩阵运行所有美国城市（我们给定的地图中的 41 个）。用户必须键入原点节点，然后算法必须运行所有美国城市，然后返回原点。

我的问题是：算法运行所有节点，但不返回原点。他只是停在最后一个节点。谢谢您的帮助

我已经制定了一个在网格图中查找哈密顿循环的工作算法。但是，我实施的方法包括递归检查所有可能的组合，直到找到正确的组合。这在小图（如 6*6）上很好，但在大图上变得太慢了，我需要找到 (30 * 30) 的循环。

在 main 中，我初始化了一个 2D 整数向量，表示出图 ( board)，并将其初始化为 -1。-1 表示该空间尚未“填充”，而高于该值的值表示它们在循环中的位置（0 - 第一个单元格，1 - 第二个单元格等）。我使用初始化一个 Vector2f（SFML 的向量处理方式，与标准库中的对相同），我用它来步进所有可能的状态。并且我还初始化了路径整数，这将在以后有所帮助。最后我调用了Hamiltionan循环查找算法（HamCycle()）。

然后我hamCycle()检查pos向量是否超出网格，如果是则返回 false。否则我给这个单元格路径的值，然后增加。我检查算法是否完成，是循环还是路径。如果是路径，则返回 false。然后我递归地检查它周围的单元格并重复这个过程。

现在它在已经阻塞出口的情况下花费大量时间检查所有可能的路径，这是无效的。我该如何改进这一点，所以检查大网格是可行的？就像不检查是否有阻塞的出口一样，但是如果您知道任何其他改进方法，请告诉我。

您好，我是answer-set-programming 的新手。我过去做了一点prolog！我正在尝试解决这个问题，我相信它可以用hamiltonian-cycle解决，让我知道你的意见。如果您不熟悉 ASP，您可以访问此站点 [clingo 和 gringo][1]。您可以使用此命令在终端中运行文件，clingo name_of_the_file.lp或者clingo name_of_the_file.lp4我在 Ubuntu 中对其进行了测试。

（这些是 .lp 或 .lp4 文件）我阅读并理解的第一个代码是具有 3 个结果的代码

我得到这个结果：

我试图将此代码转换为：

这似乎有点尴尬我得到了这个结果：

我试图纠正它，就像你在评论中告诉我的那样：

我得到了这个结果：

（如果我把node(1..6). 结果是UNSATISFIABLE）