问题标签 [hamiltonian-path]

我正在与协和飞机合作解决 TSP 问题。这是我的代码

协和飞机已正确安装在我的系统上并且工作正常。当我运行 concorde_help() 时，我得到以下输出

这表明协和飞机安装正确。但是，当我尝试运行 R 代码（在顶部给出）时，有时我会得到答案，而有时我的程序会卡住。当程序执行成功时，我得到以下输出

在上述输出中，最优解为 0.00。谁能告诉我为什么这是零？有时代码不执行并给出以下输出

在这个输出之后，什么都没有发生，程序似乎进入了一个无限循环。谁能告诉我我做错了什么？

是我系统的错吗？我正在使用 Windows 10 和 R-studio 64 位开发核心 i3 系统。

编辑：这是我正在使用的数据集

编辑2：这是会话信息

我有一个问题，我需要显示路径中包含的所有节点（从源到目标），但是我们只访问路径中的每个节点一次。仅使用 DFS（并标记已访问元素）的解决方案不够快。有人告诉我使用关节点，但我不知道该怎么做。你能帮助我吗？

谢谢。

我有一个包含 n 个顶点的完整有向图。边的权重为 0-1（即，它们的权重可以为 0 或 1）。1 权重边也是稀疏的，即不存在权重超过 n/2 的哈密顿路径。问题是找到没有。从 0 到 n/2 的每个 k 的 k 权重哈密顿路径。

https://www.youtube.com/watch?v=3xeYcRYccro&list=PLoJC20gNfC2gmT_5WgwYwGMvgCjYVsIQg&index=32

12:10 指出该示例是汉密尔顿路径。这是一个说明汉密尔顿路径不能生成汉密尔顿图的例子。事实上，所有顶点都被红线覆盖。汉密尔顿路径是一次接触所有顶点。使满意。如果我们从右上到右下添加一条边，我们会不会有一个汉密尔顿循环。然后我们可以从一个顶点开始，运行所有其他 3 个并从头开始完成。一次。为什么不是汉密尔顿循环。

我最近在考虑一种可能的解决方案，可以在多项式时间内找到无向图是否具有哈密顿路径。

作为这个实现的一部分使用的主要概念是基于我在试图找到（即在纸上）几个无向图的哈密顿路径时注意到的观察。

这些步骤可以定义如下：

1. 读取图的邻接矩阵。

2. 在读取邻接矩阵时，将为所有节点创建一个映射（即基于字典的结构）。此外，在读取邻接矩阵时，将选择路径的起始节点。这些操作可以描述如下：
   
   

   2.1。map 将存储图中的所有节点，作为键值结构。

   映射中的每个条目将表示为：（键：节点索引，值：节点类）

   节点类将包含有关节点的以下详细信息：节点索引、它的事件边数以及指示当前节点是否已被访问的标志。

   考虑到映射中的每个条目将只包含与该节点对应的值，可以说从映射中对给定节点索引的任何读取访问都是恒定的（即 O(1)）。
   
   

   2.2. 作为在步骤 2.1 读取邻接矩阵和构建地图的一部分，起始节点也将被保留。路径的起始节点将由与其关联的边数最少的节点表示。

   如果图中存在多个具有此属性的节点，则将选择具有最低索引号的节点。在这种情况下，我们可以假设每个节点都有一个与之关联的索引，从零开始：0、1、2 等。
   
   

3. 在步骤 2.2 中确定的起始节点。将被标记为已访问。

4. 其余节点将遵循下一个操作。当访问节点的数量等于图中的节点数量时，或者当没有找到当前节点的未访问的相邻节点时，循环将结束。

   因此，接下来的步骤将作为此循环的一部分进行：
   
   

   4.1。第一个操作是寻找下一个要访问的节点。

   下一个要访问的节点必须遵守以下约束：

   • 拥有当前节点的边
   • 到目前为止还没有访问过
   • 与当前节点的其他相邻节点相比，具有最少数量的边缘。
     
     

   4.2. 如果未找到下一个节点，则算法将结束并指示未找到哈密顿路径。
   
   

   4.3. 如果找到下一个节点，则这将代表当前节点。它将被标记为已访问，并且访问节点的数量将增加。
   
   

