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.
Mündəricat
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.
Step-1
İ = j-nin bütün dəyərləri üçün 0 qoyulur.
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.
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:
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:
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:
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:
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.
