Nhân ma trận

Nhân ma trận

1. Mô hình

Nhân một ma trận kích thước m×n với một ma trận n×p, số phép nhân phải thực hiện là m.n.p. Mặt khác phép nhân các ma trận có tính kết hợp, tức là: (A.B).C = A.(B.C)
Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau, mỗi trình tự tính sẽ quyết định số phép nhân cần thực hiện.
Cho N ma trận A1,A2…An, ma trận Ai có kích thước là di–1×di. Hãy xác định trình tự nhân ma trận A1.A2…An sao cho số phép nhân cần thực hiện là ít nhất.

2. Công thức

Gọi F(i,j) là số phép nhân để tính tích các ma trận từ Aiđến Aj (Ai.Ai+1....Aj).
• F(i,i)=0.
• F(i,i+1)=di–1.di.di+1
• F(i,j) = min(F(i,k)+F(k+1,j)+di–1.dk.dj với k=i,i+1,...j–1) Công thức hơi phức tạp nên tôi xin giải thích như sau:
• F(i,i)=0 là hiển nhiên.
• F(i,i+1) là số phép nhân khi nhân Ai và Ai+1. Ai có kích thước di–1×di, Ai+1 có kích thước di×di+1, do đó F(i,i+1)=di–1.di.di+1.
• Với j>i+1 thì ta thấy có thể tính Ai.Ai+1....Aj bằng cách chọn một vị trí k nào đó để đặt ngoặc theo trình tự: Ai.Ai+1....Aj = (Ai..Ak).(Ak+1..Aj) Ma trận kết quả của phép nhân (Ai..Ak) có kích thước di–1×dk, ma trận kết quả của phép nhân (Ak+1..Aj) có kích thước dk×dj. Với cách đặt đó ta sẽ mất F(i,k) phép nhân để có kết quả trong dấu ngoặc thứ nhất, mất thêm F(k+1,j) phép nhân để có kết quả trong dấu ngoặc thứ hai, và cuối cùng mất di–1.dk.dj để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt đó là: F(i,k)+F(k+1,j)+di–1.dk.dj. Ta chọn vị trí k cho số phép nhân ít nhất.

3. Cài đặt

Bảng phương án là một mảng 2 chiều F để lưu F(i,j). Chú ý khi cài đặt là để tính được F(i,j), ta phải tính F(i,k) và F(k+1,j) trước. Phương pháp đơn giản để làm điều đó là phương pháp đệ quy có nhớ.Tuy nhiên dựa vào nhận xét là trong công thức QHĐ: j–i lớn hơn k–i và j–k, ta có thể tính theo trình tự khác: tính các phần tử F(i,j) với j–i từ nhỏ đến lớn (không phải là tính các giá trị F(i,j) với i,j từ nhỏ đến lớn như vẫn làm). Với cách đó, khi tính đến F(i,j) thì ta đã có F(i,k) và F(k+1,j).
Đoạn chương trình tính bảng phương án như sau:
for i:=1 to n do F[i,i]:=0;
for i:=1 to n–1 do
F[i,i+1] := d[i–1]*d[i]*d[i+1];
for m:=2 to n–1 do begin
for i:=1 to n–m do begin
j:=i+m; F[i,j]:=oo;
for k:=i+1 to j–1 do
F[i,j]:=min(F[i,j],
F[i,k]+F[k+1,j]+d[i–1]*d[k]*d[j]);
end;
end;
Với cách cài đặt trên,chi phí không gian là O(n2), chi phí thời gian là O(n3) (đây là bài toán có chi phí lớn nhất trong tất cả các bài toán QHĐ thường gặp.