Dynamic Programming

Divide-and-Conquer: break problems into independent sub problems.

Dynamic Programming: break problems into dependent sub problems, save sub problem solutions to reuse if applicable.

DP is used to solve optimization problems, which often could require "testing" many possible solutions. The single best solution is called the optimal solution. DP's four steps:

  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 4 is not necessary.

An example problem to be solved with DP:

Matrix-chain multiplication:

<A1, A2, A3, ...,An> , n matrices to be multiplied together.

®® ®®
a11 a12 ¯ b11 b12 = c11 c12
a21 a22 ¯ b21 b22 = c21 c22

c11 =  a11 b11 + a12 b21

cij    =
  q
å
k = 1 		  aik bkj
    A   x    B   =  C
(p x q) (q x r) (p x r)

The length of the loop cost p q r multiplications.

Grouping matters: We define the order of performing our multiplications by grouping using parenthesis. A matrix product is fully parenthesized if it is:

  1. a single matrix
  2. the product of two fully parenthesized products surrounded by parenthesis.

<A1, A2, A3,A4>

  1. ( A1 ( A2 ( A3A4 )))
  2. ( A1 (( A2 A3 )A4 ))
  3. (( A1 A2 ) ( A3A4 ))
  4. (( A1 ( A2 A3 )) A4 )
  5. ((( A1 A2 ) A3 )A4 )

 Five parenthesis with four matrices.

DP Step 1: What is the structure of an optimal parenthesization?

How much can different parenthesizations cost?

<A1, A2, A3>

A1: 10 x 100

A2: 100 x 5

A3: 5 x 50

(( A1 A2) A3)  

( A1 A2 ) : 10 x 100 x 5      = 5000

(( A1 A2) A3) : 10 x 5 x 50 = 2500

                                              7500 multiplications

( A1 ( A2 A3 ))

( A2 A3 ) : 100 x 5 x 50        = 25000

( A1  (A2 A3)) : 10 x 100 x 50 = 50000

                                                  75000 multiplications

Matrix-Chain multiplication problem: Given <A1, A2, A3, ...,An> (Ai is pi-1 x pi) fully parenthesize A1, A2, A3, ...,An in a way that minimizes the number of scalar multiplications. How many parenthesizations are there? Given a chain of n matrices, we may split them between k and k + 1 for any k = 1,2, ..., n - 1. Then we parenthesize the remaining halves.

P (n) = 1   ,   if n = 1

 P (n) =
n - 1
å
k = 1 		  P (k) P ( n-k ), if   n £ 2

P (n) = C (n-1) , the (n-1)st catalan number 

C (n) = 1/ (n+1) ( 2 n / n ) = 1/(n+1) ( 2 n (2 n-1)... (n+1))/ ( n(n-1)...(2)1)

         = Omega ( 4n /n3/2 ), exponential # of parenthesizations

P (3) = C (2) = 2

P (4) = C (3) = 5

P (5) = C (4) = 14

P (6) = C (6) = 42

A i...j = A i A i+1 ... A j

To parenthesize we first pick k: A 1...k A k+1 ...n Cost of this parenthesization is

  1. A 1...k
  2. A k+1 ...n
  3. multiplying the two parts together.

For the optimal parenthesization

  1. k chosen must be optimal
  2. parenthesization of A 1...k and of A k+1 ...n must be optimal

Why:

  1. ® if not, not optimal
  2. ® if not, can use the optimal to lessen our work n the big problem.

Recursions:

m [i,j] = min # of scalar multiplications A 1...k

We seek m[1,n].  

Clearly m [i,i] = 0, i = 1,2,...,n

m[i,j] = m[i,k] + m[k+1,j] + pi-1 pk pj

If we knew the optimal k! So: m[i,j] = 0 if i = j, and:

   min
i £ k < j		 {m[i,k] + m[k+1,j] + pi-1 pk pj } i < j

 So that we can construct the optimal solution we also define: s [i,j] = k that produces the minimum. We need to compute m[i,j] 1 £ i £ j £ n

(n/2) + n = (n(n-1))2 + n = (n(n+))/2, diagonal and lower diagonal.

Matrix-Chain-Order (p)

  1. n ¬ length[p] - 1
  2. for i ¬ 1 to n
  3.    do m[i,i] ¬ 0
  4. for l ¬ 2 to n
  5.    do fro i ¬ 1 to n - l + 1
  6.       do j ¬ i + l - 1
  7.          m[i, j] ¬ ¥
  8.          for k ¬ i to j - 1
  9.             do q ¬ m[i,k] + m[k+1, j] + pi-1 pk pj
  10.                 if q < m[i,j]
  11.                    then m[i,j] ¬ q
  12.                       s[i,j] ¬ k
  13. return m and s

The above just determined the cost of the optimal solution. We must use the s[i, j] results to construct the optimal. So the information is fed to:

Matrix-Chain-Multiply ( A, s, i, j )

  1. if j > i
  2.    then X ¬ Matrix-Chain-Multiply ( A, s, i, s[i, j] )
  3.           X ¬ Matrix-Chain-Multiply ( A, s, s[i, j] + 1,j )
  4.           return Matrix-Multiply (X, Y)
  5.    else return Ai

In the example of Figure 16.1, the call Matrix-Chain-Multiply ( A, s, 1, 6 ) computes the matrix-chain product according to the parenthesization (( A1 (A2 A3 ))(( A4  A5 ) A6 ))

 

 

 
Dynamic Programming - 1 of 3