如何找到有向無環圖的最大獨立集？

假設我們有一個類似於鏈表（或有向無環圖）的圖。一個獨立的集合由不與集合中的任何其他節點共享邊的節點組成。如果每個節點都是加權的，我們如何計算獨立節點集的最大可能值？我知道我們必須使用動態編程，所以我有一點線索，但我希望有人能解釋他們將如何處理它。謝謝！如何找到有向無環圖的最大獨立集？

來源

2014-10-19 Sticky

我認爲這個問題對於任意有向無環圖是NP難的。已知無向圖的相應問題是NP-hard，並且可以通過以使得所得圖形成爲DAG的方式引導所有邊來將該問題轉換爲問題的定向版本。原始圖中的任何獨立集都將成爲有向圖中的獨立集合，反之亦然，因此任何針對有向情形的解決方案都將解決無向情況。

你的問題是關於在鏈表上解決這個問題的。如果您只是爲鏈表解決問題，那麼使用動態編程就有一個多項式時間解決方案。作爲提示，如果您在鏈接列表中選擇一個節點，則必須跳過下一個節點，然後應該最大化剩下的部分。如果您不選擇節點，那麼只需最大化其餘列表的值即可。充分利用這兩個選項並評估這種自下而上的方法會給你一個非常快速的DP算法。

希望這會有所幫助！

來源

2014-10-19 22:01:48 templatetypedef

謝謝！我試圖用一棵樹想象，但我認爲你的解釋是比我的樹更重要的解決方案... – Sticky 2014-10-19 22:24:13

只是好奇，這會提供一個線性運行時間嗎？由於它會緩存到基本情況，並且每次我們做一個子問題時，我們都會將它存儲在某個表中，從而創建持續的檢索時間，並執行n次。（因此是線性的？） – Sticky 2014-10-20 01:29:03

@Sticky Yep，這是一個線性時間解決方案！ – templatetypedef 2014-10-20 05:35:38

如何找到有向無環圖的最大獨立集？

回答

相關問題