매트릭스 체인 곱셈


난이도 중급
자주 묻는 질문 아마존 CodeNation DE Shaw 구글 Microsoft 동네 짱
배열 동적 프로그래밍 매트릭스

행렬 연쇄 곱셈 II 문제에서 우리는 행렬의 차원을 제공하고 모든 행렬의 곱셈과 관련된 연산 수가 최소화되도록 곱셈 순서를 찾습니다.

각각 크기가 axb, bxc, c xd 인 3 개의 행렬 A, B, C가 있다고 가정합니다. 그런 다음 먼저 A와 B 행렬을 곱하고 그 결과에 C를 곱하면이 총 연산에는 (axbxc + axcxd)가 걸립니다. 행렬의 곱셈 순서를 변경하면. 먼저 B와 C 행렬을 곱한 다음 그 결과에 A를 곱합니다.이 총 연산에는 (bxcxd + axbxd)가 필요합니다. 이것은 행렬에서 곱셈 순서가 변경되면 수행되는 연산 수에 영향을 미친다는 것을 보여줍니다. 따라서 주어진 모든 행렬을 곱하기 위해 수행 할 수있는 최소 연산 수를 찾아야합니다.

Input: number of matrices = 3

Dimensions of matrices = {1, 2, 3, 4}

Output: 18

설명 : 먼저 행렬에 1 x 2 및 2 x 3 차원을 곱하면 6 개의 작업 비용이 발생합니다. 그런 다음 행렬 C에 A와 B를 곱한 결과 행렬을 곱합니다.이 연산은 다시 1 x 3 x 4를 사용하여 총 18 개의 연산을 만듭니다.

Input: number of matrices = 2

Dimensions of matrices = {10, 10, 20}

Output: 2000

설명 : 행렬이 두 개뿐이기 때문에 총 2000 개의 연산이 필요한 행렬을 곱하는 단일 방법 만 있습니다.

행렬 연쇄 곱셈에 대한 접근 방식

행렬 곱셈 문제는 많은 표준 중 하나입니다. 동적 프로그래밍 문제. 행렬을 곱하는 모든 방법을 시도하는 재귀 적 접근 방식을 간단히 생각할 수 있습니다. 우리는 모든 준비에 관련된 총 비용을 찾고 모든 준비에서 최소한의 금액을 취합니다. 재귀 솔루션은 확실히 우리에게 정확한 결과를 제공하지만 충분히 효율적이지 않습니다. 재귀 솔루션이 있고 하위 문제가 겹칠 때마다. 작은 하위 문제의 결과를 저장 한 다음 이러한 결과를 결합하여 초기 문제를 해결할 가능성이 있습니다. 이 문제는 사용할 때마다 계산되는 하위 문제가 겹칩니다. 따라서 결과를 dp 테이블에 저장하거나 정렬.

행렬 연쇄 곱셈에서 중첩되는 하위 문제

먼저 단일 문제를 해결합니다. 매트릭스, 0 작업 비용이 발생합니다. 단일 행렬을 구한 후, 우리는 2 개의 행렬을 풀고 3을 구하는 식입니다. 일반적인 경우, 인덱스 i에서 j까지의 행렬에 대한 문제를 풀어야한다고 생각하십시오. 상향식으로 문제를 해결하고 있기 때문입니다. i에서 j까지의 행렬을 풀 때, i에서 j-1, j-2까지의 행렬 문제에 대한 결과를 계산했습니다. 따라서이를 해결하기 위해 i에서 j까지의 행렬에 대한 문제를 먼저 해결한다고 생각합니다. k, 행렬 k + 1에서 j까지의 문제. 그런 다음이 모든 값의 최소값을 취하십시오.

매트릭스 체인 곱셈을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int matrixMultiplicationProblem(vector<int> matrixSize) {
    int numberOfMatrices = matrixSize.size()-1;

    // dp[i][j] = minimum number of operations required to multiply matrices i to j
    int dp[numberOfMatrices][numberOfMatrices];

    // initialising dp array with INT_MAX ( maximum number of operations )
    for(int i=0;i<numberOfMatrices;i++){
        for(int j=0;j<numberOfMatrices;j++){
            dp[i][j] = INT_MAX;
            if(i == j) // for a single matrix from i to i, cost = 0
                dp[i][j] = 0;
        }
    }

    // start solving problem for 2 matrices, then 3, and so on.
    for(int len=2;len<=numberOfMatrices;len++){
        for(int i=0;i<numberOfMatrices-len+1;i++){
            int j = i+len-1;
            for(int k=i;k<j;k++)
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]));
        }
    }

    return dp[0][numberOfMatrices-1];
}

int main() {
    int t;cin>>t;
    while(t--) {
        int n; cin>>n;
        vector<int> matrixSize(n);
        for(int i=0;i<n;i++)cin>>matrixSize[i];
        cout<<matrixMultiplicationProblem(matrixSize)<<endl;
    }
}
2
5 // number of inputs = dimensions of n-1 matrices
5 6 89 49 10 // dimensions of ith matrix = matrixSize[i]*matrixSize[i+1]
7
1 5 2 3 4 1000 64
26925 
68028

매트릭스 체인 곱셈을위한 자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int matrixMultiplicationProblem(int matrixSize[]) {
        int numberOfMatrices = matrixSize.length-1;
    
        // dp[i][j] = minimum number of operations required to multiply matrices i to j
        int dp[][] = new int[numberOfMatrices][numberOfMatrices];
    
        // initialising dp array with Integer.MAX_VALUE ( maximum number of operations )
        for(int i=0;i<numberOfMatrices;i++){
            for(int j=0;j<numberOfMatrices;j++){
                dp[i][j] = Integer.MAX_VALUE;
                if(i == j) // for a single matrix from i to i, cost = 0
                    dp[i][j] = 0;
            }
        }
    
        // start solving problem for 2 matrices, then 3, and so on.
        for(int len=2;len<=numberOfMatrices;len++){
            for(int i=0;i<numberOfMatrices-len+1;i++){
                int j = i+len-1;
                for(int k=i;k<j;k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]));
            }
        }
    
        return dp[0][numberOfMatrices-1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0) {
            int n = sc.nextInt();
            int matrixSize[] = new int[n];
            for(int i=0;i<n;i++)
                matrixSize[i] = sc.nextInt();
            int ans = matrixMultiplicationProblem(matrixSize);
            System.out.println(ans);
        }
    }

}
2
5 // number of inputs = dimensions of n-1 matrices
5 6 89 49 10 // dimensions of ith matrix = matrixSize[i]*matrixSize[i+1]
7
1 5 2 3 4 1000 64
26925 
68028

복잡성 분석

시간 복잡도 : O (N ^ 3)

여기서는 O (N ^ 2)에서 실행되는 행렬의 경계 역할을하는 두 개의 포인터 i와 j를 고려하고 있습니다. 외부 루프 자체 내부의 중첩 루프는 선형 시간 O (N)을 사용합니다. 따라서 알고리즘은 총 O (N ^ 3)에서 실행됩니다.

공간 복잡성 : O (N ^ 2)

차원이 N x N 인 2D dp 배열을 사용했기 때문에 총 O (N ^ 2)가됩니다.

참조