Dynamic Programming

Both the Knapsack problem and Shortest Path problem, as noted in the previous section, can be solved with a greedy strategy. For many problems, it is not possible to make stepwise decisions (based on only local information) in such a manner that the sequence of decisions made is optimal. (Consider Example 5.4 -- shortest path and the optimality of the first "greedy" choice in the whole solution.)

See Examples 5.1 - 5.13 in text for an illustration of taking the knapsack and shortest path problems and adapting them to more difficult problems with combinatorial solutions hence requiring a sequence of decisions.

Some of the notes below are from George Washington University's Algorithms course . You may want to look at some of these notes and homeworks for more examples of problems and solutions. Note that, as I had mentioned in class, it really doesn't matter what instructor or book you use. The content of this course is pretty much consistent.

• Dynamic programming is an optimization technique.

• Greedy vs. Dynamic Programming :
  • Both techniques are optimization techniques, and both build solutions from a collection of choices of individual elements.

  • The greedy method computes its solution by making its choices in a serial forward fashion, never looking back or revising previous choices. (Only one decision sequence is ever generated.)

  • Dynamic programming computes its solution bottom up by synthesizing them from smaller subsolutions, and by trying many possibilities and choices before it arrives at the optimal set of choices.

  • There is no a priori litmus test by which one can tell if the Greedy method will lead to an optimal solution.

  • By contrast, there is a litmus test for Dynamic Programming, called The Principle of Optimality

• Divide and Conquer vs. Dynamic Programming:
  • Both techniques split their input into parts, find subsolutions to the parts, and synthesize larger solutions from smalled ones.

  • Divide and Conquer splits its input at prespecified deterministic points (e.g., always in the middle)

  • Dynamic Programming splits its input at every possible split points rather than at a pre-specified points. After trying all split points, it determines which split point is optimal.

• Definition: A problem is said to satisfy the Principle of Optimality if the subsolutions of an optimal solution of the problem are themselves optimal solutions for their subproblems.
• An optimal sequence of decisions may be found by making decisions one at a time and never making an erroneous decision
• Examples:
  • The shortest path problem satisfies the Principle of Optimality.

  • This is because if a,x₁, x₂, . . ., x_n,b is a shortest path from node a to node b in a graph, then the portion of x_i to x_j on that path is a shortest path from x_i to x_j.

  • The longest path problem, on the other hand, does not satisfy the Principle of Optimality. Take for example the undirected graph G of nodes a, b, c, d, and e, and edges (a,b) (b,c) (c,d) (d,e) and (e,a). That is, G is a ring. The longest (noncyclic) path from a to d to a,b,c,d. The sub-path from b to c on that path is simply the edge b,c. But that is not the longest path from b to c. Rather, b,a,e,d,c is the longest path. Thus, the subpath on a longest path is not necessarily a longest path.

III. Steps of Dynamic Programming

• Dynamic programming design involves 4 major steps:
  1. Develop a mathematical notation that can express any solution and subsolution for the problem at hand.

  2. Prove that the Principle of Optimality holds.

  3. Develop a recurrence relation that relates a solution to its subsolutions, using the math notation of step 1. Indicate what the initial values are for that recurrence relation, and which term signifies the final solution.

  4. Write an algorithm to compute the recurrence relation.

• Steps 1 and 2 need not be in that order. Do what makes sense in each problem.

• Step 3 is the heart of the design process. In high level algorithmic design situations, one can stop at step 3. In this course, however, we will carry out step 4 as well.

• Without the Principle of Optimality, it won't be possible to derive a sensible recurrence relation in step 3.

• When the Principle of Optimality holds, the 4 steps of Dynamic Programming are guaranteed to yield an optimal solution. No proof of optimality is needed.

V. Example: 0/1 Knapsack

If each x_i can take on only a finite set of values, then we can try all combinations.

for all combination of x_i values
check for constraints
calculate optimizing function
keep track of max.
end

one does not have to look at all possible decision sequences to obtain an optimal decision sequence because subsequences that are suboptimal are not considered. Although the total number of different decision sequences is exponential, dynamic programming algorithms often have polynomial complexity

Optimal solutions to subproblems are retained so as to avoid recomputing their values

Note the progression in the text exercises below and the steps in III.

1. Example 5.6 (2- Optimality): Principle of Optimality holds,

2. Example 5.8 (1 - a solution): Let g_j(y) be the value of an optimal solution to KNAP(j+1,n,y) then
   g₀(m) is the value of an optimal solution to KNAP(1,n,m) and g₀(m) = max {g₁(m), g₁(m- w₁) + p₁}

