Chapter 15 - Dynamic Programming

Overview

Dynamic programming (i.e. planning) is a technique for solving problems that have overlapping subproblems.

One goal is to reduce the complexity of a problem; we will see that this can often be accomplished by remembering and recalling subproblem solutions rather than recomputing the solution multiple times.

Not a specific algorithm, but a technique (like divide-and-conquer).

Used in optimization problems.

• Find a solution with the optimal value.
• Minimization or maximization.

Example - Recursive Fibonacci function

F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2  for n³2

Analysis

• F₅ at right is a full binary tree down to a depth of 5/2=2.
• Generally for F_n, n/2, the rightmost path being the shortest and has more nodes at lower depths.
• The running time is at least W(2^n/2) or exponential. Recall that a complete binary tree of height h has 2^h+1−1 nodes with 2^h at the bottom.

• Analysis T(n) = Q( fⁿ )

  T(n) = T(n-1) + T(n-2) + Q(1)

  Assume T(n) ≤ aF_n - b        a > 1 and b > 0

  T(n)	= T(n-1) + T(n-2) + Q(1)
  	≤ aFn-1 - b + aFn-2 - b + Q(1)
  	≤ a(Fn-1 + Fn-2) - 2b + Q(1)
  	= aFn - b  -(b - Q(1))
  	≤ aFn - b	for b ³ Q(1)

  T(n) = Q( fⁿ ) where f = 1.61803..., the golden ratio, and F_n = fⁿ (see equation 3.25)

Example - Using subproblem solutions to compute the problem solution.

The problem with the recursive solution is the recomputing of solutions to subproblems; F₁ is computed 5 times.

The following algorithm trades space for time, requiring 6 memory spaces for a Q(n) time and space solution.

f[0] ¬ 0 f[1] ¬ 1 for i¬2 to n do f[ i ] ¬ f[i - 1] + f[i - 2]

i 0 1 2 3 4 5 f 0 1 1 2 3 5

Developing solutions - Four-step method

1. Characterize the structure of an optimal solution.

   Example: define the Fibonacci sequence

2. Recursively define the value of an optimal solution

   Example: F(n) = F(n-1) + F(n-2)

3. Compute the value of an optimal solution in a bottom-up fashion.

   Example: compute F(0) and F(1)

4. Construct an optimal solution from computed information.

   Example: use F(0) and F(1) to compute F(2), then use F(1) and F(2) to compute F(3), ...

Memo-ization

• “Store, don’t recompute.”
• Make a table indexed by subproblem.
• When solving a subproblem:
    • Lookup in table.
    • If answer is there, use it.
    • Else, compute answer, then store it.
• In dynamic programming, go one step further. Determine in what order want to access the table, and fill it in that way.

Generally the recursive procedure A can be converted into dynamic programmed ADP by the following technique.

Assume P is the current problem:

1. Before any recursive call to solve s, a subproblem of P, check solution dictionary D for s.
   1. Lookup s in dictionary D
   2. If s is not in dictionary, make recursive call to compute s
2. Use s to compute solution to P.
3. Insert P and solution into dictionary D.
4. return solution

Example

Recursive Fibonacci

fib( n ) if n<2 then return n return fib( n-1 ) + fib( n-2)

Memo-izated Fibonacci

fib( n ) Dictionary solutions ¬ new( n )                 -- Create dictionary for n solutions insert( solutions, 0, 0 )                             -- insert key=0 and solution 0 insert( solutions, 1, 1 )                             -- insert key=1 and solution 1 return fibDP( n )                                      -- Return nth solution fibDP( k ) if f1 ¬ lookup( k-1 ) = NIL then               -- if exists use stored k-1 result    f1 ¬ fibDP( k-1 )                                   -- otherwise compute  if f2 ¬ lookup( k-2 ) = NIL then               -- if exists use stored k-2 result    f2 ¬ fibDP( k-2 )                                   -- otherwise compute  f ¬ f1 + f2 insert( solutions, k, f )                              -- insert key=k and solution f return f

