20091019


Dynamic Programming

Based on the two examples discussed so far, we discussed the dynamic programming paradigm.  Developing a DP solution to an optimization problem always follows the same sequence of steps:

Design stage (these usually happen in parallel rather than separately):
1. Prove that the problem obeys the Principle of Optimality.
2. Determine a way to represent the optimal solution as a parameterized function.  That is, create a notation for the solution.  (In the case of the grid problem, we used something like S(a,b) = minimum cost of getting to the intersection of row a and column b.  For the rod-cutting problem, we used something like OptVal(n) = maximum value obtainable from a rod of length n.)
3. Determine a recurrence relation that defines an optimal solution in terms of a combination or selection from the optimal solutions to a limited number of subproblems.

Algorithm Structure:
4. Solve the subproblems in either a top-down or bottom-up order (usually bottom-up), storing the results in a table (i.e. matrix) or other suitable data-structure.
5. If the details of the optimal solution are needed, trace back through the table to extract them.

Dynamic Programming algorithms all tend to look very similar, and are usually very low in computational complexity.  Most of the hard work is done in the design phase - coding the algorithm is usually trivial.


The Principle of Optimality is easily stated:  Every part of an optimal solution must itself be optimal.

What it means is that we can construct an optimal solution to the problem using only optimal solutions to subproblems - we don't need to find or keep non-optimal solutions to any subproblems.  Since Dynamic Programming algorithms only remember optimal solutions to subproblems, we can see immediately why the P of O is essential for a successful DP solution to a problem.

Consider our first example: the problem of finding the shortest (least-weight) path through a grid where all horizontal edges point to the right, and all vertical edges point down.  To show that this problem satisifes the P of O, consider any optimal solution S.  We need to show that each part of S is optimal.  We do this with a simple Proof by Contradiction argument (this is the proof technique of choice for this part of the Dynamic Programming algorithm design process).

Suppose some part of S is not optimal.  This non-optimal part must be a path joining some intersection A to another intersection B.  The non-optimality of this path implies that there is a better (ie. lower-weight) path from A to B.  Due to the structure of the grid, this path from A to B cannot use any edges "before" A or any "after" B - so it cannot touch any other part of S.  So we could cut out the part of S that joins A to B, and replace it with the better A-B path.  This will give a complete path from the top-left to the bottom-right corner of the grid, with a lower cost than S.  But this means S is not optimal, which is impossible.  Thus our supposition that some part of S is not optimal must be incorrect, and we conclude that each part of S must be optimal.  

Therefore this problem does satisfy the Principle of Optimality.



We next looked at a well-known optimization problem called the 01-Knapsack Problem.

In this problem, we are given a set of n objects, each with a known mass and a known value.  We also have a knapsack with a limited mass capacity k.  Our goal is to select a subset of the objects such the value of the subset is maximized and the total mass of the subset does not exceed the knapsack's capacity.

First, let us make sure that this problem satisfies the principle of optimality.  Suppose that some optimal solution O*contains an object i.  This object takes up some amount of the knapsack's capacity - and the remainder of the O* must consist of a selection from the remaining objects that fits within the reduced capacity.  Clearly, if the solution to this reduced problem contained within O* is not optimal, then we could replace it with a better solution to the subproblem, and get a new full solution that has a greater value than O*.  But that contradicts the optimality of O*, so it cannot be possible.  Therefore the solution to the reduced problem contained within O* must be optimal, and the Principle of Optimality is satisfied.

We can consider the process of describing a solution to this problem as a sequence of decisions:  do we take the first object, or not?  Then, do we take the second object, or not?  Etc.  This is a very effective way of characterizing the solution to the problem, and it fits very well with the dynamic programming technique.  At each stage of this implicit decision-making process there are only two choices, each of which leads to a single subproblem.  Since we don't know beforehand which choice we should make for each object, we solve both of them.

Now if we take any particular item, we gain its value but we are left with less capacity in the knapsack.  On the other hand if we do not take the item, we gain no value but we have not used up any of the knapsack's capacity.  From this observation, we can quickly derive the appropriate recurrence relation:

If we let KS(i, x) represent the value of an optimal solution, choosing items from the set {0, ..., i} to fit in a knapsack of size x, we see that KS(i,x) obeys the following ...

    KS(0,x)          = 0, if mass of object 0 is > x                                                    // these are the
                          =  value of object 0, otherwise                                                  // base cases

    KS(i,x) = KS(i-1, x), if mass of object i > x
                = max{value of object i  + KS(i-1, x - mass of object i),                    // take object i
                            KS(i-1, x)                                                                            // don't take object i
                          }


Using this recurrence, we can solve all the subproblems of the form K(i,x) for all values of i in the range (0 .. n-1) and for all values of x in the range (0 ... k)

We can store all of these solutions in a simple 2-dimensional table.  The final entry in the table gives the value of the optimal solution.  We can trace back through the table to get the details of the optimal solution in the usual way: we determine which of the two possible choices led to the optimal value, and step back to that subproblem, then repeat.  

The complexity of this algorithm is easily seen to be O(n*k).

The interesting thing about this problem is that it is a generalization of the Subset Sum problem, which we know is NP-Complete.  That suggests very strongly that our algorithm does not run in polynomial time ... but O(n*k) looks like it is polynomial.  What's the catch?

The key observation here is that k is not a constant: it is part of the input, and there is no upper bound on its value.  Thus it is entirely possible that k = 2^n, in which case the complexity of our algorithm is exponential.  Thus we cannot guarantee that the algorithm runs in polynomial time in all cases.

However, for "reasonable" values of k, this algorithm works very well.