ダイナミックプログラミング
「３個以上の行列の積を計算する時、行列の要素に対する掛け算の回数を最小にする」問題をDP法によって解く。
入力：五つの行列A1[r0,r1]、A2[r1,r2]、A3[r2,r3]、A4[r3,r4]、A5[r4,r5]の次数を自然数r0,r1,r2,r3,r4,r5として入力。
出力：M(i,j)の値をiからｊまでの幅毎に幅の小さい順に出力。
というC言語の課題が出たのですがわかりません。
行列はデータを縦横長方形に並べた物で、横の並びを行、縦の並びを列と呼ぶ。行の数ｈ、列の数ｋの行列AをA［h、k］と表し、ｈ、ｋを行列Aの次数という。行列A1[h、k]と行列A2[ｍ、ｎ]の積はｋ＝ｍの時、定義されていて、行列A1[h、k]と行列A2[k、n]の積はｈ行、ｎ列の行列 B[h、ｎ]となる。
行列Bのi行目のj列目（ｊ番目）のデータは：行列A1[h、k]のi行目と行列A2[k、n]のｊ列目を順に、掛けて加算したものとなる。例えば、
A1[3、2]＝ a b A2[2、4]= G H P Q
c d R S T U
e f
の積行列B[3、4]＝ aG+bR aH+bS aP+bT aQ+bU
cG+dR cH+dS cP+dT cQ+dU
eG+fR eH+fS eP+fT eQ+fU
となります。行列A1[3、2]と行列A2[2、4]の積行列B[3、4]を計算するのに掛け算が３×２×４（２×３×４）回要ります。一般に行列 A1[r0、r1] と行列A2[r1、r2]の積行列を計算するのにr0・r1・r2回掛け算が要ります。行列の積行列を求める演算を“×”で表すと、行列A1[r0、r1]、行列A2[r1、r2]、と行列A3[r2、r3]において、
（A1[r0,r1]×A2[r1,r2]）×A3[r2,r3]＝A1[r0.r1]×（A2[r1,r2]×A3[r2,r3]）
＝A1[r0,r1]×A2[r1,r2]×A3[r2,r3]
が成り立ちます。即ち、行列の積行列を求める順番はどの順番で求めても結果は同じになる。
例えば、行列A1[10,20]、行列A2[20,50]、行列A3[50,1]、行列A4[1,100]の四つの行列の積行列を求める時、
B[10,100]＝A1[10,20]×（A2[20,50]×（A3[50,1]×A4[1,100]）） ・・・(1)
＝（A1[10,20]×（A2[20,50]×A3[50,1]））×A4[1,100] ・・・(2)
が成り立ちます。ところが、(1)の順に計算すると掛け算は１２５，０００回要ります、(2)の順だと２，２００回の掛け算が要ります。このように、沢山の行列の積を求める時には、積を求める順番を工夫する事が大切です。行列Aiの積行列A1[r0,r1]×A2[r1,r2]×・・×Ai[ri-1,ri]×・・×Ak[rk-1,rk]×・・×Aj[rj-1,rj]×・・×An[rn-1,rn]を求める時、最小の掛け算の数をDP法で求める。
M(i,j)を行列の積Ai[ri-1,ri]×・・×Ak[rk-1,rk]×Ak+1[rk.rk+1]×・・×Aj[rj-1,rj]を求めるのに必要な掛け算の最小数とする。行列Aiから行列Ajまでの行列積を求める時、（Ai[ri-1,ri]×・・×Ak[rk- 1,rk]）×（Ak+1[rk.rk+1]×・・×Aj[rj-1,rj]）のように一番最後に実行する行列の積を求める演算をi<=k
M(i,j)= 0 i=jの時
= MIN {M(i,k)+M(k+1,j)+ri-1rkrj} i<jの時
i<=k<j
となる。このM(i,j)をDP法でM(1,n)まで順に求める。
という感じなのですがプログラミングにする場合どうしたらいいのでしょうか？
begin
for i ←1 until n do mii ←0;
for l ←1 until n-1 do
fori ←1 until n-l do
begin
j←i+l;
mij←MIN(mik + mk+1,j + ri-1*rk*rj)
end;
write m1n
end
n個のアルゴリズムはたぶん上記のようになると思います。
お礼
ありがとうございます。頑張ってやってみます。