連鎖行列積問題を解説

はじめに

• 書籍 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 の11.4節を参考にしています。
• aizu online judge Matrix Chain Multiplicationの解答コードを参考にしています。
• こちらのブログ記事を参考にしています。 連鎖行列積問題
• 間違っている部分があったら遠慮なく教えてもらえると幸いです。

連鎖行列積とは

行列積とは

行列積とは、行列の積（掛け算）です。

\begin{pmatrix}
1 & 2 \\
3 & 4 \\
1 & 2
\end{pmatrix}
\times
\begin{pmatrix}
5 & 6 & 7 \\
8 & 9 & 10
\end{pmatrix}
=
\begin{pmatrix}
21 & 24 & 27 \\
47 & 54 & 61 \\
21 & 24 & 27
\end{pmatrix}

この問題では求めるのは行列の掛け算の計算量のみなので、計算方法を知っている必要はありません。

この問題で行列の掛け算について知っておくことは3つあります。

ⅰ 左の列数と右の行数が同じときのみ行列の掛け算ができる

上記の行列でもAの列数は2で、Bの行数は2になっていることがわかると思います。

ⅱ 左の行数 × 左の列数 × 右の列数 が行列の掛け算で生じる計算回数である

上記の行列を掛け算を行うと下記の計算をすることになるのですが、掛け算を18回行っています。
これは 左の行数（3） × 左の列数（2） × 右の列数（3） の結果と同じです。

1*5 + 2*8 = 21, 1*6 + 2*9 = 24, 1*7 + 2*10 = 27
3*5 + 4*8 = 47, 3*6 + 4*9 = 54, 3*7 + 4*10 = 61
1*5 + 2*8 = 21, 1*6 + 2*9 = 24, 1*7 + 2*10 = 27

ⅲ 行列の掛け算の結果の行列は左の行数と右の列数を持つ行列である

上記の例で掛け算の結果の行列は左の行数・右の列数である 3,3 の行列になっています。

連鎖行列積とは

連鎖行列積とは名前の通り、行列積が連鎖したものです。

\begin{pmatrix}
1 & 2 \\
3 & 4 \\
1 & 2
\end{pmatrix}
\times
\begin{pmatrix}
5 & 6 & 7 \\
8 & 9 & 10
\end{pmatrix}
\times
\begin{pmatrix}
21\\
47\\
21
\end{pmatrix}

連鎖行列積では隣り合う行列同士であればどの順番で掛け算を行っても値を求めることができます。

行列積のⅰ,ⅲの2つのルールを使ってそのことを見ていきます。

上記の3つの行列を左からABCとします。

ⅰ のルールについて

まず行列の掛け算が成り立つには前提としてⅰのルール

「ⅰ 左の列数と右の行数が同じときのみ行列の掛け算ができる」

が存在するので連鎖行列の隣り合う行列同士はAの列数とBの行数は同じにしなければなりません。

上記ABCで言うと、AB, BC がこのルール通りでなければ連鎖行列積は成り立ちません。

ⅲ のルールについて

「ⅲ 行列の掛け算の結果の行列は左の行数と右の列数を持つ行列である」

により連鎖行列のどの隣り合う2つから掛け算を行ってもⅰのルール通りの並びになり、残りの連鎖行列の掛け算が破綻しません。

具体的には、

(A×B)×(C) は

A×B = 3行3列 の行列になる
(A×B)×(C) = 3行3列 × 3行1列
=> Aの列数(3)とBの行数(3)が同じなので計算可能

A×(B×C) は

B×C = 2行1列 の行列になる
(A)×(B×C) = 3行2列 × 2行1列
=> Aの列数(2)とBの行数(2)が同じなので計算可能

となり、どの順番で掛け算を行っても連鎖行列が破綻しないことがわかると思います。

連鎖行列積問題とは

ABCの連鎖行列積があるときに、(AB)(C), (A)(BC) どちらの順番で計算をしても値を求められることがわかりました。

連鎖行列積問題とは、連鎖行列積の最小の掛け算の計算量を求める問題です。

連鎖行列積は行列積の順番によって掛け算の回数が変わってきます。

ここではⅱのルール

「ⅱ 左の行数 × 左の列数 × 右の列数 が行列の掛け算で生じる計算回数である」

を使って考えていきます。

(AB)(C) のとき

\begin{pmatrix}
1 & 2 \\
3 & 4 \\
1 & 2
\end{pmatrix}
\times
\begin{pmatrix}
5 & 6 & 7 \\
8 & 9 & 10
\end{pmatrix}
\times
\begin{pmatrix}
21\\
47\\
21
\end{pmatrix}

