Matrix Chain Multiplication (ลำดับการคูณเมทริกซ์ให้เหนียวน้อยที่สุด)

กำหนด Chain ของเมทริกซ์: A₁, A₂, ..., Aₙ โดยเมทริกซ์ Aᵢ มีขนาด p[i-1] × p[i]

การคูณเมทริกซ์มีสมบัติ Associative: (AB)C = A(BC) แต่ จำนวนการคูณสเกลาร์ (scalar multiplications) แตกต่างกันไป ต้องการหาลำดับการคูณที่ใช้ operations น้อยที่สุด

ตัวอย่าง Input และ Output

Input: arr[] = {1, 2, 3, 4}
หมายความ: A₁(1×2), A₂(2×3), A₃(3×4)

Output: Minimum number of matrix multiplications: 18

วิธีคำนวณ:
- (A₁A₂)A₃: (1×2×3) + (1×3×4) = 6 + 12 = 18 ✓
- A₁(A₂A₃): (2×3×4) + (1×2×4) = 24 + 8 = 32

อัลกอริทึม Dynamic Programming (Interval DP)

ฟังก์ชัน matOrder(array, n) โดย n = จำนวนเมทริกซ์ + 1

กำหนด:

minMul[i][j] = จำนวนการคูณน้อยที่สุดสำหรับเมทริกซ์ Aᵢ ถึง Aⱼ (1-indexed)

Recurrence:

minMul[i][j] = min over k (minMul[i][k] + minMul[k+1][j] + p[i-1]*p[k]*p[j]) สำหรับ k = i ถึง j-1

ขั้นตอน:

1. สร้างตาราง minMul[n][n] เริ่มต้น 0 บน diagonal
2. for length = 2 ถึง n-1 (ความยาว chain):
   • for i = 1 ถึง n-length:
     • j = i + length - 1
     • minMul[i][j] = INF
     • for k = i ถึง j-1:
       • q = minMul[i][k] + minMul[k+1][j] + arr[i-1]*arr[k]*arr[j]
       • อัปเดต min
3. คืน minMul[1][n-1]

ตัวอย่างโค้ด C++

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int matOrder(int array[], int n) {
    int minMul[n][n];
    for (int i = 1; i < n; i++) minMul[i][i] = 0;

    for (int length = 2; length < n; length++) {
        for (int i = 1; i < n-length+1; i++) {
            int j = i + length - 1;
            minMul[i][j] = INT_MAX;
            for (int k = i; k <= j-1; k++) {
                int q = minMul[i][k] + minMul[k+1][j] + array[i-1]*array[k]*array[j];
                if (q < minMul[i][j]) minMul[i][j] = q;
            }
        }
    }
    return minMul[1][n-1];
}

int main() {
    int arr[] = {1, 2, 3, 4};
    int size = 4;
    cout << "Minimum number of matrix multiplications: " << matOrder(arr, size);
    return 0;
}

Output

Minimum number of matrix multiplications: 18

ความซับซ้อน

• Time: O(n³)
• Space: O(n²)

การประยุกต์: Optimal Parenthesization

เก็บค่า k ที่ให้ค่าต่ำสุดในตาราง split[i][j] แล้ว trace back เพื่อพิมพ์วงเล็บ

ความสัมพันธ์กับ Polygon Triangulation

โครงสร้าง DP เหมือนกันทั้งคู่ (Interval DP) ต่างกันแค่ cost function