algorithm - 如何找到图中最长的简单路径？

Question

我知道对于非定向图，这个问题是 NP 完全问题，因此我们应该使用蛮力来检查所有可能的路径。我们如何做到这一点？请提供一个伪代码并告诉我该算法的复杂性。

如果有优化，那就太棒了!

Answer 1

天真的方法可以遍历所有可能的顶点排列。

对于每个排列 {v1, ..., vN}，您检查是否可以从 v1 到 v2，然后从 v2 到 v3 等。如果可以，将相应的边长添加到当前路径长度。如果不是，则转到下一个排列。

最长的路径就是您的答案。

---

或者，您可以使用递归做几乎相同的事情。

path = 0
bestPath = 0
used = new bool[N] // initialize with falses
for(u = 0; u < N; u++)
    Path(u); // build paths starting from u
print bestPath

在哪里

Path(u)
    used[u] = true
    foreach v in neighborhood(u)
        if(!used[v])
            path += distance(u, v)
            bestPath = max(bestPath, path)
            Path(v)
            path -= distance(u, v)
    used[u] = false

时间复杂度是可怕的 O(N * N^N)。