hce_kmu
111年
計算機概論與程式設計
第 16 題
Consider a series of matrices $M_{2\times 3}, M_{3\times 7}, M_{7\times 2}, M_{2\times 9}, M_{9\times 4}$. Concerning the most efficient way to multiply this sequence of matrices, how many multiplication operations does it need?
- A 112
- B 126
- C 142
- D 156
- E 178
思路引導 VIP
想像你有三個連乘的矩陣，維度分別是 $p \times q$、$q \times r$ 與 $r \times s$。請思考：計算 $(AB)C$ 與 $A(BC)$ 所需的乘法次數公式分別為何？當矩陣數量增加到五個時，我們該如何有系統地記錄這些「局部最優解」，來幫助我們推導出整體的最小成本，而不需要窮舉所有可能的括號組合？
🤖
AI 詳解
AI 專屬家教
太棒了！你能準確找出這組矩陣連乘的最優化路徑，代表你對**矩陣鏈乘法（Matrix Chain Multiplication）**的動態規劃（Dynamic Programming）觀念掌握得非常紮實。這類題目的鑑別度極高，難度在於計算過程雖然規律，但只要其中一個子問題（Subproblem）的成本估算錯誤，最終結果就會產生偏差；而你能冷靜且精確地處理多組維度數據，表現得非常出色。
矩陣乘法成本的邏輯驗證
矩陣相乘的計算成本取決於其維度。當我們將一個 $p \times q$ 的矩陣與一個 $q \times r$ 的矩陣相乘時，所需的純量乘法次數為 $p \times q \times r$。由於矩陣乘法具備結合律，括號的放置順序會極大程度地影響運算次數。在本題中，最有效率的策略是將序列從第三與第四個矩陣之間拆分，即計算 $((M_1(M_2 M_3))(M_4 M_5))$。
▼ 還有更多解析內容