[알고리즘,개념] 연쇄 행렬 곱셈 문제(CMM)

Chained Matrix Multiplication Problem

---

행렬의 곱셈에서, 행렬의 곱셈은 결합법칙이 성립한다.

• (A*B)*C = A*(B*C)
• 하지만, 행렬 곱셈의 순서에 따라서, 각 원소의 곱셈 횟수가 달라지게 된다.
  • 예시) A=(5,2),B=(2,3),C=(3,6) 
  • AB *C : 5*2*3 +5*3*6 = 30+60 = 90 
  • A*BC : 5*2*6+2*3*6 = 60+36 = 96
• 각 원소의 곱셈 횟수가 가장 작아지도록 하는 곱셈 순서를 구하고 싶다.(최적의 순서)

Brute Force 하게 접근하기

---

모든 경우의 수에 대해서 계산하고,최적의 순서를 선택하면 된다.

예시를 하나씩 해보다보면 알겠지만, 이 문제는 다양하게 해석이 가능하다.

• 괄호를 씌울 수 있는 경우의 수 - (ABC)(D),(AB)(CD)...
• Binary Search Tree의 갯수 (이건 좀 안와닿을 수 있다)
• 정사각형으로 이루어진 평면에서 최저경로로 목적지에 가는 경우의 수

 

연쇄 행렬 곱셈에서, 가능한 경우의 수?

• 카탈란 수라고 따로 구하는 방법이 있다고 한다. (조합론에서 엄청 많이 나오는 수이고, 컴퓨터 쪽에서 많이 쓰인다고 합니다)

카탈란 수의 정의,구하는방법

• 이 식이 어떻게 나왔는지는 , 다양한 개념들이 들어가야하기 때문에, 글이 산으로 갈거 같다. "카탈린 수 증명"이라고 구글형님께 물어보도록 하자!

어쨋든 우리에게 중요한 사실은 , n!꼴로 나타난 다는거고, 이건 곧, 구현할 때, O(지수꼴)로 구현이 된다는 거다.

(Brute Force하게 접근하면, 지수적으로 표현이 된다)

 

DP

---

문제 정의

• n개의 연쇄행결 곱셈: A1*A2*A3,....*An
• dk를 행렬 Ak의 행의 개수로 정의하자. (1<=k<=n)
• dk-1은 행렬 Ak-1의 행의 개수이고, Ak의 열의 개수라고 할 수 있다 . A1: d0*d1,A2:d1*d2 ....Ak : dk-1*dk

재귀관계식 도출

• M: 연쇄 행렬을 곱하는데 필요한 곱셈의 최소 회수 행렬
• M[i][j] = Ai에서 Aj까지 행렬을 곱하는데 필요한 최소 횟수
• M[i][j] = min(M[1][K] +M[K+1][j] +d0*dk*dj) (i<=k<=j-1)

import sys
# arr는 d0,d1,d2 와같은 식이라고 볼 수 있다.
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))

Bottom - up 방식으로 구현하기 (python)

• 반복은 Upper diagnal 방식으로, 특이하게, 대각선을 기준으로 채워가는 방식으로 구현할 거임.
• 3중반복이 필요하지만, 연산횟수는 N^3이 아니다! 

# 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

 

 

refer

guri_coding.log

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

yotubue강의

카탈린의수 증명

[프로그래밍 수학] 카탈란 수(catalan number)