Question 15.1

• Draw the recursion tree for fibDP( 6 ) and the solutions dictionary.
• How many calls?
• What is the O running time in terms of the calls?

Discrete Knapsack problem - an optimization

Suppose you've gotten lucky and won a shopping spree in which you can fill your knapsack with any items in the store.

With a knapsack of capacity W, you would like to put in the maximum value of items.

Brute force/exhaustive search

Solution: One way is to compute all possible solutions while keeping track of the maximum.

Analysis: If only one of each item, there are 2ⁿ subsets of n items (power set) to consider.

For example: 3 items, A, B, C would be: {Æ}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

Complexity is W(2ⁿ) or exponential, 2³=8.

Example:

• Suppose there one of each item.
• Knapsack holds size W=10 capacity.

Items     1 2 3 item A B C size 7 3 4 value $42 $12 $40

Exhaustive search - {A,B} optimal solution, $54 Subset Total size Total value Æ 0 $0 {A} 7 $42 {B} 3 $12 {C} 4 $40 {A,B} 10 $54 {A,C} 11 not feasible {B,C} 7 $52 {A,B,C} 14 not feasible

 

Question 15.2.1 Suppose our knapsack held W=13? What is the optimal solution?

 

Example:

• Now suppose there are as many of each item as you want.

At right, the knapsack has a capacity of W=17 and the items are:   1 2 3 4 5 item A B C D E size 3 4 7 8 9 value 4 5 10 11 13

3 A's and 2 B's is a value 22 and size 17. 4+4+4+5+5=22. One item D and E is a value 24 and size 17, a maximum. 11+13=24. How can we determine that?

Example:

For capacity 8 the recursion tree below computes the maximum value 11.

-3/9 indicates size=3 subtracted from capacity of 8, and value=9 returned from child.

The maximum value=11 is returned by the root's D child.

Non-feasible solutions, not all shown, return 0 (e.g. triangle).

 

Solutions to knapsack( 17 )

The recursion tree above shows capacity for each call of knapsack.

• □ are leafs where no item of that capacity exists.
• All 0 leafs are solutions that fill the knapsack but non-zero solutions could be optimal.
• {A,A,B,B,A} is path <3,3,4,4,3>, filling the sack.
• There are some omissions in the diagram (e.g. at far left, capacity 8 results from putting a size 9, E, in sack; there should be a leaf of 0 after putting D, size 8, in sack).
• Line 3 excludes non-feasible solutions reducing the recursion tree size.
• It has 129 calls (determined empirically).

Analysis: Allowing multiples of any of n items to fill the knapsack to capacity W.

Each call executes for i ¬ 1 to N, Q(n).

Each call may generate W recursive calls on smaller capacities, O(W).

Complexity is O(nW).

Question 15.3

1. What value is returned from path <3,3,4,4,3>? Is that optimal?
2. Generate the first few (7 or 8) recursive calls to knapsack( 17 ).
3. Is this a greedy algorithm? Does it always choose the best choice to solve for a solution or do extra work?

	1	2	3	4	5
item	A	B	C	D	E
size	3	4	7	8	9
value	4	5	10	11	13

	int knapsack( capacity )
1	max ¬ 0
2	for i ¬ 1 to N	-- N number of items
3	if space ¬ capacity - size[ i ] ≥ 0 then	-- Room for item i
4	if  tempmax ¬ knapsack( space ) + value[ i ] > max then
5	max ¬ tempmax
6	return max

 

Optimal substructure necessary for dynamic programming

An optimal solution to a problem contains within it an optimal solution to subproblems.

Example: We saw that Fibonacci( 5 ) = Fibonacci( 4 ) + Fibonacci( 3 ).

Solution to problem Fibonacci( 5 ) contains the solution to subproblem Fibonacci( 4 ) and Fibonacci( 3 ).

Example: The optimal solution to a capacity 17 sack is D and E of size 8 and 9 respectively.

