ضرب ماتریس زنجیره ای


سطح دشواری متوسط
اغلب در آمازون CodeNation دی شاو گوگل مایکروسافت حال بارگذاری
صف برنامه نویسی پویا ماتریس

در مسئله ضرب زنجیره ماتریس II ، ما ابعاد ماتریس ها را داده ایم ، ترتیب ضرب آنها را به گونه ای پیدا کنید که تعداد عملیات مربوط به ضرب همه ماتریس ها به حداقل برسد.

در نظر بگیرید که به ترتیب 3 ماتریس A ، B ، C به ترتیب axb ، bxc ، c xd دارید. سپس ، اگر ابتدا ماتریس های A و B را ضرب کرده و نتیجه آنها را با C ضرب کنیم ، این عمل کل طول خواهد کشید (axbxc + axcxd). اگر ترتیب ضرب ماتریس ها را تغییر دهیم. ابتدا ماتریس های B و C را ضرب می کنیم و سپس نتیجه آنها را با A ضرب می کنیم. این عمل کل طول خواهد کشید (bxcxd + axbxd). این نشان می دهد که اگر ترتیب ضرب در ماتریس تغییر کند ، این بر تعداد عملیات انجام شده تأثیر می گذارد. بنابراین ، ما باید حداقل تعداد عملیاتی را که می توان برای ضرب کردن تمام ماتریس های داده شده انجام داد ، پیدا کنیم.

مثال

Input: number of matrices = 3

Dimensions of matrices = {1, 2, 3, 4}

Output: 18

شرح: ابتدا ماتریس هایی را با ابعاد 1 2 2 و 3 6 1 ضرب می کنیم که هزینه 3 عملیات را می گیرد. سپس ما ماتریس C را با ماتریس حاصل از ضرب A و B ضرب می کنیم. این عمل دوباره 4 18 XNUMX XNUMX XNUMX طول می کشد و در مجموع XNUMX عمل انجام می شود.

Input: number of matrices = 2

Dimensions of matrices = {10, 10, 20}

Output: 2000

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

رویکرد برای ضرب زنجیره ماتریس

مسئله ضرب ماتریس یکی از بسیاری از موارد استاندارد است برنامه نویسی پویا چالش ها و مسائل. ما می توانیم به سادگی به یک روش بازگشتی فکر کنیم که همه روش های ضرب ماتریس ها را امتحان کنیم. ما هزینه کل مربوط به همه تنظیمات را پیدا می کنیم و حداقل آن را از همه ترتیبات می گیریم. راه حل بازگشتی قطعاً نتیجه صحیحی به ما می دهد اما به اندازه کافی کارآمد نیست. هر زمان که ما یک راه حل بازگشتی داشته باشیم ، و با مشکلات زیر هم تداخل داشته باشیم. امکان ذخیره نتیجه زیرمشکلات کوچکتر و سپس ترکیب این نتایج برای حل مشکل اولیه وجود دارد. این مشکل دارای زیر مشکلی است که با هر بار استفاده از آنها محاسبه می شود. از این رو ، اگر نتایج آنها را در جدول dp یا صف.

مشكلات فرعی همپوشانی در ضرب زنجیره ماتریس

ابتدا مشکل را برای یک تک حل خواهیم کرد ماتریس، که 0 عملیات هزینه خواهد داشت. پس از حل برای ماتریس های منفرد ، ما برای 2 ماتریس ، سپس برای 3 و غیره حل می کنیم. در یک حالت کلی ، در نظر بگیرید که ما باید برای ماتریس ها از شاخص i تا j حل کنیم. از آنجا که ما در حال حل مشکلات به روشی از پایین به بالا هستیم. وقتی ما برای ماتریس های i تا j حل می کنیم ، نتیجه یک مسئله با ماتریس های i تا j-1 ، j-2 و غیره را محاسبه کرده ایم. بنابراین ، برای حل این مسئله در نظر می گیریم که ابتدا برای مسئله ماتریس ها از i به k ، و مشکل برای ماتریس های k + 1 تا j. سپس حداقل تمام این مقادیر را بگیرید.

C ++ کد برای ضرب زنجیره ماتریس

#include <bits/stdc++.h>
using namespace std;

int 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;
        }
    }

    // start solving problem for 2 matrices, then 3, and so on.
    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++)
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]));
        }
    }

    return dp[0][numberOfMatrices-1];
}

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];
        cout<<matrixMultiplicationProblem(matrixSize)<<endl;
    }
}
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
26925 
68028

کد جاوا برای ضرب ماتریس زنجیره ای

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int 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;
            }
        }
    
        // start solving problem for 2 matrices, then 3, and so on.
        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++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]));
            }
        }
    
        return dp[0][numberOfMatrices-1];
    }

    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();
            int ans = matrixMultiplicationProblem(matrixSize);
            System.out.println(ans);
        }
    }

}
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
26925 
68028

تحلیل پیچیدگی

پیچیدگی زمان: O (N ^ 3)

در اینجا ، ما دو نشانگر i و j را در نظر می گیریم که به عنوان مرزهای ماتریس هایی که در O (N ^ 2) اجرا می شوند ، عمل می کنند. حلقه تو در تو درون حلقه های بیرونی خود زمان خطی O (N) را می گیرد. بنابراین ، الگوریتم در کل در O (N ^ 3) اجرا می شود.

پیچیدگی فضا: O (N ^ 2)

از آنجایی که ما از یک آرایه dd 2D استفاده کرده ایم که ابعاد آن N x N. است و این باعث می شود در مجموع O (N ^ 2) شود.

منابع