Печать скобок в задаче умножения цепочек матриц


Сложный уровень Жесткий
Часто спрашивают в Амазонка Avalara Цитадель Databricks Directi JP Morgan Paytm Twilio
массив Динамическое программирование матрица

Постановка задачи

Нам нужно найти такой порядок умножения матриц, чтобы количество операций, связанных с умножением всех матриц, было минимальным. Затем нам нужно распечатать этот порядок, т.е. распечатать скобки в задаче умножения цепочки матриц.

Предположим, у вас есть 3 матрицы A, B, C размеров axb, bxc, c xd соответственно. Есть два возможных случая умножения матриц. Либо мы сначала умножаем A и B, а затем C, либо сначала умножаем B и C, а затем A. Первый выбор приведет к стоимости (axbxc + axcxd), в то время как второй вариант потребует в общей сложности (bxcxd + axbxd) операций. Мы видим, что количество задействованных операций зависит от порядка умножения матриц. Таким образом, нам нужно найти такой порядок умножения матриц, при котором количество операций будет минимальным. 

Пример

number of matrices = 3

Dimensions of matrices = {1, 2, 3, 4}
((AB)C)

 

Объяснение: Сначала мы умножаем матрицы размером 1 x 2 и 2 x 3, что требует 6 операций. Затем мы умножаем матрицу C на матрицу, полученную в результате умножения A и B. Эта операция снова занимает 1 x 3 x 4, что в сумме составляет 18 операций.

number of matrices = 2

Dimensions of matrices = {10, 10, 20}
(AB)

Объяснение: Поскольку имеется только две матрицы, существует только один способ умножения матриц, который требует в общей сложности 2000 операций.

Подход к печати скобок в задаче умножения цепочек матриц

Мы уже решили Задача умножения цепочки матриц где нам нужно было найти минимальное количество операций, необходимых для умножения всех матриц. Умножение цепочки матриц с использованием динамическое программирование является предпосылкой для этой проблемы. Внеся небольшие изменения в задачу умножения цепочки матриц, можно вывести скобки. Составляем матрицу скобок, в которой скобки [i] [j] хранят оптимальный индекс. Индекс является оптимальным для индексов i, j, если до и после которого все матрицы в границе [i, j] перемножаются. Затем их результат умножается, что дает нам минимальное количество необходимых операций. Это просто означает, что мы сначала находим результат для матриц i до оптимального индекса и матриц от оптимального индекса + 1 до j, а затем объединяем их результат.

Мы используем матрицу скобок для печати скобок вокруг матрицы. Мы продолжаем разделять нашу проблему на подзадачи, пока не получим единую матрицу, а затем распечатываем ее.

Печать скобок в задаче умножения цепочек матриц

Код для печати скобок в задаче умножения цепочки матриц

Код C ++

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

// Recursively print the arrangement for minimum cost of multiplication
void printBracketsMatrixChain(int i, int j, vector<vector<int>> &brackets, char &cur_name){
    
    // you have a single matrix ( you cannot further reduce the problem, so print the matrix )
    if(i == j){
        cout<<cur_name;
        cur_name++;
    } else {
        cout<<"(";
        
        // Reduce the problem into left sub-problem ( left of optimal arrangement )
        printBracketsMatrixChain(i, brackets[i][j], brackets, cur_name);
        
        // Reduce the problem into right sub-problem ( right of optimal arrangement )
        printBracketsMatrixChain(brackets[i][j]+1, j, brackets, cur_name);
        cout<<")";
    }
}

void 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;
        }
    }

    vector<vector<int>> brackets(numberOfMatrices, vector<int>(numberOfMatrices, 0));
    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++) {
                int val = dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]);
                if(val < dp[i][j]) {
                    dp[i][j] = val;
                    brackets[i][j] = k;
                }
            }
        }
    }

    // naming the first matrix as A
    char cur_name = 'A';
    
    // calling function to print brackets
    printBracketsMatrixChain(0, numberOfMatrices-1, brackets, cur_name);
    cout<<endl;
}

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];
        matrixMultiplicationProblem(matrixSize);
    }
}
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
(((AB)C)D)
(((((AB)C)D)E)F)

Код Java

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

class Main {
    
    static char cur_name;
    
    // Recursively print the arrangement for minimum cost of multiplication
    static void printBracketsMatrixChain(int i, int j, int brackets[][]){
        
        // you have a single matrix ( you cannot further reduce the problem, so print the matrix )
        if(i == j){
            System.out.print(cur_name);
            cur_name++;
        } else {
            System.out.print("(");
            
            // Reduce the problem into left sub-problem ( left of optimal arrangement )
            printBracketsMatrixChain(i, brackets[i][j], brackets);
            
            // Reduce the problem into right sub-problem ( right of optimal arrangement )
            printBracketsMatrixChain(brackets[i][j]+1, j, brackets);
            System.out.print(")");
        }
    }

    static void 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;
            }
        }
    
        int brackets[][] = new int[numberOfMatrices][numberOfMatrices];
        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++) {
                    int val = dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]);
                    if(val < dp[i][j]) {
                        dp[i][j] = val;
                        brackets[i][j] = k;
                    }
                }
            }
        }
    
        // naming the first matrix as A
        cur_name = 'A';
        
        // calling function to print brackets
        printBracketsMatrixChain(0, numberOfMatrices-1, brackets);
        System.out.println();
    }

    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();
            matrixMultiplicationProblem(matrixSize);
        }
    }

}

 

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
(((AB)C)D) 
(((((AB)C)D)E)F)

 

Анализ сложности

Сложность времени: O (N ^ 3)

Здесь мы рассматриваем два указателя i и j, которые действуют как границы для матриц, которые работают в O (N ^ 2). Сам вложенный цикл внутри внешних циклов занимает линейное время O (N). Таким образом, алгоритм работает в О (N ^ 3) в итоге.

Сложность пространства: O (N ^ 2)

У нас есть полиномиальная пространственная сложность О (N ^ 2) потому что у нас есть 2D массив DP.