Друк дужок у задачі множення матричного ланцюга


Рівень складності Жорсткий
Часто запитують у Амазонка Авалара Цитадель Збір даних Directi JP Morgan Paymt 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 х 2 і 2 х 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, а потім комбінуємо їх результат.

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

Друк дужок у задачі множення матричного ланцюга

Код для друку дужок у задачі множення ланцюга матриці

Код С ++

#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). Отже, це змушує алгоритм працювати O (N ^ 3) загалом.

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

Ми маємо поліноміальну просторову складність O (N ^ 2) тому що ми маємо 2D DP масив.