図のような $l \times m$ の行列 $A$ と $m \times n$ の行列 $B$ の積は、 $l \times n$ の行列 $C$ となり、$C$ の各要素 $c_{ij}$ は次の式で得られます: $$ c_{ij} = \sum_{k=1}^m a_{ik}b_{kj} $$
連鎖行列積問題では $c_{ij}$ の値に興味はなく、計算に必要な掛け算の数をなるべく小さくすることが目的です。上の $A$ と $B$ の積には、$l \times m \times n$ 回の掛け算が必要になります。以降は、複数の行列の積(連鎖行列積)について考えます。
次の図に示す $(M_1M_2...M_6)$ のように、$M_i$ が $p_i − 1$ 行 $p_i$ 列の行列であるような、$n$ 個の行列の掛け算を考えます。
これらの行列の積は様々な順番で計算することができます。たとえば、単純に左から右へ向かって計算すると$(((((M_1M_2)M_3)M_4)M_5)M_6)$ と表すことができ、右から左に向かって計算すると$(M_1(M_2(M_3(M_4(M_5M_6)))))$と表すことができます。さらに $(M_1(M_2(M_3M_4)(M_5M_6)))$ など、様々な順番で計算を行うことができます。掛け算の計算結果(連鎖行列積)は同じになりますが、行列同士の掛け算の順番によって、“掛け算の総回数”が異なってきます。
上の例の連鎖行列積に必要とする掛け算の総回数を、いくつかのケースについて考えてみましょう。
下図のように、左から右へ向かった順番で計算を行うと合計 84 回の掛け算が必要になります。
一方、下図のような順番で計算を行うと、最も効率よく計算を行うことができ、その掛け算の合計は 36回になります。
連鎖行列積問題において、全ての可能な順番を調べてみる方法は $O(n!)$ のアルゴリズムになります。この問題は、より小さな部分問題に分割することができるので、以下の二次元配列(表)を用いた動的計画法を適用することができます。
$m[n+1][n+1]$: $m[i][j]$ を $(M_iM_{i+1} ...M_j)$ を計算するための最小の掛け算の回数とする2次元配列
まず、$(M_1M_2)$ を計算するための方法(順番)は 1 通りであり、$p_0 \times p_1 \times p_2$ 回の掛け算が必要です。同様に、$(M_2M_3)$ を計算するための方法も 1 通りであり、$p_1 \times p_2 \times p_3$ 回の掛け算が必要です。一般的に表すと、$(M_iM_{i+1})$ を計算するための方法は1 通りであり、$p_{i−1} \times p_i \times p_{i+1}$ 回の掛け算が必要になります。そして、これらの掛け算の回数をコストとして$m[i][i+1]$に記録しておきます。
次に、$(M_1M_2M_3)$、$(M_2M_3M_4)$、... $(M_{n−2}M_{n−1}M_n)$ を計算するための最適解を求めます。たとえば、$(M_1M_2M_3)$ を計算するための最適解を求めるためには、$(M_1(M_2M_3))$ と $((M_1M_2)M_3)$ のコストを計算し、そのうち小さい方のコストを $(M_1M_2M_3)$ のコストとして$m[1][3]$に記録します。ここで、
一般的に、連鎖行列積 $(M_iM_{i+1}...M_j)$の最適解は、$i \leq k < j$ における $(M_iM_{i+1}...M_k)(M_{k+1}...M_j)$ の最小コストになります。
たとえば、$(M_1M_2M_3M_4M_5)$ ($i = 1$、$j = 5$ の場合) の最適解は、
$m[i][j]$ は次の式で得られます。 $$ m[i][j] = \left \{ \begin{array}{ll} 0 & \text{if} \ i = j \\ \min_{i \leq k < j} \{m[i][k] + m[k+1][j] + p[i−1] \times p[k] \times p[j]\} & \text{if} \ i < j \\ \end{array} \right. $$
具体的な例で計算してみましょう。図X.Xは4つの行列の連鎖行列積問題の最適解を動的計画法で求める流れを示します。
1-4. 1つの行列に対する掛け算のコスト
$$m[i][i] = 0$$
5. $(M_1M_2)$ のコスト
$$
m[1][2] = \min_{1 \leq k < 2} \{m[1][k] + m[k + 1][2] + p_0p_kp_2\}
= \min \left \{
\begin{array}{ll}
m[1][1] + m[2][2] + p_0p_1p_2 = 0 + 0 + 4 \times 3 \times 5
\end{array}
\right \} = 60
$$
6. $(M_1M_2)$ のコスト
$$
m[2][3] = \min_{2 \leq k < 3} \{m[2][k] + m[k + 1][3] + p_1p_kp_3\}
= \min \left \{
\begin{array}{ll}
m[2][2] + m[3][3] + p_1p_2p_3 = 0 + 0 + 3 \times 5 \times 1
\end{array}
\right \} = 15
$$
7. $(M_3M_4)$ のコスト
$$
m[3][4] = \min_{3 \leq k < 4} \{m[3][k] + m[k + 1][4] + p_2p_kp_4\}
= \min \left \{
\begin{array}{ll}
m[3][3] + m[4][4] + p_2p_3p_4 = 0 + 0 + 5 \times 1 \times 6
\end{array}
\right \} = 30
$$
8. $(M_1M_2M_3)$ のコスト
$$
m[1][3] = \min_{1 \leq k < 3} \{m[1][k] + m[k + 1][3] + p_0p_kp_3\}
= \min \left \{
\begin{array}{ll}
m[1][1] + m[2][3] + p_0p_1p_3 = 0 + 15 + 4 \times 3 \times 1 = 27 \\
m[1][2] + m[3][3] + p_0p_2p_3 = 60 + 0 + 4 \times 5 \times 1 = 80
\end{array}
\right \} = 27
$$
9. $(M_2M_3M_4)$ のコスト
$$
m[2][4] = \min_{2 \leq k < 4} \{m[2][k] + m[k + 1][4] + p_1p_kp_4\}
= \min \left \{
\begin{array}{ll}
m[2][2] + m[3][4] + p_1p_2p_4 = 0 + 30 + 3 \times 5 \times 6 = 120 \\
m[2][3] + m[4][4] + p_1p_3p_4 = 15 + 0 + 3 \times 1 \times 6 = 33 \\
\end{array}
\right \} = 33
$$
10. $(M_1M_2M_3M_4)$ のコスト
$$
m[1][4] = \min_{1 \leq k < 4} \{m[1][k] + m[k + 1][4] + p_0p_kp_4\}
= \min \left \{
\begin{array}{ll}
m[1][1] + m[2][4] + p_0p_1p_4 = 0 + 33 + 4 \times 3 \times 6 = 105 \\
m[1][2] + m[3][4] + p_0p_2p_4 = 60 + 30 + 4 \times 5 \times 6 = 210 \\
m[1][3] + m[4][4] + p_0p_3p_4 = 27 + 0 + 4 \times 1 \times 6 = 51 \\
\end{array}
\right \} = 51
$$
連鎖行列積の最適解を動的計画法で求めるアルゴリズムは次のように実装することができます。
def matrix_chain_multiplication():
for i in range(1, n + 1):
m[i][i] = 0
for l in range(2, n + 1):
for i in range(1, n - l + 2):
j = i + l - 1
m[i][j] = INFTY
for k in range(i, j):
m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j])
このプログラムでは、対象とする行列の数 $l$ を 2 から $n$ まで増やしながら、その範囲を指定する $i$ と $j$ を決めています。さらにその上で $i$ から $j$ の範囲で $k$ の位置を決めています。全体として3重のループ構造となっていることから、$O(n^3)$ のアルゴリズムとなります。
|
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ)AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。 |