Quy hoạch động với bài toán nhân ma trận
Đỗ Quốc Trí
Như ta đã biết quy hoạch động là một phương pháp phổ biến để giải các bài toán, và nếu
bạn đã học lập trình thì không thể không biết đến phương pháp này. Trong bài viết tôi
muốn đề cập đến phương pháp này với bài toán nhân ma trận đơn giản tiến tới áp dụng
giải các bài toán thực tế phức tạp hơn
Cho ma trận A có kích thước p*q và ma trận B có kích thước q*r thực hiện phép nhân ma
trận để có ma trận C có kích thước p*r
C[i,j] = ồ A[i,k]*B[k,j] (k : 1 ->q ; 1 <= i <= p , 1 <= j <= q)
Vi dụ:
A * B = C
Ma trận A có kích thước 3*4, Ma trận B có kích thước 4*5, Ma trận C có kích thước 5*3.
Để nhân ma trận ta Ăp*q) voi B (q*r) ta thực hiện chương trình sau
For i := 1 to p do
For j := 1 to r do
Begin
C[i,j] := 0 ;
For k := 1 to q do C[i,j] := C[i,j] + A[i,k] * A[k,j] ;
end ;
Dễ dàng thấy để nhân 2 ma trận này với nhau ta cần phải dùng p *q* r phép nhân, ta gọi
đây là phí tổn để nhân 2 ma trận này.
Vấn đề đặt ra là nhân một dãy ma trận M1 , M2 , M3 …Mn ;
Ta chú ý là phép nhân ma trận khôngcó tính chất giao hoán nhưng có tính chất kết hơp. Ví
dụ (A* B)*C = A*(B*C) ;
Dữ liệu vào File MATRAN.INP
Dòng đầu ghi n
Dòng thứ 2 ghi n+1 so a[1]...a[n+1] với ý nghĩa kích thước của ma trận M[i] là a[i]*a[i+1]
Dữ liệu ra File MATRAN.OUT
Ghi số n là số phép nhân cần thực hiện.
Ví dụ:
Bây giờ ta phân tích bài toán

chẳng hạn ta có aa = b ; ac = c ; chú ý ở đây không có tính kết hợp và giao hoán.
Bài toán đặt ra là cho 1 sâu có độ dài không quá 100, hãy tìm cách đặt dấu ngoặc để thể
hiện phép nhân sao cho kết quả là a.
Input GIATRI.INP: ghi sâu S
Output GIATRI.OUT nếu không đạt được thì ghi 0 nếu đạt được thì ghi cách đặt.
Ví dụ:
Trước tiên ta phân tích bài toán
Khởi tạo mảng F[i,j,u] với 1<=i, j <= 100, u = ’a’..’c’ kiểu Boolean với ý nghĩa
Có thể biến đổi được từ kí tự i đến kí tự j thành k được không (F[i,j] = true nếu được,
= false nếu ngược lại).
ở đây ta có F[i,j,u] = true nếu tồn tại k sao cho F[i,k,x] = true và F[k+1,j,y] = true và
xy = a; (x , y = ’a’..c);
Để ý thấy ta hoàn toàn có thể tiết kiệm bộ nhớ bằng cách để mảng F kiểu byte để ta dễ
dàng truy vết lúc về sau.
F[i,j,u] = 0 nếu không thể phân tích được
F[i,j,u] = k nếu F[i,k,x] <> 0 và F[k+1,j,y] <> 0 và xy = u;
Cách tính mảng F ta hoàn toan áp dụng bài toán trên
Ta sẽ trình bày thuật toán như sau:
Const
InputFile = ’GIATRI.INP’ ;
OutputFile = ’GIATRI.OUT’ ;
max = 100 ;
X : array[’a’..’c’, ’a’..’c’] of char = ((’b’,’b’,’a’) , (’c’,’b’,’a’) ,(’a’,’c’,’c’));
{X là mảng để lưu phép nhân}
Var
A : string ;
F : array[1..max , 1..max,’a’..’c’] of byte ;
i , j , n , l , k: integer ;
c , b : char ;
Fi , Fo : text ;

k : byte ;
u , v : char ;
begin
if i = j then
begin
write(Fo,A[i]) ;
exit ;
end;
Write(Fo , ’(’) ;
k := F[i,j,c] ;
for u := ’a’ to ’c’ do
For v := ’a’ to ’c’ do
if (F[i,k,u] <> 0) and (F[k+1,j,v] <> 0) and (x[u,v] = c) then
begin
Trace(i,k,u) ; trace(k+1,j,v) ;
end;
Write(Fo , ’)’) ;
end;
{ Ch ương trình chính }
Begin
Enter ;
Init ;
Optimize ;
If F[1,n,’a’] = 0 then write(Fo , 0)
else Trace(1,n,’a’) ;
Close(Fo) ;
End.
Ta cũng có thể dùng chương trình đệ quy trên để ghi ra cách nhân trong bài nhân ma trận.
Từ các bài toán trên ta rút ra công thúc truy hồi cho các bài có dạng như trên:
F[i,j] := cấu hình tốt nhất (F[i,k] , F[k+1,j]) với i <= k < j.