(AB)(C) は(AB)の計算量が 「323」 で、

\begin{pmatrix}
1 & 2 \\
3 & 4 \\
1 & 2
\end{pmatrix}
\times
\begin{pmatrix}
5 & 6 & 7 \\
8 & 9 & 10
\end{pmatrix}
=
\begin{pmatrix}
21 & 24 & 27 \\
47 & 54 & 61 \\
21 & 24 & 27
\end{pmatrix}

(AB)(C)の計算量は「331」

\begin{pmatrix}
21 & 24 & 27 \\
47 & 54 & 61 \\
21 & 24 & 27
\end{pmatrix}
\times
\begin{pmatrix}
21\\
47\\
21
\end{pmatrix}

なので計算量は 「323」 + 「331」 = 27 となります。

(A)(BC) のとき

\begin{pmatrix}
1 & 2 \\
3 & 4 \\
1 & 2
\end{pmatrix}
\times
\begin{pmatrix}
5 & 6 & 7 \\
8 & 9 & 10
\end{pmatrix}
\times
\begin{pmatrix}
21\\
47\\
21
\end{pmatrix}

(A)(BC)の計算量は（BC）の計算量が「231」で

\begin{pmatrix}
5 & 6 & 7 \\
8 & 9 & 10
\end{pmatrix}
\times
\begin{pmatrix}
21\\
47\\
21
\end{pmatrix}
=
\begin{pmatrix}
534 \\
801
\end{pmatrix}

(A)(BC)の計算量は「321」

\begin{pmatrix}
1 & 2 \\
3 & 4 \\
1 & 2
\end{pmatrix}
\times
\begin{pmatrix}
534 \\
801
\end{pmatrix}

となります。
なので(A)(BC)の計算量は (231)+(321) = 12

結果

(AB)(C) => 27
(A)(BC) => 12
計算する順番によって計算量が違うことがわかると思います。

解法

具体的な個数で見ていきます

3つのとき

ABCの3つの連鎖行列積のときは
・(AB)(C)
・(A)(BC)
の2通りのうち、掛け算の回数が小さい方が答えになる

4つのとき

ABCDの4つの連鎖行列積のときは
・(A)(BCD)
・(AB)(CD)
・(ABC)(D)
の3通りのうち、掛け算の回数が一番小さい値が答えになります

ここでのポイントは計算の過程で3つの連鎖行列積が含まれるパターンがあることです
・(A)(BCD)
・(ABC)(D)

そしてこの3つの連鎖行列積についても同じように
・(BCD) =>
(BC)(D)
(B)(CD)
のうち小さい方が答え
・(ABC)
(AB)(C)
(A)(BC)
のうち小さい方が答え

となります。

()でくくる箇所を1つずつずらして出来るパターンの中で最小の計算量を答えとする
という処理を()でくくられた中の部分連鎖行列に繰り返し行っていることがわかると思います。

解法

そうすると解法は下記となります。

・① 与えられた連鎖行列積に対して()でくくる箇所を1つずつずらして、全パターンを列挙する
例:
A|BCD
AB|CD
ABC|D
と区切り位置を1つずつずらしていることがわかります

・(A)(BCD)
・(AB)(CD)
・(ABC)(D)

・② それぞれのパターンに対して計算量を求め、その中で一番小さい計算量をその連鎖行列積の最小計算量とする
　 ・それぞれのパターンの連鎖行列積についても、①と②を行い、それぞれのパターンの連鎖行列積の最小計算量を求める

例:

ポイントとしては部分連鎖行列積の計算が終わったあとにその結果できた行列を使ってさらに積をするので、
例えば、(BCD)について最小計算量だけではなく、(BCD)の積の結果できる行列の行数・列数も知っておかなければなりません。

ABCDの下記の3パターンがあり、
・(A)(BCD)
・(AB)(CD)
・(ABC)(D)

この3つの中の最小値
MIN[(A)(BCD), (AB)(CD), (ABC)(D)]
を求めるために

・(A)(BCD)
=> BCDの最小値
MIN[(BC)(D), (B)(CD)]

「(A) × (BCD)の結果できた行列」の計算量 + MIN[(BC)(D), (B)(CD)]]

・(AB)(CD)

「A × Bの結果できた行列」 × 「C × Dの結果できた行列」 の計算量 + ABの計算量 + CDの計算量

・(ABC)(D)
=> ABCの最小値
MIN[(AB)(C), (A)(BC)]

