連鎖行列積問題の攻略
こんにちは！ Ken.Sです！
今回は、連鎖行列積問題という一体どこで使うのか分からない問題を解説します！行列をいっぱい掛け算する時ってどういう時なんだろう…。競技プログラミングの勉強でこの問題を行ったのですが、分かりやすいサイトがあまりなかったので、よりBeginner向けに書いていこうと思います！
数学で行列演算で苦しんだことのある方、競技プログラミングでDPを勉強したい方は是非見てください！
はじめに
そもそも行列とは
うまく説明できる自信が無いので、よくわからなかった方はwikiを見てください(笑)
四角形の箱に入ったデータの集合で、線形代数を習う上で避けては通れない分野です。y=ax とかのグラフを使う問題を支えるといった感じです(本当にうまく伝わっている気がしない)
行列は(n*m行列)と表現されることが多く、nは行数(縦の長さ)mは列数(横の長さ)を表しています。行も列も漢字の右側の「つくり」の方でどっちが行でどっちが列か判断するって覚え方をしている人も少なくないと思います。
行列の掛け算について
行列の和、差はこのようにして求められます。
サイズだけで言うと、[2*2] + [2*2] = [2*2] となり、足し算引き算では行列のサイズは等しくないと出来ません。
しかし、掛け算となると異なります。掛けられる行列の列と掛ける行列の行が等しいと積が求められます。
サイズだけで言うと、[3*2] * [2*4] = [3*4] となります。
複雑ですね、要素1行1列目の計算はこのようになっています。
内積は積の和って感じです(雑) (上の場合a11*b11 + a12*b21となり、1行1列目と一致します)
積の要素1行1列目の計算は、掛けられる行列の1行目と掛ける行列の1列目の内積、要素1行2列目の計算は、掛けられる行列の1行目と掛ける行列の2列目の内積となります。つまり積の要素s行t列目の計算は、掛けられる行列のs行目と掛ける行列のt列目の内積となり、積の行列のサイズは[掛けられる行列の行数 * 掛ける行列の列数]となります。
内積は同じ要素数必要なので、掛けられる行列の列数と掛ける行列の行数が必要なんです。
行列積について、このサイトの説明が綺麗で好きだったので気になる方はどうぞ！
連鎖行列積問題とは
では本題に入ります。
上の図を見てもらえれば、計算する数が多いことがわかると思います。要素のかけ算の個数を考えていきます。まず、内積の計算で2回かけ算を行ってます。この2という数字は、掛けられる行列の列数=掛ける行列の行数と一致します。その内積を何回計算しているかというと、積の行列のサイズ=掛けられる行列の行数*掛ける行列の列数です。
つまり、[k*l]行列 * [l*m]行列のかけ算数はl*k*mとなります(l : 内積の計算でのかけ算、k*m : 積の行列のサイズ)
これの何が問題かを説明します。行列A[w*x], B[x*y], C[y*z] ([]内はその行列のサイズ)があるとし、A×B×Cを計算したいとします。行列のかけ算は結合法則が成り立つので、行列 (A×B)×C, A×(B×C) は等しくなります。(交換法則 AB = BA は成り立ちません。A,B共に正方行列(行数と列数が等しい行列)である場合、積AB, BAは計算できますが結果は異なります。)
では、行列(A×B)×C (=P), A×(B×C) (=Q)それぞれについてかけ算数を考えていきます。
P : (A×B) = [w*x] * [x*y] = w*x*y, -> サイズは[w*y] , (A×B)×C = [w*y] * [y*z] = w*y*z 計 w*x*y+w*y*z
Q : (B×C) = [x*y] * [y*z] = x*y*z, -> サイズは[x*z] , A×(B×C) = [w*x] * [x*z] = w*x*z 計 x*y*z+w*x*z
となりますね。仮にw,yがとても大きくx,zが小さいとすると、Qの方がかけ算数は少なくなります。
このように、行列のかけ算はどの積を先に求めるかで計算処理数が異なり、その処理数が最も小さくなるようにした場合の順序とその数を求めるのが連鎖行列積問題です。
解説
問題
そもそも私がこの問題を知ったのはこのサイトで勉強してたからです。修士卒業するまでに水色になりたいなぁ。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
先に解いてみたい方はこちらからどうぞ！
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja
プログラミングを知らない方にもできるだけ分かりやすく書いたつもりなので、解法が気になる方は是非読んでください！
解説
今回は動的計画法を利用しました。O(N^2)でした。
以下の入力例を用いて考えていきます。
6
30 35
35 15
15 5
5 10
10 20
20 25
まず、配列dp[N][N] を用意し0で初期化します。そして上三角行列のように、dp[i][j] (i > j) は今回使いません。
dp[i][j] ( i <= j ) には、i番目からj番目の行列の積を取った際のかけ算回数最小値が入ります。つまり、今回はdp[0][n-1] の値を求め出力すれば良いのです。
i = j の時は、その行列しかないのでかけ算は行いません。故に0です。
i < j の時を考えます。dp配列の埋め方としては、j - i の差が小さい順に入れていきます。つまり、最初は行列積2個のを計算します。
dp[0][1] = (0番目の行列 * 1番目の行列のかけ算回数) = 0番目の行数 * 0番目の列数(もしくは1番目の行数) * 1番目の列数
です。2個の行列の積のかけ算回数は1通りしかないのでそのまま計算すればOKです。これをdp[n-2][n-1] まで繰り返してdpに値を入れます。
現時点でdpはこうなっています。
次に3個の場合を考えます。
考えられるかけ算の順序は以下の二つです。
- (A * B) * C
- A * (B * C)
(A * B)のかけ算回数はdp[0][1]に入っています。なので、dp[0][1]に加えて( (A * B)で生じた行列) * C のかけ算回数を足したものが1.のかけ算回数になります。同様に2についてもかけ算回数を算出し、小さい方をdp[0][2]に格納します。
dp[0][1] + (Aの行数 * Bの列数(or Cの行数) * Cの列数) or dp[1][2] + (Aの行数 * Aの列数(or Bの行数) * Cの列数)
では、行列4つの場合について考えていきます。考えられるかけ算の順序は以下の五つです。
- ( (A * B) * C) * D
- (A * (B * C) ) * D
- (A * B) * (C * D)
- A * ( (B * C) * D)
- A * (B * (C * D) )
1.2.について、A~Cの積とDを掛けています。A~Cのかけ算回数はdp[0][2]に入っています。同様に、4.5.についてもB~Dのかけ算回数はdp[1][3]に入っています。3.については、dp[0][1]及びdp[2][3]に加えて、(A*Bの行列) * (C*Dの行列)のかけ算回数を計算します。dpを使うことで、2通り削除することが出来ました。dp[0][3]に入るのは以下の3つの内最小のものになります。
dp[0][2] + (A~C) * D のかけ算回数
dp[0][1] + dp[2][3] + (A~B) * (C~D) のかけ算回数
dp[1][3] + A * (B~D) のかけ算回数
このように、行列i個(i : 2~n)を順々に求めていきます。(dp[0][1], dp[1][2],..., dp[4][5], dp[0][2], dp[1][3],..., dp[0][5])
dp[i][j] ( i < j ) の式を一般化していきます。
行列3個のかけ算最小回数を求める時には2個*1個 or 1個*2個の行列のかけ算回数に加えて今までのdp配列を利用しています。行列4個のかけ算最小回数を求める時には3個*1個 or 2個*2個 or 1個*3個の行列のかけ算回数に加えて今までのdp配列を利用しています。
行列掛け算順序をわざと()を付けて表現したのでこのイメージがすぐ持てればうれしいです。規則性があるのでfor文で表現できそうだなってなりますね。
x個*y個という形にしたのは一般化しやすいためで、以下の事が成り立つからです。
X * Y のかけ算最小回数 = Xを出すまでのかけ算最小回数 + Yを出すまでのかけ算最小回数 + (行列X行数 * 行列X列数(行列Y行数) * 行列Y列数)
X(Y)を出すまでのかけ算最小回数はdp配列に格納されています。また、Xが1つの行列の積、つまり何もかけ算していないときでもそれはdp[x][x]の値を指すことになります。dp[i][j] (i = j) の時は0なので問題ないですね。
dp[0][1~3]を求める時は以下のようなイメージです。
dp[0][3]は以下の最小値です。
- dp[赤セル2つ] + (0~0番目の行列) * (1~3番目の行列)
- dp[緑セル2つ] + (0~1番目の行列) * (2~3番目の行列)
- dp[水色セル2つ] + (0~2番目の行列) * (3~3番目の行列)
dp[0][3]と赤のセルは左に3と下に1離れており、緑のセルは左に2と下に2、水色は左に1と下に3離れており、4行列の積を2つに分けて考えた時と同じ個数になりました。
このように考えると、n個の行列の積のかけ算最小回数を求めるにはn-1通りの順序があり、それらの最小値を求めるのです。
疑似コードとしてはこんな感じですかね。
x : x個の行列積のかけ算最小回数を求めたい
n : 行列数
dpm : かけ算回数の最小値
m[n][2] : m[i][0] i番目の行列の行数, m[i][1] i番目の行列の列数 を格納している配列
dpm = INF;
for(i=0;i<n-x+1;i++) {
//n個の内x個の行列積は、n-x+1個ある。
for(j=1;j<x;j++) {
//jはx個の配列をどこで区切って二つの行列と捉えるかを判断する
//j個 * (x-j)個と考える
// (i~i+j-1番目の行列のかけ算最小回数) + (i+j~x+i-1番目の行列のかけ算最小回数) + (i~j行列行数) * (i~j行列列数) (j+1~x+i行列列数)
t = dp[i][i+j-1] + dp[i+j][i+x-1] + m[i][0] * m[i+j-1][1] * m[x+i-1][1];
if ( t < dpm) dpm = t; //最小値の更新
}
//dp配列の更新
dp[i][i+x-1] = dpm;
}
以下、私のコードです。
AIZU ONLINE JUDGE: Code Review
dp配列の扱いが難しく、また上のコードでのdynamic関数のfor文内の添え字で苦労しました…。最初は解法のイメージがいろんなサイトを見ても持てず、イメージがなんとなくできてからはデバッグの繰り返しでした(笑) DPという割には再帰的に行っていないので、少し変な感じはありますね…。
面白かったと思っていただけたら是非コメントをください！
それでは！
See you next time!
