การคูณลูกโซ่เมทริกซ์

ถ้าให้ลูกโซ่ของเมทริกซ์ เราต้องหาจำนวนขั้นต่ำของลำดับที่ถูกต้องของเมทริกซ์เพื่อคูณ

เรารู้ว่าการคูณเมทริกซ์สัมพันธ์กัน ดังนั้นเมทริกซ์สี่ตัว ABCD เราจึงสามารถคูณ A(BCD), (AB)(CD), (ABC)D, A(BC)D ได้ในลำดับเหล่านี้ เช่นเดียวกับลำดับเหล่านี้ งานของเราคือค้นหาว่าลำดับใดมีประสิทธิภาพในการเพิ่มจำนวน

ในอินพุตที่กำหนดจะมีอาร์เรย์ say arr ซึ่งมี arr[] ={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