行列の最小乗数

10134 ワード
algorithm テキストリンク

問題の説明


複数のマトリクスを乗算する場合、どのマトリクスを先に乗算するかで、乗算の回数が異なります.この問題は,複数の行列の乗算時の最小二乗回数を求める問題である.

ぶんせき


i最初の行列の行と列の数をそれぞれR[i]、C[i]と呼ぶ.
(C[i] = R[i + 1])
d[i][j]をi行列からj行列を乗じたときの最小乗算回数.(i <= j)

base case


i=jの場合、行列は1つしかないので、D[i][j]=0となる.

てんかしき


ik毎に最小演算回数は
D[i][k] + D[k + 1][j] + R[i] X C[k] X C[j]
いいですよ.
D[i][j]はこれらの値の中で最も価値がある.そのため、点火式は以下の通りです.
D[i][j] = Min(D[i][k] + D[k + 1][j] + (Ri X Ck X Cj))
(k = i ~ j - 1)

インプリメンテーション

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
  vector<int> R = { 2, 3, 5 };
  vector<int> C = { 3, 5, 2 };
  vector<int> temp = vector<int>();
  vector<vector<int>> D = vector<vector<int>>();
  int min, candidate;

  for (int i = 0; i < R.size(); i++) 
    temp.push_back(0);
	
  for (int i = 0; i < R.size(); i++) 
    D.push_back(temp);
    // n * n 이중벡터 설정

  for (int j = 0; j < R.size(); j++) {
    for (int i = j; i >= 0; i--) {
      if (i == j) continue;
      min = D[i + 1][j] + R[i] * C[i] * C[j];
      
      for (int k = i + 1; k < j; k++) {
        candidate = D[i][k] + D[k + 1][j] + R[i] * C[k] * C[j];
        if (min > candidate) min = candidate;
        // 점화식에 따라 최솟값 구함
      }
      D[i][j] = min;
    }
  }

  cout << D[0][C.size() - 1] << endl;

  return 0;
}

Reference


https://www.codeground.org/common/popCodegroundNote
RFMCで携帯電話にララベルから通知を送る
Svelteツールチップライブラリを作成