「(ABC)の結果できた行列 × D」の計算量 + MIN[(AB)(C), (A)(BC)]

という風に3つそれぞれの計算量を計算し、最小の値がABCDの答えになります

プログラムへの落とし込み

動的計画法の使用

例えば BCD と ABC の最小値の計算では

BCD の最小値の計算 => MIN[(BC)(D), (B)(CD)]
ABC の最小値の計算 => MIN[(AB)(C), (A)(BC)]

どちらの計算にも BC の最小値（2つの行列の積のパターンは1つしかないので普通に計算した値が最小値になる）を使っていることがわかると思います。

なので一度計算した部分連鎖行列積の計算量の最小値を変数に記録することで効率よく連鎖行列積の計算量の最小値を求めることができます。

1次元配列で連鎖行列積を表現

連鎖行列積の最小計算量を求めるためには具体的な行列の値は必要なく、行列の行数・列数がわかればよいのでした。

また、
「ⅰ 左の列数と右の行数が同じときのみ行列の掛け算ができる」
というルールから

一番左の行列の行数と各行列の列数だけで連鎖行列積の計算量を計算することができます。

例えば下記の行列の行数・列数が与えられたとき（左が行数、右が列数）

(3,2), (2,3), (3,1)

Aの列数とBの行数が同じというルールがあるので、
(3,2), (2,3), (3,1)
(3,2), (2,3), (3,1)
2と3は2回記載しなくても1回だけで連鎖行列積の行数・列数を表すことができます。

3（1番目の行数） 2（1番目の列数） 3（2番目の列数） 1（3番目の列数）

その結果、一番左の行列の行数と各行列の列数を1次元配列にすることで連鎖行列積の行数・列数を表現できます。

[3,2,3,1]

行列積の結果できた行列同士の積

(AB)(CDE)

の計算量を計算するためには AB と CDEの積の結果できた行列の積を考えなければなりません。

行列積の2つのルールを使うとこれを簡単に計算することができます。

まず、

・ ⅲ 行列の掛け算の結果の行列は左の行数と右の列数を持つ行列である

というルールにより、連鎖行列積の結果できる行列の列数は一番右の行列の列数になります。
(AB)ならBの列数、(CDE)ならEの列数です。
また、連鎖行列積の結果できる行列の行数は一番左の行列の行数になります。
(AB)ならAの行数、(CDE)ならCの行数です。

そして、

・ ⅱ 左の行数 × 左の列数 × 右の列数 が行列の掛け算で生じる計算回数である

というルールにより、(AB)(CDE)の行列積の計算量は、Aの行数 × Bの列数 × Eの列数であることがわかります。

ABCDEの行数・列数が与えられたとして、行列積の結果できた行列同士の積の計算量に必要なのは

行列積の結果できた行列がどのようなものになるのかは考える必要がなく、ABCDEの行数・列数のみの情報だけで良いことがわかります。

連鎖行列の1次元配列を使った計算

(3,2), (2,3), (3,1) という連鎖行列は [3,2,3,1] と表せるのでした。
左の行列からABCとします。

左の行数(x) × 左の列数(y) × 右の列数(z) が行列の掛け算で生じる計算回数である というルールにより
計算量の計算では連鎖行列が何個でも x は必ず一番左の行列の行数になり、 z は必ず一番右の行列の列数になるのでした。

それを [3,2,3,1] で考えると、配列の先頭と末尾が x, z になります。

y の決まり方

y の決まり方を下記の表を見ながら説明します

インデックス	0	1	2	3
配列の値	3	2	3	1
備考	Aの行数	Aの列数	Bの列数	Cの列数

• (A)(BC) のとき

1番目の行列 A で区切っています。

左の行列: A, 右の行列: B*C で作成される行列なので
左の行列である A の列数が y になります。

[3,2,3,1] のインデックス1の2が y になります。

• (AB)(C) のとき

2番目の行列 B で区切っています。

左の行列: AB で作成される行列, 右の行列: C なので
左の行列である AB の列数が y になります。

A*B の列数は B の列数になるので
[3,2,3,1] のインデックス2の3が y になります。

連鎖行列を1次元配列で表現した [3,2,3,1] は一番左以外は各行列の列数であり、
0オリジンでインデックスを数えるとn番目の行列の列数がインデックスnに上手いことなります。

つまり y は区切り箇所nを配列のインデックスとして使ったときの配列の値になります。

x の決まり方

(3,2), (2,3), (3,1) という連鎖行列は [3,2,3,1] と表せるのでした。
左の行列からABCとします。

