Dynamic Programming

• Dynamic Programming
  • Similar / Different to Divide and Conquer
  • Step 1, Step 2
• 3.1 : The Binomial Coefficient
  • Using Divide and Conquer
  • Using Dynamic Programming
    • Time Complexity
• 3.2 : Floyd's Algorithm for Shortest Path
  • Shortest Paths Problem
  • Simple Algorithm 
  • Floyd's Algorithm
• 3.3 Dynamic Programming and Optimization Problem
• 3.4 Optimal Binary Search Trees
• 3.6 Traveling SalesPerson Problem

 

 

---

Dynamic Programming

(1) Similar to “Divide and Conquer”

- an instance of a problem is divided into one or more smaller instances.

(2) Different from “Divide and Conquer” 

- smaller instances are solved first, and then they are retrieved later when needed

먼저 구한 뒤, 필요시 꺼내쓴다.

Dynamic Programming is Bottom-Up 

- Divide and Conquer is Top Down.

DP Top Down 방식 : memoization

 

Step 1: (중요)

Establish a recursive property that gives the solution to an instance of the problem.

Step 2 : 

Solve an instance of the problem in a bottom-up fashion by solving smaller instances first.

---

 

3.1 The Binomial Coefficient

Binomial Coefficient

0<k<n : 1~n개 중 k개를 고를 때, n을 포함/불포함의 합으로 나타낸다

k=0 or k=n : 예외처리

 

Binomial Coefficient using Divide and Conquer

(1) code

Inputs:
n, k – nonnegative integers (k ≤ n)
Output: C(n,k)

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

-> 시간 복잡도 (중복계산으로 오래걸림)

2C(n,k) - 1 개의 노드 계산이 필요하다. 

T(n,k) = T(n-1, k-1) + T(n-1, k) + 1

 

Binomial Coefficient using Dynamic Programming

(1) 개념 설명

Suppose that we use 2- dim. array B to store all the values of C(i,j) ( 0 ≤ i ≤ n, 0 ≤ j ≤ k )

B[i][j]= { B[i-1][j-1]+B[i-1][j] (0<j<i),

            1 (j=0 or i=j) }

이차원 배열을 이용해 위에서 아래로, 작은 값부터 체워넣어서 ? 값을 구한다.

(2) code

Inputs:
n, k – nonnegative integers (k ≤ n)
Output: C(n,k)

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-1]+B[i-1][j] ;
  	return B[n][k] ;
}

 

min( i, k) 

---

3.2 Floyd’s Algorithm for Shortest Paths

The Shortest Paths Problem

1. simple source : 출발점 고정 ex) 다이스트라, 그리디

2. all path : 모든 순서쌍, 출발도착 고정 X ex) Floyd

Floyd’s Algorithm

(1) 개념설명

We use an n x n weight table W for a graph with n nodes

행 : start 노드 , 열 : end 노드 로 edge가 없는 경우 무한대로 표시하고 자기자신은 0으로 표현한다.

 

Given a pair of vertices (vi , vj ), 1≤ i, j ≤n,

i에서 j까지의 최단경로의 길이이다.

중간노드는 오직, 1에서 k까지의 노드를 이용한다. (1<=k<=n)

= W[i][j]

 

example : 위의 노드들 그림에서, 

이므로, = min(length[v2 , v5 ], length[v2, v1, v5]) = min(∞ ,14) = 14

 

 

case 1 : 1~k의 중간노드에서 k를 지나지 않는 경우 

case 2 : 1~k의 중간노드에서 k를 지나는 경우

Combine (case1 + case2)

(2) code

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 

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

void floydPath(int n, const number W[ ][ ],number D[ ][ ], number P[][])
{
      index i,j,k ;
      for (i=1; i <= n ; i++)
          for (j=1; j <= n ; j++)
          		P[i][j]=0 ;
      			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 ;
					}
}

P[][]에 중간 경로를 저장해준다.

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) ;
}
}

최단 경로의 루트를 p를 통해 출력하기

 

---

3.3 Dynamic Programming and Optimization Problem

Principle of Optimality

항상 모든 subinstance들이 optimal solution에 포함되어야 한다.

 

Example: Shortest Path Problem

Counter Example: Longest Simple Path Problem

---

3.4 Optimal Binary Search Trees

Binary Search Tree

왼쪽 노드 <= root 노드 <= 오른쪽 노드 가 성립하는 트리이다.

