Notes #15 --- Dynamic Programming

Combinatorial Optimization Problems

We have considered three basic algorithm schemes in this course:

iterative algorithms (no decisions made in execution)
greedy algorithms (make the best choice at each step)
divide-and-conquer algorithms arising from inductive definitions

We want to consider optimization problems, in which we want a best solution out of a large set of possible answers to a particular problem instance. In particular, a combinatorial optimization problem is one in which the underlying search space includes all subsets, or all permutations, or a similar combinatorial object. Greedy and divide-and-conquer algorithms handle a few of these problems, generally those in some specialized form. When a problem can be solved by one of these, the solution is generally efficient, since each makes progress toward the eventual solution with each step.

Two other classes of algorithm which can be used for most optimization problems are the exhaustive algorithm scheme, which looks at all the possibilities and chooses the best one, and heuristics, which we will encounter in Artificial Intelligence.

Exhaustive algorithms are typically quite inefficient, since we will often do "useless" work, which we will later have to disregard --- in fact, in using data structures, we will actually have to retract work, a process called back-tracking.

Heuristics look at fewer than all possible solutions, but aren't guaranteed to find the best solution; in practical problems, this may be acceptable if we usually find a "good" solution (whatever that means). Greedy and divide-and-conquer methods may themselves be heuristics for problems which they cannot solve exactly.

This creates tradeoffs among generality (greedy and divide-and-conquer techniques are applicable only in limited cases), efficiency (exhaustive algorithms for combinatorial optimization problems often have exponential cost), and precision (heuristics are imprecise). We would of course like a general, efficient, and precise technique.

Dynamic programming is very nearly such a technique.

It applies precisely to a larger set of problems than greedy or divide-and-conquer techniques.
While it involves some backtracking, it also shares some features of greedy and divide-and-conquer algorithms; namely, each step obtains a precise optimal solution for some subproblem, and the solution for a large problem combines solutions for smaller parts.
Finally, dynamic programming can be used for non-optimization problems as a means of trading space for time, and can also be used as a heuristic for problems for which it does not necessarily provide an optimal solution.

The key notion

More-or-less, all dynamic programming algorithms rely on an encoding of states in an increasing linear way (although there are multidimensional analogues). Those we consider here will have an ordered set of inputs, and the subproblems we solve will handle a subinterval of those inputs. Basically, we can formulate a problem with dynamic programming if:

The problem has some sort of decomposition as a tree or graph structure, or as a recurrence.
When subtrees (subgraphs, etc.) are combined, the subtree must represent an optimal solution to some subproblem.
The additional cost of combining the subtrees into a solution for the problem at large is easily formulable and easily computable in terms of the nodes in the trees.

In a general tree-based dynamic programming algorithm with inputs 1, 2, ..., n, we create solutions for every possible subtree i..j. The general form of the algorithm is more-or-less as follows:

        determine the cost of the base cases Cost [ i, i ]
                  /* don't need to determine structure since it's usually trivial */
        for k = 1 to n-1 do
            for i = 1 to n-k do
               /* determine the cost for i .. i+k                            */
               /* record both the cost and the structure which gave the cost */
               /* remembering the root of each tree                          */
               /*     is sufficient to reconstruct the tree                  */
        Index_Set = i .. i+k	
        Cost [ i, i+k ] = min_{ r in Index_Set } { Cost [ i, r] + Cost [ r, i+k ] 
                                + Merge_Cost ( i, r, i+k ) }
        root [ i, i+k ] = the r which resulted in minimum cost
        reconstruct the tree using the root table

Notes

The set of base cases may differ in different algorithms, and include [ i, i+1 ] or even [ i, i-1 ]. This can affect the starting value for k.

Index_Set can have different boundary values, depending on the algorithm; for example, [ i+1, i+k-1 ]

More-or-less related to the way Index_Set is parametrized, the r indices may appear as r+1 or r-1

The nature of the Merge_Cost function is highly problem-dependent. However, for a number of problems, Merge_Cost will be independent of r, and can be factored out of the minimum computation

In case of ties, any minimizing r will do

The complexity of the dynamic programming algorithm without further optimization is O ( n^3 ) (times the complexity of the individual Merge_Cost operations). In general, we compute O ( n^2 ) best cases, and use O (n) of them in the final solution. Thus we do n times more work than we need. Compare this to the greedy algorithm, which does more-or-less exactly what it needs (but will not always be applicable), and the exhaustive algorithm, which will need to look at more than O ( 2^n ) trees.

Three Examples

List Merge

We wish to use repeated binary merges on a set of sorted lists L1, L2, L3, ..., Ln, each with known size ni, to obtain a single sorted list, with minimal merge cost. It should be clear that the cost of merging two lists L' and L'' is essentially the sum of their lengths. This problem has two variants, and illustrates nicely the difference between a greedy and a dynamic programming algorithm.

Variant I: the lists can be merged in any order. A greedy algorithm works: maintain a priority queue of trees, annotated with a size and a cost, and sorted by size (smallest first). Initially, each list is the root of its own tree, with cost 0. In each step (until there is only one tree), pop the two smallest trees T1 and T2, and create a tree T having a new root with children T1 and T2. Set the size of T to be the sum of the sizes, and the cost of T to be the sum of the costs and the sizes, and insert T in the priority queue.
Example: We have L1, L2, L3, L4, L5 with sizes 35, 60, 90, 140, 70.

The initial priority queue is

(L1,35,0),(L2,60,0),(L5,70,0),(L3,90,0),(L4,140,0)

Pop the first two trees, and get tree T1

L1 L2

and a new priority queue

(L5,70,0),(L3,90,0),(T1,95,95),(L4,140,0)

Now pop the next two

(T1,95,95),(L4,140,0),(T2,160,160)

and the next two

(T2,160,160),(T3,235,330)

and finally

(T4,395,885)

The tree is

T2 T3

L5 L3 T1 L4

L1 L2

Variant II: only adjacent lists can be merged. We now need to use dynamic programming.

[Much more to be added.]