行列連鎖乗算

行列連鎖乗算（または行列連鎖順序付け問題^[1]）は、与えられた行列の列を最も効率的に乗算する方法に関する最適化問題である。問題は実際に乗算を実行することではなく、関係する行列乗算の順序を決定することだけである。この問題は動的計画法を使用して解くことができる。

行列の乗算は結合法則に従うため、多くのオプションがあります。つまり、積をどのように括弧で囲んでも、得られる結果は同じになります。たとえば、4 つの行列A、B、C、およびDの場合、5 つのオプションが考えられます。

(( AB ) C ) D = ( A ( BC )) D = ( AB )( CD ) = A (( BC ) D ) = A ( B ( CD )).

括弧で囲む項の順序は積には影響しませんが、積を計算するために必要な単純な算術演算の回数、つまり計算の複雑さに影響します。X × Y行列とY × Z行列の単純な乗算には、XYZ 回の通常の乗算​​とX ( Y − 1) Z 回の通常の加算が必要です。このコンテキストでは、実行時間の複雑さの尺度として通常の乗算​​の回数を使用するのが一般的です。

Aが10×30行列、Bが30×5行列、Cが5×60行列の場合 、

( AB ) Cの計算には(10×30×5) + (10×5×60) = 1500 + 3000 = 4500回の演算が必要ですが、

A ( BC )を計算するには、(30×5×60) + (10×30×60) = 9000 + 18000 = 27000回の演算が必要です。

明らかに、最初の方法の方が効率的です。この情報を使用して、問題の説明を「n個の行列の積の最適な括弧の付け方を決定する方法」と絞り込むことができます。可能な括弧の数は ( n –1)^番目の カタロニア数、つまりO (4 ⁿ / n ^3/2 ) で与えられるため、可能な括弧のそれぞれをチェックするには (ブルート フォース)、行列の数に対して指数関数的な実行時間が必要になり、これは非常に遅く、 n が大きい場合に非現実的です。この問題をより迅速に解決するには、問題を一連の関連するサブ問題に分割します。

まず、私たちが本当に知りたいのは、行列を掛け合わせるために必要な最小コスト、つまり算術演算の最小回数だけだと仮定しましょう。2 つの行列を掛け合わせるだけの場合、掛け合わせる方法は 1 つしかないので、最小コストとは、この操作にかかるコストです。一般に、最小コストは次の再帰アルゴリズムを使用して求めることができます。

• 行列のシーケンスを取得し、それを 2 つのサブシーケンスに分割します。
• 各サブシーケンスを乗算する最小コストを見つけます。
• これらのコストを合計し、2 つの結果マトリックスを乗算するコストを追加します。
• 行列のシーケンスを分割できる可能性のある各位置に対してこれを実行し、すべての位置で最小値を取得します。

たとえば、 4 つの行列ABCDがある場合、 ( A )( BCD )、 ( AB )( CD )、 ( ABC )( D )のそれぞれを見つけるために必要なコストを計算し、ABC、AB、CD、およびBCD を計算するための最小コストを見つけるために再帰呼び出しを行います。次に、最適なものを選択します。さらに良いことに、これにより最小コストが得られるだけでなく、乗算を実行する最適な方法も示されます。つまり、合計コストが最小になるようにグループ化し、各要素に対して同じことを行います。

ただし、このアルゴリズムは実行時間が指数関数的に長くなるため、すべての順列を試す単純なアプローチと同じくらい非効率的です。その理由は、アルゴリズムが多くの冗長な作業を行うからです。たとえば、上記ではABCとAB の両方を計算するための最適なコストを見つけるために再帰呼び出しを行いました。しかし、 ABC を計算するための最適なコストを見つけるには、 AB を計算するための最適なコストも見つける必要があります。再帰が深くなるにつれて、このような不必要な繰り返しがますます多く発生します。

1 つの簡単な解決策は、メモ化と呼ばれるものです。特定のサブシーケンスを乗算するために必要な最小コストを計算するたびに、それを保存します。再度計算するように求められた場合は、保存した答えを返すだけで、再計算は行いません。約n ² /2 の異なるサブシーケンスがあるため(nは行列の数)、これを行うために必要なスペースは妥当です。この簡単なトリックにより、実行時間がO(2 ⁿ ) から O( n ³ )に短縮されることが示されており、これは実際のアプリケーションでは十分すぎるほど効率的です。これがトップダウンの動的プログラミングです。

