アルゴリズム（行列積）

質問

行列M1,M2,M3,M4が以下の数の行、列を持つ行列としたとき、行列積M1,M2,M3,M4をもっとも少ない演算回数で計算するには、どの順序で計算すればよいか？
M1:20行60列
M2:60行5列
M3:5行20列
M4:20行100列

全くわかりません(>_<)みなさま手取り足取り教えてくださいm(__)m

回答No.1

gakutensoku · ベストアンサー

まず、m行n列の行列とn行l列の行列の行列積を計算するための演算回数はお分かりでしょうか?

お礼

すみません(-_-;)全くわかりません(>_<)

回答No.3

gakutensoku

#1です。

続きです。

M1,M2,M3,M4をどのような順番で掛けるかを括弧を使って表現します。
掛け算の順番のパターンをすべて列挙すると、下記の5通りになります。

M1*((M2*M3)*M4)
M1*(M2*(M3*M4))
(M1*M2)*(M3*M4)
((M1*M2)*M3)*M4
(M1*(M2*M3))*M4

上記5通りについて、#2での内容にしたがって計算すれば、演算回数が
最小となる順番が分かります。

ただし、この方法は、今回の問題を解くくらいになら使用できますが、
掛け合わせる行列の数が多くなった場合には、使い物になりません。

一般的なアルゴリズムに関しては、「動的計画法」をキーワードに
調べてみてください。

--------------------------------------------------
困り度3のようでしたが、その後如何ですか?
レポートなどの課題で、提出期限が過ぎたから放置などでしたら悲しいですが。

回答No.2

gakutensoku

#1です。

手取り足取り行きます。

以降では、「演算回数」は「乗算の回数」として議論を進めます。

行列A:m行n列
行列B:n行l列

とし、行列CをAとBとの積とします。(C = AB)

下記の内容を確認してください。

(1)行列Cのサイズは何行何列になるでしょうか?
(2)行列Cの1個の要素を計算するのに、何回の掛け算が必要でしょうか?

(1)と(2)からAとBとの積計算に必要な乗算の回数が分かります。