void search(node_pointer tree, keytype keyin, node_pointer& p)
{
      bool found = false;
      p = tree ;
      while ( ! found )
			if (p->key == keyin)
					found = true ;
			else if (keyin < p->key)
					p = p->left ;
			else
					p = p->right ;
}

BST에서, 찾고자 하는 keyin을 찾을 때의 알고리즘

/

BST 알고리즘에서 key1 <= key2 <= ... keyn의 조건이 있다.

Pi는 , key i가 찾는keyin일때의 확률을 뜻한다.

이때 우리는

Ci가 key를 찾을 때의 내려가는 depth라고 할 때,

확률과 depth의 최소값의 합을 구하려고 한다.

 

 

example : three keys Key1≤Key2 ≤ Key3, P1= 0.7, P2 =0.2 , Pn =0.1

조건(Key1≤Key2 ≤ Key3)에 맞는 BST는 다섯가지가 있는데

찾고자 하는 이 값의 최소값은 첫번째 BST가 된다.

이것이 optimal BST이다. 

 

 

Dynamic Programming Approach

(1) DP로 풀 수 있는지 판단하기

(2) 배열 생성 및 배열의 의미부여하기

(3) boundary condition

 

(1) Suppose that keys Keyi through Keyj are arranged in a tree that minimizes

 

(2) 배열 생성.

and that A[i][j] is such a minimum value.  (Note: A[i][i] = pi )

 

루트에 있는 key k 의 optimal binary search tree 를 생각해보자. 3.3 DP조건에 따라 왼쪽, 오른쪽 subtree는 must be optimal 이다. 

왼쪽 subtree는 A[1][k-1], 오른쪽 subtree A[k+1][n]일 때,

왼쪽 subtree + 왼쪽 subtree들어가는 확률 값 + key k의 확률 + 오른쪽 subtree + 오른쪽 subtree들어가는 확률 값

 

(왼쪽 subtree들어가는 확률 값+key k의 확률 + 오른쪽 subtree들어가는 확률 값 ) 하나로 묶었다.

1<=k<=n은 위의 식이 root가 k인 경우의 식이니까, k의 범위대로 나타냄.

 

(3) boundary condition

i<=k<=j의 범위에서 k=i,j인 경우에서 조건을 넣어줘야 한다. 

만들어진 A 배열 모양.

(4) code

우리가 구해야 하는 값은 A[1][n]이다. 즉 1에서 n까지 가는 최솟값.

이때 대각선을 이용해 빠르게 찾는다. 

void optSearchTree(int n, const float p[], float& minavg, index R[][])
{
			index i,j,k, diagonal; float A[1..n+1][0..n] ;
			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 ;
			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])+∑m=ij pm;
						R[i][j]=a value of k giving the minimum
                    }
                    minavg = A[1][n] ;

(1) boundary condition 작성

(2) for문

i : 행 번호, j : 열 번호

 

---

3.6 Traveling SalesPerson Problem

Traveling SalesPerson Problem

Given n nodes in a graph,

find the shortest route starting from a node and ending at itself

while visiting each of other nodes once.

모든 노드를 한번씩 방문하고 자기 자신으로 돌아오기까지의 최단경로

Dynamic Programming Approach

(1) V1에서 출발한다고 했을 때, 아래 그림들 중 하나가 답일 것이다. 

(2) 배열 생성

Let V = {v1, v2, … , vn}, the set of all vertices

A = a subset of V ex) {v1,v2, v3} 

D[vi ][A] = the length of shortest path from vi to v1 passing through each vertex in A exactly once

(vi에서 A의 노드를 지난 뒤 v1으로 돌아오는 경로들 중 , 최단경로 )

(3) boundary condition

시작노드를 v1이라고 하고 그다음 지나는 노드를 j라고 할 때,

경로의 값 = v1-vj의 weight 값 + D[vj][ 지나온 v1,vj를 제외한 노드 ]

 

example)

 size = A가 갖고있는 노드개수

(4) code

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

					}
        D[1][V-{v1}]=min(W[1][j]+D[j][V-{v1 ,vj}]);//2≤j≤n
        P[1][V-{v1}]=value of j that gave the minimum;
        minLength = D[1][V-{v1}] ;
        }

3중 for문에서 

        for (k=1; k<= n-2; k++)  
        	for (all subsets A⊆V –{v1} containing k nodes)

D[ ][ ] : 두번째 괄호 조건들.

K 는 A의 size이다. 

k 값에 따라서 k노드들을 포함하는 

for (i such that i≠1 and vi is not in A) do {

D[ ][ ] : 첫번째 괄호 조건.