Bài giảng Phân tích và thiết kế giải thuật - Chương 5: Qui hoạch động và giải thuật tham lam

Nội dung text: Bài giảng Phân tích và thiết kế giải thuật - Chương 5: Qui hoạch động và giải thuật tham lam

1. Tính những chi phí tối ưu Thay vì tính lời giải dựa vào công thức cho ở (5.2) bằng một giải thuật đệ quy, chúng ta đi thực hiện Bước 3 của qui hoạch động: tính chi phí tối ưu bằng cách tiếp cận từ dưới lên. Giả sử ma trận Ai có kích thước pi-1 pi với i = 1, 2 , , n. Đầu vào là chuỗi trị số . Thủ tục dùng một bảng m[1 n, 1 n] để lưu các chi phí m[i, j] và bảng s[1 n, 1 n] để lưu giá trị nào của vị trí k mà thực hiện được chi phí tối ưu khi tính m[i, j]. Thủ tục MATRIX-CHAIN-ORDER trả về hai mảng m và s. 11
2. Thủ tục tính hai bảng m và s procedure MATRIX-CHAIN-ORDER(p, m, s); begin n:= length[p] - 1; for i: = 1 to n do m[i, i] := 0; for l:= 2 to n do /* l: length of the chain */ for i:= 1 to n – l + 1 do begin j:= i + l – 1; m[i, j]:= ; /* initialization */ for k:= i to j-1 do begin q:= m[i, k] + m[k + 1, j] + pi-1pkpj; if q < m[i, j] then begin m[i, j]: = q; s[i, j]: = k end end end end 12
3. Một thí dụ: Tính tích xâu ma trận Vì ta định nghĩa m[i, j] chỉ cho i < j, chỉ phần của bảng m ở trên đường chéo chính mới được dùng. Cho các ma trận với kích thước như sau: A1 30 35 A2 35 15 A3 15 5 A4 5 10 A5 10 20 A6 20 25 Hình 4.1 trình bày bảng m và s được tính bởi thủ tục MATRIX-CHAIN-ORDER với n = 6. 13
4. Một thí dụ về tính tích xâu ma trân (tt.) Mảng m i 1 2 3 4 5 6 6 15125 10500 51375 3500 5000 0 5 11875 7125 2500 1000 0 j 4 9357 4375 750 0 3 7875 2625 0 2 15750 0 1 0 Mảng s Hình 5.1 i 1 2 3 4 5 6 3 3 3 5 5 5 3 3 3 4 j 4 3 3 3 3 1 2 2 1 14
5. Một thí dụ về tính tích xâu ma trân (tt.) m[2,2]+ m[3,5] + p.p25 p = 0 + 2500 + 35.15.20 = 13000 m[2,5] = min m[2,3]+ m[4,5] + p1 p 2 p 5 = 2625 + 100 + 35.5.30 = 7125 m[2,4]+ m[5m5] + p1 p 4 p 5 = 4375 + 0 + 35.10.20 = 11375 = 7125 k = 3 for A2 5 Bước 4 của phương pháp qui hoạch động là tạo một lời giải tối ưu từ những thông tin đã tính toán. 15
6. Bước 4: Tạo một lời giải tối ưu Ta dùng mảng s[1 n, 1 n] để xác định cách tốt nhất để tính tích xâu ma trận. Mỗi phần tử s[i, j] ghi trị of k sao cho tại đó sự mở đóng ngoặc tối ưu tách đôi xâu AiAi+1 Aj thành hai đoạn tại Ak và Ak+1. Cho trước chuỗi ma trận A = , bảng s và các chỉ số i và j, thủ tục đệ quy MATRIX-CHAIN-MULTIPLY sau đây tính tích xâu ma trận Ai j,. Thủ tục trả về kết quả qua tham số AIJ. Vơi lệnh gọi ban đầu là MATRIX-CHAIN-MULTIPLY(A,s, 1, n, A1N) Thủ tục sẽ trả về kết quả ma trận tích sau cùng với mảng A1N. 16
7. Tính lời giải procedure MATRIX-CHAIN-MULTIPLY(A, s, i, j, AIJ); begin if j > i then begin MATRIX-CHAIN-MULTIPLY(A, s, i, s[i, j], X); MATRIX-CHAIN-MULTIPLY(A,s, s[i, j]+1, j, Y); MATRIX-MULTIPLY(X, Y, AIJ); end else assign Ai to AIJ; end; 17
8. Các thành phần của quy hoạch động Có hai thành phần then chốt mà một bài toán tối ưu hóa phải có để có thể áp dụng qui hoạch động: (1) tiểu cấu trúc tối ưu (optimal substructure) và (2) các bài toán con trùng lắp (overlapping subproblems). Tiểu cấu trúc tối ưu Một bài toán có tính chất tiểu cấu trúc tối ưu nếu lời giải tối ưu chứa trong nó những lời giải tối ưu của những bài toán con. 18
9. Những bài toán con trùng lắp Khi một giải thuật đệ quy gặp lại cùng một bài toán con nhiều lần, ta bảo rằng bài toán tối ưu hóa có những bài toán con trùng lắp. Giải thuật quy hoạch động lợi dụng những bài toán con trùng lắp bằng cách giải mỗi bài toán con một lần, cất lời giải vào trong một bảng mà bảng này sẽ được tham khảo đến khi cần. Các giải thuật đệ quy làm việc từ trên xuống trong khi các giải thuật quy hoạch động làm việc từ dưới lên, Cách sau hữu hiệu hơn . 19
10. Thí dụ 2: Bài toán chuỗi con chung dài nhất Một chuỗi con (subsequence) của một chuỗi (sequence) là chuỗi ấy sau khi bỏ đi một vài phần tử. Thí dụ: Z = là một chuỗi con của X = với chuỗi chỉ số . Cho hai chuỗi X và Y, ta bảo Z là chuỗi con chung (common subsequence) của X và Y nếu Z là một chuỗi con của cả hai chuỗi X và Y. Trong bài toán chuỗi con chung dài nhất, ta được cho hai chuỗi X = và Y = và muốn tìm chuỗi con chung dài nhất (LCS) của X và Y. 20
11. Tiểu cấu trúc tối ưu của bài toán chuỗi con chung dài nhất Thí dụ: X = và Y = là LCS của X and Y. Cho chuỗi X = , ta định nghĩa tiền tố thứ i của X, với i = 0, 1, , m, là Xi = . Định lý 4.1 Cho X = và Y = là những chuỗi, và Z = là LCS của X và Y. 1. Nếu xm = yn thì zk = xm = yn và Zk-1 là LCS của Xm-1 và Yn-1. 2. Nếu xm yn, thì zk xm hàm ý Z là LCS của Xm-1 và Y. 3. Nếu xm yn, thì zk yn hàm ý Z là LCS của X và Yn-1. 21
12. Lời giải đệ quy Để tìm một LCS của X và Y, ta có thể cần tìm LCS của X và Yn-1 và LCS của Xm-1 và Y. Nhưng mỗi trong hai bài toán con này có những bài toán “cháu” để tìm Xm-1 và Yn-1. Gọi c[i, j] là chiều dài của LCS của hai chuỗi Xi và Yj. Nếu i = 0 hay j = 0, thì LCS có chiều dài 0. Tính chất tiểu cấu trúc tối ưu của bài toán LCS cho ra công thức đệ quy sau: 0 nếu i =0 hay j = 0 c[i, j] = c[i-1, j-1]+1 nếu i, j > 0 và xi = yj max(c[i, j-1],c[i-1,j]) nếu i,j >0 và xi yj (5.3) 22
13. Tính chiều dài của một LCS Dựa vào phương trình (5.3), ta có thể viết một giải thuật đệ quy để tìm chiều dài của một LCS của hai chuỗi. Tuy nhiên, chúng ta dùng qui hoạch động để tính lời giải theo cách từ dưới lên. Thủ tục LCS-LENGTH có hai chuỗi X = và Y = là đầu vào. Thủ tục lưu các trị c[i, j] trong bảng c[0 m, 0 n]. Nó cũng duy trì bảng b[1 m, 1 n] để đơn giản hóa việc tạo lời giải tối ưu. 23
14. procedure LCS-LENGTH(X, Y) begin m: = length[X]; n: = length[Y]; for i: = 1 to m do c[i, 0]: = 0; for j: = 1 to n do c[0, j]: = 0; for i: = 1 to m do for j: = 1 to n do if xi = yj then begin c[i, j]: = c[i-1, j-1] + 1; b[i, j]: = “” end else if c[i – 1, j] > = c[i, j-1] then begin c[i, j]: = c[i – 1, j]; b[i, j]: = “” end else begin c[i, j]: = c[i, j-1]; b[i, j]: = “” end end; Hình 4.2 sau đây trình bày ma trận c của thí dụ. 24
15. yj B D C A B A 0 0 0 0 0 0 0 xi A 0 0  0  0  1  1  1  B 0 1  1  1  1  2  2  C 0 1  1  2  2  2  2  Hình 5.2 0 1  1  2  2  3  3  B D 0 1  2  2  2  3  3  A 0 1  2  2  3  3  4  B 0 1  2  2  3  4  4  25
16. Tạo chuỗi con chung dài nhất Bảng b có thể được dùng để tạo một LCS của X = and Y = Thủ tuc đệ quy sau đây in ra một LCS của X và Y. Lệnh gọi đầu tiên là PRINT-LCS(b, X, n, m). procedure PRINT-LCS(b, X, i, j) Thời gian tính toán begin của thủ tục PRINT- if i 0 then if b[i, j] = ''  '' then LCS là O(m+n), vì ít begin PRINT-LCS(b, X, i- 1 , j - l ) ; nhất i hay j giảm một đơn vị trong mỗi print xi end chặng của đệ quy. else if b[i,j] = '''' then PRINT-LCS (b, X, i-1, j) else PRINT-LCS(b, X, i, j-1) end; 26
17. Thí dụ 3. Bài toán cái túi (Knapsack) '‘Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng y chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Bài toán cái túi là tìm một tổ hợp các mặt hàng mà kẻ trộm nên bỏ vào cái túi để đạt một giá trị cao nhất với những món hàng mà y mang đi.” Bài toán này có thể giải bằng qui hoạch động bằng cách dùng hai bảng cost và best sau đây: cost[i] chứa giá trị tối đa mà có thể thực hiện được với một cái túi có sức chứa i cost[i] = cost[i – size[j]] + val[j] best[i] chứa mặt hàng cuối cùng bỏ vào túi nhằm đạt được giá trị tối đa. 27
18. Một thí dụ của bài toán cái túi value 4 5 10 11 13 name A B C D E M = 17 Hình 5.3 Một thí dụ của bài toán cái túi 28
19. Giải thuật quy hoạch động cho bài toán cái túi M: sức chứa tối đa của cái túi for i: = 0 to M do cost[i]: = 0; for j: = 1 to N do /* each of item type */ begin for i:= 1 to M do /* i means capacity */ if i – size[j] > = 0 then if cost[i] < (cost[i – size[j]] + val[j]) then begin cost[i]: = cost[i – size[j]] + val[j]; best[i]: = j end; end; 29
20. Một thể hiện của cái túi K 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 j=1 cost[k] 0 0 4 4 4 8 8 8 12 12 12 16 16 16 20 20 20 best[k] A A A A A A A A A A A A A A A j=2 cost[k] 0 0 4 5 5 8 9 10 12 13 14 16 17 18 20 21 22 best[k] A B B A B B A B B A B B A B B j=3 cost[k] 0 0 4 5 5 8 10 10 12 14 15 16 18 18 20 22 24 best[k] A B B A C B A C C A C C A C C j=4 cost[k] 0 0 4 5 5 8 10 11 12 14 15 16 18 20 21 22 24 best[k] A B B A C D A C C A C C D C C j=5 cost[k] 0 0 4 5 5 8 10 11 13 14 15 17 18 20 21 23 24 best[k] A B B A C D E C C E C C D E C Hình 5.4 Các mảng cost và best của một thí dụ bài toán cái túi 30
21. Ghi Chú: Bài toán cái túi có thể dễ dàng giải đưọc nếu M không lớn, nhưng khi M lớn thì thời gian chạy trở nên không thể chấp nhận được. Phương pháp này không thể làm việc được khi M và trọng lượng/kích thước là những số thực thay vì số nguyên. Tính chất 4.1.1 Giải thuật qui hoạch động để giải bài toán cái túi có thời gian chạy tỉ lệ với NM. 31
22. Thí dụ 4: Giải thuật Warshall và giải thuật Floyd Tính bao đóng truyền Trong đồ thị có hướng, chúng ta quan tâm đến tập đỉnh mà đến được từ một đỉnh nào đó bằng cách duyệt các cạnh trong đồ thị theo một hướng đã được ấn định. Một tác vụ mà ta muốn thực hiện là “thêm một cạnh từ x đến y nếu tồn tại một cách nào đó để đi từ x đến y” Đồ thị tạo ra bằng cách thêm tất cả các cạnh có tính chất trên được gọi là bao đóng truyền của đồ thị. Vì đồ thị bao đóng truyền thì thường là đồ thị dày, do đó ta nên dùng cách biểu diễn ma trận kế cận. 32
23. Giải thuật Warshall Có một giải thuật đơn giản để tính bao đóng truyền của một đồ thị được biểu diễn bằng ma trận kế cận. for y : = 1 to V do for x : = 1 to V do if a[x, y] then for j: = 1 to V do if a[y, j] then a[x, j]: = true; S. Warshall đề ra giải thuật này năm 1962, dựa trên một quan sát đơn giản: “Nếu tồn tại một cách để đi từ nút x đến nút y và cách để đi từ nút y đến nút j, thì sẽ có cách để đi từ nút x đến nút j.” 33
24. Một thí dụ tính bao đóng truyền A B C D E F G H I J K L M A 1 1 0 0 0 1 1 0 0 0 0 0 0 A B 0 1 0 0 0 0 0 0 0 0 0 0 0 H I C 1 0 1 0 0 0 0 0 0 0 0 0 0 B C G D 0 0 0 1 0 1 0 0 0 0 0 0 0 E 0 0 0 1 1 0 0 0 0 0 0 0 0 D E J K F 0 0 0 0 1 1 0 0 0 0 0 0 0 G 0 0 1 0 1 0 1 0 0 1 0 0 0 F H 0 0 0 0 0 0 1 1 1 0 0 0 0 L M I 0 0 0 0 0 0 0 1 1 0 0 0 0 J 0 0 0 0 0 0 0 0 0 1 1 1 1 Ma trận kế cận ứng với K 0 0 0 0 0 0 0 0 0 0 1 0 0 L 0 0 0 0 0 0 0 0 0 0 0 1 1 bước khởi đầu của giải M 0 0 0 0 0 0 0 0 0 0 0 1 1 thuật Warshall 34
25. A B C D E F G H I J K L M A 1 1 1 1 1 1 1 0 0 1 1 1 1 B 0 1 0 0 0 0 0 0 0 0 0 0 0 Ma trận kế cận ứng với C 1 1 1 1 1 1 1 0 0 1 1 1 1 bước cuối cùng của giải D 0 0 0 1 1 1 0 0 0 0 0 0 0 thuật Warshall E 0 0 0 1 1 1 0 0 0 0 0 0 0 F 0 0 0 1 1 1 0 0 0 0 0 0 0 G 1 1 1 1 1 1 1 0 0 1 1 1 1 H 1 1 1 1 1 1 1 1 1 1 1 1 1 I 1 1 1 1 1 1 1 1 1 1 1 1 1 Tính chất 5.3.1 Giải thuật J 1 1 1 1 1 1 1 0 0 1 1 1 1 Warshall tính bao đóng K 0 0 0 0 0 0 0 0 0 0 1 0 0 truyền với chi phí O(V3). L 1 1 1 1 1 1 1 0 0 1 1 1 1 M 1 1 1 1 1 1 1 0 0 1 1 1 1 Giải thuật Warshall thể hiện sự áp dụng chiến lược quy hoạch động vì sự tính toán căn cứ vào một hệ thức truy hồi (5.4) nhưng lại không xây dựng thành giải thuật đệ quy. Thay vào đó là một giải thuật lặp với sự hỗ trợ của một ma trận để lưu trữ các kết quả trung gian. 35
26. Giải thích giải thuật Warshall ◼ Giải thuật Warshall lặp V bước trên ma trận kế cận a, tạo ra một loại những ma trận: a(0), a(y-1),a(y), ,a(V) (5.4) ◼ Ý tưởng chính của giải thuật là ta có thể tính tất cả các phần tử trong mỗi ma trận a(y) từ ma trận đi trước nó a(y-1) trong loạt ma trận (4.1) ◼ Sau bước lặp thứ y, a[x, j] sẽ bằng 1 nếu và chỉ nếu có bất kỳ lối đi nào từ đỉnh x đến đỉnh j với những đỉnh trung gian mang chỉ số không lớn hơn y. Nghĩa là, x và j có thể là bất kỳ đỉnh nào nhưng những đỉnh trung gian trên lối đi phải nhỏ hơn hay bằng y. ◼ Tại bước lặp thứ y, ta tính các phần tử của ma trận a bằng công thức sau: ay[x,j] = ay-1[x,j] or (ay-1[x, y] and ay-1[y, j]) (5.5) Chỉ số y chỉ trị của một phần tử trong ma trận a sau bước lặp thứ y. 36
27. Giải thuật Floyd cho bài toán các lối đi ngắn nhất Đối với đồ thị có trọng số (có hướng hoặc không) ta có thể muối xây dựng một ma trận cho phép người ta tìm được lối đi ngắn nhất từ x đến y đối với mọi cặp đỉnh. Đấy là bài toán những lối đi ngắn nhất cho mọi cặp đỉnh (all-pairs shortest path problem). A 4 2 3 1 H I B 1 C G 1 1 Hình 5.7 2 2 1 1 1 D E J K 5 2 3 F 2 L M 1 37
28. Giải thuật Floyd Có thể dùng một phương pháp tương tự như phương pháp Warshall, mà được đưa ra bởi R. W. Floyd: for y : = 1 to V do for x : = 1 to V do if a [x, y] > 0 then for j: = 1 to V do if a [y, j] > 0 then if (a[x, j] = 0) or (a[x, y] + a[y, j] < a [x, j]) then a[x, j] = a[x, y] + a[y, j]; 38
29. Một thí dụ dùng giải thuật Floyd (cho đồ thi hình 5.7) A B C D E F G H I J K L M A 0 1 0 0 0 2 4 0 0 0 0 0 0 Ma trận kế cận B 0 0 0 0 0 0 0 0 0 0 0 0 0 ứng với bước C 1 0 0 0 0 0 0 0 0 0 0 0 0 khởi đầu của D 0 0 0 0 0 1 0 0 0 0 0 0 0 giải thuật Floyd E 0 0 0 2 0 0 0 0 0 0 0 0 0 F 0 0 0 0 2 0 0 0 0 0 0 0 0 G 0 0 1 0 1 0 0 0 0 1 0 0 0 H 0 0 0 0 0 0 3 0 1 0 0 0 0 Chú ý: Các phần tử trên I 0 0 0 0 0 0 0 1 0 0 0 0 0 đường chéo đều bằng 0. J 0 0 0 0 0 0 0 0 0 0 1 3 2 K 0 0 0 0 0 0 0 0 0 0 0 0 0 L 0 0 0 0 0 5 5 0 0 0 0 0 1 M 0 0 0 0 0 0 0 0 0 0 0 1 0 39
30. A B C D E F G H I J K L M Ma trận kế cận ứng A 6 1 5 6 4 2 4 0 0 5 6 8 7 với bước cuối của B 0 0 0 0 0 0 0 0 0 0 0 0 0 giải thuật Floyd C 1 2 6 7 5 3 5 0 0 6 7 9 8 D 0 0 0 5 3 1 0 0 0 0 0 0 0 Tính chất 5.3.2 Giải E 0 0 0 2 5 3 0 0 0 0 0 0 0 thuật Floyd để giải bài F 0 0 0 4 2 5 0 0 0 0 0 0 0 toán những lối đi G 2 3 1 3 1 4 6 0 0 1 2 4 3 ngắn nhất giữa H 5 6 4 6 4 7 3 2 1 4 5 7 6 những cặp có độ I 6 7 5 7 5 8 4 1 2 5 6 8 7 phức tạp tính toán J 10 11 9 11 9 12 8 0 0 9 1 3 2 O(V3). K 0 0 0 0 0 0 0 0 0 0 0 0 0 L 7 8 6 8 6 9 5 0 0 6 7 2 1 M 8 9 7 9 7 10 6 0 0 7 8 1 2 40
31. Giải thích giải thuật Floyd Giải thuật Floyd lặp V bước trên ma trận kế cận a, tạo ra một loại những ma trận: a(0), a(y-1),a(y), ,a(V) (5.6) Ý tưởng chính của giải thuật là ta có thể tính tất cả các phần tử trong mỗi ma trận a(y) từ ma trận đi trước nó, a(y-1) trong loạt ma trận. Sau bước lặp thứ y, a[x, j] sẽ chứa chiều dài nhỏ nhất của bất kỳ lối đi nào từ đỉnh x đến đỉnh j mà đi qua những đỉnh trung gian không mang chỉ số lớn hơn y. Nghĩa là, x và j có thể có là bất kỳ đỉnh nào nhưng những đỉnh trung gian trên lối đi phải nhỏ hơn hay bằng y. Tại bước lặp thứ y, ta tính các phần tử của ma trận a bằng công thức sau: ay[x,j] = min( ay-1[x,j], ay-1[x, y] + ay-1[y, j]) (5.7) Chỉ số y chỉ trị của một phần tử trong ma trận a sau bước lặp thứ y. 41
32. Công thức này được minh họa bằng hình vẽ sau đây. y ay-1[x,y] ay-1[y,j ] j x ay-1[x,j ] Giải thuật Floyd thể hiện sự áp dụng chiến lược quy hoạch động cho một bài toán tối ưu hóa vì sự tính toán căn cứ vào một hệ thức truy hồi (5.6) nhưng lại không xây dựng thành giải thuật đệ quy. Thay vào đó là một giải thuật lặp với sự hỗ trợ của một ma trận để lưu trữ các kết quả trung gian. 42
33. Cải tiến giải thuật Floyd ◼ Ta thường muốn biết lối đi ngắn nhất từ một đỉnh đến một đỉnh khác bao gồm những đỉnh trung giannào. ◼ Một cách để thực hiện điều này là dùng thêm một ma trận P, với P[i,j] chứa đỉnh k mà khiến giải thuật Floyd tìm được giá trị nhỏ nhất cho a[i,j]. ◼ Giải thuật Floyd cải tiến sẽ như sau: for i := 1 to V do for j:= 1 to V do P[i,j] := 0; for i := 1 to V do a[i,i]:= 0; 43
34. for y : = 1 to V do for x : = 1 to V do if a [x, y] > 0 then for j: = 1 to V do if a [y, j] > 0 then if (a[x, j] = 0) or (a[x, y] + a[y, j] < a [x, j]) then begin a[x, j] = a[x, y] + a[y, j]; P[x,j] := k; end Để in ra những đỉnh trung gian procedure path(x, j: int) trên lối đi ngắn nhất từ đỉnh x var k : int; đến đỉnh j, ta gọi thủ tục begin path(x,j) với path là một thủ k := P[x,j]; tục đệ quy được cho ở hình if k = 0 then return; bên. path(x,k); writeln(k); path(k,j); end 44
35. 2. Giải thuật tham lam Các giải thuật tối ưu hóa thường đi qua một số bước với một tập các khả năng lựa chọn tại mỗi bước. Một giải thuật tham lam thường chọn một khả năng mà xem như tốt nhất tại lúc đó. Tức là, giải thuật chọn một khả năng tối ưu cục bộ với hy vọng sẽ dẫn đến một lời giải tối ưu toàn cục. Vài thí dụ của giải thuật tham lam: - Bài toán xếp lịch cho các hoạt động - Bài toán cái túi dạng phân số - Bài toán mã Huffman - Giải thuật Prim để tính cây bao trùm tối thiểu 45
36. Bài toán xếp lịch cho các hoạt động (Activity- Selection Problem) Giả sử ta có một tập S = {1, 2, , n} gồm n hoạt động mà cùng muốn sử dụng cùng một tài nguyên, thí dụ như một giảng đưòng, mà chỉ có thể được dùng bởi một hoạt động tại một lúc. Mỗi hoạt động i có thời điểm bắt đầu si và một thời điểm kết thúc fi, mà si fi. Nếu được lựa chọn, hoạt động i diễn ra trong thời khoảng [si, fi). Hoạt động i và j là tương thích nếu thời khoảng [si, fi) và [sj, fj) không phủ lấp lên nhau (tức là, i và j là tương thích nếu si >= fj hay sj >= fi). Bài toán xếp lịch các hoạt động là chọn ra một chuỗi các hoạt động tương thích với nhau và có số hoạt động nhiều nhất. 46
37. Giải thuật tham lam cho bài toán xếp lịch các hoạt động Trong thủ tục áp dụng giải thuật tham lam để giải bài toán xếp lịch các hoạt động, ta giả sử rằng các hoạt động nhập vào được sắp theo thứ tự tăng của thời điểm kết thúc: f1 f2 fn. procedure GREED-ACTIVITY-SELECTOR(S, f) ; /* s is the array keeping the set of activities and f is the array keeping the finishing times */ begin n := length[s]; A := {1}; j: = 1; for i: = 2 to n do if si >= fj then /* i is compatible with all activities in A */ begin A: = A  {i}; j: = i end end 47
38. Thủ tục Greedy-activity-selector Hoạt động được chọn bởi thủ tục GREEDY-ACTIVITY- SELECTER thường là hoạt động với thời điểm kết thúc sớm nhất mà có thể được xếp lịch một cách hợp lệ. Hoạt động được chọn theo cách “tham lam” theo nghĩa nó sẽ để lại cơ hội để xếp lịch cho được nhiều hoạt độngkhác. Giải thuật tham lam không nhất thiết đem lại lời giải tối ưu. Tuy nhiên thủ tục GREEDY-ACTIVITY-SELECTOR thường tìm được một lời giải tối ưu cho một thể hiện của bài toán xếp lịch các hoạt động. 48
39. Hình 5.5 Một thí dụ i si fi của bài toán xếp lịch 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 11 12 14 49
40. Hai thành phần chính của giải thuật tham lam Có hai tính chất mà các bài toán phải có để có thể áp dụng giải thuật tham lam là: (1) tính chất lựa chọn tham lam và (2) tiểu cấu trúc tối ưu. Lựa chọn được thực hiện bởi giải thuật tham lam tùy thuộc vào những lựa chọn đã làm cho đến bây giờ, nhưng nó không tùy thuộc vào bất kỳ lựa chọn trong tương lai hay những lời giải của những bài toán con. Như vậy, một giải thuật tham lam tiến hành theo kiểu từ trên xuống, thực hiện mỗi lúc một lựa chọn tham lam. Tính chất tiểu cấu trúc tối ưu (Optimal Substructure) Một bài tóan có tính chất tiểu cấu trúc tối ưu nếu một lời giải tối ưu chứa trong nó những lời giải tối ưu cho những bài toán con. 50
41. Giải thuật tham lam so sánh với quy hoạch động Sự khác biệt giữa qui hoạch động và giải thuật tham lam khi dùng để giải bài toán tối ưu là rất tế nhị. Bài toán cái túi dạng 0-1 được định nghiã như sau: '‘Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy n loại món hàng có trọng lượng và giá trị khác nhau (món hàng thứ i có giá trị vi đô la và trọng lượng wi), nhưng chỉ có một cái túi với sức chứa về trọng lượng là M để mang các món hàng. Bài toán cái túi là tìm một tổ hợp các món hàng mà kẻ trộm nên chọn bỏ vào cái túi để đạt được một giá trị tối đa với những món hàng mà y lấy đi.”. Bài toán này được gọi là bài toán cái túi dạng 0-1 vì mỗi món hàng thì hoặc là lấy đi hoặc là bỏ lại, kẻ trộm không thể lấy đi chỉ một phần của món hàng. 51