2

アルゴリズムには次の入力があります。

各ノードに重みが関連付けられている、サイクルのないグラフG（スパニングツリーとも呼ばれます）。

S次のような独立集合を見つけたいと思います。

  • Sのエッジを形成する2つの要素はありませんG
  • 上記の条件を満たすサブセットは他にありません。その場合、S[0] + S[1] + ... + S[n-1] （ここでlen(S)==n）よりも大きな重みがあります。

これは私がこれまでに持っている高レベルの擬似コードです：

MaxWeightNodes(SpanningTree S):
    output = {0}
    While(length(S)):
        o = max(node in S)
        output = output (union) o
        S = S \ (o + adjacentNodes(o))
    End While
    Return output

誰かが私がエラーを犯したかどうか、またはこのアルゴリズムが私に望む結果を与えるかどうかを教えてもらえますか？

4

2 に答える 2

5

初期最大値の隣接ノードを除外することが最良のローカルソリューションである可能性があるが、最良のグローバル決定ではない場合にすぐに直面するため、アルゴリズムは無効です。

例output = []：

        10
      /    \
   100      20
   /  \    /  \
  80  90  10   30

output = [100]：

         x
      /    \
     x      20
   /  \    /  \
  x    x  10   30

output = [100, 30]：

         x
      /    \
     x      x
   /  \    /  \
  x    x  10   x

output = [100, 30, 10]：

         x
      /    \
     x      x
   /  \    /  \
  x    x  x    x

より良い解決策があることはわかっていますが。

これは、最適な部分構造がなくても、欲張りアルゴリズムを使用していることを意味します。

于 2013-03-25T04:07:00.010 に答える
2

頂点の重みが貪欲な解決を難しくしていると思います。すべての重みが等しい場合は、ツリーのレベルのセットを選択してみることができます（これは、完全なk-aryツリーで明らかに最も簡単ですが、スパニングツリーは通常そのクラスに分類されません）。貪欲な近似では、レベルを結合された重みを持つものと考えると便利な場合があります。これは、ツリーの同じレベルのすべての頂点（ルートする頂点に関係なく）をいつでも選択して、同じ独立に入ることができるためです。セットする; 同じレベルの2つの頂点の間にエッジを置くことはできません。これは私には難しい問題のように思われるので、私は解決策を提供していません。主な問題は、重みと、満木を扱っているとは想定できないという事実にあるようです。

編集：実際には、ルーベンスの例が視覚化に役立つため、常に1つのレベルのすべての頂点を選択することも悪い考えのようです。彼の木の右側の2番目のレベルの頂点の重みが200であると想像してください。

于 2013-03-25T05:44:12.177 に答える