Dynamic Programming

 

DP : Binomial Design - Part 1

이항계수 ( n개 중 k개를 뽑는 조합 )

(n,k) = (n-1, k-1) + (n-1, k)   0<k<n
       = 1           (if n == k or k==0)

B[n,k] = B[n-1, k-1] + B[n-1, k]   if 0<k<n
B[n,k] = 1

 

Q. solve B[5,3] => solve == algorithm 을 제시하고 design과 analysis를 제시해라 라는 뜻
==> DP.. local neighbor 계산 활용

neighbor clever enumeration != brute-force enumeration

DP == Save and Reuse.

 

 

Divide & Conquer 방식으로 Binomial design을 해보자.

D&C_Bin(n,k)
{
	if(n==k or k==0) return 1;  // termination
	else 
    		step 1  ==> 문제에 이미 Devide가 되어 있어서 필요 없음
    		step 2  ==> D&C_Bin_left(n-1, k-1) D&C_Bin_right(n-1, k) 
    		step 3  ==> return left + right 
}

 

D&C 방법
B[5,3] = B[4,2] +B[4,3]
B[4,2] = B[3,1] + B[3,2]
B[4,3] = B[3,2] + B[3,3]

--> linear recurrence가 발생함 ( 세부 문제로 쪼개는데 크게크게 쪼개지지 않음)
--> multi-dimensional recurrence.
--> observe 'subproblem overlapping' => 왼/오 가 독립이 안됨(문제 사이즈가 크게 줄어들지 않는다)
--> Fibonacci recurrence.
--> D&C recurrence X => inefficient => New approach.

 

=> 이러한 문제를 D&C 방식으로 푸는 것은 비효율적이므로, 새로운 방식을 도입.


Algorithm Design Approaches

1. Brute-Force => Full/Exhaustive Enumeration
2. Divide and Conquer
3. Dynamic Programming

 

Problem : subproblem recurrence =>  D&C 처럼 보인다.
-> D&C recurrence X -> subproblem overlap -> inefficient
-> TC grows Exponential!!! 
==> DP를 활용할 수 있다
--> Note: Principle of optimality, optimal substructure.

 

 

Binomial Design - Part 2

 