Solution to problem capacity 17 sack contains the optimal solution to subproblem capacity 8 and 9.

Key ideas: Use optimal substructure to construct optimal solution to problem from optimal solutions to subproblems.

Use memoization to maintain the computed maximum value for a given capacity.

When recursing, use the recorded maximum value when available.

When iterating, update the recorded maximum if a larger value for a capacity is computed.

Example:

For capacity 8 the recursion tree below computes the maximum value 11.

knapsack( 1 ) and knapsack( 0 ) calls are not repeated.

                                                 knapsack( 8 )                                                                 
                     -3  / 9                         -4 | 10                   -7  |  10         -8 \  11                -9 \ 0
         knapsack(5)                       knapsack(4)        knapsack( 1 )   knapsack( 0 )      Æ
    -3 / 4         -4 \ 5                     -3 / 4           -4 \ 5        
knapsack(2)  knapsack(1)    knapsack(1)  knapsack(0) 
        | 0               | 0                                                | 0                      
       Æ                 Æ                                                 Æ                        

1 2 3 4 5 item A B C D E size 3 4 7 8 9 value 4 5 10 11 13

The complete recursion tree has 45 calls (determined empirically). Solutions database for knapsack( 17 ) capacity 0 1 2 3 4 5 6 7 8 9 10 11 13 14 17 max 0 0 0 4 5 5 8 10 11 13 14 15 18 20 24

Question 15.4

1. Does the algorithm exhibit greedy behavior?
2. Why doesn't 12, 15, or 16 occur in the solutions database?
3. Is the above recursion tree complete for the dynamically programmed version? Compare <17, 9, 6, 3> and <17, 13, 6>.
4. Why does the dynamically programmed recursion tree above differ from the brute force tree below?
5. What would be returned from <17, 14, 11, 7>?

Assembly-line scheduling

A slightly more complicated example from Cormen. Actually solvable by a graph algorithm but a good, detailed introduction to dynamic programming.

Automobile factory with two assembly lines with n stations.
• S_line,station or S_1,1, . . . , S_1,n and S_2,1, . . . , S_2,n.
• Corresponding stations S_1,j and S_2,j perform the same function but can take different amounts of time a_1,j and a_2,j
• Entry times to each line, e₁ and e₂.
• Exit times from each line, x₁ and x₂.
• After going through a station, can either:

• stay on same line; no cost, or
• transfer to other line; cost after S_i,j is t_i,j. ( j = 1, . . . , n−1. No t_i,n , because the assembly line is done after S_i,n.)

Problem: Given all these costs (time = cost), what stations should be chosen from line 1 and from line 2 for fastest way through factory?

Try all possibilities?

• Each candidate is fully specified by which stations from line 1 are included. Looking for a subset of line 1 stations.
• Each line has n stations.
• 2ⁿ subsets (2 lines with 4 stations, 2⁸ = 256 different ways, of which 16 are viable solutions, 256 ways includes path using no station and illegal transfers such as:  S_1,2 ® S_1,4).
• Impractical when n is large.

Structure of an optimal solution

Think about fastest way from entry through S_1,j.
• If j = 1: just determine how long it takes to get through S_1,1.
• If j ≥ 2, have two choices of how to get to S_1,j :

• Through S_1,j-1, then directly to S_1,j .
• Through S_2,j-1, then transfer over to S_1,j .

Suppose fastest way is through S_1,j-1.

Key observation: We must have taken a fastest way from entry through S_1,j-1 in this solution. If there were a faster way through S_1,j-1, we would use it instead to come up with a faster way through S_1,j.

Suppose instead fastest way is through S_2,j-1. Again, we must have taken a fastest way through S_2,j-1. Otherwise use some faster way through S_2,j-1 to give a faster way through S_1,j

Optimal substructure:

Generally: An optimal solution to a problem (fastest way through S_1,j  ) contains within it an optimal solution to subproblems (fastest way through S_1,j-1 or S_2,j-1).

