Матрицалық тізбекті көбейту


Күрделілік дәрежесі орта
Жиі кіреді Amazon CodeNation DE Шоу Google Microsoft қиятын
Array Динамикалық бағдарламалау Matrix

Матрицалық тізбекті көбейтудің II есебінде біз матрицалардың өлшемдерін келтірдік, оларды көбейтудің ретін барлық матрицаларды көбейтуге қатысатын амалдар саны азайтылатындай етіп табыңыз.

Сізде сәйкесінше axb, bxc, c xd 3 A, B, C матрицалары бар деп есептеңіз. Содан кейін, егер біз алдымен A және B матрицаларын көбейтіп, олардың нәтижесін C-ге көбейтсек, бұл жалпы операцияны алады (axbxc + axcxd). Егер матрицаларды көбейту ретін өзгертсек. Алдымен біз В және С матрицаларын көбейтеміз, содан кейін олардың нәтижесін А-ға көбейтеміз. Бұл жалпы амал (bxcxd + axbxd) болады. Бұл матрицаларда көбейту тәртібі өзгерген болса, бұл орындалатын амалдардың санына әсер ететіндігін көрсетеді. Осылайша, біз барлық берілген матрицаларды көбейту үшін жасалатын минималды жұмыс санын табуымыз керек.

мысал

Input: number of matrices = 3

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

Output: 18

Түсіндіру: Алдымен біз 1 операцияның құнын алатын 2 x 2 және 3 x 6 өлшемді матрицаларды көбейтеміз. Содан кейін А және В көбейтінділерінен алынған матрицамен С матрицасын көбейтеміз. Бұл амал тағы 1 х 3 х 4 алады, барлығы 18 амал жасайды.

Input: number of matrices = 2

Dimensions of matrices = {10, 10, 20}

Output: 2000

Түсіндіру: Тек екі матрица болғандықтан, барлығы 2000 операцияны алатын матрицаларды көбейтудің жалғыз әдісі бар.

Матрицалық тізбекті көбейту тәсілі

Матрицаны көбейту мәселесі - көптеген стандарттардың бірі Динамикалық бағдарламалау мәселелер. Біз тек матрицаларды көбейтудің барлық тәсілдерін қолданатын рекурсивті тәсіл туралы ойлауға болады. Біз барлық келісімдерге қатысатын жалпы шығынды табамыз және барлық келісімдерден минимумды аламыз. Рекурсивті шешім бізге дұрыс нәтиже береді, бірақ тиімділігі жеткіліксіз. Бізде рекурсивті шешім болған сайын және қайталанатын ішкі проблемалар болады. Кішігірім ішкі проблемалардың нәтижелерін сақтауға, содан кейін нәтижелерді біріктіріп, алғашқы мәселені шешуге мүмкіндік бар. Бұл мәселеде біз оларды қолданған сайын есептелетін қайталанатын ішкі проблемалар бар. Демек, егер біз олардың нәтижесін dp кестесінде немесе сақтасақ, тиімдірек болады массив.

Матрицалық тізбекті көбейтудегі қайталанатын ішкі есептер

Біз алдымен мәселені жалғызға шешеміз Матрица, бұл 0 операцияны қажет етеді. Бір матрицалар үшін шешкеннен кейін біз 2 матрица үшін шешеміз, содан кейін 3 және т.с.с. Жалпы жағдайда матрицалар үшін есептерді i индексінен j-ге дейін шешу керек деп есептейміз. Біз проблемаларды төменнен жоғары қарай шешіп жатқандықтан. Біз матрицалардан j-ге дейінгі матрицалар үшін j-1, j-2 және т.б матрицалар үшін есептің нәтижесін есептедік. Осылайша, мұны шешу үшін біз біріншіден бастап матрицалар үшін есеп шығарамыз деп есептейміз. 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

Матрицалық тізбекті көбейтуге арналған Java коды

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)

Мұнда O (N ^ 2) матрицалар үшін шекара болатын i және j екі көрсеткішті қарастырамыз. Сыртқы ілмектердің ішіне салынған цикл O (N) сызықтық уақытты алады. Сонымен, алгоритм жалпы O (N ^ 3) мәнінде жұмыс істейді.

Ғарыштың күрделілігі: O (N ^ 2)

Біз өлшемдері N x N болатын 2D dp массивін қолданғандықтан, оны O (N ^ 2) құрайды.

Әдебиеттер тізімі