DAGの最小重量k-closure

問題

与えられた

  • (接続された)DAG $ G(V、E)$各ノードには(負でない)整数が割り当てられます 体重
  • 整数kここで$ 0 leq k leq | V | $

$ G $の$ H $の部分グラフを$ k $ verticesからなる

  • 頂点が$ H $にある場合、その頂点はすべて$ H $(= closure?)にもあります。
  • $ H $内のすべての頂点の重みの合計が最小になります

可能なアルゴリズム

この問題を解決する簡単なアルゴリズムは、サイズ$ k
$の頂点のすべての部分集合をループし、最初の条件が成立するかどうかをチェックすることです。もしそうなら、重みの合計が現在の最良のものよりも小さいかどうかをチェックする。このアルゴリズムは$
O(V×V!)$です。大きなグラフの場合、これは非常に遅くなります。

より効率的なアルゴリズムはありますか?

私は、空のセットから始めることによって構築され、最初の条件がまだ保持される最小ウェイト頂点を追加する欲張りアルゴリズムを考えました。このアルゴリズムは必ずしも正しい結果を出すとは限らない。

Edit: An example

weights: vertex 1:weight 6, 2:4, 3:3, 4:4, 5:1, 6:3, 7:6, 8:7, 9:1, 10:4
connections: 1->3, 2->3, 2->4, 3->5, 3->7, 4->6, 4->8, 5->7, 6->8, 7->9, 8->9, 8->10

$ k = 4
$の場合、欲張りアルゴリズムは合計重み17を持つ{1,2,4,6}を返し、{1,2,3,5}は合計重み14を返します。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です