tags: ADA 5.4 Matrix-Chain Multiplication 矩陣連鎖相乘

ADA 5.4: Matrix-Chain Multiplication 矩陣連鎖相乘

Textbook Chapter 15.2 Matrix-chain multiplication Page. 370

找出矩陣相乘的最短時間 = 找出矩陣相乘的較優順序(決定誰先✖️誰)

*注意
重點不在計算出相乘的結果而是要找出可以最快得出結果的方法

Brute-Force method 暴力破解法

直接不在意順序，乘爆！

解出的

$P_n$我們可稱之為卡塔蘭數(Catalan number)，而且長得很醜。

卡塔蘭數 Catalan number
卡塔蘭數是組合數學中一個常在各種排列組合計數問題中出現的數列。
Cn = C (2n, n) / (n+1) = (2n)! / (n! (n+1)!)

Catalan number的常見應用之一，是在n×n的正方形棋盤上，從左下角走到右下角，不穿越對角線，也不走回頭路的所有可能方法。

如下圖，是3×3的走法。

---

Step 1: Characterize an OPT Solution

• Subproblems
  • 定義：M(i, j) = 從
    $A_i$乘到
    $A_j$所需要花的最少operation數量
  • 目標：M(1, n) = 從第1個matrix乘到第n個matrix
• 檢測是否符合 Optimal substructure

  • 假設我們已知 M(i, j) 的 OPT(Optimal solution)
    –> 會有 k 種可能的cases
    

    $l_i$
    ${}_{-}$
    ${}_1$ *
    $l_k$ *
    $l_j$ =
    $A_i$
    $..$
    ${}_k$ *
    $A_k$
    ${}_{+}$
    ${}_1$
    $..$
    ${}_j$ (矩陣相乘P * Q * R 原理)
    ＝矩陣相乘所花時間

Step 2: Recursively Define the Value of an OPT Solution

• 得到Recursive式子如下：
  

• 有兩個變數，所以這是一個二維Table

Step 3: Compute Value of an OPT Solution

• 由此得知subproblems的數量 ＝
  $n^2$：
  
• 小結：
  find the best k: n *
  $n^2$ (subproblems的數量) =
  $n^3$
  

Step 4 Construct an OPT Solution by Backtracking

• 如何加入括弧來紀錄matrix的相乘順序：
  從 M [ i ] [ j ] = q –> 新增一列：B [ i ] [ j ] = k (for backtracking)
  當 M [ i ] [ j ]更新時，也更新 B [ i ] [ j ]
  透過 B [ i ] [ j ] 得出括弧順序

• 得出括弧順序並backtracking所花費時間為 n ，因為總共有n個matrix