3. Example 5.10 (3 - recurrence relation): g_i(y) = max {g_i+1(y), g_i+1(y- w_i+1) + p_i+1}

Each calculation would be single-source shortest path. O(n²) ==> O(n³)

Starting with S = {} keep adding nodes to S.
Node k being added to S
A^k-1(i,j) - before
A^k(i,j) - after

If i to j is the shortest path and k is on this path, then i to k is smallest and k to j is smallest. Principle of optimality works

• Input: A weighted graph, represented by its weight matrix W.

• Problem: find the distance between every pair of nodes.

• Dynamic Programming Design:

  • Notation: A^(k)(i,j) = length of the shortest path from node i to node j where the label of every intermediary node is < k.
    

    A⁽⁰⁾(i,j) = W[i,j]. (goes through no vertex - just (i,j) edge)

  • Principle of Optimality: We already saw that any sub-path of a shortest path is a shortest path between its end nodes.

  • recurrence relation:

  • Divide the paths from i to j where every intermediary node is of label < k into two groups:

    1. Those paths that do not go through node k

    2. Those paths that do go through node k.

  • the shortest path in the first group is the shortest path from i to j where the label of every intermediary node is < k-1.

  • therefore, the length of the shortest path of group 1 is A^(k-1)(i,j)

  • Each path in group two consists of two portions: The first is from node i to node k, and the second is from node k to node j.

    • the shortest path in group 2 does not go through K more than once, for otherwise, the cycle around K can be eliminated, leading to a shorter path in group 2.

    • Therefore, the two portions of the shortest path in group 2 have their intermediary labels < k-1.

    • Each portion must be the shortest of its kind. That is, the portion from i to k where intermediary node is < k-1 must be the shortest such a path from i to k. If not, we would get a shorter path in group 2. Same thing with the second portion (from j to k).

    • Therefore, the length of the first portion of the shortest path in group 2 is A^(k-1)(i,k)

    • Therefore, the length of the 2nd portion of the shortest path in group 2 is A^(k-1)(k,j)

    • Hence, the length of the shortest path in group 2 is A^(k-1)(i,k) + A^(k-1)(k,j)

  • Since the shortest path in the two groups is the shorter of the shortest paths of the two groups, we get

  • A^(k)(i,j)=min(A^(k-1)(i,j), A^(k-1)(i,k) + A^(k-1)(k,j)).

    Note that

    A^(k)(i,k) = A^(k-1)(i,k)
    A^(k)(k,j) = A^(k-1) (k,j)
    i.e., kth row and column remain the same.

  • The algorithm follows:

Procedure APSP(input: W[1:n,1:n];A[1:n,1:n])
begin 
   for i=1 to n do
      for j=1 to n do
         A(0)(i,j) := W[i,j];
      endfor
   endfor
   for k=1 to n do
      for i=1 to n do
         for j=1 to n do
            A(k)(i,j)=min(A(k-1)(i,j),A(k-1)(i,k) + A(k-1)(k,j))
         endfor
      endfor
   endfor
end

Procedure APSP(input: W[1:n,1:n];A[1:n,1:n])
begin 
   for i=1 to n do
        for j=1 to n do
           A(i,j) := W[i,j];
        endfor
   endfor
   for k=1 to n do
        for i=1 to n do
           for j=1 to n do
              A(i,j)=min(A(i,j),A(i,k) + A(k,j));
           endfor
        endfor
   endfor
end

books example

• Time Complexity Analysis:

  • The first double for-loop takes O(n²) time.

  • The triple-for-loop that follows has a constant-time body, and thus takes O(n³) time.

  • Thus, the whole algorithm takes O(n³) time.

V = U _{i=0 to k} V_i     Edges connect adjacent layers. If <u,v> E, then u V_i and v V_i+1

Shortest path from V₀: s (source) to V_k: t (sink)

book example shows a five-stage graph. A minimum cost path is indicated by the broken edges.

c(i,j) = cost of edge <i,j>

dist(j) = shortest path (cost of distance) from node j (in V_i) to node t (sink).     (Book uses p(i,j) for the minimum-cost path from vertex j in V_i to vertex t and cost(i,j) for its cost)

The cost of a path from s to t is the sum of the costs of the edges on the path. The multistage graph problem is to find a minimum-cost path from s to t.
Each set V_i defines a stage in the graph.

Dynamic programming formulation

consider some j V_i

