如何在加權圖中找到權值總和最大的路徑？

我有一堆對象與級別，重量和0或更多的連接到下一個級別的對象。我想知道如何獲得「最重」路徑（具有最大權重總和）。如何在加權圖中找到權值總和最大的路徑？

我也很想知道，當然，什麼書教我如何應對以務實的方式曲線圖。

來源

2011-08-08 BrainStorm

關於這個圖，是你的路雙向的嗎？你提到的水平，你想從一個層次到另一個，或任何其他節點的任何節點獲得？ – Kratz

@Kratz，他們只有一個方向，因爲'level'是時間依賴......時間不會返回。 – BrainStorm

您的圖形是非循環嗎？（我認爲是這樣，因爲一個節點總是指向下一層的節點）。如果你的圖可以有任意週期，找到最大路徑的問題就變成了NP完全的，蠻力搜索就成爲唯一的解決方案。

回到問題 - 你可以通過查找，對每個節點，導致了它的最重的路徑解決這個問題。既然你已經有一個拓撲排序的DAG的（水平本身）是straighfoward找到路徑：

對於每個節點，存儲，導致它和之前的最後一個節點最重的路徑的成本在上述路徑上。Initialy，這始終是空的（但警戒值，像成本爲負數，可能會簡化代碼後）
在第一級別的節點，你已經知道，在他們結束最重的路徑的成本 - 它是零（與父節點是None）

對於每個電平，傳播路徑信息到下一級 - 這是類似於用於最短距離的正常ALGO：

for level in range(nlevels): 
    for node in nodes[level]: 
     cost = the cost to this node 
     for (neighbour_vertex, edge_cost) in (the nodes edges): 
      alt_cost = cost + edge_cost 
      if alt_cost < cost_to_that_vertex: 
       cost_to_that_vertex = alt_cost

來源

2011-08-08 23:52:03 hugomg

感謝您的啓發=] – BrainStorm

我的書的建議是史蒂夫Skiena的"Algorithm Design Manual"。圖表上有一個很好的章節。

來源

2011-08-08 23:38:52 duffymo

已經下載它=] – BrainStorm

我認爲你只能下降到圖中的較低水平。

注意圖形如何構成一棵樹。然後你就可以解決這個使用遞歸：

heaviest_path(node n) = value[n] + max(heaviest_path(children[n][0]), heaviest_path(children[n][1]), etc)

這可以很容易地通過使用動態編程，而不是進行優化。

從最低級別的孩子開始。他們的heaviest_path只是他們自己的價值。跟蹤這個數組。然後計算下一級的heaviest_path。然後下一個級別。等等。

來源

2011-08-08 23:46:31 tskuzzy

但他們沒有一個二叉樹，我說* 0個或多個*連接，通常2，3。6 – BrainStorm

@Brainstorm - 多數民衆贊成在'etc'是什麼 – hugomg

遍歷圖最常用的方法是使用深度優先搜索。如果您的圖形確實週期一旦你得到那些「最深切的路徑」就可以計算出它們之間的距離，你應該使用深度限制搜索，您可以指定一個深刻的門檻，避免stackoverflows

。

什麼像樣的書將覆蓋圖，但我真的建議Cormen's Introduction to Algorithms這裏筆者做了出色的工作，說明有關這些算法的詳細信息。

也有條目在維基百科上關於graph traversing

來源

2011-08-08 23:46:48

又會有怎樣的深度 - 第一次遍歷幫助解決這個問題？ –

我一般的方法用它來尋找「最重的」路徑是否定的權重，然後找到最短路徑。有好的算法（http://en.wikipedia.org/wiki/Shortest_path_problem）找到最短路徑。但是，只要您的原始圖形中沒有正向權重週期，此方法就可以保持良好狀態。

對於具有正加權週期的圖，找到「最重」路徑的問題是NP完全的，並且查找最重路徑的算法將具有非多項式時間複雜度。

來源

2011-08-09 00:00:07

如何在加權圖中找到權值總和最大的路徑？

回答

相關問題