Phép nhân tổ hợp dãy ma trận

Với ma trận A kích thước pxq và ma trận B kích thước qxr. Người ta có phép nhân hai ma trận đó để được ma trận C kích thước pxr. Mỗi phần tử của ma trận C được tính theo công thức:

Ví dụ:
A là ma trận kích thước 3×4, B là ma trận kích thước 4×5 thì C sẽ là ma trận kích thước 3×5

Để thực hiện phép nhân hai ma trận A(mxn) và B(nxp) ta có thể làm như đoạn chương trình sau:

for i := 1 to p do
  for j := 1 to r do
    begin
      cij := 0;
      for k := 1 to q do cij := cij + aik * bkj;
    end;

Phí tổn để thực hiện phép nhân này có thể đánh giá qua số phép nhân, để nhân hai ma trận A(pxq) và B(qxr) ta cần thực hiện p.q.r phép nhân số học.
Phép nhân ma trận không có tính chất giao hoán nhưng có tính chất kết hợp

(A * B) * C = A * (B * C)

Vậy nếu A là ma trận cấp 3×4, B là ma trận cấp 4×10 và C là ma trận cấp 10×15 thì:
• Để tính (A * B) * C, ta thực hiện (A * B) trước, được ma trận X kích thước 3×10 sau 3.4.10 = 120 phép nhân số. Sau đó ta thực hiện X * C được ma trận kết quả kích thước 3×15 sau 3.10.15 = 450 phép nhân số. Vậy tổng số phép nhân số học phải thực hiện sẽ là 570.
• Để tính A * (B * C), ta thực hiện (B * C) trước, được ma trận Y kích thước 4×15 sau 4.10.15 = 600 phép nhân số. Sau đó ta thực hiện A * Y được ma trận kết quả kích thước 3×15 sau 3.4.15 = 180 phép nhân số. Vậy tổng số phép nhân số học phải thực hiện sẽ là 780.
Vậy thì trình tự thực hiện có ảnh hưởng lớn tới chi phí. Vấn đề đặt ra là tính số phí tổn ít nhất khi thực hiện phép nhân một dãy các ma trận:

M₁ * M₂ * … * M_n

Với :
M₁ là ma trận kích thước a₁ x a₂M₂ là ma trận kích thước a₂ x a₃…
M_n là ma trận kích thước a_n x a_n+1

Input: file văn bản MATRIXES.INP
• Dòng 1: Chứa số nguyên dương n ≤ 100
• Dòng 2: Chứa n + 1 số nguyên dương a₁, a₂, …, a_n+1 (∀i: 1 ≤ a_i ≤ 100) cách nhau ít nhất một dấu cách

Output: file văn bản MATRIXES.OUT
• Dòng 1: Ghi số phép nhân số học tối thiểu cần thực hiện
• Dòng 2: Ghi biểu thức kết hợp tối ưu của phép nhân dãy ma trận

Trước hết, nếu dãy chỉ có một ma trận thì chi phí bằng 0, tiếp theo ta nhận thấy để nhân một cặp ma trận thì không có chuyện kết hợp gì ở đây cả, chi phí cho phép nhân đó là tính được ngay. Vậy thì phí tổn cho phép nhân hai ma trận liên tiếp trong dãy là hoàn toàn có thể ghi nhận lại được. Sử dụng những thông tin đã ghi nhận để tối ưu hoá phí tổn nhân những bộ ba ma trận liên tiếp … Cứ tiếp tục như vậy cho tới khi ta tính được phí tổn nhân n ma trận liên tiếp.

1. Công thức truy hồi:

Gọi F[i, j] là số phép nhân tối thiểu cần thực hiện để nhân đoạn ma trận liên tiếp: M_i*M_i+1*…*M_j.
Thì khi đó F[i, i] = 0 với i.
Để tính M_i * M_i+1 * … * M_j, ta có thể có nhiều cách kết hợp:
M_i * M_i+1 * … * M_j = (M_i * M_i+1 * … * M_k) * (M_k+1 * M_k+2 * … * M_j) (Với i ≤ k < j)
Với một cách kết hợp (phụ thuộc vào cách chọn vị trí k), chi phí tối thiểu phải thực hiện bằng:

• Chi phí thực hiện phép nhân M_i * M_i+1 * … * M_k = F[i, k]
• Cộng với chi phí thực hiện phép nhân M_k+1 * M_k+2 * … * M_j = F[k + 1, j]
• Cộng với chi phí thực hiện phép nhân hai ma trận cuối cùng: ma trận tạo thành từ phép nhân (M_i * M_i+1 * … * M_k) có kích thước a_i x a_k+1 và ma trận tạo thành từ phép nhân (M_k+1 * M_k+2 * … * M_j) có kích thước a_k+1 x a_j+1, vậy chi phí này là a_i * a_k+1 * a_j+1.
Từ đó suy ra: do có nhiều cách kết hợp, mà ta cần chọn cách kết hợp để có chi phí ít nhất nên ta sẽ cực tiểu hoá F[i, j] theo công thức:

2. Tính bảng phương án

Bảng phương án F là bảng hai chiều, nhìn vào công thức truy hồi, ta thấy F[i, j] chỉ được tính khi mà F[i, k] cũng như F[k + 1, j] đều đã biết. Tức là ban đầu ta điền cơ sở quy hoạch động vào đường chéo chính của bảng(F[i, i] = 0), từ đó tính các giá trị thuộc đường chéo nằm phía trên (Tính các F[i, i + 1]), rồi lại tính các giá trị thuộc đường chéo nằm phía trên nữa (F[i, i + 2]) … Đến khi tính được F[1, n] thì dừng lại