BC を計算するときに y はインデックス2番目の3、z は一番右の1ですがBの行数はどこになるかというと
Bのインデックス2から1を引いたインデックスがBの行数になります。

A(インデックス1)の行数はインデックス0の3
B(インデックス2)の行数はインデックス1の2
C(インデックス3)の行数はインデックス2の3

となっていることがわかると思います。

なので

左の行数(x) × 左の列数(y) × 右の列数(z)

の x は左の行列の　インデックス-1　の配列の値を見ればよいことになります。

解き方

小さな連鎖行列積から計算

ある連鎖行列積はより小さな連鎖行列積でできています。
例えばABCD は (A)と(BCD)というより小さな連鎖行列積でできています。

そのため一度計算した計算量を再利用するために小さな連鎖行列積から大きな連鎖行列積という順番で計算をしていきます。

具体的にはABCDの連鎖行列積があるとして

① 長さが2の連鎖行列積の計算量を計算
AB, BC, CD

② 長さが3の連鎖行列積の計算量を計算
ABC, BCD
このときに変数に記録しておいた長さが2のAB, BC, CDの計算量の情報を使う

③ 長さが4の連鎖行列積の計算量を計算
ABCD
このときに変数に記録しておいた長さが3のABC, BCDの計算量の情報を使う

という流れになります。

各長さのときの計算量の最小値の計算

対象範囲のスライド

小さい連鎖行列積から計算量を求めるのでした。

そこで小さな長さから順に各長さの範囲をスライドしてその長さの全パターンの計算量を求めます。

例えば ABCD の連鎖行列積があるときに長さ2のパターンを列挙するときは
長さが2の範囲をAから右にずらしていきます。

A	B	C	D	外	備考
=	=				AB
	=	=			BC
		=	=		CD
			=	=	範囲がはみ出るので無効

対象範囲の分割

洗い出した各パターンに対してさらに区切り箇所を洗い出します。

長さが3のときは ABC, BCD ができます。

A	B	C	D	外	備考
=	=	=			ABC
	=	=	=		BCD
		=	=	=	範囲がはみ出るので無効

そのとき例えば ABC に対して区切り箇所を1つずつずらすことで
(A)(BC), (AB)(C) の計算順序を求めることができます。

A	B	C	備考
↑			Aまでで区切る => (A)(BC)
	↑		Bまでで区切る => (AB)(C)
		↑	Cまでで区切る => 無効

プログラム

1つず見ていきます。

6個の行列の連鎖行列積が与えられたとします。
行列は[行数,列数]の配列で表します。

n = 6
data = [[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]]

最小計算量を記録しておく2元表を作る

例えば1番目から3番目までの最小計算量、5番目から6番目までの最小計算量というように
開始番号から終了番号までの最小計算量を保存するために2元表を使います。
n+1 の長さで作っているのはインデックスを1から使用するためです。
そのため一番外側は使いません。

dp[開始番号][終了番号] となります。

n = 6
data = [[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]]

dp = Array.new(n + 1) {Array.new(n + 1, 0)}
  =>
[[0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0]]

行列を一次元配列として保存する

一番左の行列の行数と各行列の列数だけわかればよいので下記のようになります。

n = 6
data = [[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]]
dp = Array.new(n + 1) {Array.new(n + 1, 0)}       

matrices = 
# 一番左の行列の行数, 各行列の列数
[data[0][0]] + data.map(&:last)
=> [30, 35, 15, 5, 10, 20, 25]

短い連鎖行列積から値を求めていく

長い連鎖行列積の計算に使うために、短い連鎖行列積の最小計算値から求めていくのでした。
長さが1の連鎖行列積の計算量は求める必要がないので、長さは2から最終的な連鎖行列積の数（n）になります。

length は対象範囲の長さとなります。

n = 6
data = [[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]]
dp = Array.new(n + 1) {Array.new(n + 1, 0)}       

matrices = [data[0][0]] + data.map(&:last)

2.upto(n) do |length|

end

対象範囲のスライド

対象範囲をスライドしていき、各位置での最小計算量を求めていきます

開始位置、終了位置

対象範囲の開始位置(i)、終了位置(j)の1オリジンのインデックスを求めます。
各範囲の最小値を記録する dp 配列は1オリジンで記録するように作ったのでした。

開始位置は1から n - length + 1 までとなります。

ABCDの4つの連鎖行列を長さ2がスライドする場合、長さ分を引いて引いたあとの次のインデックスの3が最大開始位置になることがわかります。

