L-13 Dynamic Programming

Dynamic Programming Lecture 12 Umar Manzoor

Dynamic Programming „

Dynamic programming like the divide and conquer method, solves problem by combining the solutions of sub problems

„

Divide and conquer method partition the problem into independent sub problems, solves the sub problems recursively and then combine their solutions to solve the original problem.

Dynamic Programming „

Dynamic programming is applicable, when the subproblems are NOT independent, that is when subproblems share sub sub-problems.

„

It is making a set of choices to arrive at optimal solution.

„

If sub-problems are not independent, we have to further divide the problem.

„

In worst case, we may end-up with an exponential time algorithm.

Dynamic Programming „

Frequently, there is a polynomial number of subproblems, but they get repeated.

„

A dynamic programming algorithm solves every subproblem just once and then saves its answer in a table, thereby avoiding the work of re-computing the answer every time the sub-problem is encountered

„

So we end up having a polynomial time algorithm.

„

Which is better, Dynamic Programming or Divide & conquer?

Optimization Problems „

Dynamic problem is typically applied to Optimization Problems

„

In optimization problems there can be many possible solutions. Each solution has a value and the task is to find the solution with the optimal ( Maximum or Minimum) value. There can be several such solutions.

4 steps of Dynamic Programming Algorithm 1. Characterize the structure of an optimal solution. 2. Recursively define the value of an optimal solution. 3. Compute the value of an optimal solution bottom-up. 4. Construct an optimal solution from computed information

Often only the value of the optimal solution is required so step-4 is not necessary.

Recursive Definition of the Fibonacci Numbers The Fibonacci numbers are a series of numbers as follows: fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 ...

fib(n) =

1, n <= 2 fib(n-1) + fib(n-2), n > 2

fib(3) = 1 + 1 = 2 fib(4) = 2 + 1 = 3 fib(5) = 2 + 3 = 5

Recursive Algorithm Takes Exponential time, seen few lectures back! „ Actual sub problems are polynomial (O(n)) but they get repeated „ Sub problems are not INDEPENDENT. „ Sub problems share sub-sub problems. „ We can solve it using Dynamic programming. „

Benefit of Dynamic Programming Run an O(n) time loop, keep a temp variable to store the solution of subproblems and then reuse them rather then recalculating them. „ So by using dynamic programming we can solve a problem in polynomial time which otherwise was solved in exponential time. „

Matrix Chain Multiplication Our second example of dynamic programming is an algorithm that solves the problem of Matrix Chain Multiplication

Matrix Chain Multiplication „

We are given a sequence (chain) , of n matrices to be multiplied together. And we wish to compute the product A1A2A3…An

„

A product of matrices is fully parenthesized, if it is either a single matrix or product of two fully parenthesized matrix product, surrounded by parenthesis.

„

As matrix multiplication is associative, so all parenthesizations yield the same product/result.

Matrix multiplication revisited We can multiply two matrices A and B, only if the number of columns of A is equal to the number of rows of B. If A is a p x q matrix, and B is a q x r matrix, the resulting matrix C is p x r matrix. So the time to compute C, is dominated by scalar multiplications i.e. pqr

Matrix Chain Multiplication Thus computing the product according to the 1st parenthesization is 10 times faster. This clearly demonstrates the benefit of calculating the optimum order before commencing the product calculations.

Counting the number of parenthesization. „

For a single matrix, we have only one parenthesization.

„

The number of alternative parenthesization for a sequence of n matrices is denoted by P( n).

„

We can split a sequence of n matrices between the kth and (k+1)st matrices for any k=1,2…n-1, and then parenthesize the two resulting subsequences independently.

Computing the optimal costs The idea of dynamic programming is, rather than computing m (min number of scalar multiplications) recursively, computing it bottom up: A recursive computation takes exponential time; a bottom-up computation O(n3) time.

Example „

Let n = 6

Matrix A1

Dimension 30 x 35

A2

35 x 15

A3

15 x 5

A4

5 x 10

A5

10 x 20

A6

20 x 25

Order A2 x A3 = A1 (A2 x A3) =

Matrix Size 35 x 5 30 X 5

Products 2,625 5,250 + 2,625

