動態規劃_備忘錄法_矩陣鏈乘問題

• 2021 年 7 月 10 日
• 筆記
• 演算法

問題描述

給定\(n\)個矩陣\(\{A_1,A_2,A_3,…,A_n\}\)，其中\(A_i\)為\(P_{i-1}\times P_i\)矩陣，\(i = 1,…,n\)，並且\(A_i\)與\(A_{i-1}\)是可乘的。由於矩陣乘法滿足結合律，所以計算矩陣的鏈乘可有許多不同的計算次序，兩個矩陣\(A_{i\times j}\)與\(A_{j\times k}\)相乘的工作量為\(i\times j\times k\)次數乘。
給定向量\(P=<P_0,P_1,…,P_n>\)為\(n\)個矩陣的行數和列數，確定一種乘法次序，使得基本運算「數乘」的總次數最少。

完全加括弧

完全加括弧的矩陣鏈乘積可遞歸地定義為：

• 單個矩陣是完全加括弧的
• 矩陣鏈乘積\(A\)是完全加括弧的，則\(A\)可表示為兩個完全加括弧的矩陣鏈乘積\(B\)和\(C\)的乘積，並加括弧，即\(A=(BC)\)

最優子結構

• 矩陣鏈乘\(A_iA_{i+1}…A_j\)簡記為\(A_{i…j},i\leq j\)，於是矩陣鏈乘\(A_1A_2…A_n\)可記為\(A_{1…n}\)，完全加括弧形式為\(A_{1…n}=A_{1…k}A_{k+1…n},1\leq k < n\)
• 矩陣連乘\(A_{1…n}\)的最優計算次序的計算量等於\(A_{1…k}\)和\(A_{k+1…n}\)兩者的最優計算次序的計算量之和，再加上\(A_{1…k}\)和\(A_{k+1…n}\)相乘的計算量。矩陣鏈乘問題的最優解具有最優子結構特性。

最優解的遞推關係

• 由\(i\)和\(j\)確定子問題的邊界，輸入\(P=<P_0,P_1,…P_n>\)

• 確定優化函數和遞推方程：二維數組\(m\)用來保存矩陣鏈乘時所需的最小計算量

• 設立標記函數：為了確定加括弧的次序，設計表\(s[i,j]\)記錄求得最優時，最後一次運算的位置，即\(m[i][j]\)達到最小時\(k\)的劃分。

演算法描述（偽程式碼）

• 迭代實現 備忘錄法

MatrixChain(P,n)
	令所有m[i,j]的初值為0；
	for r <- 2 to n   do
		for i <- 1 to n-r+1  do
			j <- i+r-1;
			m[i,j] <- m[i+1,j]+P_i-1P_iP_j;
			s[i,j] = i;
			for k <- i+1 to j-1  do
				t <- m[i,k]+m[k+1,j]+P_i-1P_kP_j;
				if t < m[i,j]
					then m[i,j] <- t;
						 s[i,j] <- k;

結束語

醉後不知天在水，滿船清夢壓星河

作者：花城