[Algorithms] Matrix-Chain Multiplication Problem | 행렬 곱셈 순서 문제

Matrix-Chain Multiplication Problem

행렬 곱셈 순서 문제

- \(n\)개의 행렬들에 대해서, 스칼라 곱셈 횟수를 최소로 하는 곱셈 순서를 정의하는 문제이다.
- 예를 들어, \(p\times q\) Matrix \(A\)와 \(q\times r\) Matrix \(B\)에 대한 스칼라 곱셈 횟수는 \(p * q * r\)회 이다.
- 일반적으로 \(n\)개의 행렬들에 대해서는 \(n-1\)번의 행렬 곱셈이 행해져야 하고,
  곱셈의 순서의 경우의 수는 충분히 큰 \(n\)에 대해 \(\Omega(2^n)\)이다.
- 예를 들어, 행렬 \(A_1, A_2, A_3, A_4\)의 곱셈 \(A_1A_2A_3A_4\)의 순서는 아래와 같은 경우로 나눌 수 있다.
  \(((A_1A_2)A_3)A_4\)
  \((A_1A_2)(A_3A_4)\)
  \((A_1(A_2A_3))A_4\)
  \(A_1((A_2A_3)A_4)\)
  \(A_1(A_2(A_3A_4))\)

---

Theorem of Cases in Matrix-Chain Multiplication

\(n\)개의 행렬 곱셈에서 곱셈의 순서에 대한 경우의 수는 충분히 큰 \(n\)에 대해 \(\Omega(2^n)\)이다.

pf) \(n\)개의 행렬을 곱하는 순서의 경우의 수를 \(T(n)\)이라 했을 때,
\(T(n) = T(1)T(n-1) + T(2)T(n-2) + T(3)T(n-3) + \cdots + T(n-1)T(1)\) 이다.

\(C = {1 \over 2}\) 이고, \(n_0 = 1\) 이라 할 때,
모든 \(n \geq n_0\)에 대해,
\(T(n) \geq c2^n\)을 만족하기에
\(T(n) = \Omega(2^n)\) 이다.

이에 대한 Inductive Proof는 아래와 같다.

1) Basis
\(T(1) = 1\) 임은 자명하며, \(T(1) \geq c2^1\) 또한 참이다.

2) Inductive Step
모든 \(k < n\) 에 대해,
\(T(k) \geq c2^k\)가 참이라 가정하자.

\(T(n) = T(1) * T(n-1) + T(2) * T(n-2) + T(3) * T(n-3) + \cdots + T(n-1) * T(1)\)
\(\qquad \; \, \geq c2^1 * c2^{n-1} + c2^2 * c2^{n-2} + c2^3 * c^{n-3} + \cdots + c2^{n-1} * c^1\)
\(\qquad \; \, \geq c2^n\)
이다.

따라서, 모든 \(n \geq 1\) 에 대해,
\(T(n) \geq c2^n\)이며,
이는 \(T(n) = \Omega(2^n)\) 임을 의미한다.

---

Mechanism (원리)

※ 이 문제의 답은 Optimal Substructure를 갖고 있으므로, Dynamic Programming (URL) 기법을 적용해 볼 수 있다.

[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍

- Matrix \(A_1, A_2, \cdots, A_n\)이 각각 \(p_0\times p_1, p_1\times p_2, \cdots, p_{n-1}\times p_n\) 행렬이라 하자.
  (즉, Matrix \(A_i\)는 \(p_{i-1}\times p_i\)행렬이다.)
- \(n\)개의 행렬들의 곱셈 연산 중 가장 마지막 곱셈에 대해 존재할 수 있는 경우의 수는 \(n-1\)가지이며, 아래와 같다.
  \(A_1(A_2\cdots A_n)\)
  \((A_1A_2)(A_3\cdots A_n)\)
  \((A_1A_2A_3)(A_4\cdots A_n)\)
     \(\vdots\)
  \((A_1\cdots A_{n-2})(A_{n-1}A_n)\)
  \((A_1\cdots A_{n-1})A_n\)

- (A_1\cdots A_i)(A_{i+1}\cdots A_n)은
  i개짜리 행렬 곱셈 문제 (A_1\cdots A_i)와
  n-i개짜리 행렬 곱셈 문제 (A_{i+1}\cdots A_n)를 포함하고 있는 구조이다.

---

Recursive Formula

\(C_{i, j}\) : Matrix-Chain \(A_i \cdots A_j\) 를 계산하는데 드는 최소 비용

\(C_{i, j} = 
\begin{cases}
0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \mathrm{(if} \; i = j)\\\\
\min_{i \leq k \leq j-1} (C_{i, k} + C_{k+1, j} + p_{i-1}p_kp_j) \qquad \, \mathrm{(if} \; i < j)
\end{cases}\)

- 여기서, \(p_{i-1}p_kp_j\)는 마지막 행렬곱셈에서 치르는 스칼라 곱셈 횟수이다.

---

Implementation

1. Stupid Recursion (\(\Omega(2^n)\))

matrix_chain(i, j)
// 행렬 곱셈 A_i ... A_j의 최소 곱셈 횟수를 리턴한다.
{
    if (i == j)
        return 0;
        
    min = INT_MIN;
    
    for (int k = i; k <= j-1; k++){
        q = matrix_chain(i, k) + matrix_chain(k+1, j) + (p_{i-1} * p_{k} * p_{j});
        if (q < min)
            min = q;
    }
    return min;
}

2. Dynamic Programming with Loop (\(\Theta(n^3)\))

matrix_chain(i, j)
// 행렬 곱셈 A_i ... A_j의 최소 곱셈 횟수를 리턴한다.
{
    for (int i = 1; i <= n; i++)
        m[i, i] = 0;
    
    for (int r = 1; r <= n-1; r++)
        for (int i = 1; i <= n-r; i++){
            j = i+r;
            min = INT_MAX;
            for(int k = i; k <= j-1; k++){
                opt_val = m[i, k] + m[k+1, j] + p_{i-1}*p_{k}*p_{j};
                if(min <= opt_val)
                    min = opt_val;
            }
            m[i, j] = min;
        }
        
    return m[1, n];
}

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)