頂点 - 離散パスの最大カバーを見つける

Question

各ノードに重み付き有向グラフがあると仮定します。任意の2つのノード間のパスの重みは、パス内のすべてのノードの合計と、そのパス内のノードの数を掛け合わせたものとして定義されます。

このカバー内のすべてのパスの重みの合計が最大である頂点 - 離散パスカバーを探したいとします。

これはNP問題です。この問題を解決するアルゴリズムはありますか？または、この問題を軽減する問題がありますか？

Answer 1

O（3^nポリ（n））時間アルゴリズムがあります。手順は次のとおりです。

1. パスに配置できるすべての頂点のセットを検索します。
2. 得られたセットパッキングの問題を解決します。

ステップ1は、（a）パス内の頂点のセット（b）、パス内の最初の頂点からなるペアによってインデックスされる動的プログラムによって実行されます。ステップ2は、動的プログラムによっても達成され、テーブルの頂点のセットは、そのサブグラフ上の不連続なパスによって達成可能な最大値にマッピングされる。ステップ1

再発は今PようIsPath（P、V）中のVが存在することPは、すべてのセットを収集

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). 

あります。これらの各パスのスコアを計算します。

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).