मैट्रिक्स श्रृंखला गुणन

यदि आव्यूहों की एक श्रृंखला दी गई है, तो हमें गुणा करने के लिए आव्यूहों के सही अनुक्रम की न्यूनतम संख्या ज्ञात करनी होगी।

हम जानते हैं कि मैट्रिक्स गुणा सहयोगी है, इसलिए चार मैट्रिक्स एबीसीडी, हम इन अनुक्रमों में ए (बीसीडी), (एबी) (सीडी), (एबीसी) डी, ए (बीसी) डी गुणा कर सकते हैं। इन अनुक्रमों की तरह, हमारा कार्य यह पता लगाना है कि कौन सा क्रम गुणा करने के लिए कुशल है।

दिए गए इनपुट में एआर कहते हैं कि एक सरणी है, जिसमें एआर [] ={1, 2, 3, 4} शामिल है। इसका मतलब है कि मैट्रिक्स (1 x 2), (2 x 3), (3 x 4) क्रम के हैं।

इनपुट और आउटपुट

Input:
The orders of the input matrices. {1, 2, 3, 4}. It means the matrices are
{(1 x 2), (2 x 3), (3 x 4)}.
Output:
Minimum number of operations need multiply these three matrices. Here the result is 18.

एल्गोरिदम

matOrder(array, n)

इनपुट - मेट्रिसेस की सूची, सूची में मेट्रिसेस की संख्या।

आउटपुट - मैट्रिक्स गुणन की न्यूनतम संख्या।

Begin
   define table minMul of size n x n, initially fill with all 0s
   for length := 2 to n, do
      fir i:=1 to n-length, do
         j := i + length – 1
         minMul[i, j] := ∞
         for k := i to j-1, do
            q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
            if q < minMul[i, j], then 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];          //holds the number of scalar multiplication needed

   for (int i=1; i<n; i++)
      minMul[i][i] = 0;           //for multiplication with 1 matrix, cost is 0

   for (int length=2; length<n; length++) {        //find the chain length starting from 2
      for (int i=1; i<n-length+1; i++) {
         int j = i+length-1;
         minMul[i][j] = INT_MAX;     //set to infinity
         for (int k=i; k<=j-1; k++) {
            //store cost per multiplications
            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