on
Dynamic Programming
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
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=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
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를 통해 출력하기
from http://bohyeonstudy.tistory.com/114 by ccl(A) rewrite - 2021-08-12 13:00:18