次のボトムアップアプローチ^{[2]は、2 ≤} k ≤ nごとに、すでに計算されたより小さなサブシーケンスのコストを使用して、長さkのすべてのサブシーケンスの最小コストを計算します。これは同じ漸近実行時間を持ち、再帰を必要としません。

疑似コード:

// 行列 A[i] の次元は dims[i-1] x dims[i] です。 for i = 1..n 
MatrixChainOrder ( int dims [] ) { // length[dims] = n + 1 n = dims . length - 1 ; // m[i,j] = 行列 A[i] を計算するために必要なスカラー乗算の最小数 (つまり、コスト) A[i+1]...A[j] = A[i..j] // 1 つの行列を乗算する場合、コストは 0 です。for ( i = 1 ; i <= n ; i ++ ) m [ i , i ] = 0 ; 

    
        
    
    
    
           
           

    for ( len = 2 ; len <= n ; len ++ ) { // サブシーケンスの長さfor ( i = 1 ; i <= n - len + 1 ; i ++ ) { j = i + len - 1 ; m [ i , j ] = MAXINT ; for ( k = i ; k <= j - 1 ; k ++ ) { cost = m [ i , k ] + m [ k + 1 , j ] + dims [ i - 1 ]* dims [ k ]* dims [ j ] ; if ( cost < m [ i , j ] ) { m [ i , j ] = cost ; s [ i , j ] = k ; // 最小コストを達成したサブシーケンス分割のインデックス} } } } }         
                    
                  
               
                      
                        
                     
                       
                        
                
            
        
    

• 注: dims の最初のインデックスは 0 で、m と s の最初のインデックスは 1 です。

標準ライブラリのメモ化デコレータを使用した Python実装:

 functools からキャッシュをインポート 

def  matrixChainOrder ( dims :  list [ int ])  ->  int : 
    @cache 
    def  a ( i ,  j ): 
        return  min (( a ( i ,  k )  +  dims [ i ]  *  dims [ k ]  *  dims [ j ]  +  a ( k ,  j ) 、  
                   kが範囲( i + 1 、j )内である場合)、 デフォルト= 0 )      

     ( 0 、len ( dims ) - 1 )を返す   

O ( n3 )動的計画法アルゴリズムよりも複雑^ではあるが、 より効率的なアルゴリズムも存在する。

TC Huと M.-T. Shingによって公開されたアルゴリズムは、O ( n  log  n )の計算量を実現します。^{[3] [4] [5]彼らは、}行列チェーンの乗算問題を正多角形の三角形分割の問題に変換 (または縮小) する方法を示しました。多角形は、最終結果を表す底辺と呼ばれる水平な底辺があるように配置されます。時計回り方向の多角形の他のn辺は、行列を表します。辺の各端の頂点は、その辺で表される行列の次元です。乗算チェーンにn 個の行列がある場合、 n −1 個のバイナリ演算とC _{n −1}個の括弧の配置方法があります。ここで、C _{n −1}は ( n −1)番目のカタラン数です。このアルゴリズムは、 n +1 辺 を持つ多角形の三角形分割にもC _{n −1 通り}の方法があることを利用しています。

この画像は、正六角形の三角形分割の例を示しています。これらは、5 つの行列の積の乗算を順序付けるために括弧を配置するさまざまな方法に対応しています。

以下の例では、4 つの辺 A、B、C があり、最終結果は ABC です。A は 10×30 行列、B は 30×5 行列、C は 5×60 行列で、最終結果は 10×60 行列です。この例の正多角形は 4 角形、つまり正方形です。

行列積 AB は 10x5 行列で、BC は 30x60 行列です。この例では、次の 2 つの三角分割が可能です。

• 
  (AB)Cの多角形表現
• 
  A(BC)の多角形表現

三角形 1 つあたりのコストは、必要な乗算回数で表すと、その頂点の積になります。多角形の特定の三角形分割の総コストは、その三角形すべてのコストの合計です。

( AB ) C : (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 回の掛け算

A ( BC ): (30×5×60) + (10×30×60) = 9000 + 18000 = 27000回の乗算

Hu & Shingは、最小コスト分割問題の最適解をO ( n  log  n )時間で見つけるアルゴリズムを開発した。このアルゴリズムの正しさの証明は、1981年の技術レポートで証明され、公開された論文では省略された「補題1」に依存している。^{[6] [4]}技術レポートの補題の証明は間違っているが、Shingは修正された証明を提示した。^[1]

 王、朱、 田は簡略化されたO ( nlogm )アルゴリズムを発表した。ここでnは行列チェーン内の行列の数、mは与えられた行列チェーンの次元シーケンス内の局所最小値の数である。^[7]

Nimbark、Gohel、Doshiは貪欲O ( nlogn )アルゴリズムを発表したが^[8]、最適性の証明は間違っており、そのアルゴリズムはいくつかの行列連鎖に対して最も効率的な括弧割り当てを生成できない [  1 ^{] 。}

^{Chin [9]}とHu & Shing ^[10]が独自に作成したアルゴリズムはO( n )で実行され、最適な選択よりも最大で15.47%悪い括弧を生成します。ほとんどの場合、アルゴリズムは最適なソリューション、または最適なソリューションよりもわずか1〜2%悪いソリューションを生成します。^[5]

アルゴリズムは、問題を多角形分割問題に置き換えることから始まります。多角形の各頂点Vには重みwが関連付けられています。連続する 3 つの頂点があり、それが最小の重みを持つ頂点であるとします。頂点のある四辺形を(時計回りの順序で) 見てみましょう。これを三角形に分割するには、次の 2 つの方法があります。 ${\displaystyle V_{i-1},V_{i},V_{i+1}}$${\displaystyle V_{\min }}$${\displaystyle w_{\min }}$${\displaystyle V_{\min },V_{i-1},V_{i},V_{i+1}}$

• ${\displaystyle (V_{\min },V_{i-1},V_{i})}$そして、費用がかかる${\displaystyle (V_{\min },V_{i+1},V_{i})}$${\displaystyle w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}}$
• ${\displaystyle (V_{\min },V_{i-1},V_{i+1})}$そしてコストがかかります。${\displaystyle (V_{i-1},V_{i},V_{i+1})}$${\displaystyle w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}}$

したがって、もし

${\displaystyle w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}}$

