備忘錄方法和動態規劃算法在矩陣連乘問題中的應用

摘要：文章從算法思路、算法步驟、代碼實現、時間復雜度和空間復雜度幾個方面，介紹了備忘錄方法和動態規劃算法在矩陣連乘問題中的應用。指出了兩種算法的實現方式、計算順序、空間需求和適用場景的不同點，得出動態規劃算法和備忘錄方法都是解決優化問題的有效工具。

關鍵詞：矩陣連乘；備忘錄；動態規劃算法；優化問題

中圖分類號：TP301.6 文獻標識碼：A

文章編號：1009-3044（2025）02-0050-03 開放科學（資源服務） 標識碼（OSID） ：

1 矩陣連乘問題

矩陣連乘問題是指給定n 個矩陣A1，A2，...，An ，通過加括號來確定一種最優的計算順序，使得計算這些矩陣乘積所需的乘法次數最少[1]。矩陣乘法不滿足交換律，所以不同的計算順序會得到不同的結果。但矩陣乘法滿足結合律，對于三個矩陣 A、B、C，（A×B）×C = A×（B×C）。不同的計算順序在計算量上可能會有很大差異。例如，有三個矩陣A1 （p0×p1） 、A2 （p1×p2） 和 A3（p2× p3） ，不同的計算順序會導致不同的乘法次數。（A1 A2） A3的計算次數=p0×p1×p2+p0×p2×p3、A1（A2A3） 的計算次數= p1×p2×p3+p0×p1×p3。若A1（2×3）、A2（3×4）、A3（4×2），則（A1 A2） A3的計算次數=2×3×4+2×4×2=40，A1（A2A3） =3×4×2+2×3×2=36，所以A1（A2A3） 計算順序的計算次數最少。

矩陣連乘廣泛應用于圖形變換、神經網絡和數據降維等領域。在處理大規模矩陣連乘時，最小化計算次數能夠明顯減少乘法運算量。例如，在計算機圖形學中對3D 模型進行先旋轉再平移操作時，可以通過矩陣連乘來表示。假設有一個3D 模型，其頂點坐標用齊次坐標（x，y，z）表示，模型空間中的一個點P用齊次坐標表示為（x，y，z，1）。若對其進行繞z 軸旋轉α角度，則其旋轉矩陣Rz為：

然后考慮將其平移，沿x軸方向平移距離為tx，沿y 軸方向平移距離為ty，沿z軸方向平移距離為tz，則平移矩陣T 為：

則P 點經過先旋轉再平移得到的點P’=Rz×T×P[2]，如果能找到三個矩陣的最小計算次數的連乘順序，就可以大大縮短此3D模型渲染的時間。

2 動態規劃算法在矩陣連乘問題中的應用

2.1 算法定義

動態規劃（Dynamic Programming） 是一種用于解決具有重疊子問題和最優子結構性質問題的算法策略。它通過保存子問題的解來避免重復計算，從而提高算法的效率[3]。

最優子結構：一個問題的最優解可以由其子問題的最優解構建而成。例如，在計算斐波那契數列時，F[n]=F[n-1]+F[n-2]，這體現了最優子結構特性。

重疊子問題：解決問題時會多次遇到相同的子問題。以斐波那契數列為例，計算 F （n） 時會多次計算 F （n - 1）、F （n - 2） 等子問題，子問題的重復計算會導致效率低下，而動態規劃可以有效地解決這個問題。

動態規劃算法在資源分配、編輯距離問題、最長遞增子序列問題、矩陣鏈乘法問題、股票買賣問題等方面都有廣泛的應用。本文以矩陣鏈乘法為例，介紹動態規劃算法的具體應用。

2.2 算法思路

1） 定義狀態。用二維數組 m[i][j] 表示計算矩陣Ai 到Aj 的最少乘法次數。

2） 確定狀態轉移方程。將矩陣序列劃分為兩部分，即 Ai 到 Ak 和 Ak+1 到 Aj ， 則有： m[i][ j] =mini?k lt; j {m[i][k] + m[k + 1][ j] + pi - 1 pk }，其中pi - 1是矩陣Ai 的行數， pk 是矩陣 Ak+1 的行數，pj 是矩陣 Aj 的列數[3]。

3） 確定邊界條件。當 i=j 時，m[i][i]=0，即只有一個矩陣，因為一個矩陣自身不需要進行乘法運算。

4） 確定計算順序。按照矩陣鏈的長度從短到長進行計算。先計算長度為 2 的子問題，然后是長度為3 的子問題，以此類推，直到計算出整個矩陣鏈的最優解。

2.3 算法步驟

1） 使用一維數組p來存儲矩陣序列的維度信息，其中p0是第一個矩陣的行數， p1是第一個矩陣的列數，同時也是第二個矩陣的行數，以此類推。

2） 創建二維數組 m，用于存儲子問題的最優解。初始化m[i][i]=0，對于所有的i。

3） 計算長度為 2 的矩陣相乘，即m[i][i+1]，對于i=1，2，...，n-1 。

4） 逐步增加矩陣鏈的長度3=

2.4 代碼實現