Use optimal substructure to construct optimal solution to problem from optimal solutions to subproblems.

Fastest way through S_1,j is either

• fastest way through S_1,j-1 then directly through S_1,j, or
• fastest way through S_2,j-1, transfer from line 2 to line 1, then through S_1,j .

Symmetrically: Fastest way through S_2,j is either

• fastest way through S_2,j-1 then directly through S_2,j, or
• fastest way through S_1,j-1, transfer from line 1 to line 2, then through S_2,j.

Therefore, to solve problems of finding a fastest way through S_1,j and S_2,j, solve subproblems of finding a fastest way through S_1,j-1 and S_2,j-1.

 

Recursive solution

Let f_i [ j ] = fastest time to get through S_i,j , i = 1,2 and j = 1, . . . , n.

e₁ and e₂ entry time

x₁ and x₂ exit time

Transfer time is t_i,j

Station time is a_i,j

Goal: fastest time to get all the way through = f*.

f* ¬ min( f₁[n] + x₁, f₂[n] + x₂)   -- Minimum time to exit either line 1 or 2

f1[1] ¬ e1 + a1,1 f2[1] ¬ e2 + a2,1 for j ¬ 2, . . . , n: f1[ j ] ¬ min( f1[ j−1] + a1,j , f2[ j−1] + t2,j−1 + a1,j ) f2[ j ] ¬ min( f2[ j−1] + a2,j , f1[ j−1] + t1,j−1 + a2,j )

f₁[ j−1] + a_1,j gives the value for staying on line 1 in station j.

f₂[ j−1] + t_2,j−1 + a_1,j gives the value for transferring to line 1 in station j.

f₁[ j ] gives the value of an optimal solution to station j of line 1.

f₂[ j ] gives the value of an optimal solution to station j of line 2.

Constructing an optimal solution

• l_i [ j ] = line # (1 or 2) whose station j−1 is used in fastest way through S_i,j
• In other words S_{li [ j ], j−1} precedes S_i,j
• Defined for i = 1,2 and j = 2, . . . , n.
• l* = line # whose station n is used; the exit line.

Example - f* and l* for assembly line

Note: f₂[ 2 ] ¬ min( f₂[1] + a_2,2 , f₁[1] + t_1,1 + a_2,2 ) = min( 12+5 , 9+2+5 ) = min( 17 , 16 ) =

Question 15.5

To determine the solution, trace backward through the optimal path given by l_i values starting with i=l*.

Compute an optimal solution

Recursive algorithm based on above recurrences.
• Let r_i ( j ) = # of references made to f_i [ j ].
• r₁(n) = r₂(n) = 1.
• r₁( j ) = r₂( j ) = r₁( j + 1) + r₂( j + 1) for j = 1, . . . , n − 1.

Claim: r_i ( j ) = 2^n−j .

Proof: Induction on j , down from n.

Basis: j = n. 2^n−j = 2⁰ = 1 = r_i (n).

Inductive step: Assume r_i ( j + 1) = 2^{n−( j+1)}.
Then r_i( j ) = r_i( j + 1) + r₂( j + 1)
                  = 2^{n−( j+1)} + 2^{n−( j+1)}
                  = 2^{n−( j+1)+1}
                  = 2^n−j .

Therefore, f₁[1] alone is referenced 2ⁿ⁻¹ times! So top down isn’t a good way to compute f₁[ j ].

Observation: f_i [ j ] depends only on f₁[ j − 1] and f₂[ j − 1] (for j ≥ 2). So compute in order of increasing j .

Example - f* and l* for assembly line

Output: line 1, station 5 line 1, station 4 line 2, station 3 line 1, station 2 line 1, station 1

 

Elements of dynamic programming

• optimal substructure
• overlapping subproblems
   

Optimal substructure

• Show that a solution to a problem consists of making a choice, which leaves one or subproblems to solve.

