Chap 3. Dynamic Programming

Dynamic Programming이란?

최적화 문제를 풀기 위한 수학적인 알고리즘.
문제를 작은 부분 문제로 나누고, 중복되는 부분 문제의 해를 저장하여 중복 계산을 피할 수 있고, 작은 부분 문제의 해를 조합하여 전체 문제의 해를 구하는 방법(=Bottom-Up)
 
4가지의 예시를 통해 Dynamic Programming에 대해 자세히 알아보자.

1. The Binomial Coefficient

C(n, k) = C(n-1, k) + C(n-1, k-1) for 0<k<n
C(n, k) = 1 for k=0 or k=n
 
Pseudo-Code using Divide and Conquer -> Top Down

public static int Bin(int n , int k){
	if(k == 0 || k == n)
    		return 1;
	else
    		return Bin(n-1, k) + Bin(n-1, k-1);
}

Pseudo-Code using Dynamic Programming

public static int Bin2(int n, int k){
	index i, j;
	int [][]B = new int[0..n][0..k];
    
    for(i = 0; i <= n; i++)
	for(j = 0; j <= min(i,k); j++)
            if(j == 0 || j == i)
            	B[i][j]=1;
            else
            	B[i][j]=B[i-1][j]+B[i-1][j-1];
	return B[n][k];
}

2. Floyd's Algorithm for Shortest Paths

given a pair of vertices (vi, vj), 1 <= i, j <= n

• D(k)[i][j] = 오직 집합 {v1, v2, .... , vk} 에 있는 노드들만 사용해서 vi → vj 로 가는 최단 경로
• D(0)[i][j] = W[i][j]
  • 어떤 노드도 통과하지 않고 바로 vi → vj로 가는 경로

Floyd's Algorithm 재귀식

D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i - 1][j] + D(k-1)[i - 1][j - 1])

void Floyd(int n, const number W[][], number D[][]){
    index i, j, k;
    D = W;
    
    for(k = 1; k <= n; k++)
    	for(i = 1; i <= n; i++)
            for(j = 1; j<= n; j++)
            	D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
}

T(n) = n * n * n 

void FloydPath(int n, const number W[][], number D[][], number P[][]){
    idex i, j, k;
    
    for(i = 1; i <= n; i++)
    	for(j = 1; j <= n; j++)
        	P[i][j] = 0;	// 중간에 거치는 v가 없음
    D = W;
    
    for(k = 1; k <= n; k++)
    	for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
            	if(D[i][k] + D[k][j] < D[i][j]{
                    D[i][j] = D[i][k] + D[k][j];
                    P[i][j] = k;	// vi → vj로 갈 때, k 거침
                 }
}

void Path(index q, r) {
    if(P[q][r] != 0) {
    	Path(q, P[q][r]);
    	cout << "v" << P[q][r];
    	Path(P[q][r], r);
    }
}

3. Optimal Binary Search Trees

Binary Search Tree 정의

• 각각의 노드는 하나의 key를 포함
• 주어진 노드의 왼쪽 서브트리에 있는 key들은 주어진 노드의 키보다 작거나 같음
• 주어직 노드의 오른쪽 서브트리에 있는 key들은 주어진 노드의 키보다 크거나 같음

 

Boundary condition

• A[i][i] = Pi
  • key i 만 가지고 binary search tree를 만듦
  • 즉, 노드 1개짜리 binary search tree가 됨 

⭐️ ∑ 수식 설명 ⭐️
Pk : 루트 노드가 등장할 확률, Pk* 1 값인데 생략된 *1은  depth가 1이므로 곱해주는 값
A[1][k-1] : 왼쪽 서브트리의 최적화 값
A[k+1][n] : 오른쪽 서브트리의 최적화 값
첫번째 ∑ : 왼쪽 서브트리 각각의 key 값들을 루트 노드( = key k)와 비교한 값들의 합
두번째 ∑ : 오른쪽 서브트리 각각의 값들을 루트 노드( = key k)와 비교한 값
 

Optimal Binary Search Trees 재귀식

A[i][j] = min(A[i][k-1] + A[k+1][j] + ∑ Pm
------------ Boundary Condition ------------
A[i][i] = Pi
A[i][i-1] = A[j+1][j] = 0    →    없는 case
----------------------------------------------
 
Pseudo-Code

void OptSearchTree(int n, const float p[], float& minavg, index R[][]){
    index i, j, k, diagonal;
    float A[1..n+1][o..n];
    
    // boundary condition
    for(i = 1; i <= n; i++){
    	A[i][i-1] = 0; A[i][i] = p[i];
        R[i][i] = i; R[i][i-1] = 0;
    }
    A[n+1][n] = 0; R[n+1][n] = 0;
    
    // recursive property
    for(diagonal = 1; diagonal <= n-1; diagonal++)
    	for(i = 1; i <= n - diagonal; i++){
            j = i + diagonal;
            A[i][j] = min(A[i][k-1] + A[k+1][j]) + pm;
            
            R[i][j] = a value of k giving the minimum;
	}
    // answer
    minavg = A[1][n];
 }

T(n) = ∑ (j-i+1) * (n-diagonal) = ∑ (diagonal+1) * (n-diagonal) = n(n-1)(n+4)/6 ∈ 𝚯(n^3)

4. Traveling SalesPerson Problem(TSP)

TSP 재귀식
D[vi][A] = min(W[i][j] + D[vj][A-{vj}]) if A ≠ ∅
------------ Boundary Condition ------------
D[vi][∅] = W[i][1]
----------------------------------------------
 
Pseudo-Code

void Travel(int n, const number W[][], index p[][], number& minLength){
	index i, j, k; 
	number D[1..n][subset of V-{v1}];
    
	//boundary condition
	for(i = 2; i <= n; i++)
		D[i][∅] = W[i][1];
	for(k = 1; k <= n-2; k++)
    	for(all subsets A ⊆ V-{v1} contains k nodes)
        	for(i such that i≠1 and vi is not in A){
            	D[i][A] = min(W[i][j] + D[j][A-{vj}]);
                
                R[i][A] = value of j giving the minimum
            }
	// answer
	D[1][V-{v1}] = min(W[i][j] + D[j][V-{v1, vj}]);
	P[1][V-{v1}] = value of j that gave the minimum;
	minLength = D[1][V-{v1}];
}