循環圖中最長路徑問題的優化

循環圖中最長的路徑已知是NP完全的。什麼優化或啓發式算法可以比查找整個圖表更快地找到最長的路徑？有沒有任何概率方法？

我有一個具有特定質量的圖，但我在尋找一般情況下的答案。鏈接到論文將是太棒了。下面是部分答案：

確認它是循環的。非循環圖中最長的路徑很容易使用動態編程來計算。
找出圖表是否是平面的（哪種算法最好？）。如果是，您可能會看到它是塊圖，托勒密圖還是仙人掌圖，並應用this paper中的方法。
找出有多少個簡單的週期使用Donald B Johnson's algorithm（Java implementation）。您可以通過刪除簡單循環中的邊來將任何循環圖變成非循環圖。然後您可以運行the Wikipedia page上的動態編程解決方案。爲了完整性，您必須對每個循環執行N次，其中N是循環的長度。因此，對於整個圖表，您必須運行DP解決方案的次數等於所有周期長度的乘積。
如果必須DFS整個圖形，可以通過提前計算每個節點的「可達性」來修剪一些路徑。這種主要適用於有向圖的可達性是每個節點無需重複就可以到達的節點數量。這是來自該節點的最長路徑可能的最大值。有了這些信息，如果您當前的路徑加上子節點的可達性小於您已經找到的最長路徑，那麼採用該分支就沒有意義了，因爲您不可能找到更長的路徑。

2010-11-23 Craig Younkins

不（3 ）涉及到查找強連接組件？（http://en.wikipedia.org/wiki/Strongly_connected_component） - 如果沒有，我會認爲你可以對這些做些什麼。我發現Tarjans算法很容易理解。 – Steve314 2010-11-23 02:49:56

我真的不知道如何識別強連接組件或頂點收縮有助於解決LPP，但我可能是錯的。爲了強制它成爲一個非循環圖，我相信你需要簡單的循環（Johnson's），因爲強連通組件中可能還有循環。 – 2010-11-23 03:37:50

這裏是一個爲O（n * 2^n）的動態規劃方法，應該是可行的，最多說20個頂點：

m(b, U) =任何路徑的b結束並僅訪問最大長度（一些）U中的頂點。

最初，設置m(b, {b}) = 0。

然後，m(b, U) =最大的m(x, U - x) + d(x, b)在所有x在U使得x值不b和邊緣(x, b)存在。取所有端點的最大值b，其中U = V（全部頂點）。這將是任何路徑的最大長度。

下面的C代碼假設在d[N][N]中有一個距離矩陣。如果圖形未加權，則可以將此陣列的每次讀取訪問更改爲常量1。顯示最佳頂點序列（可能不止一個）的回溯也在數組p[N][NBITS]中計算。

#define N 20 
#define NBITS (1 << N) 

int d[N][N];  /* Assumed to be populated earlier. -1 means "no edge". */ 
int m[N][NBITS]; /* DP matrix. -2 means "unknown". */ 
int p[N][NBITS]; /* DP predecessor traceback matrix. */ 

/* Maximum distance for a path ending at vertex b, visiting only 
    vertices in visited. */ 
int subsolve(int b, unsigned visited) { 
    if (visited == (1 << b)) { 
     /* A single vertex */ 
     p[b][visited] = -1; 
     return 0; 
    } 

    if (m[b][visited] == -2) { 
     /* Haven't solved this subproblem yet */ 
     int best = -1, bestPred = -1; 
     unsigned i; 
     for (i = 0; i < N; ++i) { 
      if (i != b && ((visited >> i) & 1) && d[i][b] != -1) { 
       int x = subsolve(i, visited & ~(1 << b)); 
       if (x != -1) { 
        x += d[i][b]; 
        if (x > best) { 
         best = x; 
         bestPred = i; 
        } 
       } 
      } 
     } 

     m[b][visited] = best; 
     p[b][visited] = bestPred; 
    } 

    return m[b][visited]; 
} 

/* Maximum path length for d[][]. 
    n must be <= N. 
    *last will contain the last vertex in the path; use p[][] to trace back. */ 
int solve(int n, int *last) { 
    int b, i; 
    int best = -1; 

    /* Need to blank the DP and predecessor matrices */ 
    for (b = 0; b < N; ++b) { 
     for (i = 0; i < NBITS; ++i) { 
      m[b][i] = -2; 
      p[b][i] = -2; 
     } 
    } 

    for (b = 0; b < n; ++b) { 
     int x = subsolve(b, (1 << n) - 1); 
     if (x > best) { 
      best = x; 
      *last = b; 
     } 
    } 

    return best; 
}

在我的PC，這解決了與在範圍[0，1000）中隨機選擇的約7秒的邊權重20×完全圖，並且需要大約160MB（的一半是用於前身跡線）。

（請，沒有關於使用固定大小的數組的意見。在實際的程序中使用malloc()（或更好，但C++ vector<int>），我只是寫了這樣這樣的事情會更清晰。）

來源

2010-11-24 06:58:10

循環圖中最長路徑問題的優化

回答

相關問題