Note that for a k stage graph, every s to t path is a result of a sequence of k - 2 decisions. The ith decision involves determining which vertex in V_i+1 is to be on the path. It is easy to see that the principle of optimality holds.

Recurrance formula:     dist (j) = min   _{l Vi+1 and (j,l) E}   {c(j,l) + dist (l)}

start with {dist (t) = 0}

     book example solved

Calculate dist for nodes according to decreasing layer number.

Time: at each node, work done proportional to degree
allocate work done to edges O(n + e)

Example of use:

Consider a resource allocation problem in which n units of resource are to be allocated to r projects.
If j, 0 < j < n, units of the resource are allocated to project i, then the resulting net profit is N(i,j). The problem is to allocate the resource to the r projects in such a way as to maximize total net profit.
This problem can be formulated as an r + 1 stage graph problem as follows:

• Stage i, 1 < i < r, represents project i. (Consider: like V's are points between projects; projects/stages are links between V's)
• There are n + 1 vertices V(i,j), 0 < j < n, associated with stage i, 2 < i < r (the first (1) and last (r+1) have one node)
  Represents that at each project, there are 0 or 1 or 2 or ... n resources that could have been used (0 to n at each stage indicates n+1 possibilities)
• Stages 1 and r + 1 each have one vertex, V(1,0) = s and V(r+1, n) = t, respectively.
• Vertex V(i,j), 2 < i < r, represents the state in which a total of j units of resource have been allocated to projects 1,2, ..., i -1.
• The edges in G are of the form (V(i,j), V(i+1,l)) for all j < l and 1 < i < r
• The edge (V(i,j), V(i+1,l)), j < l, is assigned a weight or cost of N(i, l-j) and corresponds to allocating l-j units of resource to project i, 1 < i < r
• G has edges of the type (V(r,j), V(r+1,n)). Each such edge is assigned a weight or cost of max_{0< p < n-j} {N(r,p)}.

Note X and Y. Since X is from V(3,3), 3 resources have already been allocated by stage 3.
      Hence the best net profit (N) is max{N(3,0),N(3,1)} since I can use only 4 resources total to get from stage 3 to V(4,4).
Similarly, since Y is from V(3,2), 2 resources have already been allocated by stage 3.
      Hence the best net profit (N) is max{N(3,0),N(3,1),N(3,2)} since I can use only 4 resources total to get from stage 3 to V(4,4).

Try problem 1 on page 264

VIII. Traveling Salesperson

Note that for the knapsack problem, we were looking at a "subset" problem, i.e., we needed the correct choices for objects in a set of size n. Hence the possible number of alternatives (or possible subsets for a set n with two options for each) was bⁿ (Or 2ⁿ when we had two choices). This (traveling salesperson problem) is a permutation problem. We have n cities to visit; note that the number of permutations of a set of n items is n!.
Also note than n! >> 2ⁿ (as early as n=4 ... and then grows quite fast).

Dynamic programming formulation

c_ij is cost from i to j, so we are looking at all the j's that link to i . In your mind say, "I have the problem solved for everywhere except this vertex. Look at all the places that this vertex connects to and how good are the solutions up to that point. I want the miminum new sum of (1)what has been done so far with (2)this new edge I need to complete."

Look how much this looks like the multistage problem. Discuss differences. Read Section 5.9 for additional interesting applications of this problem.

Trace a traveling sales example (page 300) and look at another example of single source with negative paths and dynamic programming (Figure 5.10, page 272)

Here is a lecture from MIT on Longest Common Subsequence

IX. Summary

• think about the problem and its structure to determine a possible data structure. Remember the Dykstra quote: "If you don't know what your program is supposed to do, you'd better not start writing it." Take this seriously. Look at the problem and make sure that you understand it. Take a small example and determine the data structure that will hold the answers (is it an array? a matrix? what info needs to be known/held to determine the next solution?). Use numbers to see what the problem looks like. While doing it, think about what the constraints are and how you are using them to generate the solution at each state. Then try to generalize.
• does the principle of optimality hold? At each point that a solution is determined, would it be the solution if I stopped here?
• to determine the recurrance formula
  • remember that you "have" the solutions for all of the previous cases
  • with the solutions in a data structure, what are the constraints to be considered?
  • using the solutions for each previous case, what are the "options" for the next item (i.e., like for 0/1 knapsack, either it was 0 or 1; for all-pairs shortest path you either needed a vertex or not; for shortest path in multistage, you looked where you were, and what was already known, and took the min)