高考申論題
110年
[資訊處理] 資料結構
第 一 題
📖 題組：
A 為（8×4）矩陣、B 為（4×10）矩陣、C 為（10×3）矩陣、D 為（3×20）矩陣、E 為（20×4）矩陣，(一)請列出此 5 個矩陣相乘 A×B×C×D×E 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）(二)請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A×B×C×D×E 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）(三)請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）
A 為（8×4）矩陣、B 為（4×10）矩陣、C 為（10×3）矩陣、D 為（3×20）矩陣、E 為（20×4）矩陣，(一)請列出此 5 個矩陣相乘 A×B×C×D×E 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）(二)請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A×B×C×D×E 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）(三)請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）
📝 此題為申論題，共 3 小題
小題 (一)
請列出此 5 個矩陣相乘 A×B×C×D×E 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）
思路引導 VIP
- 考點辨識：這是一個典型的「矩陣鏈乘積（Matrix Chain Multiplication）」問題，第一小題要求列出所有組合。2. 知識聯結：矩陣相乘的結合律。五個矩陣 A, B, C, D, E 的括號組合數量符合卡特蘭數（Catalan number）C(n-1)，其中 n=5，所以 C(4) = 14 種。3. 展開邏輯：建議採用系統化的展開方式，例如先固定最後一次相乘的位置（如 (ABCD)E, (ABC)(DE)...），再對括號內部進行遞迴拆解，以確保不漏列。
小題 (二)
請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A×B×C×D×E 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）
思路引導 VIP
- 考點辨識：動態規劃解矩陣鏈相乘問題。2. 定義維度：$p_0=8, p_1=4, p_2=10, p_3=3, p_4=20, p_5=4$。3. 建立 DP 表：$m[i,j]$ 表示從矩陣 $i$ 到 $j$ 的最小乘法次數。轉移方程為 $m[i,j] = \min_{i \le k < j} {m[i,k] + m[k+1,j] + p_{i-1}p_kp_j}$。4. 實戰建議：考試時務必畫出表格，從小區間長度（2個矩陣）算到大區間（5個矩陣），並記錄分割點 $s[i,j]$ 以回推最佳括號順序。
小題 (三)
請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）
思路引導 VIP
此題與第二小題連動，直接引用 DP 表格最終計算出的數值 $m[1,5]$。在申論中，這部分的給分通常取決於前面的 DP 過程是否完整。
矩陣連乘積最佳化
💡 利用動態規劃（DP）與卡特蘭數解決矩陣相乘的最優化問題。
🔗 矩陣連乘積 DP 求解三部曲
- 1 初始化與定義 — 定義 m[i,j] 為矩陣 Ai 到 Aj 連乘的最少成本。
- 2 填寫 DP 狀態表 — 依矩陣長度遞增計算，紀錄最小相乘次數與分割點 k。
- 3 回溯重建括號 — 根據分割點紀錄表 s[i,j] 由外而內加上括號順序。
↓
↓
🔄 延伸學習：延伸學習：空間複雜度優化與大 O 符號漸進分析（O(n^3)）。
