ถ้าให้โซ่ของเมทริกซ์ เราต้องหาจำนวนการคูณน้อยที่สุดของลำดับเมทริกซ์ที่ถูกต้อง
เรารู้ว่าการคูณเมทริกซ์มีสมบัติ associative ดังนั้นเมทริกซ์ 4 ตัว ABCD เราสามารถคูณเป็น A(BCD), (AB)(CD), (ABC)D, A(BC)D ฯลฯ งานของเราคือหาลำดับที่มีประสิทธิภาพสูงสุด
ในอินพุตมีอาร์เรย์ arr[] = {1, 2, 3, 4} หมายถึงเมทริกซ์มีออเดอร์ (1x2), (2x3), (3x4)
อินพุต − ออเดอร์ของเมทริกซ์ {1, 2, 3, 4} หมายถึงเมทริกซ์คือ {(1 x 2), (2 x 3), (3 x 4)}
เอาต์พุต − จำนวนการดำเนินการน้อยที่สุดในการคูณเมทริกซ์ 3 ตัวนี้ คือ 18
อัลกอริทึม
matOrder(array, n) Input: รายการเมทริกซ์ จำนวนเมทริกซ์ Output: จำนวนการคูณเมทริกซ์น้อยที่สุด Begin define table minMul of size n x n, initially fill with all 0s for length := 2 to n, do for 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
