הדפסת סוגריים בבעיית כפל שרשרת מטריקס


רמת קושי קשה
נשאל לעתים קרובות אמזון בעברית אבלארה מצודה דאטבריקס דירקטי 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 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). אז זה גורם לאלגוריתם לרוץ פנימה O (N ^ 3) בסך הכל.

מורכבות שטח: O (N ^ 2)

יש לנו מורכבות שטח פולינומית של O (N ^ 2) כי יש לנו מערך DP 2D.