इस समस्या में, हमें मैट्रिक्स का एक अनुक्रम (सरणी) दिया गया है। हमारा कार्य मैट्रिक्स चेन गुणन के लिए 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 MatrixChainMultiplication(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("मैट्रिक्स गुणन के लिए आवश्यक न्यूनतम गुणन की संख्या %d है", MatrixChainMultiplication(arr, size)); getchar(); return 0; } आउटपुट
मैट्रिक्स गुणन के लिए आवश्यक न्यूनतम गुणन की संख्या 444 है
