Đây là chương trình C++ để thực hiện phân tích ngoặc tối ưu (Optimal Parenthesization) sử dụng thuật toán Quy hoạch động (Dynamic Programming). Bài toán tìm cách đặt ngoặc cho chuỗi nhân ma trận sao cho số phép nhân vô hướng (scalar multiplications) là tối thiểu.
Thuật toán
Bắt đầu
Nhập độ dài n và kích thước các ma trận.
Hàm MatrixChain() tìm số phép nhân tối thiểu:
Tham số:
a[i][j] = số phép nhân vô hướng tối thiểu để tính tích ma trận A[i]A[i+1]...A[j] = A[i..j]
trong đó kích thước A[i] là p[i-1] x p[i].
a[i][j] = 0 khi chỉ nhân một ma trận.
L = độ dài chuỗi.
m = chi phí / số phép nhân vô hướng.
Thân hàm:
với i = 1 đến n-1
Khởi tạo a[i][i] = 0
với L = 2 đến n-1
với i = 1 đến n - L + 1
j = i + L - 1
a[i][j] = INT_MAX
với k = i đến j - 1
m = a[i][k] + a[k+1][j] + p[i-1] * p[k] * p[j]
nếu (m < a[i][j])
a[i][j] = m
b[i][j] = k
trả về a[1][n-1]
Kết thúc
Ví dụ mã nguồn
#include <limits.h>
#include <iostream>
using namespace std;
int MatrixChain(int p[], int n) {
int a[n][n];
int b[n][n];
int i, j, k, L, m;
for (i = 1; i < n; i++)
a[i][i] = 0;
for (L = 2; L < n; L++) {
for (i = 1; i <= n - L + 1; i++) {
j = i + L - 1;
a[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++) {
m = a[i][k] + a[k+1][j] + p[i-1] * p[k] * p[j];
if (m < a[i][j]) {
a[i][j] = m;
b[i][j] = k;
}
}
}
}
return a[1][n-1];
}
int main() {
cout << "Nhập độ dài: ";
int n;
cin >> n;
int a[n];
cout << "Nhập các kích thước: ";
for (int v = 0; v < n; ++v) {
cin >> a[v];
}
cout << "Số phép nhân tối thiểu là: " << MatrixChain(a, n);
return 0;
}
Kết quả
Nhập độ dài: 5 Nhập các kích thước: 2 3 7 6 4 Số phép nhân tối thiểu là: 174