Умножение матричной цепочки


Сложный уровень средний
Часто спрашивают в Амазонка CodeNation Де Шоу Google Microsoft Uber
массив Динамическое программирование матрица

В задаче умножения цепочки матриц 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 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 до 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

Код 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)

Поскольку мы использовали двумерный массив dp с размерами N x N. Это составляет всего O (N ^ 2).

дело