遞迴解決方案

Created: November-22, 2018

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

假設我們有兩個矩陣 A 1 和 A 2 ，其維數為 m * n 和 p * q 。根據矩陣乘法的規則，我們知道，

當且僅當 n = **p 時，**我們可以乘以 A 1 和 A 2 。這意味著 A 1 的列數必須等於 A 2 的行數。 **** ****
如果滿足第一個條件並且我們將 A 1 和 A 2 相乘，我們將得到一個新矩陣，我們稱之為維數 m * q 的 A 3 。 **** ****
要乘以 A 1 和 A 2 ，我們需要進行一些縮放器乘法。我們需要執行的縮放器乘法的總數是（ m * n * q ）或（ m * p * q ）。
甲 1 * 阿 2 是不等於阿 2 * 阿 1 。

如果我們具有分別具有尺寸 m * n ， n * p 和 p * q 的三個矩陣 A 1 ， A 2 和 A 3 ，那麼 A 4 = A 1 * A 2 * A 3 將具有 m * q 的尺寸。現在我們可以通過兩種方式執行此矩陣乘法： **** **** **** **** **** **** **** ****

首先，我們將 A 1 和 A 2 相乘，然後將結果乘以 A 3 。即：（ A 1 * A 2 ）* A 3 。
首先，我們將 A 2 和 A 3 相乘，然後將結果乘以 A 1 。即： 甲 1 *（ 阿 2 * 阿 3 ）。

你可以注意到乘法的順序保持不變，即我們不會乘以（ A 1 * A 3 ）* A 2， 因為它可能無效。我們只更改括號以在將其與剩餘值相乘之前將其相乘。我們如何放置這些括號是很重要的。為什麼？比方說，的 3 維矩陣阿 1 ，阿 2 和阿 3 是 10 * 100 ， 100 * 5 ， 5 * 50 。然後，

對於（ A 1 * A 2 ）* A 3 ，縮放器乘法的總數是：（ 10 * 100 * 5 ）+（ 10 * 5 * 50 ）= 7500 次。
對於 A 1 *（ A 2 * A 3 ），縮放器乘法的總數是：（ 100 * 5 * 50 ）+（ 10 * 100 * 50 ）= 75000 次。

對於第 2 種型別，縮放器乘法的數量是第 1 種型別的 10 倍！因此，如果你能夠找到一種方法來找出最小化總縮放器乘法所需的正確的括號方向，那麼它將減少矩陣乘法所需的時間和記憶體。這就是矩陣鏈乘法派上用場的地方。在這裡，我們不會關注矩陣的實際乘法，我們只會找出正確的括號順序，以便縮放器乘法的數量最小化。我們將有矩陣 A 1 ， A 2 ， A 3 …….. A n 我們將找出乘以這些所需的最小縮放器乘法數。我們假設給定的維度是有效的，即它滿足我們對矩陣乘法的第一個要求。

我們將使用分而治之的方法來解決這個問題。由於常見的子問題，需要動態程式設計。例如：對於 n = 5 ，我們有 5 個矩陣 A 1 ， A 2 ， A 3 ， A 4 和 A 5 。我們想要找出執行此矩陣乘法所需的最小乘法次數 A 1 * A 2 * A 3 * A 4 * A 5 。在很多方面，讓我們專注於一個方面:( A. 1 * A 2 ）*（ A 3 * A 4 * A 5 ）。

對於這個，我們將發現 A left = A 1 * A 2 。阿右 = 阿 3 * 甲 4 * 甲 5 。然後，我們會發現一個答案 = 一個左 * 一個向右 。找出所需的縮放乘法總數一個答案 ：=確定需要縮放乘法的總數一左 +以確定所需的總人數定標器的乘法一個正確的 +確定 A 左 * A 右 所需的縮放器乘法總數。

最後一項，以確定需要縮放乘法的總數一左 * 一個右 行數：可以寫成一個左 *列的數一離開 *在列數一個合適的 。（根據矩陣乘法的第 2 條規則）

但我們也可以用其他方式設定括號。例如：

甲 1 *（ 阿 2 * 阿 3 * 甲 4 * 甲 5 ）
（ A 1 * A 2 * A 3 ）*（ A 4 * A 5 ）
（ A 1 * A 2 * A 3 * A 4 ）* A 5 等

對於每種可能的情況，我們將確定找到 A 左 和 A 右 所需的縮放器乘法數，然後確定 A 左 * A 右 。如果你對遞迴有一個大致的瞭解，那麼你已經瞭解瞭如何執行此任務。我們的演算法將是：

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

為什麼這是動態程式設計問題？要確定（ A 1 * A 2 * A 3 ），如果你已經計算過（ A 1 * A 2 ），那麼在這種情況下它會有所幫助。

為了確定這種遞迴的狀態，我們可以看到為了解決每種情況，我們需要知道我們正在使用的矩陣範圍。所以我們需要一個開始和結束。當我們使用分而治之時，我們的基本情況將少於 2 個矩陣（開始 > = 結束），我們根本不需要乘法。我們將有 2 個陣列：行和列。 row [i] 和 column [i] 將儲存矩陣 A i 的行數和列數。我們將有一個 dp [n] [n] 陣列來儲存已經計算的值並用它初始化它 -1 ，其中 -1 表示尚未計算的值。 dp [i] [j] 表示乘以 A i ， A i + 1 ，…..， A j 所需的縮放器乘法的數量。虛擬碼看起來像：

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

複雜：

begin 和 end 的值可以是 1 到 n 。有 n 2 種不同的狀態。對於每個狀態，內部迴圈將執行 n 次。總時間複雜度：O(n³) 和記憶體複雜度：O(n²)。