इस समस्या में, हमें मेट्रिक्स का अनुक्रम (सरणी) दिया जाता है। हमारा काम मैट्रिक्स श्रृंखला गुणन के लिए एक C प्रोग्राम बनाना है . हमें इन मैट्रिक्स को गुणा करने का एक तरीका खोजने की जरूरत है ताकि, गुणा की न्यूनतम संख्या की आवश्यकता हो।
मैट्रिक्स की सरणी में n तत्व होंगे, जो मैट्रिक्स के आयामों को परिभाषित करते हैं, arr[i-1] X arr[i] ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
array[] = {3, 4, 5, 6} आउटपुट
स्पष्टीकरण
मैट्रिक्स क्रम के होंगे -
Mat1 = 3X4, Mat2 = 4X5, Mat3 = 5X6
इन तीन आव्यूहों के लिए, गुणा करने के दो तरीके हो सकते हैं,
mat1*(mat2*mat3) -> (3*4*6) + (4*5*6) = 72 + 120 = 192 (mat1*mat2)*mat3 -> (3*4*5) + (3*5*6) = 60 + 90 = 150
(mat1*mat2)*mat3 के मामले में गुणन की न्यूनतम संख्या 150 होगी।
डायनेमिक प्रोग्रामिंग का उपयोग करके समस्या को हल किया जा सकता है क्योंकि इसमें डायनेमिक प्रोग्रामिंग में इष्टतम सबस्ट्रक्चर और ओवरलैपिंग सबस्ट्रक्चर दोनों गुण होते हैं।
तो यहाँ है डायनामिक प्रोग्रामिंग का उपयोग करके मैट्रिक्स श्रृंखला गुणन के लिए C प्रोग्राम
उदाहरण
#include <stdio.h>
int MatrixChainMultuplication(int arr[], int n) {
int minMul[n][n];
int j, q;
for (int i = 1; i < n; i++)
minMul[i][i] = 0;
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
j = i + L - 1;
minMul[i][j] = 99999999;
for (int k = i; k <= j - 1; k++) {
q = minMul[i][k] + minMul[k + 1][j] + arr[i - 1] * arr[k] * arr[j];
if (q < minMul[i][j])
minMul[i][j] = q;
}
}
}
return minMul[1][n - 1];
}
int main(){
int arr[] = {3, 4, 5, 6, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications required for the matrices multiplication is %d ", MatrixChainMultuplication(arr, size));
getchar();
return 0;
} आउटपुट
Minimum number of multiplications required for the matrices multiplication is 444