Prolem : Find an optimal order for mult. n mat
Q. Given (d0, d1, d2, d3, d4, d5) = (2,4,1,3,4,2), solve the chained matrix multiplication problem. You may have only to make an array M and an array P. (You have only to make a table such as in p46 of the notebook.) What is the optimal order of the matrix multiplications?
1. i, j의 거리가 1일때
M[1,2] = 2 x 4 x 1 = 8 (k = 1)
M[2,3] = 4 x 1 x 3 = 12 (k = 2)
M[3,4] = 1 x 3 x 4 = 12 (k = 3)
M[4,5] = 3 x 4 x 2 = 24 (k = 4)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 8 (k = 1) | |||
| 2 | 0 | 12 (2) | |||
| 3 | 0 | 12 (3) | |||
| 4 | 0 | 24 (4) | |||
| 5 | 0 |
2. i, j의 거리가 2일 때
M[1,3] = min ( M[1,1] + M[2,3] + d0d1d3 = 0 + 12 +2 x 4 x 3 = 20,
M[1,2] + M[3,3] + d0d2d3 = 8 x 0 + 2 x 1 x 3 = 14 ) = 14 (k = 2)
M[2,4] = min ( M[2,2] + M[3,4] + d1d2d4 = 0 + 12 + 4 x 1 x 4 = 28,
M[2,3] + M[4,4] + d1d3d4 = 12 +0 + 4 x 3 x 4 =60 ) = 28 (k =2)
M[3,5] = min ( M[3,3] + M[4,5] + d2d3d5 = 0 + 24 + 1 x 3 x 2 = 30,
M[3,4] + M[5,5] + d2d4d5 = 12 + 0 + 1 x 4 x 2 = 20) = 20 (k = 4)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 8 (k = 1) | 14 (2) | ||
| 2 | 0 | 12 (2) | 28 (2) | ||
| 3 | 0 | 12 (3) | 20 (4) | ||
| 4 | 0 | 24 (4) | |||
| 5 | 0 |
3. i, j의 거리가 3일 때
M[1,4] = min (M[1,1] + M[2,4] + d0d1d = 0 + 28 + 2 x 4 x 4 = 56,
M[1,2] + M[3,4] + d0d2d4 = 8 + 12 + 2 x 1 x 4 = 28,
M[1,3] + M[4,4] + d0d3d4 = 14 + 0 + 2 x 3 x 4 = 38) = 28 (k =2)
M[2,5] = min (M[2,2] + M[3,5] + d1d2d5 = 0 + 20 + 4 x 1 x 2 = 28,
M[2,3] + M[4,5] + d1d3d5 = 12 + 24 + 4 x 3 x 2 = 60,
M[2,4] + M[5,5] + d1d4d5 = 28 + 0 + 1 x 4 x 2 = 36) = 28 (k = 2)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 8 (k = 1) | 14 (2) | 28 (2) | |
| 2 | 0 | 12 (2) | 28 (2) | 28 (2) | |
| 3 | 0 | 12 (3) | 20 (4) | ||
| 4 | 0 | 24 (4) | |||
| 5 | 0 |
4. i,j의 거리가 4일 때
M[1,5] = min (M[1,1] + M[2,5] + d0d1d5 = 0 + 28 + 2 x 4 x 2 = 44,
M[1,2] + M[3,5] + d0d2d5 = 8 + 20 + 2 x 1 x 2 = 32,
M[1,3] + M[4,5] + d0d3d5 = 14 + 24 + 2 x 3 x 2 =50,
M[1,4] + M[5,5] + d0d4d5 = 28 + 0 + 2 x 4 x 2 = 44) = 32 (k = 2)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 8 (k = 1) | 14 (2) | 28 (2) | 32 (2) |
| 2 | 0 | 12 (2) | 28 (2) | 28 (2) | |
| 3 | 0 | 12 (3) | 20 (4) | ||
| 4 | 0 | 24 (4) | |||
| 5 | 0 |
따라서 묵는 방법은 첫행을 비교해서 K일때 끊어주면 된다.
1 . A1A2 | A3 (2)
2. A1A2 | A3A4 (2)
3. A1A2 | A3A4A5 (2)
따라서 , A1A2((A3A4)A5)
연습문제
Q1. (d0, d1, d2, d3, d4, d5) = (7,4,6,2,3,5)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 168 (k = 1) | 104 (1) | 146 (3) | 204 (4) |
| 2 | 0 | 48 (2) | 72 (3) | 132 (4) | |
| 3 | 0 | 36 (3) | 90 (3) | ||
| 4 | 0 | 30 (4) | |||
| 5 | 0 |
1. A1 | A2A3
2. A1A2A3 | A4
3. A1A2A3A4 | A5
따라서 (A1(A2A3)A4)A5
Q2. (d0, d1, d2, d3, d4, d5) = (4,3,2,2,3,4)
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 24 (k = 1) | 36 (1) | 60 (2, 3) | 92 (2, 3) |
| 2 | 0 | 12 (2) | 30 (2, 3) | 60 (2, 3) | |
| 3 | 0 | 12 (3) | 36 (4) | ||
| 4 | 0 | 24 (4) | |||
| 5 | 0 |
1. A1 | A2A3
2. A1A2 | A3A4
3. A1A2 | A3A4A5
A1A2((A3A4)A5)
cf.) k 가 2개인 경우 작은 수!