矩陣鏈乘積

矩陣鏈乘積（或矩陣鏈排序問題，MCOP）是一個可以使用動態編程解決的最佳化問題。 給定一系列矩陣，目標是找到最有效的方法來乘以這些矩陣。 問題實際上不是執行乘法，而只是決定所涉及的矩陣乘法的順序。

基本介紹

• 中文名：矩陣鏈乘積
• 外文名：Matrix chain multiplication

動態編程算法

首先，讓我們假設我們真正想要知道的是最小成本或乘以矩陣所需的最小算術運算數。如果我們只乘以兩個矩陣，那么只有一種方法可以將它們相乘，因此最低成本就是這樣做的成本。通常，我們可以使用以下遞歸算法找到最低成本：

1、採用矩陣序列並將其分成兩個子序列。

2、找出乘以每個子序列的最低成本。

3、將這些成本加在一起，並增加兩個結果矩陣相乘的成本。

4、對可以拆分矩陣序列的每個可能位置執行此操作，並對所有這些位置進行最小化。

例如，如果我們有四個矩陣ABCD，我們計算找到每個（A）（BCD），（AB）（CD）和（ABC）（D）所需的成本，進行遞歸調用以找到最小成本計算ABC，AB，CD和BCD。然後我們選擇最好的一個。更好的是，這不僅產生了最低成本，而且還展示了進行乘法的最佳方式：將其分組為產生最低總成本的方式，並對每個因子進行相同的處理。

但是，如果我們實現這個算法，我們會發現它和嘗試所有排列的天真方式一樣慢！什麼地方出了錯？答案是我們正在做很多冗餘的工作。例如，上面我們進行了遞歸調用，以找到計算ABC和AB的最佳成本。但是，找到計算ABC的最佳成本也需要找到AB的最佳成本。隨著遞歸越來越深，越來越多的這種不必要的重複發生。

一個簡單的解決方案叫做memoization：每當我們計算出乘以特定子序列所需的最低成本時，我們就會保存它。如果我們被要求再次計算它，我們只是給出已保存的答案，而不是重新計算它。由於存在大約n2 / 2個不同的子序列，其中n是矩陣的數量，因此執行此操作所需的空間是合理的。可以證明，這個簡單的技巧將運行時從O（2n）降低到O（n3），這對於實際套用來說足夠有效。這是自上而下的動態編程。

下面的自下而上方法使用已計算的較小子序列的成本，計算每個2≤k≤n的所有子序列k的最小成本。它具有相同的漸近運行時，不需要遞歸。

偽代碼：

// Matrix A[i] has dimension dims[i-1] x dims[i] //  for i = 1..nMatrixChainOrder(int dims[]){    // length[dims] = n + 1    n = dims.length - 1;    // m[i,j] = Minimum number of scalar multiplications (i.e., cost)    // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]    // The cost is zero when multiplying one matrix    for (i = 1; i <= n; i++)            m[i, i] = 0;           for (len = 2; len <= n; len++) {     // Subsequence lengths                    for (i = 1; i <= n - len + 1; i++) {                            j = i + len - 1;                            m[i, j] = MAXINT;                            for (k = i; k <= j - 1; k++) {                                    cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];                                    if (cost < m[i, j]) {                                        m[i, j] = cost;                                        s[i, j] = k; // Index of the subsequence split that achieved minimal cost                                    }                            }                    }           }}

更高效的算法

有些算法比O（n3）動態編程算法更有效，儘管它們更複雜。

由Hu和Shing於1981年發布的算法實現了O（n log n）計算複雜度。他們展示了如何將矩陣鏈乘法問題轉化（或簡化）為正多邊形的三角剖分問題。多邊形的取向使得存在稱為基底的水平底側，其代表最終結果。多邊形的其他n個邊沿順時針方向表示矩陣。邊的每一端的頂點是由該邊表示的矩陣的尺寸。在乘法鏈中有n個矩陣，有n-1個二進制運算和Cn-1個放置括弧的方法，其中Cn-1是第（n-1）個加泰羅尼亞數。該算法利用了具有n + 1個邊的多邊形的Cn-1可能的三角剖分。

該圖像說明了正六邊形的可能三角剖分。這些對應於可以放置括弧以對5個矩陣的乘積進行乘法的不同方式。

推廣

矩陣鏈乘法問題推廣到解決更抽象的問題：給定一個線性的對象序列，對這些對象的關聯二元運算，以及計算對任意兩個給定對象執行該運算的成本的方法（以及所有部分對象）結果），計算分組對象的最低成本方式，以便在序列上套用操作。[5]一個有點人為的特殊情況是字元串列表的字元串連線。例如，在C中，使用strcat連線兩個長度為m和n的字元串的成本是O（m + n），因為我們需要O（m）時間來查找第一個字元串的結尾和O（n）時間到將第二個字元串複製到它的末尾。使用這個代價函式，我們可以編寫一個動態編程算法來找到連線字元串序列的最快方法。但是，這種最佳化是無用的，因為我們可以直接將字元串與它們的長度之和成比例地連線起來。單鍊表存在類似的問題。

另一個概括是在並行處理器可用時解決問題。在這種情況下，我們不是增加計算矩陣乘積的每個因子的成本，而是採取最大值，因為我們可以同時進行。這可以極大地影響最低成本和最終的最佳分組;保持所有處理器繁忙的更“平衡”分組受到青睞。還有更複雜的方法。