哈密尔顿循环 Python 错误答案

Question

给定 n 作为节点的数量，edges 是一个边的列表。

有没有人能告诉我我的代码哪里出问题了？它在某些情况下能正常工作，但并不是所有情况下都能运行。

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是存在的，但你却找不到它。

解决方案：

解决哈密顿路径问题最简单的方法是生成所有可能的排列，然后检查其中是否有形成哈密顿路径的排列。虽然还有更高效（但也更复杂）的解决方案，但它们同样需要指数级的运行时间。