python - 哈密​​尔顿循环 python 错误答案

Question

给定 n 作为节点数和边数作为边列表

谁能告诉我我的代码有什么问题。它适用于某些情况，但不适用于所有情况

for edgeindex in range(len(edges)):
    alltrue = [True]*(n)
    visited = [False]*(n)
    S = []
    start = edges[edgeindex][1]
    visited[start] = True
     S.append(start)
     nex = start
     for edgeindex2 in edges[edgeindex:]:
         if edgeindex2[0] != nex:
             continue
         if visited[edgeindex2[1]] == False:
             visited[edgeindex2[1]] = True
             S.append(edgeindex2[1])
             nex = edgeindex2[1]
         if visited == alltrue:
             return 'yes'
return 'no'

Answer 1

您的代码是一种贪婪的方法，并将它可以行进的下一个边缘添加到您的路径中。然而，这种贪心方法不适用于哈密顿路径问题(它是 NP 完全问题，因此没有已知的“有效”解决方案...)

失败示例:

G = (V,E), V = {1,2,3}, E = {(1,3),(1,2),(2,3)}

现在，假设您从 1 开始，首先经过 (1,3)。此时你已经完成了，你找不到哈密顿路径。但是，路径 1->2->3 存在，您将找不到它。

解决方案:

求解哈密顿路径的最简单方法是生成所有可能的permutations ，并检查它们中的任何一个是否形成哈密顿路径。有更高效(和复杂)的解决方案 - 但它们也需要指数级的运行时间。