3

動的計画法を使用した行列乗算の以下のアルゴリズムを理解しようとしています。

mi, jが製品評価の最小コストである場合Mi × ... × Mj:

  • mi、j = 0、i = j の場合、および
  • mi, j = MIN, i ≤ k < j { mi,k + mk+1,j + ri-1rkrj } (i < j の場合)。

アルゴリズム：

for i := 1 to n do
   mi,i := 0
for length := 1 to n-1 do
   for i := 1 to n-length do
      j := i + length
      mi,j = MINi≤k<j{mi,k + mk+1,j + ri-1rkrj}

それが実際にどのように機能するか、または誰かが私に良い参考文献を教えてくれるかどうかの手がかり。

4

2 に答える 2

2

このアルゴリズムは、一連の行列を乗算するための最小コストを見つけます。

行と列からなる行列Aと、行pと列からなる行列が与えられた場合、標準的な行列の乗算では、積のエントリごとに、の対応する行と対応する列の要素間の乗算が行われます。qBqrA·Bp*q*rp×rqAB

現在、行列の乗算は結合的であるため、積を括弧で囲むことができます

M_1 · M_2 · … · M_n

好きなように、常に同じ結果が得られます。

ここで、r_0の行数と のM_1列r_i数を とします(これは、製品を定義するためのM_iの行数でもある必要があります)。M_(i+1)

次にM_i · … · M_k、r_(i-1)×r_kマトリックスでありM_(k+1) · … · M_j、r_k×r_jマトリックスです。したがって、最初に積をM_i · … · M_j計算し、次に結果の 2 つの行列を乗算して積を計算する場合、乗算の総コストは次のようになります。M_i · … · M_kM_(k+1) · … · M_j

c_{i,k} + c_{k+1,j} + r_(i-1)×r_k×r_j

ここc_{i,k}で、 は選択された計算方法のコストですM_i · … · M_k(および に類似していc_{k+1,j}ます)。

ここで、M_i · … · M_j分割による評価の最小コストはM_k、2 つのサブプロダクトが最小コストで評価される場合に明らかに達成されます。

そして、評価M_i · … · M_jの最小コストは、考えられるすべての分割の最小コストを計算することによって見つけられます。

m_{i,j} = min { m_{i,k} + m_{k+1,j} + r_(i-1)×r_k×r_j : i <= k < j }

のためにi < j。

次に、完全な製品の最小コストは、最初に 2 つのマトリックスのみを含むサブ製品の最小コストを計算することによって計算されます [可能な分割は 1 つだけです]。次に、3 つのマトリックスを使用するサブ製品の最小コストを計算します。たった 2 つの行列の副積 - ここで括弧が有効になり、通常は違いが生じます - 次に、合計計算の最小コストが見つかるまで 4 つなど。

最小コストを生み出す括弧を見つけるには、最小コストの配列を検索して、それを生み出す分割を見つけます [そして、2 つのサブ製品など]。mアレイ内の最小コストと並んで最小コストに分割します。

于 2013-01-11T22:42:36.937 に答える
0

コピー＆ペーストは好きではありません。短くして、自分の言葉で説明します。

この問題の重要なポイントは、A*B*C の計算には、A*(B*C) または (A*B)*C の 2 つの方法しかないということです。同様に、A*B*C*D の計算には、A*(B*C*D)、(A*B)*(C*D)、(A*B*C)*D の 3 つの方法しかありません。(注: (B*C*D) と (A*B*C) はサブ問題で、以前に計算済みです)

したがって、M1*M2*... Mn を計算すると、 M1 (M2*M3*...*Mn)、(M! M2) (M3*...*Mn)、...、( M1*M2*...*Mn-1)*Mn

それがあなたの与えられた疑似コードに含まれるものです:)

于 2013-01-12T09:27:08.217 に答える