6-3강 - Dynamic Programming 3 (the principal of optimality, 행렬 곱셈)

간혹 Dynamic Programming을 적용할 수 없는지 알아내는 방법이 바로 The Principle of Optimality입니다.

 

cf> The Principle of Optimality

instance 전체에서 optimal solution이면 → subinstance 한정해서도 optimal solution이어야 한다.

1> 예제 1 

- P(s, t)가 shortest path -> P(s, w)와 P(w, t) 모두 shortest path (True)

- reverse : P(s, w)와 P(w, t) 모두 shortest path -> P(s, t)가 shortest path (False)

 

2> 예제 2 - Floyd's shortest path problem

Dk (i, j)가 i에서 j까지의 shortest path일 때, P(i, j) = shortest path라고 한다. 

= P(i, j) 내부 vertex는 모두 k이하입니다.

-> P(u, v) [in P(i, j)] 내부 vertex도 모두 k이하이다.

 

3> 예제 3 - The Principle of Optimality이 적용이 안 되는 경우

[v1, v2, v3, v4]가 longest simple path이지만 

-> [v1, v3]는 longest simple path가 아닙니다.

 

3. Chained Matrix Multiplication

0) Chained Matrix Multiplication

• A[n x k]와 B[k x m]은 n x K x m개의 multiplication이 필요합니다.
• 그래서 최적의 곱셈 순서가 존재합니다.

 

1> Brute Force Method (전체 탐색)

A₁, A₂, ... , A_n을 곱할 때 곱셈의 경우의 수를 모두 탐색하면 

=> 곱셈의 경우의 수 t_n ≥ 2^n-2

=> 경우의 수가 너무 많아서 전체 탐색하기 어렵습니다. 

 

2> The Principle of Optimality

OR : A₁, A₂, ... , A_n 곱셈에서 optimal order

OR_R : A₁, A₂, ... , A_k-1 곱셈에서 optimal order 후보 (OR의 앞부분)

OR_L : A_k, A_k+1, ... , A_n 곱셈에서 optimal order 후보 (OR의 뒷부분)

(귀류법 사용해본다.)

전제 : OR이 optimal order이고 이를 분할하면 OR_R과 OR_L로 나뉩니다. 

가정 : OR'_R이 optimal order라고 가정합니다.

전제 부정 : 그러면 OR이 아닌 OR'_R + OR_L이 전체에서 optimal order이라는 모순이 생깁니다.

∴ 그러므로 Chained Matrix Multiplication에도 DP를 적용할 수 없습니다.

 

3> Divde and Conquer?

아무 곳에서나 divide가 불가능합니다.

A2 -> A3 -> A4 순서대로 연산하기 때문에 A3과 A4 사이에서 divde가 불가능합니다. 

 

1) Algorithm (DP 적용)

0개 index 차이나는 것 -> 1개 index 차이나는 것 -> 2개 index 차이나는 것 -> 3개 index 차이나는 것

 

0> recursive form을 위한 정의 M[i][j] 정의

M[i][j] : Ai부터 Aj까지 곱셈할 때, minimum number of multiplication

(0개 index 차이나면, M[i][i] = 0)

 

1> recursive form

M[i][j] = min(M[i][k] + M[k][j] + di-1dkdj) (i ≤ k ≤ j - 1)

k에서 cut한 경우

[1] M[i][k] : Ai~Ak에서의 최소 곱셈 수 (shape : di-1 x dk)

[2] M[k][j] : Ak~Aj에서의 최소 곱셈 수 (shape : dk x dj)

[3] di-1dkdj : [1]과 [2]를 곱해서 생기는 곱셈 수

그리고 k가 i~j까지 변하면서 최소를 찾으면 됩니다.

 

2> bottom-up

(M[j][i] 그리기)

index 1개 차이나는 것을 계산하고

index 2개 차이나는 것을 계산하고

index 3개 차이나는 것을 계산하고

...

그러면 전체 A1~An 곱셈했을 때, 최소 연산 수를 구할 수 있습니다.

 

3> top-down

[1] memo

P[i][j] : M[i][j]에서 최소로 분할하는 k를 기록합니다.

diagonal : 2> 그림에서 index 차이를 의미합니다. (index 1개 차이 -> index n-1개 차이)

 

[2] 그래서 optimal order를 출력하려면

P[i][j] = k를 기준으로 계속해서 나눠가고

더 이상 나눌 수 없을 때, Ak를 print합니다.

 

 

2) Time Complexity

θ(n^3)