または同等

${\displaystyle {\frac {1}{w_{i}}}+{\frac {1}{w_{\min }}}<{\frac {1}{w_{i+1}}}+{\frac {1}{w_{i-1}}}}$

多角形から頂点を削除し、辺を三角形分割に追加します。上記の条件を満たす頂点がなくなるまで、このプロセスを繰り返します。残りのすべての頂点に対して、辺を三角形分割に追加します。これにより、ほぼ最適な三角形分割が得られます。 ${\displaystyle V_{i}}$${\displaystyle (V_{i-1},V_{i+1})}$${\displaystyle V_{i}}$${\displaystyle V_{n}}$${\displaystyle (V_{\min },V_{n})}$

行列連鎖乗算問題は、より抽象的な問題を解決するために一般化されます。つまり、オブジェクトの線形シーケンス、それらのオブジェクトに対する連想二項演算、および任意の2つのオブジェクト（およびすべての部分結果）に対してその演算を実行するコストを計算する方法が与えられた場合、シーケンスに対して演算を適用するためにオブジェクトをグループ化する最小コストの方法を計算します。^[11]この実用的な例は、データベースの結合操作の順序付けから来ています。クエリの最適化§結合の順序付けを参照してください。

これのもう 1 つのやや不自然な特殊なケースは、文字列のリストの文字列連結です。たとえば、Cでは、 strcat を使用して長さmとnの 2 つの文字列を連結するコストはO( m  +  n ) です。これは、最初の文字列の末尾を見つけるのにO( m ) 時間、2 番目の文字列をその末尾にコピーするのに O( n ) 時間かかるためです。このコスト関数を使用して、文字列のシーケンスを連結する最も速い方法を見つける動的プログラミング アルゴリズムを作成できます。ただし、文字列をその長さの合計に比例した時間で簡単に連結できるため、この最適化はあまり役に立ちません。単一リンク リストにも同様の問題があります。

もう 1 つの一般化は、並列プロセッサが利用可能な場合に問題を解決することです。この場合、行列積の各要素を計算するコストを加算する代わりに、同時に実行できるため、最大値を取ります。これは、最小コストと最終的な最適なグループ化の両方に劇的な影響を与える可能性があります。すべてのプロセッサをビジー状態にしておく、より「バランスのとれた」グループ化が好まれます。さらに洗練されたアプローチもあります。^[12]

• アソシアヘドロン
• たまり格子