スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




連鎖行列積 Matrix Chain Multiplication

2006.06.26 01:36  動的計画法

l × m の行列 A と、m × n の行列 B が与えられた時、AB の積 C

C[i, j] = Σmk=1A[i, k] * B[k, j] ( 1 ≦ il, 1 ≦ jn)

を満たす l × n の行列になります。

matrixChain1.gif

この計算では、 l × m × n 回の掛け算が必要です。では複数の行列の積(連鎖行列積)について考えてみましょう。

(M1M2M3...Mn) のように、1 ≦ i ≦ n について、行列 Miri の行と ri+1 の列をもつ(下図参照) n 個の行列の掛け算を考えます。

matrixChain2.gif

この条件の下では、これらの行列の積は様々な順番で計算することができます。例えば、左から右へ向かって計算すると

(...((M1M2)M3)...Mn)

と表すことができ、右から左に向かって計算すると

(M1...(Mn-2(Mn-1Mn))...)

と表すことができます。さらに

(M1..(M2(M3M4)M5)...Mn)

などの、様々な順番が可能です。

ここで注目すべきことは、勿論掛け算の計算結果(連鎖行列積)は同じですが、行列の掛け算の順番によって、"掛け算の総回数"が異なってきます。例えば、上記の連鎖行列積に必要とする掛け算の総回数を、いくつかのケースについて考えてみましょう(2つの行列の掛け算には上記式の標準的な方法を用いることとします)。

Case 1. 左から右へ向かって: 86 回

matrixChainCase1.gif

Case 2. 右から左に向かって: 69 回

matrixChainCase2.gif

Case 3. 最適な順番: 36 回

matrixChainCase3.gif

連鎖行列積では、隣り合う2つの行列の掛け算にどのような方法を用いたとしても、「どのような順番で」掛け算を行うかが、総演算回数に大きく影響します。Matrix Chain Multiplication (連鎖行列積) は、掛け算の総回数を最小にする最適な連鎖行列の掛け算の順番を求める問題です。

連鎖行列積を計算する最適な順番を直接求めるために、全ての可能な順番を調べてみるアルゴリズムは現実的ではありません。行列の個数が大きくなれば、計算量が指数的に膨大になることは明らかです。以下に示すように、この問題には Dynamic Programming (DP) (動的計画法) が適用できます。

まず、(M1M2) を計算するための方法(順番)はただ 1 通りであり、r1 × r2 × r3 回の掛け算が必要です。同様に、(M2M3) を計算するための方法もただ 1 通りであり、r2 × r3 × r4 回の掛け算が必要です。つまり、(Mn-1Mn) を計算するための方法はただ 1 通りであり、rn-1 × rn × rn+1 回の掛け算が必要です。そして、これらの掛け算の回数をコストとして表に記録しておきます。

次に、(M1M2M3)、(M2M3M4)、...(Mn-2Mn-1Mn) を計算するための最適な方法を求めます。

例えば、(M1M2M3) を計算するための最適な方法を求めるためには、(M1(M2M3)) と ((M1M2)M3)のコストを計算し、小さい方のコストを (M1M2M3) のコストとして表に記録します。この時、

(M1(M2M3)) のコスト = (M1) のコスト + (M2M3) のコスト + r1 × r2 × r4
((M1M2)M3) のコスト = (M1M2) のコスト + (M3) のコスト + r1 × r3 × r4

となります。ここで注目すべきことは、これらの計算に用いた (M1M2) 及び (M2M3) は再計算する必要がなく、表から参照することができるということです。また、1 ≦ in について、(Mi) のコストは 0 であることに注意します。

一般的な形式では、(MiMi+1...Mi+j) を計算するための最適な方法は、 i + 1 ≦ ki + j における (MiMi+1...Mk-1)(Mk...Mi+j) の中から最小のコストを見つけることによって決定します。

例えば、、(M1M2M3M4M5) (つまり、i = 1、j = 4 の場合)のコストは、

k = 2 (M1)(M2M3M4M5) のコスト = (M1) のコスト + (M2M3M4M5) のコスト + r1×r2×r6
k = 3 (M1M2)(M3M4M5) のコスト = (M1M2) のコスト + (M3M4M5) のコスト + r1×r3×r6
k = 4 (M1M2M3)(M4M5) のコスト = (M1M2M3) のコスト + (M4M5) のコスト + r1×r4×r6
k = 5 (M1M2M3M4)(M5) のコスト = (M1M2M3M4) のコスト + (M5) のコスト + r1×r5×r6

のうちの最小値となります。


実装に向けて、さらに具体的に見てみましょう。

まず、cost[][] を cost[i][i + j]> が (MiMi+1...Mi+j) を計算するための最適なコストを記録する配列とします。

さらに、best[][] を best[i][i + j] が (MiMi+1...Mi+j) を (MiMi+1...Mk-1)(Mk...Mi+j) によって与えるような k を記録する配列とします。

以下に、プログラム例を示します。

#include<iostream>
#include<stdio.h>
#include<algorithm>

using namespace std;

void output( int, int, int, int);

#define MAX 100
#define INFTY (1 << 21)

int SIZE;
int R[MAX + 2];
int C[MAX+1][MAX+1]; // cost table
int B[MAX+1][MAX+1]; // best table

void compute(){
    for ( int i = 1; i <= SIZE; i++ )
    for ( int j = 1; j <= SIZE; j++ ) C[i][j] = INFTY;
    
    for ( int i = 1; i <= SIZE; i++ ) C[i][i] = 0;
    
    for ( int j = 1; j <= SIZE - 1; j++ ){
        for ( int i = 1; i <= SIZE - j; i++ ){
            for ( int k = i + 1; k <= i + j; k++ ){
                // C[i][i+j] = min( C[i][i+j], 
                //                  C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1]);
                int cost = C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1];
                if ( cost < C[i][i+j] ){
                    C[i][i+j] =  cost;
                    B[i][i+j] = k;
                }
                
            }
        }
    }
}

void order( int i, int j ){
    if ( i == j ) cout << "M" << i;
    else{
        cout << "(";
        order( i, B[i][j]-1 ); order(B[i][j], j);
        cout << ")";
    }
}

void input(){
    cin >> SIZE;
    for ( int i = 1; i <= SIZE + 1; i++ ) cin >> R[i];
}

void output(){
    cout << "minimum cost = " << C[1][SIZE] << endl;
    order(1, SIZE);
    cout << endl;
}

main(){
    input();
    compute();
    output();
}




Sample Input

6
40 20 30 10 20 20 30

Sample Output

minimum cost = 36000
((M1(M2M3))((M4M5)M6))


スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(1) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

とってもわかりやすく
参考になりました。
ありがとうございます。

迷える子羊 | URL | 2009.07.28 18:45 | 編集

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。