Nhân Dãy Ma Trận: Tìm Thứ Tự Nhân Tối Ưu

Giới thiệu

Khi được cho một dãy các ma trận, bài toán nhân dãy ma trận (Matrix Chain Multiplication) yêu cầu tìm thứ tự nhân các ma trận sao cho tổng số phép nhân vô hướng (scalar multiplications) là nhỏ nhất. Việc nhân ma trận có tính kết hợp, nghĩa là với 4 ma trận A, B, C, D ta có thể nhân theo nhiều cách: A(BCD), (AB)(CD), (ABC)D, A(BC)D, v.v. Mục tiêu là xác định thứ tự hiệu quả nhất.

Đầu vào và Đầu ra

Đầu vào: Mảng kích thước ma trận, ví dụ arr[] = {1, 2, 3, 4}. Nghĩa là các ma trận có kích thước (1×2), (2×3), (3×4).
Đầu ra: Số phép nhân tối thiểu cần thiết để nhân 3 ma trận trên. Kết quả là 18.

Thuật toán Quy hoạch động

Sử dụng bảng minMul[n][n] để lưu số phép nhân tối thiểu cho dãy con từ i đến j.

matOrder(array, n)
Begin
    định nghĩa bảng minMul kích thước n x n, khởi tạo toàn 0
    for length := 2 to n do
        for i := 1 to n - length do
            j := i + length - 1
            minMul[i, j] := ∞
            for k := i to j-1 do
                q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
                if q < minMul[i, j] then minMul[i, j] := q
            done
        done
    done
    return minMul[1, n-1]
End

Ví dụ C++

#include <iostream>
using namespace std;

int matOrder(int array[], int n) {
    int minMul[n][n];
    for (int i = 1; i < n; i++)
        minMul[i][i] = 0; // chi phí 0 với 1 ma trận

    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 << "Số phép nhân ma trận tối thiểu: " << matOrder(arr, size);
    return 0;
}

Kết quả

Số phép nhân ma trận tối thiểu: 18