インデックス	1	2	3	4
連鎖行列	A	B	C	D
備考			=	=

※ インデックスが1オリジンで始まっているのは最小計算量を記録するdpが1インデックスで情報を記録し、
また連鎖行列の情報が入っている matrices も0インデックスが行数で1インデックスがn番目の行列の列数を表すからです。

それぞれの開始位置に対する終了位置は i + length - 1 です。
開始位置に長さ分を足し、1を引いたインデックスになります。

n = 6
data = [[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]]
dp = Array.new(n + 1) {Array.new(n + 1, 0)}       

matrices = [data[0][0]] + data.map(&:last)

2.upto(n) do |length|
  1.upto(n - length + 1) do |i|
    j = i + length - 1
  end
end

対象範囲の中の連鎖行列の区切り位置

3の長さで ABC の連鎖行列が対象範囲になったとします。

インデックス	1	2	3	備考
行列	A	B	C
	↑			Aまでで区切る => (A)(BC)
		↑		Bまでで区切る => (AB)(C)
			↑	Cまでで区切る => 無効

有効なのはインデックス2の区切りまでであり、
区切りの範囲は開始位置の1から終了位置のインデックス3から1を引いた2(j-1)までが区切り位置であることがわかります。

※ インデックスが1オリジンで始まっているのは最小計算量を記録するdpが1インデックスで情報を記録し、
また連鎖行列の情報が入っている matrices も0インデックスが行数で1インデックスがn番目の行列の列数を表すからです。

n = 6
data = [[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]]
dp = Array.new(n + 1) {Array.new(n + 1, 0)}       

matrices = [data[0][0]] + data.map(&:last)

2.upto(n) do |length|
  1.upto(n - l + 1) do |i|
    j = i + l - 1
    dp[i][j] = Float::INFINITY
    i.upto(j - 1) do |k|
    
    end
  end
end

最小計算量の計算

流れ

例えば ABCD の連鎖行列で対象範囲 ABC の最小計算量を求める場合、

1. (A)(BC) を計算、開始位置1・終了位置3なので dp[1][3] に値を保存
2. (AB)(C)を計算、先ほど計算した dp[1][3] と値を比べて小さかったら dp[1][3] に値を入れる

というように一番計算量が短い区切り位置を探して dp 変数にそれを記録していきます

連鎖行列積の計算

連鎖行列積の計算の処理は、

例えば (AB)(C) 連鎖行列積の計算は

{「A × Bの結果できた行列」 × 「C」} の計算量 + ABの計算量 + Cの計算量 なので

・{「A × Bの結果できた行列」 × 「C」}
=> matrices[i - 1] * matrices[k] * matrices[j]

行列積の結果できた行列同士の積
をコードで表すとこのようになります。

matrices[i - 1] : 左行列の行数

AB の行数はAの行数になります。
行数を求めたいときはその行列のインデックスから1を引いたインデックスの値になるのでした。

matrices[k]: 左行列の列数

AB の列数はBの列数になります。
列数はその行列のインデックスで配列を参照すればよいのでした。

matrices[j]: 右行列の列数
列数はその行列のインデックスで配列を参照すればよいのでした。
対象範囲の終了位置のインデックスで配列を見ます。

・ABの計算量 + Cの計算量
=> dp[i][k] + dp[k + 1][j]

(AB)(C) は区切り位置がインデックス2のBなので
開始位置（A）~区切り位置（B） + 区切り位置プラス1（C）

コード

連鎖行列積の計算のコードは下記のようになります。

matrices[i - 1] * matrices[k] * matrices[j] + dp[i][k] + dp[k + 1][j]

1つ前に求めた区切り位置での計算量との比較

[dp[i][j], tmp].min

求めたいのは1番目から最後の行列までの最小計算量なので dp[1][n] を出力します。

最終的なコードは下記になります。

n = 6
data = [[30, 35], [35, 15], [15, 5], [5, 10], [10, 20], [20, 25]]
dp = Array.new(n + 1) {Array.new(n + 1, 0)}       

matrices = [data[0][0]] + data.map(&:last)

2.upto(n) do |length|
  1.upto(n - length + 1) do |i|
    j = i + length - 1
    dp[i][j] = Float::INFINITY
    i.upto(j - 1) do |k|
      tmp = dp[i][k] + dp[k + 1][j] + matrices[i - 1] * matrices[k] * matrices[j]
      dp[i][j] = [dp[i][j], tmp].min
    end
  end
end

puts dp[1][n]