알고리즘 스터디 [DP] - 연쇄 행렬 곱셈 feat. Python

연쇄행렬곱셈(Matrix Chain Multiplication)

• 연속 행렬이 주어졌을 때, 행렬의 곱셈 중 가장 효율적인 방법을 찾는 이론이다. 이 문제는 실제로 곱셈을 실행하는 것이 아니고, 어떤 순서로 곱셈을 할지 결정을 하는 것이다.

• 연쇄행렬의 곱셈을 수행하는 것은 행렬곱이 연관되어있어 많은 옵션들이 존재한다. 다른 말로 하면, 우리가 어떤 알고리즘을 짜든, 결과는 같다는 것이다. 만약 우리가 A, B, C, D 행렬이 있다면 다음과 같은 형태로 구성될 수 있다.

(ABC)D = (AB)(CD) = A(BCD) = ...

• 우리가 곱셈 순서를 어떻게 정하든 같은 결과를 낫지만 가장 효율적인 것을 찾아야 한다. 만약 A가 10 x 30, B가 30 x 5, C가 5 x 60이면

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000

명확한 것은 우리가 연산 과정을 최대한 줄이는 것이 좋다는 것이다.

알고리즘 짜기

1) 하위 구조

• 가장 간단한 방법은 가능한 모든 가정에 따라 연산을 수행하는 것이다. 행렬의 크기가 n이라면, n-1개의 조합이 나타나게 된다. 예를 들어, A, B, C, D가 있다면 (A)(BCD) (AB)(CD) (ABC)(D) 이런 하위 구조를 이용해 최소 연산의 수를 구하려면 각각 연산을 다하고 최솟값을 찾는 것이다.

2) 재귀함수

• 이 방식은 단순히 하위구조를 이용해 적절하게 재귀함수로 실행하는 것이다.

import sys

# Matrix A[i] 는 p[i-1] x p[i]의 차원을 가지고 있다. 
def MatrixCahinOrder(p, i, j):
	if i == j:
    	return 0
    
    _min = sys.maxsize
    
    # 각각의 경우를 생성해 재귀적으로 각 연산의 수를 측정하는 것이다.
    # 여기서 가장 작은 값을 반환하게 된다.
    for k in range(i, j):
    	count = (
        	MatrixCahinOrder(p, i, k)
        	+ MatrixCahinOrder(p, k+1, j)
            + p[i-1] * p[k] * p[j]
        )
        
        if count < _min:
        	_min = count
     return _min
arr = [1, 2, 3, 4, 3]
n = len(arr)
print("최소 연산의 수는", MatrixCahinOrder(arr, 1, n-1))

• 이 경우의 시간복잡도는 "지수(exponential)"로 늘어난다.

3) 메모이제이션 이용하기

import sys

dp = [[-1 for i in range(100)] for j in range(100)]

# 연쇄 행렬 곱셈 함수
def matrixChainMemoised(p, i, j):
	if i == j:
    	return 0
    
    if dp[i][j] != -1:
    	return dp[i][j]
    
    dp[i][j] = sys.maxsize
    
    for k in range(i, j):
    	dp[i][j] = min(dp[i][j], matrixChainMemoised(p, i, k) + matrixChainMemoised(p, k + 1, j)+ p[i - 1] * p[k] * p[j]))
    
    return dp[i][j]

def MatrixChainOrder(p, n):
	i = 1
    j = n - 1
    return matrixChainMemoised(p, i, j)
    
arr = [1, 2, 3, 4]
n = len(arr)
print("최소 연산 수는", MatrixChainOrder(arr, n))

4) DP 이용하기

# Dynamic Programming 이용하기
import sys

def MatrixChainOrder(p, n):
    m = [[0 for x in range(n)] for x in range(n)]
    for i in range(1, n):
        m[i][i] = 0
 
    # L은 체인의 길이
    for L in range(2, n):
        for i in range(1, n-L + 1):
            j = i + L-1
            m[i][j] = sys.maxint
            for k in range(i, j):
 
                # q = cost / scalar multiplications
                q = m[i][k] + m[k + 1][j] + p[i-1]*p[k]*p[j]
                if q < m[i][j]:
                    m[i][j] = q
 
    return m[1][n-1]

arr = [1, 2, 3, 4]
size = len(arr)
 
print("최소 연산 수는" +
      str(MatrixChainOrder(arr, size)))
# This Code is contributed by Bhavya Jain