Dinamik Proqramlaşdırma istifadə edərək Matris Zəncirinin Çarpılması

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon microsoft
Geyim Dinamik proqramlaşdırma MatrisBaxılıb 81

Matris Zəncirinin vurulması tapdığımız bir üsuldur ən yaxşı yolu verilmiş matrisləri çoxaltmaq. Matris vurmağın hamısı olduğunu bilirik assosiativ (A * B = B * A) təbiətdə. Beləliklə, vurma əmrini yerinə yetirmək istədiyimiz bir çox sifariş var. Əslində bu alqoritmdə bütün matrislərin vurulmasından sonra son matrisə rast gəlmirik. Burada matris vurma üçün ən səmərəli yolu tapırıq. 30 * 35, 35 * 15, 15 * 5, 5 * 10, 10 * 20, 20 * 25 sıra matrislərinin vurulmasına baxaq.

Biz istifadə  Dinamik proqramlaşdırma matrisləri çoxaltmaq üçün ən yaxşı yolu tapmaq üçün yanaşma.

Dinamik Proqramlaşdırma istifadə edərək Matris Zəncirinin Çarpılması

Matris Zəncirinin vurulması - Əvvəlcə hər hüceyrənin dəyərini tapmaq üçün istifadə olunan formulu təyin edirik. M [i, j] A (i… k) və A (k + 1… j) alt məhsullarını hesablamaq üçün minimum xərclə üstəlik bu iki matrisin birlikdə vurma xərcinə bərabərdir.

Matris Zəncirinin vurulmasıPin

Step-1

İ = j-nin bütün dəyərləri üçün 0 qoyulur.

Matris Zəncirinin vurulmasıPin

Step-2

M [1,2] = 30 * 35 * 15 = 15750, M [2,3] = 35 * 15 * 5 = 2625, M [3,4] = 15 * 5 * 10 = 750, M [4,5 ] = 5 * 10 * 20 = 1000, M [5,6] = 10 * 20 * 25 = 5000.

Pin

Step-3

M [1,3] = MIN ((M [1,1] + M [2,3] + P0P1P3), (M [1,2] + M [3,3] + P0P2P3)) = MIN (2625+) 30 * 35 * 5, 15750 + 35 * 15 * 5) = 7875, M [2,4] = MIN ((M [2,2] + M [3,4] + P1P2P4), (M [2,3) ] + M [4,4] + P1P3P4)) = MIN (750 + 35 * 15 * 10, 2625 + 35 * 5 * 10) = 4374, eyni konsepsiyadan istifadə edərək yuxarıdakı düsturdan sonra digər dəyərləri tapın M [3,5, 2500] = 4,6 və M [3500] = XNUMX.

Sonra matrisdəki yenilənmiş dəyərlər belədir:

Pin

Step-4

İndi müzakirə etdiyimiz yuxarıdakı düsturdan istifadə edərək j = i + 3 üçün dəyərləri tapın. Sonra son matris olacaq:

Matris Zəncirinin vurulmasıPin

Step-5

İndi müzakirə etdiyimiz yuxarıdakı düsturdan istifadə edərək j = i + 4 üçün dəyərləri tapın. Sonra son matris belə olacaq:

Matris Zəncirinin vurulmasıPin

Step-6

Son addım dəyərində müzakirə etdiyimiz yuxarıdakı düsturdan istifadə edərək j = i + 5. Sonra son matris belə olacaq:

Pin

Beləliklə, tələb olunan minimum əməliyyat sayını tapırıq 15125 matrislərin üstündə çoxaltmaq.

Üçün alqoritm Matris Zəncirinin vurulması

Step:1 Create a dp matrix and set all values with a big value(INFINITY).
Step:2 for i in range 1 to N-1:
       dp[i][i]=0.
Step:3 for i in range 2 to N-1:
            for j in range 1 to N-i+1:
                ran=i+j-1.
                for k in range i to j:
                    dp[j][ran]=min(dp[j][ran],dp[j][k]+dp[k+1][ran]+v[j-1]*v[k]*v[ran]).
Step:4 Print dp[1][N-1].

Həyata keçirilməsi

C ++ Proqramı Matris Zəncirinin vurulması

/*C++ Implementation of Matrix Chain Multiplication using DP.*/ 
#include<bits/stdc++.h> 
using namespace std; 
#define INF 1000000009
int min_operation(vector<int> &v, int n) 
{ 
    int dp[n+1][n+1];
    memset(dp,INF,sizeof(dp));
    /*if i=j then dp[i,j]=0.*/
    for(int i=1;i<n;i++)
    {
        dp[i][i]=0;
    }
    /*Find M[i,j] using the formula.*/
    int ran;
    for(int i=2;i<n;i++) 
    { 
        for(int j=1;j<n-i+1;j++) 
        { 
            ran=i+j-1; 
            for(int k=j;k<=ran-1;k++) 
            { 
                /*formula used here.*/
                dp[j][ran]=min(dp[j][ran],dp[j][k]+dp[k+1][ran]+v[j-1]*v[k]*v[ran]); 
            } 
        } 
    }
    /*return the answer.*/
    return dp[1][n-1]; 
}
int main() 
{
    /*input values.*/
    int n;
    /*number of matrices.*/
    cin>>n;
    /*sequence/chain of the matrices if there are n matrices then chain contain n+1 numbers.*/
    vector<int> chain;
    for(int i=0;i<n+1;i++)
    {
        int x;
        cin>>x;
        chain.push_back(x);
    }
    /*store the min operation needed to multiply all the given matrices in ans.*/
    int ans=min_operation(chain,n+1);
    /*print the result.*/
    cout<<ans<<endl;
    return 0;
}

Input

6
30 35 15 5 10 20 25

Buraxılış

Minimum number of operation used are: 15125

Matris Zəncirinin Çarpılması üçün Zaman Mürəkkəbliyi

O (N * N * N) burada N - matrislər zəncirində mövcud olan rəqəmdir. Bildiyimiz kimi minimum əməliyyatları tapmaq üçün N * N matrisindən istifadə edirik. İ <= k <= j olduğu bütün k dəyərlər üçün minimum dəyəri tapmaq lazımdır. Beləliklə, ümumilikdə loop üçün 3 iç içə istifadə edirik.

Kosmik Mürəkkəblik

O (N * N) burada N - matrislər zəncirində mövcud olan rəqəmdir. Hər əməliyyatdan sonra nəticələri saxlayan bir DP matrisi yaradırıq.

References

Translate »