Bài giảng Giải thuật - Chương 2: Greedy Algos

Bài toán chọn hoạt động (activity-selection problem) 
Cho 
Một tập các hoạt động S = {1, 2,, n } 
Một tài nguyên chung mà tại mọi thời điểm nó được dùng bởi nhiều lắm là một hoạt động 
Hoạt động i có thời điểm bắt đầu là s i và thời điểm chấm dứt là f i 
Nếu hoạt động i được chọn thì i tiến hành trong thời gian [ s i , f i ) 
Hai hoạt động i và j là tương thích nhau (“ compatible ”) nếu 
[ s i , f i ) và [ s j , f j ) không chạm nhau. 
Bài toán chọn hoạt động là tìm một tập các hoạt động tương thích nhau mà có số phần tử lớn nhất. 
29.01.04 
1 
Giải thuật greedy cho bài toán chọn hoạt động 
Giải thuật 
Giả sử: f 1  f 2    f n . 
G REEDY -A CTIVITY -S ELECTOR ( s , f ) 
1	 n  length [ s ] 
2	 A  {1} 
3	 j  1 
4	 for i  2 to n 
5	 do if s i  f j 
6	 then A  A  { i } 
7	 j  i 
8	 return A 
29.01.04 
2 
Chạy G REEDY -A CTIVITY -S ELECTOR lên một ví dụ 
 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 
1 
1 
1 
1 
1 
1 
1 
1 
1 
1 
1 
4 
4 
4 
4 
4 
4 
4 
4 
8 
8 
8 
8 
11 
2 
4 
3 
5 
6 
7 
8 
9 
10 
11 
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 thời gian 
 i s i f i 
vòng lặp for với i = 2 
vòng lặp for với i = 3 
29.01.04 
3 
Correctness của giải thuật greedy cho bài toán chọn hoạt động 
Định lý Giải thuật G REEDY -A CTIVITY -S ELECTOR tìm được lời giải tối ưu cho bài toán chọn hoạt động. 
Chứng minh 
Gọi S = {1, 2,, n } là tập hợp các hoạt động. Các hoạt động được xếp thứ tự theo thời điểm chấm dứt. Do đó hoạt động 1 có thời điểm chấm dứt sớm nhất. 
Ta chứng minh có lời giải tối ưu bắt đầu bằng hoạt động do chọn lựa greedy, tức là bắt đầu bằng hoạt động 1: 
Giả sữ A  S là lời giải tối ưu, ta xếp thứ tự các hoạt động trong A theo thời điểm chấm dứt. Giả sữ k là hoạt động đầu tiên trong A . 
Nếu k = 1 thì ta xong. Nếu k  1, ta xét B = A  { k }  {1}. Vì f 1  f k , nên B cũng là lời giải tối ưu. 
Nếu A là lời giải tối ưu cho bài toán nguyên thủy S , thì A’ = A  {1} là lời giải tối ưu cho bài toán S’ = { i  S : s i  f 1 }. 
29.01.04 
4