연쇄 행렬 곱셈

연쇄 행렬 곱셈은 주어진 n개의 연쇄 행렬을 곱하는 최적의 순서를 구하는 문제

  • 행렬 곱셈은 결합 법칙이 성립하지만 곱셈 순서에 따라 각 원소의 곱셈 횟수가 달라짐 → 이 곱셈 횟수가 가장 작아지는 최적의 순서를 구하기
  • 2 x 3 행렬과 3 x 4 행렬을 곱하면 2 x 4 행렬이 됨
    → i x k 행렬과 k x j 행렬을 곱하면 i x j 행렬이 되며
    → 원소 곱셈의 횟수는 i * k * j가 된다
  • Brute-force 방식으로 접근하기
    • 모든 경우의 수(카탈랑 수)를 계산하여 최적의 순서를 선택
    • 카탈랑 수는 결국 지수함수이므로 너무 오래걸림
  • Dynamic Programming 방식으로 접근하기
    1. 재귀 관계식을 찾는다
    • M: 연쇄 행렬을 곱하는데 필요한 최소 횟수 행렬
    • M[i][j]: Ai에서 Aj까지 행렬을 곱하는데 필요한 최소 횟수
    • Ai … Aj 행렬을 (Ai … Ak)(Ak+1 … Aj)로 분할하는 재귀 관계식 찾기
    1. 상향식 방법으로 해답을 구하기
    • M[i][i] = 0 (대각선에 위치하는 원소를 0으로 초기화)
    • M[1][n]을 상향식으로 계산 (대각선 1번, 대각선 2번 … 대각선 n-1번)
    • n개의 행렬을 두 개의 최적 부분행렬의 곱으로 분할
    • M[i][j] = minimum(M[i][k] + M[k+1][j] + di-1dkdj) // 단, i ≤ k ≤ j-1

파이썬으로 연쇄 행렬 곱셈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def minmult (d):
    n = len(d) - 1
    M = [[-1] * (n + 1) for _ in range(n+1)]
    P = [[-1] * (n + 1) for _ in range(n+1)]
    for i in range(1, n + 1):
        M[i][i] = 0
    for diagonal in range(1, n):
        for i in range(1, n - diagonal + 1):
            j = i + diagonal
            M[i][j], P[i][j] = minimum(M, d, i, j)
    return M, P 

def minimum (M, d, i, j):
    minVal = INF
    minK = 0
    for k in range(i, j):
        value = M[i][k] + M[k + 1][j]
        value += d[i -1] * d[k] * d[j]
        if (minVal > value):
            minVal = value
            minK = k
    return minVal, minK

def order(P, i, j):
    if (i == j):
        print('A%d'%(i), end = '')
    else:
        k = P[i][j]
        print('(', end = '')
        order(P, j, k)
        order(P, k + 1, j)
        print(')', end = '')

자바스크립트로 연쇄 행렬 곱셈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const minmult = d => {
    let n = d.length -1
    let arr = Array.from(Array(n+1), () => Array(n+1).fill(-1))
    let arr2 = [...arr];
    for (let i = 1; i < n+1; i++){
        arr[i][i] = 0;
    }

    for (let diagonal = 1; diagonal < n; diagonal++){
        for (let i = 1; i < n - diagonal + 1; i++){
            j = i + diagonal;
            arr[i][j] = minimum(arr, d, i, j).minVal; 
            arr2[i][j] = minimum(arr, d, i, j).minK; 
        }
    }
    return { result : arr, optimal: arr2 };
}

const minimum = (arr, d, i, j) => {
    let minVal = Infinity;
    for (let k = i; k < j; k++) {
        let value = arr[i][k] + arr[k+1][j] + d[i - 1] * d[k] * d[j]
        if (minVal > value){
            minVal = value;
            minK = k
        }
    }
    return {minVal : minVal, minK : minK}
}

const order = (arr2, i, j) => {
    if (i === j) str += `A${i}`
    else {
        let k = arr2[i][j]
        str += '('
        order(arr2, i, k)
        order(arr2, k+1, j)
        str += ')'
    }
}
/*
예시) 
let d = [5, 2, 3, 4, 6, 7, 8];
let { result, optimal } = minmult(d)
order(optimal, 1, d.length - 1)
console.log(result)
console.log(str) -> `(A1(A2(A3(A4(A5A6)))))`
*/