如何在圖形問題中應用並行編程？

Question

問題描述：

有n tasks，並且在這些任務，one might be dependent on the others，這意味着如果A是依賴於B，那麼B必須是一個被完成之前結束。

1.找到一種方法儘快完成這些任務？

2.if take parallelism into account，如何設計程序來完成這些任務？

問：

顯然，回答第一個問題是，拓撲排序這些任務，然後完成它們的順序。

但是如果考慮到並行性，該怎麼做？

我的回答是，第一拓撲排序這些任務，然後選擇那些獨立的任務，首先完成它們，然後選擇在休息結束那些獨立的...

我說得對不對？

Answer 1

拓撲排序算法可能會給你各種不同的結果順序，所以你不能只取前幾個元素，並假定它們是獨立的。

而不是拓撲排序我建議通過傳入依賴邊的數量來排序您的任務。所以，例如如果你的圖有A→B→A→C→B→C→D→C，你可以將它排序爲A [0]，D [0]，B [1] ，C [3]其中[i]是進入邊的數量。

通過拓撲排序，你也可以得到A，B，D，C。在這種情況下，發現可以並行執行A和D並不容易。

請注意，在任務完成處理後，您必須更新剩餘的任務，特別是依賴於完成的任務的任務。但是，如果進入某個任務的依賴關係的數量限制在相對較小的數量上（比如幾百），那麼可以很容易地依賴諸如radix/bucket-sort之類的東西，並保持排序結構在不變的時間更新。

通過這種方法，您可以在完成單個並行任務後輕鬆啓動新任務。只需更新依賴項計數，並啓動現在有0個傳入依賴項的所有任務。

請注意，此方法假定您具有足夠的處理能力來處理同時無依賴關係的所有任務。如果您的資源有限，並且在處理時間方面關心最佳解決方案，那麼您將不得不投入更多的努力，因爲問題變爲NP難（正如已經提到的那樣）。

所以要回答你的原始問題：是的，你基本上是正確的，但是，你沒有解釋如何有效地確定這些獨立的任務（見上面我的例子）。

Answer 2

我會嘗試在任務執行時間作爲邊緣權重的情況下將它們排序在定向森林結構中。爲了從最重到最輕的樹木訂購，並從最重的開始。使用這種方法，您可以同時檢查循環依賴關係。

使用並行性，你會得到bin問題，這是NP難。嘗試尋找針對該問題的近似解決方案。

Answer 3

看一下Critical Path Method，取自project management。它基本上滿足你的需求：給定具有依賴性和持續時間的任務，它會產生多少時間，以及何時激活每個任務。

（*）請注意，此技術假設無限數量的資源以獲得最佳解決方案。對於有限的資源，有貪婪算法的啓發式算法，例如：GPRW [當前+任務時間之後]或MSLK [最小total slack時間]。 （*）另請注意，它需要了解[或至少估計]每項任務需要多長時間。