Chain Matrix Multiplication
2020-1νκΈ°, λνμμ βμκ³ λ¦¬μ¦β μμ μ λ£κ³ 곡λΆν λ°λ₯Ό μ 리ν κΈμ λλ€. μ§μ μ μΈμ λ νμμ λλ€ :) μ 체 ν¬μ€νΈλ Algorithm ν¬μ€νΈμμ νμΈνμ€ μ μμ΅λλ€.
μΌλ°μ μΌλ‘ νλ ¬ κ³±μ $A_1 \times A_2 \times \cdots \times A_n$μ Associative νκΈ° λλ¬Έμ νλ ¬μ κ³±μ μμλ₯Ό μ΄λ»κ² μ§ννλλμ λ°λΌμ μ 체 μ°μ°μ μκ° λ¬λΌμ§λ€.
μλ₯Ό λ€μ΄,
- $A: 50 \times 20$
- $B: 20 \times 1$
- $C: 1 \times 10$
- $D: 10 \times 100$
4κ°μ§ νλ ¬μ΄ μμ λ,
- $A \times ((B \times C) \times D) = 120,200$
- $(A \times B) \times (C \times D) = 7,000$
μ΄ λλ€. μ¦, νλ ¬μ κ³±μ μμλ₯Ό μ μ‘°μ ν΄ νμν μ°μ°μ μλ₯Ό μ€μΌ μ μλ€λ κ²μ΄λ€!!
naive approach
κ°μ₯ κ°λ¨νμ§λ§, κ°μ₯ λΉμ©μ΄ λ§μ΄ λλ λ°©λ²μ λͺ¨λ νλ ¬ κ³±μ μμλ₯Ό λͺ¨λ μ΄ν΄λ³΄λ κ²μ΄λ€. νλ ¬μ κ³±μ μ binary operationμ΄κΈ° λλ¬Έμ μ 체 νλ ¬ μ°μ°μ μ΄λ€ binary treeμ ννλ‘ ννν μ μλ€. μ΄λ, μ°λ¦¬λ $n$κ°μ νλ ¬μ κ°μ§κ³ μκΈ° λλ¬Έμ, μ΄ binary treeλ $n$κ°μ leaf nodeλ₯Ό κ°μ§ νΈλ¦¬κ° λλ€. λν, κ·Έ κ°μ§μλ exponentially manyν $2^n$κ°κ° λλ€.

Dynamic Programming
DPμμλ μ΄ λ¬Έμ λ₯Ό μλμ κ°μ΄ μ κ·Όνλ€.
λ€λ₯Έ κ³³μμλ λΆλΆμμ΄(sebsequence)μ μ΄μ©ν΄ λ¬Έμ λ₯Ό ν΄κ²°νλ€κ³ λ μ€λͺ νλ€.
- μ 체 μμ΄μ κΈΈμ΄ 2μ λΆλΆ μμ΄λ‘ λΆλ¦¬νλ€.
- κΈΈμ΄ 2μ λΆλΆ μμ΄μμ (μ΅μ) λΉμ©μ ꡬνλ€.
- κΈΈμ΄ 3μ λΆλΆ μμ΄μ μ΄ν΄λ³Έλ€. μ΄λ, κΈΈμ΄ 2μ λΆλΆ μμ΄μμ ꡬν λΉμ©μ λ°νμΌλ‘ μ΅μ λΉμ©μ ꡬνλ€.
- κΈΈμ΄ 4λ κΈΈμ΄ 3μμ ꡬν μ΅μ λΉμ©μ λ°νμΌλ‘ μ΅μ λΉμ©μ ꡬνλ€.
- μ΄ κ³Όμ μ κΈΈμ΄ $n$κΉμ§ λ°λ³΅
μ΄ κ³Όμ μ μ λ¦¬ν΄ κΈ°μ νλ©΄,
- $C(i, j)$ = min cost of multiplying $A_i \times \cdots A_j$
for $\ell = 1, 2, \dots, n$
ββfor $i=1, 2, \dots, n - \ell + 1$
ββββ$j = i + \ell$
ββββfor $k=i, \dots, j-1$
ββββββ$\texttt{cost} = C(i, k) + C(k+1, j) + m_{i-1} \times m_k \times m_j$
ββββββ$C(i, j) = \min \{ C(i, j), \; \texttt{cost}\}$
return $C(1, n)$
μμ κ³Όμ μ κ·Έλ¦ΌμΌλ‘ νννλ©΄ μλμ κ°μ΄ ννν μ μλ€.

Image from here
λ§μ½ best-split μμλ₯Ό κΈ°λ‘ν΄ μ€μ binary opr treeλ₯Ό ꡬμ±νκ³ μΆλ€λ©΄, $C(i, j)$λ₯Ό κ°±μ νλ κ³Όμ μμ μΈμ minimumμ λ¬μ±νλμ§ κΈ°λ‘ν΄λλ©΄ λλ€.
ββββββif $\texttt{cost} < C(i, j)$
ββββββββ$C(i, j) = \texttt{cost}$
ββββββββ$S(i, j) = k$
κ·Έλ¦¬κ³ binary opr treeλ₯Ό μ¬νν λλ $S(1, n)$μΌλ‘ splitting pointλ₯Ό μ°Ύκ³ , κ·Έλ¦¬κ³ $S(1, k)$, $S(k, n)$μ κ°μΌλ‘ κ·Έ λ€μ splitting pointμ μ°Ύκ³ , β¦ μ΄λ° μμΌλ‘ μ§ννλ©΄ λλ€ π