在多项式时间内找到哈密顿路径的可能解决方案
Possible solution to find a Hamiltonian path in polynomial time
我最近在想一个可能的解决方案，在多项式时间内找到无向图是否有哈密顿路径。
作为此实现的一部分使用的主要概念基于我注意到的观察
试图找到（即在纸上）几个无向图的哈密顿路径。
步骤定义如下：
读取图的邻接矩阵。
在读取邻接矩阵时，将为所有节点创建映射（即基于字典的结构）。此外，路径的起始节点将被选择，而邻接矩阵
正在阅读。这些操作可以描述如下：
2.1。地图将存储图中的所有节点，作为键值结构。
映射中的每个条目将表示为：（键：节点索引，值：节点class）
节点class将包含节点的以下详细信息：节点索引、事件数
它的边缘，以及一个标志来指示当前节点是否已经被访问过。
考虑到映射中的每个条目都只包含值
对应于该节点，可以说对于给定节点从映射的任何读取访问
索引将是常量（即 O(1)）。
2.2。作为在步骤 2.1 中读取邻接矩阵和构建地图的一部分，开始
节点也将被保留。路径的起始节点将由以下节点表示
有最少数量的边缘入射到它。
如果具有此属性的图中存在多个节点，则索引最低的节点
号码将被选中。在这种情况下，我们可以假设每个节点都有一个索引
与其关联，从零开始：0、1、2 等
在步骤 2.2 中识别的起始节点。将被标记为已访问。
接下来的操作将针对剩余的节点进行。循环将在以下时间结束
访问的节点数等于图中的节点数，或者当没有
已找到当前节点未访问的相邻节点。
因此，接下来的步骤将作为此循环的一部分进行：
4.1。第一个操作将是找到下一个要访问的节点。
要访问的下一个节点必须遵守以下约束：
- 与当前节点有边
- 到目前为止还没有访问过
- 与其他相邻节点相比，有最少数量的边缘入射到它
到当前节点。
4.2。如果没有找到下一个节点，则算法将结束并指示没有
发现了哈密顿路径。
4.3。如果找到下一个节点，则这将代表当前节点。会标明
as visited，并且访问的节点数将递增。
如果访问的节点数等于图中的节点数，则哈密顿量
已找到路径。无论哪种方式，都会根据算法的结果显示一条消息。
实施/测试可在 GitHub 上获得：https://github.com/george-cionca/hamiltonian-path
我的主要问题是：
- 是否存在导致此算法无法生成正确解的无向图？
- 在存储库的页面上，我包含了一些更多的细节，并声明此实现提供了二次时间的解决方案（即 O(n2)）。在时间复杂度上有没有我没有考虑到的方面？
算法不保证找到正确答案
据我了解，你的算法是启发式贪心算法。也就是说，路径从度数最低的顶点开始，路径继续朝向度数最低的未访问顶点（或与未访问节点的边最少的顶点）。
如果度数最低的顶点不是正确的顶点，则此操作失败。
例如，考虑一个具有单个顶点 v1 的图，该图通过两条边连接两个大型完整图。然后我们有连接到 v2 和 v7 的顶点 v1，我们有顶点 {v2, v3, v4, v5, v6} 和 {v7, v8, v9, v10, v11}，两个集合都完全连接。
哈密顿路径肯定存在，因为我们可以覆盖一个集群，移动到另一个并清除那个集群。但是，你的算法会从v1开始，找不到路径。
解名题的笔记
哈密尔顿路径问题是 NP-完全的，您一定会注意到。当您提出多项式时间算法来解决问题时，正确性意味着您已经证明了 P=NP。这是极不可能的。当你似乎已经证明了一些著名的未解决的问题并且被广泛认为是错误的时，我建议稍微降低你的期望，并寻找你可能犯的错误，而不是寻找算法是否有效的验证。在这种情况下，您可能已经查看了算法的隐含假设（例如最低度数的顶点是有效的起点）并试图为这种直觉想出一个反例。
我最近在想一个可能的解决方案，在多项式时间内找到无向图是否有哈密顿路径。
作为此实现的一部分使用的主要概念基于我注意到的观察 试图找到（即在纸上）几个无向图的哈密顿路径。
步骤定义如下：
读取图的邻接矩阵。
在读取邻接矩阵时，将为所有节点创建映射（即基于字典的结构）。此外，路径的起始节点将被选择，而邻接矩阵 正在阅读。这些操作可以描述如下：
2.1。地图将存储图中的所有节点，作为键值结构。
映射中的每个条目将表示为：（键：节点索引，值：节点class）
节点class将包含节点的以下详细信息：节点索引、事件数 它的边缘，以及一个标志来指示当前节点是否已经被访问过。
考虑到映射中的每个条目都只包含值 对应于该节点，可以说对于给定节点从映射的任何读取访问 索引将是常量（即 O(1)）。
2.2。作为在步骤 2.1 中读取邻接矩阵和构建地图的一部分，开始 节点也将被保留。路径的起始节点将由以下节点表示 有最少数量的边缘入射到它。
如果具有此属性的图中存在多个节点，则索引最低的节点 号码将被选中。在这种情况下，我们可以假设每个节点都有一个索引 与其关联，从零开始：0、1、2 等
在步骤 2.2 中识别的起始节点。将被标记为已访问。
接下来的操作将针对剩余的节点进行。循环将在以下时间结束 访问的节点数等于图中的节点数，或者当没有 已找到当前节点未访问的相邻节点。
因此，接下来的步骤将作为此循环的一部分进行：
4.1。第一个操作将是找到下一个要访问的节点。
要访问的下一个节点必须遵守以下约束：
- 与当前节点有边
- 到目前为止还没有访问过
- 与其他相邻节点相比，有最少数量的边缘入射到它
到当前节点。
4.2。如果没有找到下一个节点，则算法将结束并指示没有 发现了哈密顿路径。
4.3。如果找到下一个节点，则这将代表当前节点。会标明 as visited，并且访问的节点数将递增。
如果访问的节点数等于图中的节点数，则哈密顿量 已找到路径。无论哪种方式，都会根据算法的结果显示一条消息。
实施/测试可在 GitHub 上获得：https://github.com/george-cionca/hamiltonian-path
我的主要问题是：
- 是否存在导致此算法无法生成正确解的无向图？
- 在存储库的页面上，我包含了一些更多的细节，并声明此实现提供了二次时间的解决方案（即 O(n2)）。在时间复杂度上有没有我没有考虑到的方面？
算法不保证找到正确答案
据我了解，你的算法是启发式贪心算法。也就是说，路径从度数最低的顶点开始，路径继续朝向度数最低的未访问顶点（或与未访问节点的边最少的顶点）。
如果度数最低的顶点不是正确的顶点，则此操作失败。
例如，考虑一个具有单个顶点 v1 的图，该图通过两条边连接两个大型完整图。然后我们有连接到 v2 和 v7 的顶点 v1，我们有顶点 {v2, v3, v4, v5, v6} 和 {v7, v8, v9, v10, v11}，两个集合都完全连接。
哈密顿路径肯定存在，因为我们可以覆盖一个集群，移动到另一个并清除那个集群。但是，你的算法会从v1开始，找不到路径。
解名题的笔记
哈密尔顿路径问题是 NP-完全的，您一定会注意到。当您提出多项式时间算法来解决问题时，正确性意味着您已经证明了 P=NP。这是极不可能的。当你似乎已经证明了一些著名的未解决的问题并且被广泛认为是错误的时，我建议稍微降低你的期望，并寻找你可能犯的错误，而不是寻找算法是否有效的验证。在这种情况下，您可能已经查看了算法的隐含假设（例如最低度数的顶点是有效的起点）并试图为这种直觉想出一个反例。