如何找到在图形中最长的简单的路径？ [英] How to find the longest simple path in a graph?

问题描述

我知道，对于非定向图这个问题是NP完全问题，因此，我们应该做的蛮力，以检查所有可能的路径。我们怎样才能做到这一点？请提出一个伪code和告诉我那个算法的复杂性。

I know that for non-directed graph this problem is NP-complete hence we should do Brute Force in order to check all possible paths. How we can do that? Please suggest a pseudo code and tell me the complexity of that algorithm.

如果有优化，那么这将是真棒！

If there are optimizations, then that would be awesome!

推荐答案

一个naïvem方法可以通过一切可能的顶点排列运行。

A naïvem approach could run through all possible vertex permutations.

对于每一个排列 {V1，...，VN} 您检查您是否可以从 V1 到达 V2 ，然后从 V2 到 V3 等，如果您可以添加相应的边长为当前路径长度。如果没有，进入下一个排列。

For every permutation {v1, ..., vN} you check if you can get from v1 to v2, then from v2 to v3 etc. If you can, add corresponding edge length to the current path length. If not, go to the next permutation.

这样的路径最长的是你的答案。

The longest of such paths is your answer.

或者，你可以做pretty的大致使用递归一样的。

Or, you could do pretty much the same using recursion.

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）。

这篇关于如何找到在图形中最长的简单的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！