5. 如果访问节点的数量等于图中的节点数量，则已找到哈密顿路径。无论哪种方式，都会根据算法的结果显示一条消息。

GitHub 上提供了实现/测试：https ://github.com/george-cionca/hamiltonian-path

我的主要问题是：

1. 是否有无向图会导致该算法无法生成正确的解决方案？
2. 在存储库的页面上，我包含了更多细节，并指出此实现提供了二次时间的解决方案（即 O(n ² )）。有没有我没有考虑到时间复杂度的任何方面？

我目前在业余时间从事一个项目，我需要检查图中是否存在哈密顿路径，但是，路径开始或结束的位置无关紧要，只有一个存在于图中。

我在这里从另一个用户那里复制了这段代码：

显然有一个起始值的参数。现在我的第一个直觉是迭代函数并为每个起始顶点运行它，但由于我将在具有 100 多个顶点的图上运行它，因此需要很长时间才能完成。我真的不需要知道通过所有顶点的路径是什么，我只需要知道存在一个是否有帮助。

我将如何调整它以提供任意起始位置？

Ultra-Hamiltonian 自行车被定义为一种封闭的步行，它只访问每个顶点一次，除了最多一个顶点访问不止一次。

问题：- 证明确定给定图是否包含超哈密顿循环是 NP 难的。

我们可以从哈密顿循环问题中减少它，这是一个 NP 难题，但我没有从哪里开始将它减少到超哈密顿循环问题。

你能告诉我这样做的方法吗？

我最近在CodeBullet的 Snake AI 视频中发现了 Hamiltonian Path/Circuit，并决定亲自尝试一下。我编写了一个基本的深度优先搜索算法来访问图中的所有节点并在电路完成时存储路径。

下面是算法的伪代码：

这个实现在理论上是可行的，因为它确实为我提供了一个 6x6 及以下网格的解决方案，但问题是，它非常慢。在视频中，它甚至无法为 8x8 网格提供解决方案，并提到这是一种非常快速的算法，因为他已经计算了 50x50 网格的哈密顿电路，所以它也显示出来了。

我真的很想知道如何加快速度，因为我确信我的初学者技能不足以指出一些你可能很容易看到的明显缺陷。任何帮助表示赞赏。

我试图证明以下主张：

给定 DAG 图，如果以下算法返回 true，则存在 Hamilton 路径：

1. 进行拓扑排序。
2. 一个一个地移动图形的顶点（从低到高）。如果没有边连接 2 个顶点与拓扑排序中的相邻值，则返回 false。如果我们检查所有顶点后没有返回 false，则返回 true。

我无法证明一方面是：如果存在汉密尔顿路径，则算法返回真。

我尝试对图n中的顶点数使用归纳法：

• 对于 n==0，基本情况很简单。

• 假设声明对于 n 是正确的，我想证明 n+1

所以我说，让我们排除给定 Hamilton 路径中的最后一个顶点（我们称之为 a），并假设算法返回错误。

这意味着以下两种之一：

1. 具有相邻值的两个顶点没有连接它们的边，并且都不是 a。这与该主张适用于具有 n 个顶点的图的假设相矛盾。

2. 两个顶点之一是a，另一个不是a。

我坚持证明案例（2）会给我们带来矛盾，我该如何继续？

我正在尝试通过一系列所需的总成本或总边长来计算哈密顿路径，即访问图中每个节点一次的路径。旅行推销员问题有多种算法可以计算最短路径，但我还没有找到一个按所需总成本计算的解决方案。

结果，我采用了适用于少数节点的蛮力解决方案，但无法计算出我拥有的 50 个节点。

请注意，我还返回了标准偏差，因此我可以按所需的游览长度和最低标准偏差进行过滤（以在节点之间获得大致相等的距离），例如：

用例是一个城市游戏，我想为参与者提供一些等距的个性化路线，以避免他们混合（Covid-restrictions）。路线的总长度取决于游戏的持续时间，因此需要按总成本进行过滤。

是否有任何算法或解决方案允许这种类型的计算，或者是否有可能提高我的代码的效率，使其在合理的时间内为 50 个节点工作？