def matrix_chain_order（p）：

n = len（p） - 1

m = [[0] * （n + 1） for _ in range（n + 1）]

for l in range（2， n + 1）：

for i in range（1， n - l + 2）：

j = i + l - 1

m[i][j] = float（'inf'）

for k in range（i， j）：

q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]

if q lt; m[i][j]：

m[i][j] = q

return m[1][n]

2.5 時間復雜度和空間復雜度

時間復雜度：O（n3） ，其中n是矩陣的個數。因為需要計算n2個狀態，每個狀態的計算需要O（n） 的時間。

空間復雜度：O（n2） ，用于存儲二維數組m。

動態規劃算法通過分析問題的最優子結構和子問題重疊性質，有效地解決了矩陣連乘問題，避免了重復計算，提高了計算效率。

3 備忘錄在矩陣連乘問題中的應用

3.1 備忘錄的作用

備忘錄（Memoization） 是一種優化技術，它是動態規劃算法的一個變形。

備忘錄方法用一個表格來保存已解決的子問題答案，當再次遇到該子問題時，只須查看該子問題的答案，無須再進行重復計算。與動態規劃算法不同的是，備忘錄方法采用的自頂向下的遞歸方式，而動態規劃算法采用的自底向上的非遞歸方式[4]。通過使用備忘錄來記錄子問題的解，可以有效地減少計算量。在矩陣連乘問題中，由于不同的子問題可能會被多次求解，使用備忘錄可以大大提高算法的效率。

3.2 實現方法

1） 定義備忘錄表。創建一個二維數組m[i][j] ，用于存儲子問題Ai 到Aj 的最優解，即最少的乘法次數。

2） 初始化備忘錄表。當 i=j 時，m[i][i]=0 時，因為一個矩陣自己相乘的次數為 0。

3） 遞歸定義最優值。m[i][ j]=mini?k

4） 填充備忘錄表。從較小的子問題開始，逐步計算并填充備忘錄表，直到求解出整個問題的最優解。

3.3 算法步驟

1） 輸入矩陣序列的維度信息，存儲在數組p中，其中p0是第一個矩陣的行數， p1是第一個矩陣的列數，同時也是第二個矩陣的行數，以此類推。

2） 創建備忘錄表，即一個二維數組 ，用于存儲子問題的最優解。初始時，將所有元素設置為無窮大，表示尚未求解，并初始化對角線元素為 0。

3） 按照矩陣鏈的長度從 2 開始逐步增加，計算并填充備忘錄表。

4） 對于長度為l 的矩陣鏈，遍歷所有可能的劃分點k ，計算m[i][j]的值。

在計算m[i][j]時，首先檢查m[i][j]是否已經被計算過。如果已經計算過，則直接返回結果；否則，進行計算并將結果存儲在m[i][j]中。最終m[l][n]即為矩陣連乘的最少乘法次數。

3.4 代碼實現

def matrix_chain_order（p）：

n = len（p） - 1

m = [[float（'inf'）] * n for _ in range（n）]

return lookup_chain（m， p， 0， n - 1）

def lookup_chain（m， p， i， j）：

if m[i][j] lt; float（'inf'）：

return m[i][j]

if i == j：

m[i][j] = 0

else：

for k in range（i， j）：

q = lookup_chain（m， p， i， k） + lookup_chain（m， p， k+ 1， j） + p[i] * p[k + 1] * p[j + 1]

if q lt; m[i][j]：

m[i][j] = q

return m[i][j]

3.5 時間復雜度和空間復雜度

時間復雜度：O（n3） ，其中n是矩陣的個數。

空間復雜度：O（n2） ，用于存儲備忘錄表。

備忘錄方法通過記錄子問題的解，避免了重復計算，有效地解決了矩陣連乘問題。

4 算法比較

動態規劃算法通常采用自底向上的方式，通過填充二維數組m來逐步求解問題[5]。首先計算兩個矩陣相乘的乘法次數，然后利用這些小問題的解來，逐步計算三個、四個等更多矩陣相乘的最優乘法次數，最終得到整個矩陣鏈的最優乘法次數，即原問題的解。

備忘錄方法通過遞歸調用并結合備忘錄，即存儲已計算子問題結果的二維數組m來求解問題。在遞歸過程中，對于矩陣連乘問題，在計算Ai 到Aj 的乘法次數時，先檢查備忘錄中是否已經存儲了該子問題的結果。如果沒有，就遞歸地計算不同劃分點下的乘法次數，并選擇最小的結果存入備忘錄[6]。與動態規劃法相比，備忘錄法的狀態轉移方程和計算邏輯基本相同，只是計算順序有所不同。動態規劃法是自底向上計算，而備忘錄法是自頂向下計算。備忘錄方法結合了遞歸的簡潔性和動態規劃避免重復計算的優點，在一些情況下，代碼結構可能更直觀，具體的比較如表1 所示。

5 圖形變換中的矩陣連乘應用

