有序圖中最長的路徑

設G =（V，E）爲有節點v_1，v_2，...，v_n的有向圖。如果G具有以下屬性，我們說G是一個有序圖。有序圖中最長的路徑

每條邊都從具有較低索引的節點進入具有較高索引的節點。也就是說，每個有向邊都具有（v_i，v_j）的形式。
除v_n之外的每個節點都至少有一條邊離開它。也就是說，對於每個節點v_i，至少有一個形式邊（v_i，v_j）。

給出一個有效的算法，該算法採用有序圖G並返回從v_1開始到v_n結束的最長路徑的長度。

如果你想看到漂亮的乳膠版本：here

我嘗試：

動態規劃。 Opt（i）= max {Opt（j）} + 1.對於所有j，這樣的j可從i到達。

有沒有更好的方法來做到這一點？我認爲，即使記憶我的算法仍然是指數。（這是從我在網上找到的一份舊期中期評論中得到的）

來源

2014-11-06 user2079802

你的做法是正確的，你將不得不做

Opt(i) = max {Opt(j)} + 1} for all j such that j is reachable from i

然而，這是唯一的指數，如果你沒有記憶化運行。通過記憶，當您在節點i上時，您將獲得每個節點j，j> i的記憶最優值。

對於最壞情況的複雜性，讓我們假設每兩個可連接的節點都連接在一起。這意味着，v_1與(v_2, v_3, ... v_n)連接; v_i與(v_(i+1), v_(i+2), ... v_n)連接。頂點

號（V）= N

因此，邊緣（E）= n*(n+1)/2 = O(V^2)

讓我們把注意力集中於一個頂點v_k的數量。對於這個頂點，我們必須通過(n-k)節點的已經導出的最優值。

到達v_k直接=（K-1）

因此最壞情況下的時間複雜度=>sigma((k-1)*(n-k)) from k=1 to k=n，其是功率2多項式作的Σ，並且因此將導致O(n^3)時間複雜度的方式的數量。

簡單地說，最壞情況下的時間複雜度爲O(n^3) == O(V^3) == O(E) * O(V) == O(EV)。

來源

2014-11-07 03:26:29

由於第一個屬性，這個問題可以用O（E）來解決O（V^2）甚至更好，其中V是頂點的數量， E是邊的數量。事實上，它使用的動態編程方法與您提供的方法非常類似。讓opt [i]是v_1到v_i的最長路徑的長度。然後

opt[i] = max(opt[j]) + 1 where j < i and we v_i and v_j is connected, 
         using this equation, it can be solved in O(V^2).

更好的是，我們可以用另一種順序解決這個問題。

int LongestPath() { 
    for (int v = 1; v <= V; ++v) opt[v] = -1; 
    opt[1] = 0; 
    for (int v = 1; v <= V; ++v) { 
    if (opt[v] >= 0) { 
    /* Each edge can be visited at most once, 
     thus the runtime time is bounded by |E|. 
     */ 
     for_each(v' can be reached from v) 
     opt[v'] = max(opt[v]+1, opt[v']); 
    } 
    } 
return opt[V];

}

來源

2014-11-07 03:14:40

有序圖中最長的路徑

回答

相關問題