1

N 個のノードと N-1 個のエッジを持つツリーがあります (ツリーになります)。各ノードには重み W(i) があります。元のツリーのルートをまだ含んでいるサイズ K ノードのサブツリーをどのように選択できますか? この「サブツリー」を選択する「コスト」を最小限に抑えるために、これを行う必要があります。コストは、保持されるすべてのエッジの重みの合計として定義されます。

私は以前にこのような問題をやったことがあると思います.DP/再帰のようです. ただし、ノードごとに 2 つの子に制限されている場合の対処方法を知っています。ノード n から始まる i ノードを維持するための最小コストを意味する関数 cost(n, i) を定義しました。子の 1 つで i = 0 から n まで反復し、残りを他の子に渡します。ただし、各ノードは無制限の数の子を持つことができるため、これに対処する方法はありますか?

ありがとう

4

2 に答える 2

2

特定のノードについて、その子のcost（n、i）を使用してcost（n、i）を計算する必要があります。0..Kから子に番号を付けると、別の動的プログラムがあります。ステージjでは、子0..jのみを使用して、可能な限り最良のコスト（n、i）のセットを計算します。

機械学習をいじくり回しながら、このようなコーディングを考えていました（楽しみのために、1つではなく2つのWeka分類子をフィッティングして異常を探すプログラムを作成したいと思います）。それはあなたの目的のようなものですか？

于 2012-10-12T19:19:10.670 に答える
0

DPソリューション（mcdowellaが説明したものと似ている場合と似ていない場合があります）：

ルート ノードの番号を 0 にします。残りのノードには任意に番号を付けることができます (ただし、ノードにレベルごとに 1 つずつ番号を付けるのが最善の方法です)。

f(i, j)i より大きいインデックスを持つすべての兄弟ノードと、該当する場合は子ノードを考慮した場合の最小コストを示し、有効なノードから j 個のノードを選択します。

f(i, 0) = 0            // i can be anything, even NOT_FOUND
f(NOT_FOUND, j) = +Inf // j > 0
f(i, j) = min(f(x, j), // Node i not chosen
              min[r = 0 to j - 1] (f(x, j - 1 - r) + f(y, r)) + cost(i))
              // Node i is chosen, then we can pick some elements from 
              // children node, or from untouched sibling nodes + descendants

どこ

  • xiは 、ノードxおよびiは兄弟ノードである よりも大きい最小のインデックスです。
  • yは最小のインデックスです。ここで、ノードyはノード i の子です。
  • NOT_FOUND が割り当てられx、yインデックスが見つからない場合。

結果は になりますf(0, K)。

于 2012-10-12T20:59:00.433 に答える