Chained Matrix Multiplication

강한친구·2021년 9월 3일

자료구조와 알고리즘

이 글은 유튜브 주니온TV의 알고리즘 기초 수업을 바탕으로 작성된 글입니다. 이미지, 내용 등 모든 저작권은 채널을 운영하시는 교수님에게 있습니다.

연쇄 행렬 곱셈

Chained Matrix Mulipication
n개의 행렬을 곱하는 최적의 순서를 구하는 문제

2 X 3 3 X 4 행렬하면 2 X 4 행렬이 나오고
총 필요한 계산수는 2 X 3 X 4이다.

그래서 어떻게 풀어야 하는가?

우선 Brute-Force로 풀어보겠다.
단순무식법으로 풀기 위해서는 말 그대로 모든 경우의 수를 다 수해아고 총 수행한 계산의 수를 비교하여 최적의 수를 찾는 방법이다.

이와 관련하여 카탈란 수라는 개념이 있다.

이와 관련된 증명이 있지만 일단은 넘기도록하겠다.

이렇게 Brute-Force를 사용할 경우 만약 4개의 행렬을 두고 계산한다면, 총 5가지의 경우의 수가 존재한다.

보다시피 3번째 방법이 가장 빠른 계산법이라는걸 알 수 있고, 같은 행렬 계산이지만 계산수행횟수가 거의 10배정도 차이나는것을 알 수 있다.
이게 바로 연쇄행렬곱셈이 필요한 이유라 생각된다.

우선 더 진행하기 전에 행렬의 곱셈 조건에 대해서 간단히 짚고 넘어가도록 하자. 교수님꼐서 친절하게 정리해주셨다.

정리하자면 곱하려는 두 행렬 A, B중 A 행렬의 행 또는 열이, B 행렬의 열 또는 행과 같아야 한다는 뜻이다.

점화식 찾기

1단계 재귀관계식을 찾는다

M : 연쇄 행렬ㅇ르 곱하는데 필요한곱셉의 최소 회수 행렬
M[i][j] = 𝐴𝑖에서 𝐴𝑗까지 행렬을 곱하는데 필요한 곱셈의 최소 회수 (1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛)
⁃ 목표: 𝐴𝑖 ⋯ 𝐴𝑗 행렬을 (𝐴𝑖 ⋯ 𝐴𝑘)(𝐴𝑘+1 ⋯ 𝐴𝑗)로 분할하는 재귀 관계식 찾기

2단계

주대각선, 즉 중앙을 가로지르는 대각선은 모두 0으로 설정한다 𝑀[𝑖][𝑖] = 0
최종목표는 M[1][n]을 구하는 계산이고, 상향식 계산을 통해 구할 수 있다.

재귀관계식은 사진으로 설명을 대체하도록 하겠다.

상향 대각선 기법 Upeer Diagonal Method

예를 들어 M[1][4]를 찾는다고하면 𝑚𝑖𝑛
( 𝑀[1][1] + 𝑀[2][4] + 𝑑0𝑑1𝑑4, // k가 1일때
𝑀[1][2] + 𝑀[3][4] + 𝑑0𝑑2𝑑4, // k가 2일때
𝑀[1][3] + 𝑀[4][4] + 𝑑0𝑑3𝑑4 ) // k가 3일때

의 과정을 통해서 가장 작은 diagoanl 의 합이 그 값이 되고 마지막 diagonal의 값이 optimal한 값이 된다.

코드작성

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] = 1
    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

재귀식을 실행하는 코드이다.
우선 M과 P 두 이중배열을 -1로 모두 초기화 한 다음, 중심선은 전부 1로 처리한다. 그 후 1 에서 n-1 까지 loop하고 그 대각선 안에서는 1에서 n - diagonal 까지 반복한다.

대각선이 4 3 2 1 이런식으로 줄어들기에 diagonal 만큼 빼준 수 까지 돌면 대각선의 모든 경우의 수를 계산하게 된다

그 후 j = i 값과 diagonal을 합한 값으로 설정하고

현재 diagnoal에서 몇번째의 경우인가를 찾는것
한가지 유의할 것은 1번 대각선의 경우 이미 초기값이 설정되어 있기에 2번대각선부터 계산을 수행하게 된다.

그때의 M[i][j]와 P[i][j]를 minimum 함수를 통해 결정한다.

def minimum(M ,d , i ,j):
    INF = 999
    minV = 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 (minV > value):
            minV = value
            minK = k
    return minV, minK

최소값은 무한대, 위치는 0으로 두고 value의 값을 점화식에 따라 계산한다.

value = M[i][k] + M[k+1][j]
value += d[i-1] d[k] d[j]

그리고 계산을 마무리하계 된다.

계산순서의 출력

M 은 Optimal Value를 가지고 있다. 우리가 알고 싶은 것은 어떤것이 최적의 순서인가이다.
따라서 P를 이용하여 이를 찾아낸다.

앞서 두 코드에서 P[i][j]에 K를 저장하였다. 이 뜻은 즉, (Ai ... Ak)(Ak+1...Aj)로 분활되어 계산된다는 뜻이고 이를 통해 우리는 어떠한 순서로 계산되었는지 파악 할 수 있다.

코드는 다음과 같다

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

마지막으로

INF = 999
d = [5, 2, 3, 4, 6, 7, 8]
M, P = minmult(d)
print('M =')
for i in range(1, len(M)):
    print(M[i][1:])
print('P =')
for i in range(1, len(P)):
    print(P[i][1:])

print('minimum order: ', end ='')
order(P, 1, len(d) - 1)