如何在圖表中找到最長的簡單路徑？

我知道，對於非有向圖，這個問題是NP完全的，因此我們應該使用Brute Force來檢查所有可能的路徑。我們如何做到這一點？請建議一個僞代碼，並告訴我該算法的複雜性。如何在圖表中找到最長的簡單路徑？

如果有優化，那就太棒了！

2014-02-19 Narek

你必須加上額外的限制。否則路徑是無限的... – hivert

每個頂點只包含在路徑中的一個 - 是一個簡單的路徑。 – Narek

僅僅因爲它是NP完全並不意味着你應該使用暴力。當然，在最壞的情況下，你不能（比已知的）做得比指數時間更好，但是最壞的情況是罕見的，並且舉幾個例子，帶有數千個子句和變量的3-SAT實例以及數千個TSP實例的城市通常得到解決，顯然不是蠻橫的。 – harold

naïvem方法可以貫穿所有可能的頂點排列。

對於{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)。

來源

2014-02-19 12:46:46 AlexD

這是瑣碎的蠻力解決方案。 –

很好如何修改DFS做這個蠻力？ – Narek

@BasSwinckels當然。但是這個問題說：「我們應該採取暴力行動來檢查所有可能的路徑，我們該如何做到這一點？」。所以我聽說強力是好的。 – AlexD

如果你的圖是在它的定向和非循環一個特殊的情況下，你可以做一個動態規劃方法，如一個描述here。您基本上對拓撲圖進行排序，然後按拓撲順序對每個節點V進行檢查，如果它大於已經記住的「距離」（使用-infinity或其他屬性初始化），則檢查其所有鄰居並更新其「距離」值。

否則，在一般情況下，問題確實是NP完全的，因爲它減少到哈密爾頓週期。你可以做的一件事是否定所有的邊緣，並嘗試Bellman-Ford算法。但是，請注意，這對於負面循環不利。

來源

2014-02-19 12:49:08 webuster

如何在圖表中找到最長的簡單路徑？

回答

相關問題