Dynamic Programming - Chained Matrix Multiplication

3.3 Dynamic Programming and Optimization Problems

substance -> subinstance

Optimal solution 안에는 그 문제의 모든 subinstance의 solution이 다 포함되어 있다.

문제 자체가 이런 성질을 가지고 있어야 DP를 적용할 수 있다.

 

모든 문제가 가지고 있는 성질이 아니다.

---

3.4 Chained Matrix Multiplication

행렬이 교환법칙은 성립하지 않지만 결합법칙은 성립한다.

행렬의 곱셈은 standard algorithm을 사용한다.

 

scalar multiplication 이기도 하고 scalar addition 이기도 하다.

3번째가 가장 적게 걸린다.

 

곱하는 서로다른 순서가 몇가지냐? : Catalan number

 

 

괄호를 치는 방법의 가지 수는 2^(n-2) 보단 훨씬 크다.

곱하는 순서가 다른 방법의 가짓수를 tn 이라고 하면

tn ≥ tn-1 + tn-1 이다. 같거나 큰거보단 훨씬 크다.

tn-1 → A1 x (A2 x A3 x .... x An)

tn-2 → (A1 x A2 x .. X An-1) x An

 

---

M[i][j] = A[i] x .... x A[j] 를 구하는데 필요한 scalar multiplication의 최소 횟수 (1 ≤ i ≤ j ≤ n)

parentheses : 괄호

(Ai × ... × Ak) × (Ak+1 × ... × Aj)

M[i][k] = minimum(Ai × ... × Ak)

M[k+1]M[j] = minumum(Ak-1 × ... × Aj)

× 했을 때의 횟수 = d(i-1) × d(k) × d(j)

---

d0 d1 d2 d3 d4 d5 d6

 5   2   3   4   6   7   8

 

M[1][2] = M[1][1] + M[2][2] + d0d1d2

             = 0 + 0 + 5×2×3 = 30

 

30 / 24 / 72 / 168 / 336 먼저 채우고

그 다음 64 / 72 / 198 / 392 채운다.

 

왜냐면 M[1][4] 를 계산하기 전에 M[1][3]이 계산되어 있어야 하기 때문이다. 

 

M[i][j] = M[i][i] + M[i+1][j] + di × di+1 × dj

                  M[i][i+1] + M[i+2][j] + di × di+2 × dj

                  M[i][i+2] + M[i+3][j] + di × di+3 × dj

 

0 + 268 + (d0 × d1 × d6 = 180) = 348

30 + 366 + (d0 × d2 × d6 = 120) = 516

64 + 392 + (d0 × d3 × d6 = 160) = 616

132 + 336 + (d0 × d4 × d6 = 240) = 708

226 + 0 + (d0 × d5 × d6 = 280) = 506

중 minimum 값이 348이 된다.

 

이때 minimum이 되는 k값도 알아야 한다.

scalar multiplication만 구하면 안된다.

 

optimal order 은 T table에서 알 수 있다.

P(1,6) = 1 => A1 × (A2 × ... × A6)

P(2,6) = 5 => A1 × ((A2 × ... × A5) × A6)

P(2,5) = 4 => A1 × (((A2 × ... × A4) × A5) × A6)

P(2,4) = 3 => A1 × ((((A2 × A3) × A4) × A5) × A6)

이것이 optimal order 이다.

 

---

diagonal 은 i, j 간의 차이이다.  

diagonal = j - i

 

minimum이 되는 k값은 P에 저장한다.

 

최종적으로 리턴되는 값은 M[1][n] 이다.

---

A1 ... Ai ... Aj ... An 까지 곱하는 최소값

if ) i와 j 가 같다면 A 하나만 출력하면 된다.

else ) j가 i 보다 크다면 P배열의 i,j 값을 찾아봐야 한다.

그럼 그게 k 값이 된다.

 

A1 ... (Ai ... Aj) ... An 

Ai x ... x Aj 에서

(Ai x ... x Ak) 의 order 를 출력하고

(Ak+1 x ... x Aj) 의 order 를 출력한다 recursive로

 

그 후 cout 로 괄호 씌운다.

---

시간 복잡도

for loop로 구현

 

때마다 다르다. 괄호가 몇번 쳐지는지를 봐야 한다.

괄호가 마지막거 까지 합해서 총 5번 쳐진다.

 

각각의 행렬 출력하는 사건 = n

괄호 출력하는 사건 = n-1

order는 합쳐서 = 2n-1 번 호출된다.

 

따라서 

 

O(n^3 + n) = O(n^3)

---

곱셈 연산을 최소화 시키자

뭐가 optimal 한가?

경우의 수 에 따라서 T(n)이 달라진다.

최소 O(2^n)

 

d = d[0] , d[1] , ... , d[6]

0은 자기 자신을 곱한 것이다. 

6개의 행렬을 곱하는 

 

i>j 일 때는 볼 필요 없다. 

M[i][j] = minimum( [i]부터 [k]까지 곱하는 최소 갯수 + [k+1]부터 [j]까지 곱하는 최소 갯수 + d[i-1]d[k]d[j] )

 

d[0]d[k]d[4]