براکت های چاپ در مسئله ضرب زنجیره ماتریس


سطح دشواری سخت
اغلب در آمازون Avalara دژ پایگاه داده دیرتی JP مورگان 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 2 2 و 3 6 1 ضرب می کنیم که هزینه 3 عملیات را می گیرد. سپس ما ماتریس C را با ماتریس حاصل از ضرب A و B ضرب می کنیم. این عمل دوباره 4 18 XNUMX XNUMX XNUMX طول می کشد و در مجموع XNUMX عمل انجام می شود.

number of matrices = 2

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

شرح: از آنجا که فقط دو ماتریس وجود دارد ، تنها یک روش واحد برای ضرب ماتریس وجود دارد که در مجموع 2000 عملیات طول می کشد.

رویکرد چاپ براکت در مسئله ضرب زنجیره ماتریس

ما در حال حاضر حل شده است مسئله ضرب زنجیره ماتریس که در آن ما نیاز به پیدا کردن حداقل تعداد عملیات در ضرب تمام ماتریس. ضرب زنجیره ماتریس با استفاده از برنامه نویسی پویا پیش نیاز این مشکل است. ایجاد فقط تغییرات کوچک در مسئله ضرب زنجیره ماتریس می تواند براکت ها را چاپ کند. ما یک ماتریس براکت درست می کنیم که در آن براکت ها [i] [j] شاخص بهینه را ذخیره می کنند. اگر برای قبل و بعد از آن ، تمام ماتریس های موجود در مرز [i ، j] ضرب شوند ، شاخص برای شاخص های i بهینه است. پس از آن نتیجه آنها ضرب می شود که حداقل تعداد عملیات مورد نیاز را به ما می دهد. این فقط بدان معنی است که ما ابتدا نتیجه را برای ماتریس های 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)

کد جاوا

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 داریم.