मैट्रिक्स चेन मल्टीप्लिकेशन

यदि मैट्रिक्स की एक चेन दी गई है, तो हमें मैट्रिक्स को गुणा करने के सही क्रम के लिए न्यूनतम संख्या ढूंढनी है।

हम जानते हैं कि मैट्रिक्स गुणन साहचर्य है, इसलिए चार मैट्रिक्स ABCD के लिए, हम A(BCD), (AB)(CD), (ABC)D, A(BC)D जैसे क्रम में गुणा कर सकते हैं। इन क्रमों की तरह, हमारा कार्य यह ढूंढना है कि कौन सा क्रम गुणा करने के लिए कुशल है।

दिए गए इनपुट में एक ऐरे है, मान लें 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)

इनपुट: मैट्रिक्स की सूची, सूची में मैट्रिक्स की संख्या
आउटपुट: न्यूनतम मैट्रिक्स गुणन संख्या

शुरुआत
    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
            पूर्ण
        पूर्ण
    पूर्ण
    वापस minMul[1, n-1]
अंत

उदाहरण (C++ कोड)

#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;
    
    for (int length = 2; length < n; length++) {
        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