• Suppose that you are given this last choice that leads to an optimal solution. People often have trouble understanding the relationship between optimal substructure and determining which choice is made in an optimal solution. One way that helps understanding optimal substructure is to imagine that “God” tells you what was the last choice made in an optimal solution.

• Given this choice, determine which subproblems arise and how to characterize the resulting space of subproblems.

• Show that the solutions to the subproblems used within the optimal solution must themselves be optimal. Usually use cut-and-paste.

• Suppose that one of the subproblem solutions is not optimal.

• Cut it out.

• Paste in an optimal solution.

• Get a better solution to the original problem. Contradicts optimality of problem solution. That was optimal substructure.

Need to ensure that you consider a wide enough range of choices and subproblems that you get them all.

Try all the choices, solve all the subproblems resulting from each choice, and pick the choice whose solution, along with subproblem solutions, is best.

How to characterize the space of subproblems?

• Keep the space as simple as possible.
• Expand it as necessary.

Assembly-line scheduling
• Space of subproblems was fastest way from factory entry through stations S_{1, j} and S_{2, j} .
• No need to try a more general space of subproblems.

Dynamic programming uses optimal substructure bottom up.
• First find optimal solutions to subproblems.
• Then choose which to use in optimal solution to the problem.

When we look at greedy algorithms, we’ll see that they work top down: first make a choice that looks best, then solve the resulting subproblem.

Don’t be fooled into thinking optimal substructure applies to all optimization problems. It doesn’t.
 

Here are two problems that look similar. In both, we’re given an unweighted, directed graph G = (V, E).
• V is a set of vertices.
• E is a set of edges.

And we ask about finding a path (sequence of connected edges) from vertex u to vertex v.
• Shortest path: find path u v with fewest edges. Must be simple (no cycles), since removing a cycle from a path gives a path with fewer edges.
• Longest simple path: find simple path u v with most edges. If didn’t require simple, could repeatedly traverse a cycle to make an arbitrarily long path.

Shortest path has optimal substructure.

• Suppose p is shortest path u v.
• Let w be any vertex on p.
• Let p1 be the portion of p, u w.
• Then p1 is a shortest path u w.

Proof Suppose there exists a shorter path p'₁ , u w. Cut out p₁, replace it with p'₁ , get path with fewer edges than p.

Therefore, can find shortest path u v by considering all intermediate vertices w, then finding optimal sub-problem solutions to shortest paths  u w and w v.

Same argument applies to p2.

Does longest path have optimal substructure?

• It seems like it should.
• It does not.

Consider q ® r ®  t = longest path q t. Are its subpaths longest paths? No!
• Subpath q r is q ® r.
• Longest simple path q r is q ® s ® t ® r.
• Subpath r t is r ® t.
• Longest simple path r t is r ® q ® s ® t.

Not only isn’t there optimal substructure, but cannot even assemble a legal solution from solutions to subproblems.

Combine longest simple paths:

q ® s ® t ® r ® q ® s ® t

Not a simple path!

In fact, this problem is NP-complete (so it probably has no optimal substructure to find.)

What’s the big difference between shortest path and longest path?
• Shortest path has independent subproblems.
• Solution to one subproblem does not affect solution to another subproblem of the same problem.

• Longest simple path: subproblems are not independent.
• Consider subproblems of longest simple paths q r and r t.
• Longest simple path q r uses s and t.
• Cannot use s and t to solve longest simple path r t, since if we do, the path isn’t simple.
• But we have to use t to find longest simple path r t!
• Using resources (vertices) to solve one subproblem renders them unavailable to solve the other subproblem. [For shortest paths, if we look at a shortest path , no vertex other than w can appear in p₁ and p₂. Otherwise, we have a cycle.]

Assembly line independent subproblem example:

1 subproblem Þ automatically independent.

Overlapping subproblems

Occur when a recursive algorithm revisits the same problem over and over: Fibonacci.

Good divide-and-conquer algorithms usually generate a brand new problem at each stage of recursion.

Example: merge sort

from Cormen