Giải thuật và lập trình: §3.5. 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 3x4, B là ma trận kích thước 4x5 thì C sẽ là ma trận kích thước 3x5.

Để 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 3x4, B là ma trận cấp 4x10 và C là ma trận cấp 10x15 thì:

• Để tính (A * B) * C, ta thực hiện (A * B) trước, được ma trận X kích thước 3x10 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 3x15 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 4x15 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 3x15 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 MULTMAT.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 MULTMAT.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:

MULTMAT.INP	MULTMAT.OUT
6 3 2 3 1 2 2 3	31 ((M[1] * (M[2] * M[3])) * ((M[4] * M[5]) * M[6]))

3.5.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 mọ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:

3.5.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.5.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 hai biểu thức đó.

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

program MatrixesMultiplier;

const
  InputFile = 'MULTMAT.INP';
  OutputFile = 'MULTMAT.OUT';
  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;
  fo: Text;

procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn}
var
  i: Integer;
  fi: Text;
begin
  Assign(fi, InputFile);
  Reset(fi);
  ReadLn(fi, n);
  for i := 1 to n + 1 do Read(fi, a[i]); Close(fi);
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(fo, '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(fo, '('); {Mở ngoặc}
  end;
  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(fo, ' * '); {Dấu nhân}
  Trace(k + 1, j); {In ra phép kết hợp để nhân đoạn sau}
  Write(fo, ')'); {Đóng ngoặc}
end;

begin
  Enter;
  Optimize;
  Assign(fo, OutputFile);
  Rewrite(fo);
  WriteLn(fo, F[1, n]); {Số phép nhân cần thực hiện}
  Trace(1, n); {Truy vết bằng đệ quy}
  Close(fo);
end.