Như vậy là một giải thuật thời gian mũ, trong khi chỉ có một đa thức các bài toán con. Ðiều đó chứng tỏ rằng có những bài toán con được giải nhiều lần.
Chẳng hạn:
Để tính Comb(4,2) ta phải tính Comb(3,1) và Comb(3,2). Ðể tính Comb(3,1) ta phải tính Comb(2,0) và Comb(2,1). Ðể tính Comb(3,2) ta phải tính Comb(2,1) và Comb(2,2). Như vậy để tính Comb(4,2) ta phải tính Comb(2,1) hai lần.
Áp dụng kĩ thuật quy hoạch động để khắc phục tình trạng trên, ta xây dựng một bảng O gồm n+1 dòng (từ 0 đến n) và n+1 cột (từ 0 đến n) và điền giá trị cho O(i,j) theo quy tắc sau: (Quy tắc tam giác Pascal)
O(0,0) = 1;
O(i,0) =1;
O(i,i) = 1 với 0 < i n;
0 | 1 | 2 | 3 | 4 | |
0 | 1 | ||||
1 | 1 | 1 | |||
2 | 1 | 2 | 1 | ||
3 | 1 | 3 | 3 | 1 | |
4 | 1 | 4 | 6 | 4 | 1 |
Có thể bạn quan tâm!
-
Thiết kế và đánh giá thuật toán - 16 -
Trọng Lượng Và Giá Trị Của 4 Loại Đồ Vật -
Thiết kế và đánh giá thuật toán - 18 -
Trọng Lương Và Giá Trị 5 Loại Đồ Vật -
Thiết kế và đánh giá thuật toán - 21 -
Thiết kế và đánh giá thuật toán - 22
Xem toàn bộ 205 trang tài liệu này.
O(i,j) = O(i-1,j-1) + O(i-1,j) với 0 < j < i < n. Chẳng hạn với n = 4 ta có bảng dưới đây:
Hình 6.1. Quy tắc tam giác Pascal O(n,k) chính là Comb(n,k) và ta có giải thuật như sau:
Comb(n, k)
{
C[0][0] = 1;
for(i=1;i<=n;i++)
{
C[i][0] = 1;
C[i][i] = 1;
for(j=1;j<=i-1;j++)
C[i][j] =C[i-1][j-1] + C[i-1][j];
}
return(C[n][k])
}
Phép toán tích cực là phép toán C[i][j] =C[i-1][j-1] + C[i-1][j] có thời gian là
O(1). Vòng lặp for(j=1;j<=i-1;j++) thực hiện i-1 lần, mỗi lần O(1). Vòng lặp for(i=1;i<=n;i++) có i chạy từ 1 đến n, nên nếu gọi T(n) là thời gian thực hiện giải thuật thì ta có:
n
T( n )
1
i 1 1 2 3 ... ( n 1 ) n( n 1 )
2
Vậy T(n) = O(n2)
Nhận xét:
Thông qua việc xác định độ phức tạp, ta thấy rò ràng giải thuật quy hoạch động hiệu quả hơn nhiều so với giải thuật đệ qui (n2 < 2n). Tuy nhiên việc sử dụng bảng (mảng hai chiều) như trên còn lãng phí ô nhớ, do đó ta sẽ cải tiến thêm một bước bằng cách sử dụng véctơ (mảng một chiều) để lưu trữ kết quả trung gian.
Cách làm cụ thể như sau:
Ta sẽ dùng một véctơ V có n+1 phần tử từ V[0] đến V[n]. Véctơ V sẽ lưu trữ các giá trị tương ứng với dòng i trong tam giác Pascal ở trên. Trong đó V[j] lưu trữ giá trị số tổ hợp chập j của i (j = 0 đến i). Dĩ nhiên do chỉ có một véctơ V mà phải lưu trữ nhiều dòng i do đó tại mỗi bước, V chỉ lưu trữ được một dòng và ở bước cuối cùng, V lưu trữ các giá trị ứng với i = n, trong đó V[k] chính là Ckn.
Khởi đầu, ứng với i =1, ta cho V[0] = 1 và V[1] = 1. Tức là:
C
1
0 = 1 và
1
C1= 1.
Với các giá trị i từ 2 đến n, ta thực hiện như sau:
i
- V[0] được gán giá trị 1 tức là C0
= 1. Tuy nhiên giá trị V[0] = 1 đã được
gán ở trên, không cần phải gán lại.
i
- Với j từ 1 đến i-1, ta vẫn áp dụng công thức C j
j 1 i1
j
C
i1
. Nghĩa là để
= C
tính các giá trị trong dòng i ta phải dựa vào dòng i-1. Tuy nhiên do chỉ có một véctơ V và lúc này nó sẽ lưu trữ các giá trị của dòng i, tức là dòng i-1 sẽ không còn. Để khắc phục điều này ta dùng thêm hai biến trung gian p1 và p2. Trong đó p1 dùng để
i1
i1
i1
lưu trữ Cj1 và p2 dùng để lưu trữ Cj. Khởi đầu p1 được gán V[0] tức là C0và
i1
i
p2 được gán V[j] tức là C j , V[j] lưu trữ giá trị C j sẽ được gán bới p1+p2, sau đó
i1
p1 được gán bởi p2, nghĩa là khi j tăng lên 1 đơn vị thành j+1 thì p1 là C j
và nó
i
được dùng để tính C j 1 .
i
- Cuối cùng với j = i thực hiện gán V[i] giá trị 1 tức là Ci
= 1.
Giải thuật:
Comb(n, k )
{
V[0] = 1;
V[1] = 1;
for(i=2;i<=n;i++)
{
p1 := V[0];
for(j=1;i<=i-1;j++)
{
p2 := V[j];
V[j]:= p1+p2; p1:= p2;
}
V[i] := 1;
}
return(V[k]);
}
Dễ thấy rằng độ phức tạp của giải thuật vẫn là O(n2).
6.2.2. Bµi to¸n nh©n nhiÒu ma trËn
1) Bµi to¸n
Tính tích các ma trận : A = A1×...× An sao cho số phép tính cần thực hiện là ít nhất (Với giả thiết các phép nhân là thực hiện được).
2) Phân tích bài toán
Ta nhận thấy rằng:
Do tính kết hợp của phép nhân ma trận, các ma trận Ai có thể nhóm lại theo nhiều cách khác nhau, mà ma trận kết quả A không đổi. Tuy nhiên có sự khác biệt về chi phí khi thay đổi các tổ hợp các ma trận Ai.
Dưới đây là thuật toán nhân hai ma trận A và B, các thuộc tính rows và columns là số hàng và số cột của ma trận.
MATRIX-MULTIPLY(A, B)
{
if (columns[A] rows[B]) return;
else for(i=1;i<=rows[A];i++)
for(j=1;j<=columns[B];j++)
{
}
return C;
}
C[i, j] = 0
for(k=1;k<=columns[A];k++)
C[i, j] = C[i, j] + A[i, k] * B[k, j];
Ta chỉ có thể nhân hai ma trận A và B khi và chỉ khi nó là phù hợp: số cột của ma trận A phải bằng số hàng của ma trận B. Nếu A là ma trận cỡ m n và B là ma trận n p thì ma trận kết quả C có cỡ là m p. Thời gian để tính C được quyết định bởi số phép tính C[i, j] = C[i, j] + A[i, k] * B[k, j], đó là m n p.
Để minh hoạ cho sự khác nhau về thời gian tính C do cách đặt các cặp dấu ngoặc đơn khác nhau trong phép nhân các ma trận ta xét các ma trận A, B, C, D với các kích thước như sau:
A30x1 B1x40 C40x10 D10x25
Hãy tính ma trận tích A×B×C×D
Ta sẽ thấy chi phí cho phép nhân các ma trận phụ thuộc vào cách tổ hợp các ma trận qua việc thực hiện nhân các ma trận này theo các thứ tự khác nhau và tính chi phí theo từng cách như sau:
Chi phí | |
((AB)C)D | 30×1×40 + 30×40×10 + 30×10×25 = 20700 |
(A(B(CD)) | 40×10×25 + 1×40×25 + 30×1×25 = 11750 |
(AB)(CD) | 30×1×40 + 40×10×25 + 30×40×25 = 41200 |
A((BC)D) | 1×40×10 + 1×10×25 + 30×1×25 = 1400 |
Hình 6.2. Chi phí theo các cách tổ hợp ma trận
3) Ý tưởng
Ta giải bài toán bằng cách tiếp cận từ dưới lên. Ta sẽ tính toán và luu trữ lời giải tối ưu cho từng phần nhỏ để tránh tính toán lại cho bài toán lớn hơn.
Trước hết là cho các bộ 2 ma trận, các bộ 3 ma trận . . .
Chẳng hạn, để tính A×B×C ta có thể tính theo các cách : (A×B)×C hoặc A×(B×C).
Nên chi phí để tính A×B×C là chi phí tính được từ 2 phần :
Phần một là chi phí kq1×C, với kq1 = A×B ( chi phí này đã tính và được lưu
trữ)
Phần hai là chi phí A × kq2, với kq2 = B×C ( chi phí này đã được lưu trữ) So sánh 2 phần trên và lưu trử chi phí nhỏ hơn. . .
4) Thiết kế thuật toán
Mấu chốt là tính chi phí nhân bộ các ma trận : Ai×...×Aj , với 1≤ i < j ≤ n, trong đó các bộ nhỏ hơn đã được tính và lưu trử kết quả.
Với một cách tổ hợp các ma trận :
Ai×...×Aj = (Ai×...×Ak) × (Ak+1×...×Aj)
Chi phí để nhân các ma trận Ai,...,Aj sẽ bằng tổng : Chi phí để nhân Ai×...×Ak ( kq1), chi phí để nhân Ak+1×...×Aj ( kq2), và chi phí kq1×kq2.
thì:
Nếu gọi Mij là chi phí nhỏ nhất để nhân bộ các ma trận Ai×...×Aj ,1≤ i < j ≤ n
* Mik là chi phí nhỏ nhất để nhân bộ các ma trận Ai×...×Ak
* Mk+1,j là chi phí nhỏ nhất để nhân bộ các ma trận Ak+1×...×Aj Với ma trận kq1 cỡ di-1×dk và kq2 có cỡ dk×dj , nên chi phí để nhân
kq1×kq2 là di-1dkdj.
Do đó:
M ij = Min {M ik + M k +1, j + d i −1 d k d j };1 ≤ i < j ≤ n
i ≤ k ≤ j −1
M ii = 0
Ta có thể xem M là ma trận tam giác trên : (Mij)1≤i<j≤n . Ta cần tính và làm đầy các phần tử của ma trận này cho đến khi xác định được M1n . Tất cả các phần tử nằm trên đường chéo chính bằng 0.
Tính Mij , ta cần biết Mik , Mk+1,j. Ta tính bảng dọc theo các đường chéo bắt đầu từ đường chéo kế trên đường chéo chính và thay đổi về hướng góc phải trên.
Ta muốn biết thứ tự tốt nhất để nhân dãy các ma trận (theo nghĩa chi phí nhỏ nhất). Mỗi lần ta xác định được tổ hợp tốt nhất, ta dùng biến k để lưu trữ thứ tự này. Đó là Oij = k, với M ik + M k +1, j + d i −1 d k d j đạt min.
Các Mij ta lưu trữ trong mảng 2 chiều M.
Các chỉ số k để xác định được Mij ta lưu trữ trong mảng 2 chiều O.
Kích thước của các ma trận ta lưu trữ trong mảng 1 chiều d : Ai là ma trận có di-1 hàng , di cột.
Thuật toán:
Input d = (d0,d1,...,dn); Output M = (Mij) ,
O = (Oij); MO(d,n,O,M)
{
for (i = 1; i <= n; i++) M[i][i] = 0;
for (diag = 1; diag <= n-1; diag++) for (i = 1; i <= n - diag; i++)
{
j = i + diag; csm = i;
min = M[i][i]+M[i+1][j]+d[i-1]*d[i]*d[j]; for (k= i; k <= j - 1; k++)
if (min > (M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j] ))
{
min= M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]; csm = k;
}
M[i][j] = min;
O[i][j] = csm;
}
return M[1][n];
}
Khi đó dùng hàm sau để xuất thứ tự các tổ hợp nhân ma trận: MOS(i, j, O)
{
if (i == j)
printf(Ai);
}
Ví dụ 6.1.
else
{
}
k = O[i][j];
printf("(");
MOS(i,k,O);
printf("*:);
MOS (k+1,j,O);
printf(")");
Thuật toán được minh họa qua phép nhân các ma trận:
A1×A2×A3×A4×A5×A6
Với kích cỡ của các ma trận là:
Cỡ | |
A1 | 30 35 |
A2 | 35 15 |
A3 | 15 5 |
A4 | 5 10 |
A5 | 10 20 |
A6 | 20 25 |
Hình 6.3. Kích cỡ các ma trận
6
1
j
5
15.125
2
i
4 11.875 10.500
3
3
9.375
7.125
5.375
4
Để tiện theo dòi ta quay các mảng M và mảng O sao cho đường chéo chính nằm ngang.
2 | 7.875 | 4.375 | 8.456 | 3.500 | 5 | |||
1 | 15.750 | 2.625 | 750 | 16.000 | 5.000 | 6 | ||
0 | 0 | 0 | 0 | 0 | 0 |
A1 A2 A3 A4 A5 A6
Hình 6.4. Mảng M
6
1
j
5
3
2
i
4
3
3
3
3
3
3
3
4
2
1
3
3
5
1
2
3
4
5
5
Hình 6.5. Mảng O