0

给定 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'
4

1 回答 1

1

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

失败的例子：

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

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

解决方案：

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

于 2014-04-08T07:02:23.370 回答