Dynamic programming Assembly Line Scheduling

Assembly Line Scheduling „

Automobile factory with two assembly lines Each line has n stations: S1,1, . . . , S1,n and S2,1, . . . , S2,n … Corresponding stations S1, j and S2, j perform the same function but can take different amounts of time a1, j and a2, j … Entry times are: e1 and e2; exit times are: x1 and x2 …

Assembly Line Scheduling „

After going through a station, can either: … stay

on same line at no cost, or … transfer to other line: cost after Si,j is ti,j , j = 1, . . . , n -1

Assembly Line Scheduling „

Problem: what stations should be chosen from line 1 and which from line 2 in order to minimize the total time through the factory for one car?

One Solution „

Brute force … Enumerate

all possibilities of selecting

stations … Compute how long it takes in each case and choose the best one … There are 2n possible ways to choose stations … Infeasible when n is large!!

1. Structure of the Optimal Solution „

How do we compute the minimum time of going through a station?

1. Structure of the Optimal Solution „

Let’s consider all possible ways to get from the starting point through station S1,j … We

have two choices of how to get to S1, j:

Through S1, j - 1, then directly to S1, j „ Through S2, j - 1, then transfer over to S1, j „

Line 1

S1,j-1

S1,j

a1,j-1

a1,j t2,j-1

Line 2

a2,j-1 S2,j-1

1. Structure of the Optimal Solution „

Suppose that the fastest way through S1, j is through S1, j – 1 … We

must have taken a fastest way from entry through

S1, j – 1 … If there were a faster way through S1, j - 1, we would use it instead Similarly for S2, j – 1 Line 1

S1,j-1

S1,j

a1,j-1

a1,j

Optimal Substructure Line 2

t2,j-1 a2,j-1 S2,j-1

Optimal Substructure „

Generalization: an optimal solution to the problem “find the fastest way through S1, j” contains within it an optimal solution to subproblems: “find the fastest way through S1, j - 1 or S2, j – 1”.

„

This is referred to as the optimal substructure property

„

We use this property to construct an optimal solution to a problem from optimal solutions to subproblems

2. A Recursive Solution „

Define the value of an optimal solution in terms of the optimal solution to subproblems

2. A Recursive Solution (cont.) „

Definitions: … f*

: the fastest time to get through the entire factory … fi[j] : the fastest time to get from the starting point through station Si,j f* = min (f1[n] + x1, f2[n] + x2)

2. A Recursive Solution (cont.) „

Base case: j = 1, i=1,2 (getting through station 1) f1[1] = e1 + a1,1 f2[1] = e2 + a2,1

2. A Recursive Solution (cont.) „ „

General Case: j = 2, 3, …,n, and i = 1, 2 Fastest way through S1, j is either: … the

way through S1, j - 1 then directly through S1, j, or

f1[j - 1] + a1,j

way through S2, j - 1, transfer from line 2 to line 1, then through S1, j S S

… the

f2[j -1] + t2,j-1 + a1,j

1,j-1

Line 1

1,j

a1,j-1

a1,j t2,j-1

Line 2

a2,j-1 S2,j-1

f1[j] = min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j)

2. A Recursive Solution (cont.) f1[j] =

f2[j] =

e1 + a1,1

if j = 1

min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j) if j ≥ 2 e2 + a2,1

if j = 1

min(f2[j - 1] + a2,j ,f1[j -1] + t1,j-1 + a2,j) if j ≥ 2

3. Computing the Optimal Solution f* = min (f1[n] + x1, f2[n] + x2) 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)

„

1

2

3

4

5

f1[j]

f1(1)

f1(2)

f1(3)

f1(4)

f1(5)

f2[j]

f2(1)

f2(2)

f2(3)

f2(4)

f2(5)

4 times

2 times

Solving top-down would result in exponential running time

3. Computing the Optimal Solution For j ≥ 2, each value fi[j] depends only on the values of f1[j – 1] and f2[j - 1] „ Idea: compute the values of fi[j] as follows: „

in increasing order of j 1

2

3

4

5

f1[j] f2[j] „

Bottom-up approach … First

