Chained Matrix Multiplication

この文章はyoutube サンシャインテレビのアルゴリズム基礎授業に基づいて書かれた.画像、コンテンツなどのすべての著作権は、チャンネルを運営する教授に帰属します.

チェーンマトリクス乗算

Chained Matrix Mulipication
n個のマトリックスの乗算する最良の順序の問題を求めます
2 X 3 3 X 4行列は2 X 4行列を表す.
合計必要な計算数は2×3×4です.

どうすればいいのでしょうか?

は、まずBret−Forceで説明される.
単純な無知な方法で解くためには,その名の通り,すべての場合の数を比較することによって最適数を見つける方法である.

これに関連して、カタラン数の概念がある.

それに関する証明はありますが、先にお渡ししましょう.
このようにBret-Forceを用いると,計算に4つの行列がある場合,合計5つのケースの数が存在する.

ご覧のように、3つ目の方法は最も速い計算方法で、同じマトリクス計算ですが、計算実行回数は10倍近く違います.
これがチェーンマトリクス乗算が必要な理由だと思います.
さらに進む前に,行列の乗算条件を簡単に論じた.教授は親切に整理した.

まとめると、乗算する2つの行列A、BのA行列の行または列は、B行列の列または行と同じでなければならない.

点火式を探す

1次再帰関係を探す

M:チェーン行列ㅇに必要な乗子最小回収行列

を乗じる

M[i][j] = 𝐴𝑖活動場所を表す𝐴𝑗行列に乗算するために必要な乗算の最小回数(1≦𝑖 ≤ 𝑗 ≤ 𝑛)
目標:𝐴𝑖 ⋯ 𝐴𝑗 行列(𝐴𝑖 ⋯ 𝐴𝑘)(𝐴𝑘+1 ⋯ 𝐴𝑗)分割された再帰関係を検索する

ステップ2

州対角線、すなわち中央を通る対角線は、いずれも0とする𝑀[𝑖][𝑖] = 0

最終目標はM[1][n]を求める計算であり、上方計算により求めることができる.

再回帰関係は説明の代わりに写真を使う.

上向き対角線技術Uper Diagonal Method

例えば、Mを検索する場合[1][4]、𝑚𝑖𝑛
( 𝑀[1][1] + 𝑀[2][4] + 𝑑0𝑑1𝑑4,//kが1の場合
𝑀[1][2] + 𝑀[3][4] + 𝑑0𝑑2𝑑4、/kが2の場合
𝑀[1][3] + 𝑀[4][4] + 𝑑0𝑑3𝑑4)//kが3の場合
通過する過程で,最小diageanlの和がその値となり,最後に対角線の値が最適値となる.

コードの作成

def minmult(d) :
    n = len(d) - 1
    M = [[-1] * (n+1) for _ in range(n+1)]
    P = [[-1] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n+1):
        M[i][i] = 1
    for diagonal in range(1, n):
        for i in range(1, n - diagonal + 1):
            j = i + diagonal
            M[i][j] , P[i][j] = minimum(M, d, i ,j)
    return M, P

再帰的なコードを実行します.
まずMとPの2つの二層配列を−1に初期化し,次に中心線を全て1に処理した.次に、1〜n−1をループし、その対角線内で1〜n−対角線を繰り返す.

の対角線がこのように収縮する対角線から1つの数を減算と、対角線のすべての場合の数

を算出することができる.
次に、j=i値と対角値を和に設定します.

現在diagnoalでいくつかの状況のライセンスを検索しています
なお、1番対角線については初期値が設定されているため、2番対角線から計算が開始される.

最小関数で当時のM[i][j]とP[i][j]を決定する.

def minimum(M ,d , i ,j):
    INF = 999
    minV = INF
    minK = 0
    for k in range(i, j):
        value = M[i][k] + M[k+1][j]
        value += d[i-1] * d[k] * d[j]
        if (minV > value):
            minV = value
            minK = k
    return minV, minK

最小値は無限大、位置はゼロで、値の値は点化式で計算されます.
value = M[i][k] + M[k+1][j]
value += d[i-1] d[k] d[j]
そして計算を終了します.

けいさんちくじしゅつりょく

MはOptimal Valueを有する.私たちが知りたいのは何が最適な順序なのか.
そこで,Pを利用してそれを探し出す.
前の2つのコードはP[i][j]にKを格納している.これは(Ai...Ak)(Ak+1...Aj)を意味し,計算の順序を知ることができる.

コードは次のとおりです.

def order(P, i, j):
    if (i == j):
        print('A%d'%(i), end = '')
    else:
        k = P[i][j]
        print('(', end = '')
        order(P,i,k)
        order(P, k+1, j)
        print(')', end = '')

最後に.

INF = 999
d = [5, 2, 3, 4, 6, 7, 8]
M, P = minmult(d)
print('M =')
for i in range(1, len(M)):
    print(M[i][1:])
print('P =')
for i in range(1, len(P)):
    print(P[i][1:])

print('minimum order: ', end ='')
order(P, 1, len(d) - 1)

コードで実行します.

次の結果が得られます.

の最後の部分

学校の正規授業で習ったことのないアルゴリズムなので、理解するのは難しいですが、勉強が終わったら本当にこれを見ないで、理解して、証明して、コードを書くことができますか?という疑問に陥りました.
しかし、誰がやったとしても、アルゴリズムが分からなければそのまま暗記します.
ユーチューブでこのような良い内容の講座を無料で提供してくれた教授に改めて感謝します.