1. 설명
연쇄 행렬 곱셈(chained matrix multiplication) 문제는 주어진 연쇄 행렬의 곱셈을 할 때, 각 원소의 곱셈 횟수를 최소로 하는 곱셈의 순서를 찾는 최적화 문제이다. 예를 들어, 4개의 행렬을 곱하는 ABCD의 경우를 생각해 보자. 행렬 곱셈은 결합법칙이 성립하므로, 행렬을 곱하는 순서는 상관이 없다.| [math(\displaystyle \begin{aligned} ABCD = ((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD)) \end{aligned} )] |
연쇄 행렬 곱셈 알고리즘은 연쇄 형렬 곱셈 문제를 풀어, 가장 효율적으로 행렬을 곱하는 순서를 찾는 알고리즘이다. 이 알고리즘은 동적 계획법과 메모이제이션으로 풀 수 있는 대표적인 알고리즘으로, 알고리즘 교재에 자주 등장한다.
2. 코드 예시
본 문단에서는 Python으로 작성한 코드만 제시했다. 쉬운 이해를 위해 NumPy를 사용하지 않았다.연쇄 행렬 곱셈 알고리즘은 먼저 재귀 관계를 찾은 후에 이차원 배열을 이용하여 상향식으로 동적계획법을 적용하는 알고리즘이다.
#!syntax python
def minimum(M:list[list[int]], d:list[int], i:int, j:int) -> tuple[int, int]:
min_value = float('inf')
min_k = 0
for k in range(i, j):
value = M[i][k] + M[k + 1][j]
value += d[i - 1]*d[k]*d[j]
if value < min_value:
min_value = value
min_k = k
return min_value, min_k
def minmult(d:list[int]) -> tuple[list[list[int]], list[list[int]]]:
'''연쇄 행렬 곱셈 알고리즘'''
n = len(d) - 1
M = [[-1]*(n + 1)]*(n + 1)
P = [[-1]*(n + 1)]*(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