DP <Design>
Step 1:
 - Establish a recursive property from the problem
 - Identify(Find out. Derive) a recurrence equation from P.
 - 큰 문제 = 작은 문제 +/* 작은문제 +...+ 작은문제

Step 2:
 - Solve in a bottom-up fashion programming
  cf) D&C : top-down fashion(recursion) programming => 중첩되는 현상을 미리 알 수 없음
 - Solve smaller problems first
 - Save them(smaller problems) in arrays(tables, dict...)
 - Use them later. (from look-up tables)

 

Q. solve B[5,3]

Step 1. 

B[n,k] = B[n-1, k-1] + B[n-1, k]   if 0<k<n
B[n,k] = 1

수식은 이미 세워진 상태이다.

 

Step 2.

1) 가장 작은 문제 먼저 해결.

	0	1	2	3	4	5
0	1	N / A	N / A	N / A	N / A	N / A
1	1	1	N / A	N / A	N / A	N / A
2	1		1	N / A	N / A	N / A
3	1			1	N / A	N / A
4	1				1	N / A
5	1			ans.		1

 

• n개에서 k개를 뽑는 것이므로 n < k 인 경우는 구할 필요가 없음
• n개에서 n개를 뽑는 경우, n개에서 1개를 뽑는 경우의 수는 1가지

2) local neighbor 계산을 이용해 그 다음으로 쉬운 문제 점점 풀어나가기

	0	1	2	3	4	5
0	1	N / A	N / A	N / A	N / A	N / A
1	1	1	N / A	N / A	N / A	N / A
2	1	2	1	N / A	N / A	N / A
3	1	3	3	1	N / A	N / A
4	1		here	here	1	N / A
5	1			ans.		1

 

• 그 다음 쉬운 문제 => B[2,1] = B[1,0] + B[1,1] = 1 + 1 = 2
• 그 다음 => B[3,1] = B[2,0] + B[2,1] = 1 + 2 = 3
• 그다음 => B[3,2] = B[2,1] + B[2,2] = 2 + 1 = 3
• ...
• ans (5,3) = (4,2)+(4,3) ==> 표의 바로 위와 왼쪽 위를 활용하여 채울 수 있음.
• => neighbor clever enumeration 

neighbor clever enumeration != brute-force enumeration

=> burte force는 매순간 필요한 계산을 매번 함, 하지만 이 방식은 한번씩만 계산 해 놓고, 그걸 활용해서 계산에 이용.

DP == Save and Reuse.

 

	0	1	2	3	4	5
0	1	N / A	N / A	N / A	N / A	N / A
1	1	1	N / A	N / A	N / A	N / A
2	1	2	1	N / A	N / A	N / A
3	1	3	3	1	N / A	N / A
4	1		6	4	1	N / A
5	1			ans. = 10		1

 

 

DP : Binomial Design - Analysis

Step 1(resurrent eqn)

Step 2(bottom-up save and reuse)

Design = steps + 기본적 골격. + example
           = detailed algorithmic code X

DP_Bin(n,k) : iterative(for-loop, while-loop)
----------------------------------
for i = 0 -> n //step 2
    for j = 0 -> min(i,k) // k는 n의 개수를 넘을 수 없으므로 
        if(j==0 or j == i) B[i,j] = 1
        else B[i,j] = B[i-1,j-1] + B[i-1. j]  // step 1.
return B[n,k]

Analysis? Time complexity : T(n, k) = O(?)

 

D&C analysis TC = divide + conquer + combine

DP basic operations = array cell computations.
= table build-up time

 

 

B[5,3]의 계산량을 파악해보자.

	0	1	2	3	4	5
0	1
1	2	3
2	4	5	6
3	7	8	9	10
4	11	12	13	14	필요없음
5	15	16	17	18

 

• 1
• 2
• 3 (k)
• 4
• 4
• 4

 

B[5,4]의 계산량을 파악해보자.

	0	1	2	3	4	5
0	1
1	2	3
2	4	5	6
3	7	8	9	10
4	11	12	13	14	15
5	16	17	18	19	20

• 1
• 2
• 3
• 4 (k)
• 5
• 5

 

==> 

 

T(n,k) = 1+2+3+...+ k + (k+1)*(n-k+1) 
= k(k+1)/2 + (k+1)*(n-k+1) = O(nk)
= (2n-k+2)(k+1)/2 = O(nk)  ==> 테이블 크기 만큼

===> 쉽다. 그러므로 step 1을 유도하는 과정에 힘을 쏟아야 함.

 

 

 

DP : CMM Design - Part 1

DP for Chained Matrix Multiplication(CMM)

Def. Given a given ordered sequence of matrices,
Find an optimal order(= min # multiplications) for CMM.

 

Multiplying A = [pxq], B = [qxr] => AB = [pxr]
A = [3x3], B = [3x2] => AB = [3x2]  ==> matrix 곱 자체가 cpu 낭비가 심한 operation

Multiplying Chained Matrices (a sequence of matrices)
     A   x   B   x    C    x   D
[20x2] [2x30] [30x12] [12x8]  ==> 가장 짧게 끝나는 행렬 곱은?

--> Design : B&F = O(2^n), D&C(???), DP

 

 

 

Step 0. examples (guessing)
Step 1. recursive property = recurrence (math. expression)
Step 2. save/reuse

 

 

Step 0. examples (guessing)
: start with easier subproblems (hand computation)
: insight

  A1 x  A2 x  A3 x  A4 x  A5 x A6
[5x2] [2x3] [3x4] [4x6] [6x7] [7x8]
=> 가장 쉬운 문제? A1 x A1 = 0
=> 쉬운 문제? A2 x A3, A4xA5 ... A5xA6  (matrix 두개 곱하기)

A4 x A5 = 4x6x7 -> array 2D array M[4,5] save
*이걸 이차원 배열에 저장한다는 생각부터 하기 쉽지 않다...
A5 x A6 = 6x7x8 -> M[5,6] save
==> A3 x A2(X)   :  왜? 애초부터 matrix 순서는 1-2-3-4-5-6 으로 정해져서 주어짐. 반대 => 아예 다른거

 

M	1	2	3	4	5	6
1	0	5x2x3
2	N / A	0	2x3x4
3	N / A	N / A	0	3x4x6
4	N / A	N / A	N / A	0	4x6x7
5	N / A	N / A	N / A	N / A	0	6x7x8
6	N / A	N / A	N / A	N / A	N / A	0

 

 

 

==> 한단계 더 나아간다
==> 그 다음 쉬운 문제는?
A4 x A5 x A6 = min(P,Q)
1) (A4xA5)xA6 = 4x6x7 + 4x7x8 = M[4,5] + 4x7x8 = P
2) A4x(A5xA6) = 6x7x8 + 4x6x8 = M[5,6] + 4x6x8 = Q

 

M	1	2	3	4	5	6
1	0	5x2x3
2	N / A	0	2x3x4
3	N / A	N / A	0	3x4x6
4	N / A	N / A	N / A	0	4x6x7	min(P,Q)
5	N / A	N / A	N / A	N / A	0	6x7x8
6	N / A	N / A	N / A	N / A	N / A	0

 

====> next ?
A1xA2xA3xA4 = M[1,4]
= min(M[1,3] + alpha, M[2,4]+beta, M[1,2]+M[3,4]+gamma)
(A1~A3)xA4
A1x(A2~A4)
(A1xA2)x(A3xA4)

 

M	1	2	3	4	5	6
1	0	5x2x3	M[1,3]	M[1,4]
2	N / A	0	2x3x4	M2,4]
3	N / A	N / A	0	3x4x6
4	N / A	N / A	N / A	0	4x6x7
5	N / A	N / A	N / A	N / A	0	6x7x8
6	N / A	N / A	N / A	N / A	N / A	0

 

 

====> Final : M[1,6] = min
1. A1x(A2~A6) =      M[1,1] + M[2,6] + 5x2x8
2. (A1A2)x(A3~A6) =  M[1,2] + M[3,6] + 5x3x8
3. (A1~A3)x(A4~A6) = M[1,3] + M[4,6] + 5x4x8
4. (A1~A4)x(A5A6) =  M[1,4] + M[5,6] + 5x6x8
5. (A1~A5)xA6 =      M[1,5] + M[6,6] + 5x7x9

 

 A1 x  A2 x  A3 x  A4 x  A5 x A6
[5x2] [2x3] [3x4] [4x6] [6x7] [7x8]

M	1	2	3	4	5	6
1	0	5x2x3 = 30	30 + 5x3x4 = 90 24 + 5x2x4 = 64	64 + 5x4x6 = 184 72 + 5x2x6 = 132 30+72+5x3x6 = 192	132 + 5x6x7 = 342 156 + 5x2x7 = 226 64+168+5x4x7 30+198+5x3x7	226 + 5x7x8 = 506 268 + 5x2x8 = 348 132+336+5x6x8 = 708 64+392+5x4x8 = 616 30+276+5x3x8 = 426
2	N / A	0	2x3x4 = 24	24 + 2x4x6 = 72 72 + 2x3x6 = 108	72 + 2x6x7 = 156 198 + 2x3x7 = 240 24+168+2x4x7 = 248	156 + 2x7x8 = 268 276 + 2x3x8 = 324 72+336+2x6x8 24+392+2x4x7
3	N / A	N / A	0	3x4x6 = 72	72 + 3x6x7 = 198 168 + 3x4x7 = 252	198 + 3x7x8 = 366 392 + 3x4x8 = 488 72+336+3x6x8 = 552
4	N / A	N / A	N / A	0	4x6x7 = 168	168 + 4x7x8 = 392 336 + 4x6x8 = 528
5	N / A	N / A	N / A	N / A	0	6x7x8 = 336
6	N / A	N / A	N / A	N / A	N / A	0

 

Recurrence eqn.  

M[1,6] = min(M[1,k] + M[k+1,6] + C(0)xC(k)xX(6))
         for 1<=k<=5  (==> k 값이 변함 ?  k에 대한 범위가 필요함)

M[i,j] = min{  M[i,k] + M[k+1, j] + C(i-1)C(k)C(j)  }   
            for i <= k <= j-1
M[i,i] = 0

 

** C(i-1) 인 이유

=> result matrix의 크기는 i번째 matrix의 행 x   ?    x  j번째 matrix 의 열

=> 여기서의 C는 column을 나타내므로, i번째 matrix의 row를 나타내려면, i-1번째 matrix가 있다고 가정 후

Ai-1[?, C(i-1)]  Ai[C(i-1), C(i)] ....... Aj [?, C(j)]  이렇게 나타내는 것. (순서가 있는 행렬곱이라 이어진다)

 

 

 

DP: CMM - Analysis

DP(CMM) = linear # combinations

DP_CMM(input: matrices_seq, dimensions_row_col)
{
    for i -> n
        for j -> n
            M[i,j] = recurrence : function of subproblems
            ==> for(k= i -> j-1)

            즉
            for-loop(k)
            ...
            M[i,j] <- min()

}

 

==> 낭비 심함  ==> code optimization!! in DP.

 

 

Analysis: Time complexity A1xA2x...xAn

T(n) = #subproblems * time/subprob = O(n^3)
T(n) = O(n^2) * n -> O(n^3)

교과서 보면 보다 자세하게 구현되어 있다고 한다.
==> 아래쪽을 계산할 필요가 없으므로 인덱싱을 잘해서 코드 최적화를 이룰 수 있다.

=> code optimization is required for running-time for A.