Dynamic programming is a technique to efficiently compute recursively defined quantities. The recursion is typically with respect to some integer parameters.
We can also define such functions recursively on the nodes of a tree. The idea is to associate a value with each node that combines the values defined for each of its children—in some cases we may process the children in a fixed order. Analogous to regular dynamic programming, we can evaluate such a function bottom up. This is what we call dynamic programming on trees.
For instance, suppose we are given a tree with N nodes and a weight assigned to each node, along with a number K. The aim is to delete enough nodes from the tree so that the tree is left with precisely K leaves. The cost of such a deletion is the sum of the weights of the nodes deleted. What is the minimum cost to reduce to tree to a tree with K leaves?
Let D(v,k) denote the minimum cost to transform the subtree rooted at a vertex v to have precisely k leaves. Then, for any leaf node lv,
On the other hand, for any internal node v,
Suppose the children of a node v are w1,w2,…,wm. Clearly, the best possible answer, D(v,j), is obtained by taking all possible ways of distributing the j leaves among the m children 1…m and taking the minimum among those.
D(v,j) = | Minimum | Sum | D(wi,ji) | ||
j1+j2..jm = j | i |
This is not efficient as there are too many choices to be considered. However, we can use dynamic programming once again to compute D(v,j) (for j ≥ 1) by processing the children of j in a fixed order. For this, we need some additional definitions.
Let C(i,j) be the minimum cost of reducing the trees T(w1),…,T(wi) so that together they have j leaves.
C(i,0) = | Sum | Wt(T(wk)) | ||
k ≤ i |
C(i+1,j) = | Sum | C(i,j-k) + D(wi+1,k) | ||
k ≤ j |
If we want just one leaf below v, we can either delete all its children and make v a leaf, or retain exactly one leaf amongst the subtrees rooted at its children. This yields the following.
Finally, when we need more than one leaf, we cannot make v a leaf, so we need to prune the subtress below the children of v to generate j leaves between them. This gives us
We can now use the equations to compute D(v,j) for any value of j using dynamic programming.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky