Python으로 알고리즘 공부 10. 연쇄행렬 최소곱셈 알고리즘

연쇄행렬 최소곱셈 알고리즘 (Matrix Chan Multiplication)

• 연쇄행렬 최소곱셈은 동적 프로그래밍(Dynamic Programming)을 활용하여 연산을 최적화 시키는 것

• 행렬은 결합법칙이 성립한다.

• (AB)C = A(BC)

• 그러나 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.

• 예를들어,

  • A : 10x30 행렬

  • B : 30x5 행렬

  • C : 5x60 행렬일 경우

• (AB)C는 (10x30x5) + (10x5x60) = 1,500 + 3,000 = 4,500번의 연산으로 구할 수 있지만

• A(BC)는 (30x5x60) + (10x30x60) = 9,000 + 18,000 = 27,000번의 연산을 해야 구할 수 있다.

즉, 연쇄행렬 최소곱셈은 곱하는 순서에 따라 연산의 순서가 달라지는데, 이를 최적화 하는 방법이다.

위의 식을 토대로 ABC의 최소 연산 회수를 구해보자.

• A : 10x30 행렬

• B : 30x5 행렬

• C : 5x60 행렬

• ​ : 10, ​ : 30, ​ : 5, ​ : 60

​

행렬 A~B의 곱

​

행렬 B~C의 곱

​

행렬 A~C의 곱

Python code

import sys
d = [10, 30, 5, 60]
M = [[0 for x in range(4)] for y in range(4)]
​
for diag in range(1, 4):
    for i in range(1, 4-diag):
        j = i+diag
        M[i][j] = sys.maxsize
        for k in range(i,j):
            M[i][j] = min(M[i][j],
                          M[i][k] + M[k+1][j] + d[i-1]*d[k]*d[j])
            
print(M[1][3])