find optimal solutions to subproblems … Find an optimal solution to the problem from the subproblems

Example

f1[j] =

e1 + a1,1,

if j = 1

min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j) 1

if j ≥ 2

2

3

4

5

f1[j]

9

18[1]

20[2]

24[1]

32[1]

f2[j]

12

16[1]

22[2]

25[1]

30[2]

f* = 35[1]

FASTEST-WAY(a, t, e, x, n) 1.

f1[1] ← e1 + a1,1

2.

f2[1] ← e2 + a2,1

3.

for j ← 2 to n

4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

Compute initial values of f1 and f2

do if f1[j - 1] + a1,j ≤ f2[j - 1] + t2, j-1 + a1, j then f1[j] ← f1[j - 1] + a1, j l1[j] ← 1 else f1[j] ← f2[j - 1] + t2, j-1 + a1, j

O(N) Compute the values of f1[j] and l1[j]

l1[j] ← 2 if f2[j - 1] + a2, j ≤ f1[j - 1] + t1, j-1 + a2, j then f2[j] ← f2[j - 1] + a2, j l2[j] ← 2 else f2[j] ← f1[j - 1] + t1, j-1 + a2, j l2[j] ← 1

Compute the values of f2[j] and l2[j]

FASTEST-WAY(a, t, e, x, n) (cont.) 14.

if f1[n] + x1 ≤ f2[n] + x2

15.

then f* = f1[n] + x1

16. 17. 18.

l* = 1 else f* = f2[n] + x2 l* = 2

Compute the values of the fastest time through the entire factory

4. Construct an Optimal Solution Alg.: PRINT-STATIONS(l, n) i ← l* print “line ” i “, station ” n for j ← n downto 2 do i ←li[j] print “line ” i “, station ” j - 1 1

2

3

4

5

f1[j]/l1[j]

9

18[1]

20[2]

24[1]

32[1]

f2[j]/l2[j]

12

16[1]

22[2]

25[1]

30[2]

l* = 1

Elements of dynamic programming When should we look for a dynamic programming solution to a problem? Two key ingredients? … …

Optimal sub-structure Overlapping sub-problems

Elements of dynamic programming Optimal sub-structure A problem exhibits optimal sub-structure, if an optimal solution to a problem contains within it optimal solutions to sub-problems.

Overlapping Sub problems When a recursive algorithm revisits the same problem, over and over again, we say that the optimization problem has overlapping sub problems. Typically the total number of distinct sub problems, is polynomial in the input size. Divide & Conquer approach is suitable when brand new problems are generated at each step of the recursion.

Overlapping Sub problems Two ways of solving the same problem: Top-down approach This being based on recursion i.e. recursively solving the larger problem by breaking it down Bottom-Up approach This being based on dynamic programming. Starting with the smallest sub-problems, solving them and using their solutions

Overlapping Sub problems

Top-down approach Vs Bottom-Up approach Bottom-Up approach More efficient because it takes advantage of the overlapping sub-problem property. There are only θ(n2) different sub-problems. Each problem solved exactly once. Top-down approach Must repeatedly resolve each sub-problem, each time it reappears in the recursion.

Memoization „

A variation of Dynamic Programming and is TOP-DOWN

„

Memoize the natural, but inefficient, recursive algorithm.

„

Maintains an entry in the table for the solution to each sub-problem.

„

Offers efficiency while maintaining top-down strategy.

Memoization „

A special character stored at each empty solution space.

„

When the sub-problem is first encountered, it’s solution is computed and stored.

„

Each subsequent time the sub-problem is encountered, its solution is looked up.

„

Time to search the sub-problem solutions?

Memoization „

This approach presupposes that the set of all possible sub-problem parameters is known and that the relation between table position and sub-problem is established.

„

Another approach is to memoize by using hashing with the sub-problem parameters as keys.

Memoization

Memoization „

The matrix chain multiplication problem can be solved in O(n3) time by either a Top-Down, memoized algorithms or Bottom-up dynamic programming.

„

If all sub-problems must be solved at least once, then dynamic-programming is better

„

If some sub-problems in the sub-problem space need not be solved at all, the memoized solution has the advantage of only solving those sub-problems that are definitely required.