5

わかりました、誰かが私にこれを説明してくれることを願っています。決勝に向けて勉強しているのですが、何かがよくわかりません。

問題は動的計画法です。最適な二分探索木 (OBST) を構築します。私は一般的に動的計画法を理解し、特にこの問題の概念を理解していますが、この問題の再帰的な形式は理解していません。

これらのノードのサブセットの増加に合わせて最適なバイナリ検索ツリーを構築し、再計算を避けるために、テーブルに答えを保持していることがわかります。また、a_{k} でツリーをルート化すると、a_{1} から a_{k-1} までの成功したすべてのノードと、それに対応する架空の失敗したノード (つまり、ツリーの葉) が左のサブツリー、右のサブツリーのサブツリーは a_{k+1} から a_{n} までです。

私が理解していない方程式の再帰的な形は次のとおりです。

c(i, j) = min (i < k <= j) {c(i, k-1) + c(k, j) + p(k) + w(i, k-1) + w(k +j)}

ここで、w(i, j) = q(i) + i+1 から j までの合計 (q(l) + p(l))。

したがって、c(i,j) では、左から右に、左のサブツリーのコスト + 右のサブツリーのコスト + ルートの検索が成功する確率 + w(i, k-1) + w(k +j) になります。

私の混乱は、c（i、k-1）がw（i、k-1）とどのように異なるかです。

テキストは Horowitz、Sahni、および Rajasekeran による Computer Algorithms ですが、OBST で CLRS を読んだり、オンラインで検索したりしましたが、方程式のこれらの部分の違いをうまく説明するものは見つかりませんでした。

4

2 に答える 2

8

c(i,j) は、キー ki、...、kj を含む最適な二分探索木を探索する予想コストを表します。w(i,j) は、キー ki, ..., kj を含むサブツリーの確率和を表します。式の場合：</p> 

c(i, j) = min (i < k <= j) {c(i, k-1) + c(k, j) + p(k) + w(i, k-1) + w(k,j)}

c(i,k-1)+w(i,k-1) は、キー k をルートとして選択した場合の左側のサブツリーのコストを表します。c(k,j)+w(k,j) は、右側のサブツリーのコストを表します。p(k) はルート k のコストを表します。

キー k をルートとして選択すると、左側のサブツリーにはキー ki, ..., k(k-1) が含まれ、右側のサブツリーにはキー k(k+1), ..., kj が含まれます。 . しかし、次のように単純に言うことはできません。

c(i,j)=min (i < k <= j) {c(i, k-1) + c(k, j) + p(k)}

ルートのキー k を選択すると、生成されたサブツリーの深さが 1 追加されるためです。したがって、c(i,k-1)+w(i,k-1) が左サブツリーの正しいコストになります!

于 2012-12-15T15:56:14.960 に答える
2

これは、特定の深さでノードの頻度*深さを計算する微妙な方法です。

ノードがルートとして評価されるたびに、その左 (または右) サブツリーを合計しながら、頻度の合計を追加して、すべての子の深さを増やします。

たとえば、ノード「A」、「B」、および「C」を想定します。ここで、「A」はルート、「B」は「A」の左側の子、「C」は「B」の左側の子です。（物事を単純化する権利のある子供はいません。）

リーフ 'C' をルートとするボトムアップ方式:

cost is Pr(C) = freqC*1  (no children)

'B' をルートとして:

cost = Pr(B) + Cost[C,C] + sum of children freq 
     = freqB*1 + freqC*1 + freqC*1
     = freqB*1 + freqC*2 

where Pr(B) = freqB*1
     Cost[C,C] = freqC*1
     sum of children freq = freqC*1

そして最後に、「A」をルートとして:

cost = Pr(A) + Cost[C,B] + sum of children freq 
     = freqA*1 + freqB*1 + freqC*2 + freqB*1 + freqC*1
     = freqA*1 + freqB*2 + freqC*3

where Pr(A) = freqA*1
     Cost[C,B] = freqB*1 + freqC*2
     sum of children freq = freqB*1 + freqC*1
于 2015-04-16T21:02:59.747 に答える