在圖形學中，圖形的變換（如平移、旋轉、縮放等） 可以通過矩陣乘法來實現。例如，二維平面上的一個點（x，y）經過一個2×2的變換矩陣后的新坐標（x'，y'）可以通過[x' y']"= M [x y ]來計算。復雜的圖形變換往往是多個基本變換矩陣的連乘。

假設有三個圖形變換矩陣A1（2×3）、A2（3×4）、A3（4×2）。具體的計算示意圖如圖1所示。

首先，根據邊界條件，m[1][1]=m[2][2]=m[3][3]=0。

計算子矩陣的鏈長度為2的情況：

m[1][2]=p0p1p2=2×3×4=24

m[2][3]=p1p2p3=3×4×2=24

計算子矩陣的鏈長度為3的情況：

m[1] [3] =min{m[1] [1] +m[2] [3] +p0p1p3， m[1] [2] +m[3][3]+p0p2p3}

=min{0+24+2×3×2，24+0+2×4×2}

=min{36，40}=36

具體的計算次數如表2 所示，計算順序如表3 所示。

所以，由表2可知A1（2×3）、A2（3×4）、A3（4×2）連乘的最小計算量為36，由表3可知最優的矩陣連乘順序是A1（A2A3）。在圖形變換中，按照這個順序進行矩陣連乘可以減少計算量，提高圖形變換的效率。

矩陣連乘還可用于組合圖像變換，如連續旋轉和平移。前文中提到將3D模型中的一點P（x，y，z，1）先繞z 軸旋轉α度，得到旋轉矩陣Rz；再沿x軸方向平移tx，沿y軸方向平移ty，沿z軸方向平移tz，得到平移矩陣T，變換后結果P’=Rz×T×P。

可以選擇的計算順序有Rz×（T×P）和 （Rz×T）×P，根據具體的旋轉角度和平移距離，能算出最小的計算次數。

利用矩陣連乘還可以優化圖像變換計算的效率，即減少重復計算。例如，對于三個矩陣A1 （p0×p1） 、A2 （p1×p2） 和 A3（p2×p3） ，根據矩陣乘法結合律（A1×A2）×A3=A1×（A2×A3），但是兩種計算順序的乘法運算次數不同。在實際的圖像變換中，涉及的矩陣可能更多，合理安排矩陣連乘的順序可以顯著減少計算量。

6 總結

在矩陣連乘問題中，動態規劃算法和備忘錄都可以有效地解決最優計算順序的問題。備忘錄方法的空間需求通常相對較小，對于矩陣連乘問題，備忘錄只需要一個二維數組存儲不同區間的子問題的最優乘法次數。動態規劃算法需要用二維數組來存儲所有子問題的解，空間復雜度取決于問題的規模[7]。對于矩陣連乘問題，其空間需求可能會比備忘錄算法略大，因為它需要存儲所有可能的子問題的解。如果問題的規模不是很大，或者遞歸求解比較直觀，備忘錄方法可以快速實現并得到較好的效果。當矩陣的數量較多時，動態規劃算法能夠高效地求解最優乘法次數，并且可以通過分析表格中的結果得到最優的乘法順序。

矩陣連乘問題也可以使用基于分治策略的并行算法，將矩陣鏈A1 × A2 × ...×An 劃分為大致相等的兩個子鏈。例如，對于n=8的矩陣鏈，劃分為A1 × A2 × A3 × A4 和A5 × A6 × A7 × A8 兩個子鏈。使用兩個處理器同時計算兩個子鏈的乘積，一個處理器計算子鏈A1 × A2 × A3 × A4 的乘積，得到結果矩陣B1；另一個處理器計算子鏈A5 × A6 × A7 × A8 的乘積，得到結果矩陣B2。再使用一個處理器計算B1×B2得到最終結果[8]。由于并行算法的加速比和效率，既和使用的處理器個數有關，還和數據劃分的開銷有關，所以此算法解決矩陣連乘問題也有待改進。

參考文獻：

[1] 蘇旺輝，劉海濤，謝繼國.求解矩陣連乘最小乘法次數的一個自底向上算法[J].甘肅高師學報，2008，13（2）：16-17.

[2] 李野，童小念.矩陣乘并行算法的仿真與性能分析[J].現代計算機（專業版），2008（9）：20-22.

[3] 王曉東.計算機算法設計與分析[M].北京：電子工業出版社，2007.

[4] 王秋芬，趙剛彬.算法設計與分析：基于C++編程語言的描述[M].北京：清華大學出版社，2023.

[5] 劉文強，周波，桑海濤，等.算法分析與設計課程中矩陣連乘問題的教學探討[J].教育教學論壇，2016（18）：206-208.

[6] 趙雪巖，徐繼明，陳景森.最值吸收算法解決矩陣連乘次序問題[J].西安工程大學學報，2013，27（6）：827-830.

[7] 周浩慧.兩種矩陣連乘動態規劃優化算法對比分析[J].長春理工大學學報（自然科學版），2010，33（8）：61-62.

[8] 武錚.面向申威異構眾核處理器的高效矩陣乘并行算法研究[D].合肥：中國科學技術大學，2023.

【通聯編輯：梁書】

基金項目：基于知識圖譜的線上一流課程《高級語言程序設計》