3. Tìm cách kết hợp tối ưu

Tại mỗi bước tính F[i, j], ta ghi nhận lại điểm k mà cách tính (M_i * M_i+1 * … * M_k) * (M_k+1 * M_k+2 … * M_j) cho số phép nhân số học nhỏ nhất, chẳng hạn ta đặt T[i, j] = k.
Khi đó, muốn in ra phép kết hợp tối ưu để nhân đoạn M_i * M_i+1 * … * M_k * M_k+1 * M_k+2 * … * M_j ta sẽ in ra cách kết hợp tối ưu để nhân đoạn M_i * M_i+1 * … * M_k và cách kết hợp tối ưu để nhân đoạn M_k+1 * M_k+2 * … * M_j (có kèm theo dấu đóng mở ngoặc) đồng thời viết thêm dấu “*” vào giữa biểu thức đó.

 PROG03_4.PAS * Nhân tối ưu dãy ma trận

program MatrixesMultiplier;
const
  max = 100;
  MaxLong = 1000000000;
var
  a: array[1..max + 1] of Integer;
  F: array[1..max, 1..max] of LongInt;
  T: array[1..max, 1..max] of Byte;
  n: Integer;
procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn}
var
  i: Integer;
begin
  ReadLn(n);
  for i := 1 to n + 1 do Read(a[i]);
end;
procedure Optimize;
var
  i, j, k, len: Integer;
  x, p, q, r: LongInt;
begin
  for i := 1 to n do
    for j := i to n do
      if i = j then F[i, j] := 0
      else F[i, j] := MaxLong; {Khởi tạo bảng phương án: đường chéo chính = 0, các ô khác = +∞}
  for len := 2 to n do {Tìm cách kết hợp tối ưu để nhân đoạn gồm len ma trận liên tiếp}
    for i := 1 to n - len + 1 do
      begin
        j := i + len - 1; {Tính F[i, j]}
        for k := i to j - 1 do {Xét mọi vị trí phân hoạch k}
          begin
            {Giả sử ta tính Mi * ... * Mj = (Mi * ... * Mk) * (Mk+1 * ... * Mj)}
            p := a[i]; q := a[k + 1]; r := a[j + 1]; {Kích thước 2 ma trận sẽ nhân cuối cùng}
            x := F[i, k] + F[k + 1, j] + p * q * r; {Chi phí nếu phân hoạch theo k}
            if x < F[i, j] then {Nếu phép phân hoạch đó tốt hơn F[i, j] thì ghi nhận lại}
              begin
                F[i, j] := x;
                T[i, j] := k;
              end;
          end;
      end;
end;
procedure Trace(i, j: Integer); {In ra phép kết hợp để nhân đoạn Mi * Mi+1 * ... * Mj}
var
 k: Integer;
begin
  if i = j then Write('M[', i, ']') {Nếu đoạn chỉ gồm 1 ma trận thì in luôn}
  else {Nếu đoạn gồm từ 2 ma trận trở lên}
    begin
      Write('('); {Mở ngoặc}
      k := T[i, j]; {Lấy vị trí phân hoạch tối ưu đoạn Mi...Mj}
      Trace(i, k); {In ra phép kết hợp để nhân đoạn đầu}
      Write(' * '); {Dấu nhân}
      Trace(k + 1, j); {In ra phép kết hợp để nhân đoạn sau}
      Write(')'); {Đóng ngoặc}
    end;
end;
begin
  Assign(Input, 'MATRIXES.INP'); Reset(Input);
  Assign(Output, 'MATRIXES.OUT'); Rewrite(Output);
  Enter;
  Optimize;
  WriteLn(F[1, n]); {Số phép nhân cần thực hiện}
  Trace(1, n); {Truy vết bằng đệ quy}
  WriteLn;
  Close(Input); Close(Output);
end.

Cài đặt bằng ngôn ngữ C++

#include <iostream>
#include <fstream>
using namespace std;

#define Input "MATRIXES.INP"
#define Output "MATRIXES.OUT"

#define MAX 101
#define MAXLONG 1000000000

int A[MAX+1],n,F[MAX][MAX],T[MAX][MAX];

void Enter()
{
    ifstream fi(Input);
    fi>>n;
    fi.ignore();
    for (int i=1; i<=n+1; i++) fi>>A[i];
    fi.close();
}

void Optimize()
{
    int i,j,k,t,len;
    for (i=1; i<=n; i++)
        for (j=1; j<=n;j++)
            F[i][j]= i==j ? 0: MAXLONG;

    for (len=2; len<=n; len++)
        for (i=1; i<=n-len+1; i++)
        {
            j = i+len-1;

            for (k=i; k<j; k++)
            {
                t = F[i][k] + F[k+1][j] + A[i]*A[k+1]*A[j+1];
                if (t < F[i][j])
                {
                    F[i][j] = t;
                    T[i][j] = k;
                }
            }
        }
}

void Trace(ofstream &o, int i, int j)
{
    if (i==j)
        o<<"M["<<i<<"]";
    else
    {
        o<<"(";
        Trace(o,i,T[i][j]);
        o<<") * (";
        Trace(o,T[i][j]+1,j);
        o<<")";
    }
}

void PutOut()
{
    ofstream fo(Output);
    fo<<F[1][n]<<endl;
    Trace(fo,1,n);
    fo.close();
}

int main()
{
    Enter();
    Optimize();
    PutOut();
    return 0;
}

Nguồn: Bài giảng chuyên đề Quy hoạch động – Lê Minh Hoàng