資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究矩陣鏈乘法（C++ 中的 O(N^3) 解決方案）
如果給定一個矩陣鏈，我們必須找到乘以正確順序的最少矩陣數。
我們知道矩陣乘法是關聯的，所以對於四個矩陣 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) Input: List of matrices, the number of matrices in the list. Output: Minimum number of matrix multiplication. 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
更新於： 2019 年 9 月 25 日
3 千多次瀏覽
廣告