動的計画法４ 連鎖行列積

問題定義

連鎖行列積問題
n個の行列の連鎖が与えられたとき，スカラーの乗算回数を最小化するように積 A1, A2, .... An を完全に括弧付けする問題です．
（与えられた行列計算を実行するために，掛け算の回数が最小となる計算順序を決定することが目的．）

なかなか上の定義だと難解なので，自分解釈します．

０．行列の掛け算

二つの行列の掛け算をする時に必要な回数は，下記のように求まります．

行列演算は結合法則が成り立つので，どの順番で掛け算をしても結果は同じになりますが，結果を求めるための掛け算回数は下記のようにどの順番で計算するかに依存します．

上の例では，A1, A2を計算して，そのあとA3との掛け算をした場合，7500回，A2, A3の掛け算をして，A1の掛け算をした場合，75000回となり，演算回数が10倍も異なります．この問題は，行列の掛け算問題が与えられたときに掛け算回数が最小となる順序を求めるものです．

ということで，動的計画法で問題を解決する下記３ステップを通して，問題を解いていきたいと思います．

１．再帰的に求める方法を考える．
２．再帰関数の分岐から漸化式を作る．
３．漸化式を使って，ボトムアップで表を埋めていく

１．再帰的に求める方法を考える

行列の連鎖積が下記のように与えられたとき，

最小掛け算回数を返してくれる下記の関数があったとします．

get_min_mult_calc(i, j, mat_list)
i :  mat_list 内の行列開始端インデックス．
j :  mat_list 内の行列終了端インデックス．
mat_list :  行列リスト．

で，この魔法の関数がうまく動くとします．であるとすると，(i, j) の連鎖積の最適値を求めるときには (i, k), (k+1, j) に対するこの関数のアウトプットを使えばよく，この k を変化させて最適値を調べます．ここで，(i, j) の連鎖積を最小にする k の位置は i + 1 ~ j - 1 のどこかにあります．この関数のコールイメージは下記のようになります．

i = j の時，
0
i ≠ j の時，
min(
get_min_mult_calc(i, i+1, mat_list) + get_min_mult_calc(i+2, j, mat_list) + pi-1pi+1pj,
....
get_min_mult_calc(i, k, mat_list) + get_min_mult_calc(k+1, j, mat_list) + pi-1pkpj,
....
get_min_mult_calc(i, j-2, mat_list) + get_min_mult_calc(j-1, j, mat_list) + pi-1pj-2pj, 
)

という形で，i ≠ j の時は k をひとつづつ動かして最小なものを選ぶループが必要になります．上記をコードに落とすと，下記のようになります．

import sys

class Mat(object):

  def __init__(self, row, col):
    self.row = row
    self.col = col

def get_min_mult_cnt(i, j, mat_list):

  val = 0
  if (i == j):
    val = 0
  else:
    val = sys.maxsize
    for k in range(i, j):
      p = mat_list[i].row
      n = mat_list[k].col
      q = mat_list[j].col
      tmp = get_min_mult_cnt(i, k, mat_list) + get_min_mult_cnt(k+1, j, mat_list) + p*n*q

      if (tmp < val):
        val = tmp

  return val


if __name__ == '__main__':

  print("Matrix Multiplication Problem")
  mat_list = [Mat(30, 35), Mat(35, 15), Mat(15, 5), Mat(5, 10), Mat(10, 20), Mat(20, 25)]
  print(get_min_mult_cnt(0, 5, mat_list))

２．再帰関数の分岐から漸化式を作る

ということで，ここまでくればあとは機械的に行けそうです．漸化式は，下記のようになります．m[i, j] は，i から j までの行列連鎖積の最小掛け算回数です．

m[i, j] = 0 :  （i = j の時．）
m[i, j] =  :  （i ≠ j の時．）
mini≦k≦j(m[i, k] + m[k+1, j] + pi-1pkpj)

漸化式の中にループが入っている点が今までと違うところだと思います．この漸化式を使って，実際に表を作っていきます．

３．漸化式を使って，ボトムアップで表を埋めていく

今回の場合，漸化式の中にループが入っているので，テーブルの計算方法が少し複雑になります．ここで，テーブルの構造を下記のように定義します．

m[i, j] : 連鎖行列積列の i 番目から j 番目までの最小掛け算回数を収めたテーブル．

三重のループになるので，テーブルの計算方法がちょっと複雑です．参考に4つの行列連鎖積の場合について，テーブルの計算順序を書き出してみました．３重になっている一番内側のループは，kを動かすためのループになります．kを動かすことによって，m[i, j]がそれ以前に計算されている要素からどのように求められているかは，下記の図の最後に書いてあります．

で，これをコードに落とすと，，，

import sys
import numpy as np

class Mat(object):

  def __init__(self, row, col):
    self.row = row
    self.col = col

def get_min_mult_cnt_rec(i, j, mat_list):

  val = 0
  if (i == j):
    val = 0
  else:
    val = sys.maxsize
    for k in range(i, j):
      p = mat_list[i].row
      n = mat_list[k].col
      q = mat_list[j].col
      tmp = get_min_mult_cnt_rec(i, k, mat_list) + get_min_mult_cnt_rec(k+1, j, mat_list) + p*n*q

      if (tmp < val):
        val = tmp

  return val

def get_min_mult_cnt_dp(i, j, mat_list):

  multp = np.zeros((len(mat_list), len(mat_list)))
  multp.fill(sys.maxsize)
  
  # 長さ0連鎖の演算量
  for i in range(len(mat_list)):
    multp[i, i] = 0

  for le in range(1, len(mat_list)):
    for i in range(len(mat_list)-le):
      j = i + le

      tmp = sys.maxsize
      for k in range(i, j):
        p = mat_list[i].row
        n = mat_list[k].col
        q = mat_list[j].col
        tmp = multp[i, k] + multp[k+1, j] + p*n*q

        if (tmp < multp[i, j]):
          multp[i, j] = tmp

  print(multp)
  return multp[i, j]

if __name__ == '__main__':

  print("Matrix Multiplication Problem")
  mat_list = [Mat(30, 35), Mat(35, 15), Mat(15, 5), Mat(5, 10), Mat(10, 20), Mat(20, 25)]
  
  print("Solve Recursively")
  print(get_min_mult_cnt_rec(0, 5, mat_list))
  
  print("Solve Dynamic Programing")
  print(get_min_mult_cnt_dp(0, 5, mat_list))