5

頂点の重みがその次数であるツリーを扱う既存の質問がありますが、頂点が任意の重みを持つことができる場合に興味があります。

これは宿題ではありませんが、現在読んでいるアルゴリズム設計マニュアルの質問の 1 つです。回答セットは次のように解を与えます

  1. DFS を実行し、各ステップで Score[v][include] を更新します。v は頂点で、include は true または false です。
  2. v がリーフの場合、Score[v][false] = 0、Score[v][true] = w vを設定します。ここで、w vは頂点 v の重みです。
  3. DFS 中に、ノード v の最後の子から上に移動するときに、Score[v][include] を更新します。 Score[v][false] = Score[c][true] と Score の children(v) の c の合計[v][true] = w v + min(Score[c][true]; Score[c][false]) の children(v) の c の合計
  4. スコアをバックトラックして実際のカバーを抽出します。

ただし、実際にそれを機能するものに変換することはできません。（コメントへの回答：これまでに試したことは、「実際のカバーを抽出する」部分が透明ではないステップ4まで、重みを使用していくつかの小さなグラフを紙に描き、アルゴリズムを紙に実行することです。）

Aそれに応じて、アリの答え：だから、等によって与えられた頂点とその後のかっこ内の重みを持つこのグラフがあるとします：

A(9)---B(3)---C(2) \ \ E(1) D(4)

正解は明らかに{B,E}です。

このアルゴリズムを使用して、次のように値を設定します。

  • score[D][false] = 0;score[D][true] = 4
  • score[C][false] = 0;score[C][true] = 2
  • score[B][false] = 6;score[B][true] = 3
  • score[E][false] = 0;score[E][true] = 1
  • score[A][false] = 4;score[A][true] = 12

わかりました、それで、私の質問は基本的に、次は何ですか? 単純なことを実行し、scoreベクトルを反復処理して、ローカルで最も安いものを決定することは機能しません。あなただけを含めることになりBます。親に基づいて決定し、交互にすることも機能しません。の重みが の場合を考えてみましょEう1000。正解は{A,B}で、隣接しています。混乱させるべきではないかもしれませんが、率直に言って、私は混乱しています。

4

2 に答える 2

2

それは実際には混乱を招くことを意味するものではなく、ただの動的プログラミングであり、すべてのアルゴリズムをほとんど理解しているようです。もっと明確にしたいのなら、私は言わなければなりません：

  1. 最初にグラフで DFS を実行し、葉を見つけます。
  2. アルゴリズムが言うように、すべての葉に値を割り当てます。
  3. 葉から開始し、その式によって各葉の親に値を割り当てます。
  4. グラフのルートに到達するまで、すでに値を持つノードの親に値を割り当て始めます。

それだけです。アルゴリズムをバックトラックすることは、子がすでに値を持っている各ノードに値を割り当てることを意味します。上で述べたように、この種の問題を解くことは動的計画法と呼ばれます。

質問の変更を説明するためだけに編集してください。あなたは次のグラフを持っているので、答えは明らかにB、Eですが、このアルゴリズムはあなたにBを与えるだけで、あなたは間違っていますこのアルゴリズムはあなたにBとEを与えます.

A(9)---B(3)---C(2) \ \ E(1) D(4) 

score[D][false] = 0; score[D][true] = 4
score[C][false] = 0; score[C][true] = 2
score[B][false] = 6 this means we use C and D; score[B][true] = 3 this means we use B
score[E][false] = 0; score[E][true] = 1
score[A][false] = 4 This means we use B and E; score[A][true] = 12 this means we use B and A.

4 を選択すると、B と E を使用する必要があります。B だけの場合、答えは 3 になります。しかし、正しく見つけたので、答えは 4 = 3 + 1 = B + E です。

また、E = 1000 の場合

A(9)---B(3)---C(2) \ \ E(1000) D(4)

隣接するノードを選択したくないという理由だけで E を使用するのは間違っているため、答えが B と A であることは 100% 正しいです。このアルゴリズムを使用すると、答えは A と B であることがわかります。チェックするだけで、それも見つけることができます。これがカバーするとします：

C D A = 15
C D E = 1006
A B = 12

最初の 2 つの回答には隣接するノードがありませんが、隣接するノードを持つ最後の回答よりも大きくなっています。そのため、カバーには A と B を使用するのが最適です。

于 2014-12-17T07:00:59.483 に答える