1.引言 多矩陣連乘
對于一般的矩陣乘法來說,如矩陣A(m,n)與矩陣B(n,p)相乘需要進行的加法次數為m*n*p次乘法。
由于矩陣乘法滿足結合律,是以矩陣相乘的結合性,會影響整個計算表達式的乘法執行次數。
如下面的例子,其中A(10,5)、B(5,20)、C(20,3):
(1) ((AB)C) 執行乘法次數為1300次
(2) (A(BC)) 執行乘法次數為450次
2.求最優的矩陣結合表達式
(1)設矩陣連乘積AiAi+1…Aj簡記為A[i:j],設最優計算次序在Ak和Ak+1之間斷開,則加括号方式為:
((AiAi+1…Ak) (Ak+1…Aj) )
則依照這個次序,先計算A[i:k]和A[k+1:j]然後再将計算結果相乘,計算量是:
A[i:k]的計算量+A[K+1:j]的計算量+它們兩者相乘的計算量
這裡的關鍵是:計算A[i:j]的最優次序所包含的兩個子過程(計算A[i:k]和A[K+1:j])也是最優次序
(2)具體計算
設計算A[i,j]需要的乘法次數記為m[i,j]。
M[i,j] = 0; (i == j,表示一個矩陣,當然不需要乘法運算)
M[i,j] = min(M[i,k]+M[k+1,j]+pi*pk*pj); (k在[i,j)之間取值,表示分割點的位置,求最适合的分割點使得乘法次數最少)
下面是使用動态規劃計算6個矩陣連乘的示意圖。可以使用自底向上計算,這樣矩陣的分割點好計算。如先計算01兩個矩陣乘積,在計算02三個矩陣乘積,在計算03四個矩陣乘積:
01 12 23 34 45
02 13 24 35
03 14 25
04 15
05
3.程式執行個體
程式可以根據給出的多個矩陣的行、列,生成最優結合的相乘表達式。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIml2ZuUWYxYmZhR2MiNjY3QGMjFGZlNTOzUWZjJGO2YzM1MWMfdWbp9CXt92Yu4GZjlGbh5SZslmZxl3Lc9CX6MHc0RHaiojIsJye.gif)
View Code
輸入矩陣,表示每個矩陣的行、列:
輸出最優的結合表達式: