アルゴリズム入門講座: 連鎖行列積問題の考え方

連鎖行列積問題の解法の考え方についてまとめます

例題として、AIZU ONLINE JUDGEの問題を引用します。

問題

n個の行列の連鎖 M1,M2,M3,...,Mn が与えられたとき、
スカラー乗算の回数が最小になるように積 M1M2M3...Mnの計算順序を決定する問題
を連鎖行列積問題(Matrix-Chain Multiplication problem)と言います。

n個の行列について、行列 Mi の次元が与えられたとき、積 M1M2...Mn
の計算に必要なスカラー乗算の最小の回数を求めるプログラムを作成してください。

入力

入力の最初の行に、行列の数 nが与えられます。
続く n 行で行列 Mi(i=1...n) の次元が空白区切りの２つの整数 r、c で与えられます。
r は行列の行の数、cは行列の列の数を表します。

出力

最小の回数を１行に出力してください。

行列の積の考え方

下図のようなl × mの行列Aとm × nの行列Bの積はl × nとなり、
各要素の$C_{ij}$は次の式で得られる

$C_{ij} = \displaystyle \sum_{ i = 1 }^{ m } a_{ik}b_{kj}$

なので、この計算では、l × m × n回のかけ算が必要になる。

複数行列積について考える

下図のような$(M_1,M_2,M_3..M_6)$のような、$M_i$が$p_{i-1}行$$p_i$行の行列であるような、
n個の行列のかけ算を考えます。

これらの行列は様々な順番で計算できるので、行列同士のかけ算の順番によって、
かけ算の計算回数が変わってきます。

連鎖行列問題の解き方考察

連鎖行列において、全ての可能な順番をを調べる方法は$0(n!)$になります。
ただ、小さな部分問題として分割できるので、動的計画法を使うことができます。

動的計画法で解くための考え方

$(M_1,M_2)$を計算するための方法は1通りであり、$p_0 × p_1 × p_2$回のかけ算が必要です。
同様に$(M_2,M_3)$を計算する方法も1通りで、$p_1 × p_2 × p_3$回のかけ算が必要です。
これらのかけ算をコストとして、記録しておきます。

次に、$(M_1,M_2,M_3)$、$(M_2,M_3,M_4)$、...$(M_{n - 2},M_{n - 1},M_n)$ を計算するための最小計算回数つまり最適解を求めます。

例として、$(M_1,M_2,M_3)$の最適解を求めるには、$(M_1(M_2×M_3))$と$((M_1×M_2)M_3))$のコストを計算し、
そのうちの小さい方のコストを$(M_1,M_2,M_3)$のコストとして記録します。

計算量を考えると、

$(M_1(M_2×M_3))$のコスト = $(M_1)$のコスト + $(M_2M_3)$のコスト + $p_0 × p_1 × p_3$
$((M_1×M_2)M_3))$のコスト = $(M_1M_2)$のコスト + $(M_3)$のコスト + $p_0 × p_2 × p_3$

となります。

上記の計算に関して、$(M_1M_2)$のコストと$(M_2M_3)$のコストは記録してあるので、再計算する必要がありません。

また、$1 \leqq i \leqq n$について、$(M_i)$のコストは0になります。

連鎖行列の最適解

一般に連鎖行列の最適解$(M_iM_{i + 1}...M_j)$の最適解は、
$i \leqq k < j$における$(M_iM_{i + 1}...M_k)(M_{k + 1}...M_j)$の最小コストになります

例をあげると
$(M_1M_2M_3M_4M_5)(i = 1,j = 5)$の最適解は

$(M_1)(M_2M_3M_4M_5)$のコスト = $(M_1)$のコスト + $(M_2M_3M_4M_5)$のコスト + $p_0 × p_1 × p_5$(k = 1)のとき

$(M_1M_2)(M_3M_4M_5)$のコスト = $(M_1M_2)$のコスト + $(M_3M_4M_5)$のコスト + $p_0 × p_2 × p_5$(k = 2)のとき

$(M_1M_2M_3)(M_4M_5)$のコスト = $(M_1M_2M_3)$のコスト + $(M_4M_5)$のコスト + $p_0 × p_3 × p_5$(k = 3)のとき

$(M_1M_2M_3M_4)(M_5)$のコスト = $(M_1M_2M_3M_4)$のコスト + $(M_5)$のコスト + $p_0 × p_4 × p_5$(k = 4)のとき

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

上記のアルゴリズムの実装例

以下のような役割の変数を定義します。

m[n + 1][n + 1]	m[i][j]を$(M_iM_{i + 1}...M_j)$を計算するための最小のかけ算の回数とする2次元配列
p[n + 1]	$M_i$がp[i - 1] × p[i]の行列となるような1次元配列

これらの変数を用いて、m[i][j]の値を以下のように設定します。

if(i == j){
  m[i][j] = 0 
}

if(i < j){
m[i][j] = $min_{i \leqq k < j}\{m[i][k] + m[k + 1][j] + p[i - 1] × p[k] × p[j]\}$
}

これを疑似アルゴリズムで書くと以下のようになります。

matrixMultiplication()
  for i = 1 to n
    m[i][j] = 0

  for l = 2 to n
    for i = 1 to n - l + 1
      j = i + l - 1
      m[i][j] = INFTY
      for k = i to j - 1
      m[i][j] = min(m[i][j],m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j])

計算量の考察

上記の疑似コードでは、対象とする行列の数lを2からnまで増やしながら、その範囲を指定するiとjを決めています。
さらにその中で、iからjの範囲でkの位置を決めています。
forの3重ループになっているので、$O(n^3)$になります。

例題の解答

上記をふまえて、例題の解答をc++で書きます。

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

using namespace std;
#define N 100

int main(void){
    int n;
    int p[N + 1],m[N + 1][N + 1] = {};
    
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> p[i - 1] >> p[i];
    }
    for(int l = 2;l <= n;++l){
        for(int i = 1;i <= n - l + 1;++i){
            int j = i + l - 1;
            m[i][j] = __INT_MAX__;
            for(int k = i;k <= j - 1;++k){
                m[i][j] = min(m[i][j],m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
            }
        }
    }
    cout << m[1][n] << endl;
}

参考

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

アルゴリズム入門講座

2019年10月29日火曜日

連鎖行列積問題の考え方

問題

入力

出力