मॅट्रिक्स चेन गुणाकार समस्येमध्ये कंस मुद्रित करणे


अडचण पातळी हार्ड
वारंवार विचारले ऍमेझॉन अवलारा किल्ला डेटाबे्रिक्स डायरेक्टि जेपी मॉर्गन पेटीएम Twilio
अरे डायनॅमिक प्रोग्रामिंग मॅट्रिक्स

समस्या विधान

आम्हाला मॅट्रिकच्या गुणाकाराचा क्रम शोधणे आवश्यक आहे की सर्व मॅट्रिक्सच्या गुणाकारात गुंतलेल्या ऑपरेशन्सची संख्या कमी केली जाते. मग आपल्याला ही ऑर्डर मुद्रित करणे आवश्यक आहे म्हणजे मॅट्रिक्स चेन गुणाकार समस्येमध्ये कंस मुद्रित करणे.

आपल्याकडे अनुक्रमे 3 मॅट्रिक ए, बी, सी आकाराचे अक्ष, बीएक्ससी, सी एक्सडी आहेत याचा विचार करा. मॅट्रिक्सची गुणाकार करण्यासाठी दोन संभाव्य प्रकरणे आहेत. एकतर आम्ही प्रथम 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 ऑपरेशन्सची किंमत लागते. नंतर आम्ही मॅट्रिक्स सी ला परिणामी मॅट्रिक्ससह ए आणि बीच्या गुणाकारातून गुणाकार करतो. हे ऑपरेशन पुन्हा १ एक्स 1 एक्स takes घेते आणि एकूण १ a ऑपरेशन्स बनतात.

number of matrices = 2

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

स्पष्टीकरण: तेथे फक्त दोन मॅट्रिक आहेत कारण गुणाकार मॅट्रिकचा एकच मार्ग आहे ज्यामध्ये एकूण 2000 ऑपरेशन्स लागतात.

मॅट्रिक्स चेन गुणाकार समस्येमध्ये कंस मुद्रित करण्यासाठी दृष्टिकोण

आम्ही आधीच निराकरण केले आहे मॅट्रिक्स चेन गुणाकार समस्या जिथे आम्हाला सर्व मॅट्रिकांच्या गुणाकारात गुंतलेली किमान ऑपरेशन शोधण्याची आवश्यकता होती. वापरून मॅट्रिक्स चेन गुणाकार डायनॅमिक प्रोग्रामिंग या समस्येसाठी एक पूर्व शर्त आहे. मॅट्रिक्स चेन गुणाकार समस्येमध्ये फक्त लहान बदल केल्याने कंस प्रिंट होऊ शकतात. आम्ही कंसात मॅट्रिक्स बनवितो, ज्यामध्ये कंस [i] [j] इष्टतम अनुक्रमणिका ठेवतो. इंडेक्स i, j च्या आधी व त्या नंतर निर्देशांकासाठी इष्टतम आहे, सर्व सीमेत [i, j] मधील मॅट्रिक्स गुणाकार आहेत. त्यानंतर त्यांचा परिणामी गुणाकार होतो जे आम्हाला आवश्यक ऑपरेशनची किमान संख्या देते. याचा अर्थ असा की आम्ही प्रथम इष्टतम निर्देशांक ते मॅट्रिक आणि इष्टतम अनुक्रमणिका + 1 ते जे पर्यंत मॅट्रिक आणि नंतर त्यांचे परिणाम एकत्रित करण्यासाठी निकाल शोधतो.

आम्ही मॅट्रिक्सच्या कंसात कंस मुद्रित करण्यासाठी कंसात वापरतो. आमच्याकडे एकच मॅट्रिक्स होईपर्यंत आणि नंतर प्रिंट होईपर्यंत आम्ही आमच्या समस्येला उप-समस्यांमधे विभाजित करतो.

मॅट्रिक्स चेन गुणाकार समस्येमध्ये कंस मुद्रित करणे

मॅट्रिक्स चेन गुणाकार समस्येमध्ये कंस मुद्रित करण्यासाठी कोड

सी ++ कोड

#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)

 

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी: ओ (एन ^ 3)

येथे आम्ही दोन पॉइंटर्स i आणि j विचारात घेत आहोत जे ओ (एन ^ 2) मध्ये चालणार्‍या मॅट्रिक्सच्या सीमांचे कार्य करीत आहेत. बाहेरील पळवाटांमधील नेस्टेड पळवाट स्वतः ओळीचा वेळ ओ (एन) घेते. त्यामुळे अल्गोरिदम चालू होतो ओ (एन ^ 3) एकूण.

स्पेस कॉम्प्लेक्सिटी: ओ (एन ^ 2)

आमच्याकडे बहुपक्षीय जागेची जटिलता आहे ओ (एन ^ 2) कारण आपल्याकडे 2D DP अ‍ॅरे आहे.