Dynamic programming: optimal binary search tree

Question

Well, I hope someone can explain it to me. I am participating in the finals and I can’t understand anything.

The problem is dynamic programming; building an optimal binary search tree (OBST). I understand dynamic programming in general and the concepts of this problem in particular, but I do not understand the recursive form of this problem.

I understand that we are building optimal binary search trees for a growing subset of these nodes and storing the answers in the table as we move in order to avoid recalculation. I also get that when you are a root tree in a_ {k}, all successful nodes from a_ {1} through a_ {k-1} together with their corresponding fictitious unsuccessful nodes (that is, leaves of the tree) are in the left subtree, and then in the right subtree there is a_ {k + 1} through a_ {n}.

Here's a recursive form of an equation that I don't understand:

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

where w (i, j) = q (i) + the sum from i + 1 to j (q (l) + p (l)).

So, in c (i, j), from left to right, we have the cost of the left subtree + the cost of the right subtree + the probability of a successful search root + w (i, k-1) + w (k + k).

My confusion is how c (i, k-1) differs from w (i, k-1).

The text is the computer algorithms of Horowitz, Sahni and Rajasekeran, but I also read CLRS on OBST and searched the Internet, and nothing that I came across explains the difference between these parts of the equation well.

Answer 1

c (i, j) represents the expected cost of finding the optimal binary search tree containing the keys ki, ..., kj. w (i, j) is the sum of the probability of a subtree containing the keys ki, ..., kj. For the formula:

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) represents the cost of the left subtree if the key k is selected as the root. c (k, j) + w (k, j) represents the value for the right subtree. p (k) is the value for root k.

Note: if you select the key k as the root, then the left subtree contains the keys ki, ..., k (k-1), and the right subtree contains the kyes k (k + 1), ..., kj. But we cannot simply say that:

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

Since when we select the key k for the root, the generated subtrees have their depth added by 1. Thus, c (i, k-1) + w (i, k-1) will be the right value for the left subtree!

Answer 2

This is a subtle way to calculate the frequency * depth for a node at a specific depth.

Each time a node is evaluated as a root by summing its left (or right) subtree, you add a sum of frequencies to increase the depth of all children.

For example, suppose nodes "A", "B", and "C", where "A" is the root, "B" is the left child of "A", and "C" is the remaining child from "B". (There are no right kids to make things simple.)

In the reverse order, with the leaf 'C' as root:

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

with 'B' as root:

 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 

And finally, with 'A' as root:

 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