Множення ланцюга матриці


Рівень складності Medium
Часто запитують у Амазонка CodeNation Д. Е. Шоу Google Microsoft Убер
масив Динамічне програмування Матриця

У задачі множення ланцюжків матриць II ми навели розміри матриць, знайдіть порядок їх множення такий, щоб кількість операцій, задіяних у множенні всіх матриць, було мінімізовано.

Вважаємо, у вас є 3 матриці A, B, C розмірами axb, bxc, c xd відповідно. Тоді, якщо спочатку помножити матриці 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 х 2 і 2 х 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 до k, і задача для матриць k + 1 до j. Тоді візьміть мінімум усіх цих значень.

Код С ++ для множення ланцюжків матриць

#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

Код Java для множення ланцюжків матриць

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)

Тут ми розглядаємо два вказівники i та j, які діють як межі для матриць, що працюють в O (N ^ 2). Вкладений цикл всередині зовнішніх циклів займає лінійний час O (N). Таким чином, алгоритм працює в O (N ^ 3) в цілому.

Складність простору: O (N ^ 2)

Оскільки ми використовували 2D-масив dp, розміри якого становлять N x N. Це в цілому робить O (N ^ 2).

посилання