ფრჩხილების ბეჭდვა მატრიცის ჯაჭვის გამრავლების პრობლემაში  


Რთული ტური Hard
ხშირად ეკითხებიან Amazon ავალარა ციხედ მონაცემთა ბაზები დირექტი JP Morgan Paytm Twilio
Array დინამიური პროგრამირება Matrix

პრობლემის განცხადება  

უნდა ვიპოვოთ მატრიცების გამრავლების ისეთი რიგი, რომ ყველა მატრიცის გამრავლებაში ჩართული ოპერაციების რაოდენობა შემცირდეს. შემდეგ ჩვენ უნდა დავაბეჭდოთ ეს შეკვეთა, ანუ ბეჭდვის ფრჩხილები მატრიცული ჯაჭვის გამრავლების პრობლემაში.

გაითვალისწინეთ, რომ გაქვთ 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] საზღვარში არსებული ყველა მატრიცა გამრავლებულია. ამის შემდეგ მათი შედეგი მრავლდება, რაც ოპერაციების მინიმალურ რაოდენობას გვაძლევს. ეს მხოლოდ იმას ნიშნავს, რომ პირველ რიგში ვიპოვით შედეგს მატრიცების ოპტიმალურ ინდექსამდე და მატრიცებს ოპტიმალური ინდექსიდან + 1-დან j და შემდეგ გავაერთიანებთ მათ შედეგს.

ჩვენ ვიყენებთ ფრჩხილების მატრიცას მატრიცის გარშემო ფრჩხილების დასაბეჭდად. ჩვენ ვაგრძელებთ ჩვენი პრობლემის დაყოფას ქვე-პრობლემებად, სანამ არ გვექნება ერთი მატრიცა და შემდეგ არ ვბეჭდავთ მას.

ფრჩხილების ბეჭდვა მატრიცის ჯაჭვის გამრავლების პრობლემაშიPin

მატრიცის ჯაჭვის გამრავლების პრობლემაში ფრჩხილების დასაბეჭდი კოდი  

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)

 

იხილეთ ასევე
K მაქსიმალური თანხები, რომლებიც გადაფარავს მომიჯნავე ქვე-მასივებს

სირთულის ანალიზი  

დროის სირთულე: O (N ^ 3)

აქ განვიხილავთ ორ და j მაჩვენებლებს, რომლებიც მოქმედებენ O (N ^ 2) მატრიცების საზღვრებად. გარე მარყუჟების შიგნით ჩასმული მარყუჟი იღებს ხაზოვან დროს O (N). ასე რომ, ის ალგორითმს მუშაობს O (N ^ 3) მთლიანობაში.

სივრცის სირთულე: O (N ^ 2)

ჩვენ გვაქვს პოლინომური სივრცის სირთულე O (N ^ 2) რადგან ჩვენ გვაქვს 2D DP მასივი.