Matris Zəncirinin Çarpılması Problemində mötərizələrin çap edilməsi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Avalara Citadel Verilənlər bazası Directi JP Morgan Paytm Twilio
Geyim Dinamik proqramlaşdırma MatrisBaxılıb 83

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Matrislərin vurma qaydasını elə tapmaq lazımdır ki, bütün matrislərin vurulmasında iştirak edən əməliyyatların sayı minimuma endirilsin. Sonra bu əmri, yəni matris zənciri vurma problemində mötərizəni çap etməliyik.

Müvafiq olaraq axb, bxc, c xd ölçülü 3 A, B, C matrisiniz olduğunu düşünün. Matrisləri çoxaltmaq üçün iki hal mövcuddur. Ya əvvəlcə A və B, sonra C, ya da əvvəlcə B və C, sonra A-ya vururuq. İlk seçim (axbxc + axcxd) maliyyəti ilə nəticələnir, ikinci seçim isə cəmi (bxcxd + axbxd) əməliyyatları alır. İştirak olunan əməliyyatların sayının matrislərin vurma qaydasından asılı olduğunu görə bilərik. Beləliklə, minimum əməliyyat sayı ilə nəticələnən matrislərin vurma qaydasını tapmalıyıq. 

misal

number of matrices = 3

Dimensions of matrices = {1, 2, 3, 4}
((AB)C)

 

Explanation: Əvvəlcə 1 əməliyyatın dəyərini alan 2 x 2 və 3 x 6 ölçüləri ilə matrisləri çoxaldırıq. Daha sonra A və B-nin vurulmasından alınan matris ilə C matrisini çoxaldırıq. Bu əməliyyat yenidən 1 əməliyyat olmaqla 3 x 4 x 18 çəkir.

number of matrices = 2

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

Explanation: Yalnız iki matris olduğundan, ümumilikdə 2000 əməliyyat aparan matrisləri vurmağın tək bir yolu var.

Matris zənciri vurma problemində mötərizələrin çapına yanaşma

Artıq həll etdik Matris Zəncirinin Çarpılması problemi burada bütün matrislərin vurulmasında iştirak edən minimum əməliyyat sayını tapmaq lazım idi. Matrix Zəncir vurma istifadə dinamik proqramlaşdırma bu problem üçün bir şərtdir. Matris zəncirinin vurulması problemində yalnız kiçik dəyişikliklər edilməsi mötərizələri çap edə bilər. Mötərizədə [i] [j] -də optimal göstəricini saxladığı mötərizə matrisi düzəldirik. İndeks i, j indeksləri üçün optimaldır, bundan əvvəl və sonra sərhəddəki [i, j] bütün matrislər vurulursa. Bundan sonra onların nəticəsi vurulur və bu da bizə tələb olunan minimum əməliyyat sayını verir. Bu, sadəcə əvvəlcə matrislər i-dən optimal indeksə və matrisləri optimal göstəricidən + 1-dən j-yə tapdığımızdan sonra nəticələrini birləşdirdiyimiz deməkdir.

Matrisin ətrafındakı mötərizələri çap etmək üçün mötərizələr matrisindən istifadə edirik. Tək bir matrisə sahib çıxana qədər problemimizi alt problemlərə bölməyə davam edirik və sonra çap edirik.

Matris Zəncirinin Çarpılması Problemində mötərizələrin çap edilməsiPin

Matrix Zənciri Çarpma problemində mötərizələrin çapı üçün kod

C ++ kodu

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

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)

 

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (N ^ 3)

Burada O (N ^ 2) -də işləyən matrislər üçün sərhəd rolunu oynayan iki i və j göstəricisini nəzərdən keçiririk. Xarici döngələrin içərisindəki iç içə döngə O (N) xətti vaxt alır. Beləliklə, alqoritmi işə salır O (N ^ 3) Toplam.

Kosmik Mürəkkəblik: O (N ^ 2)

Polinom boşluğu mürəkkəbliyinə sahibik O (N ^ 2) çünki 2D DP sıra var.

Crack Sistemi Dizayn Müsahibələri
Translate »