यदि मैट्रिक्स की एक चेन दी गई है, तो हमें मैट्रिक्स को मल्टीप्लाई करने के लिए सही क्रम की न्यूनतम संख्या ढूंढनी होगी।
हम जानते हैं कि मैट्रिक्स मल्टीप्लिकेशन एसोसिएटिव है, इसलिए चार मैट्रिक्स ABCD के लिए, हम A(BCD), (AB)(CD), (ABC)D, A(BC)D जैसे क्रम में मल्टीप्लाई कर सकते हैं। इन क्रमों की तरह, हमारा कार्य यह ढूंढना है कि कौन सा क्रम मल्टीप्लाई करने के लिए कुशल है।
दिए गए इनपुट में एक ऐरे है जैसे arr, जिसमें arr[] = {1, 2, 3, 4} है। इसका मतलब है कि मैट्रिक्स (1 x 2), (2 x 3), (3 x 4) के ऑर्डर के हैं।
इनपुट - इनपुट मैट्रिक्स के ऑर्डर। {1, 2, 3, 4}। इसका मतलब है मैट्रिक्स हैं
{(1 x 2), (2 x 3), (3 x 4)}.आउटपुट - इन तीन मैट्रिक्स को मल्टीप्लाई करने के लिए आवश्यक न्यूनतम ऑपरेशन्स की संख्या। यहां परिणाम 18 है।
एल्गोरिदम
matOrder(array, n) इनपुट: मैट्रिक्स की सूची, सूची में मैट्रिक्स की संख्या। आउटपुट: न्यूनतम मैट्रिक्स मल्टीप्लिकेशन की संख्या। Begin साइज n x n की टेबल minMul डिफाइन करें, शुरू में सभी 0s से भरें length := 2 से n तक, करें i:=1 से n-length तक, करें j := i + length – 1 minMul[i, j] := ∞ k := i से j-1 तक, करें q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j] यदि q < minMul[i, j], तो minMul[i, j] := q done done done return minMul[1, n-1] End
उदाहरण
#include<iostream> using namespace std; int matOrder(int array[], int n){ int minMul[n][n]; //स्केलर मल्टीप्लिकेशन की संख्या रखता है for (int i=1; i<n; i++) minMul[i][i] = 0; //1 मैट्रिक्स से मल्टीप्लिकेशन के लिए कॉस्ट 0 for (int length=2; length<n; length++){ //चेन लंबाई 2 से शुरू करके ढूंढें for (int i=1; i<n-length+1; i++){ int j = i+length-1; minMul[i][j] = INT_MAX; //इनफिनिटी पर सेट करें for (int k=i; k<=j-1; k++){ //प्रति मल्टीप्लिकेशन कॉस्ट स्टोर करें int q = minMul[i][k] + minMul[k+1][j] + array[i-1]*array[k]*array[j]; if (q < minMul[i][j]) minMul[i][j] = q; } } } return minMul[1][n-1]; } int main(){ int arr[] = {1, 2, 3, 4}; int size = 4; cout << "Minimum number of matrix multiplications: "<<matOrder(arr, size); }आउटपुट
Minimum number of matrix multiplications: 18
