找到最大頂點不交疊路徑覆蓋

Question

假設我在每個節點上都有一個帶有權重的有向圖。任何兩個節點之間的路徑權重定義如下：路徑中所有節點的總和乘以該路徑中節點的數量。

我們想要找到一個頂點不相交的路徑覆蓋，該覆蓋中所有路徑的權重總和最大。

我知道這是一個NP問題。有沒有解決這個問題的算法？或者有什麼問題可以減輕這個問題嗎？

Answer 1

有一個O（3^n poly（n））時間算法。步驟是

1. 查找可以排列在路徑中的所有頂點集。
2. 解決由此產生的集合打包問題。

步驟1是通過一個動態程序來完成的，該程序的表格由包括（a）路徑頂點集合（b）路徑中第一個頂點的一組索引組成。步驟2也是通過動態程序完成的，其中一個表格將頂點集合映射到該子圖上不相交路徑可達到的最大值。

復發爲步驟1是

IsPath({v}, v) = true (for all vertices v) 
IsPath(S, v) = exists w in S - {v} such that v->w is an arc and IsPath(S - {v}, w) (for all sets of vertices S, for all v in S). 

現在收集所有組P，使得在P所在v的IsPath（P，V）。計算每條路徑的得分。

BestCover({}) = 0 
BestCover(S) = max Score(P) + BestCover(S - P) over all P subset of S such that P is a path (for all nonempty S).