Bàn về tính đúng đắn của thuật toán Tham lam trong bài toán Lựa chọn công việc
Nguyễn Thị Chinh
Các thuật toán để giải bài toán tối ưu thường được chia làm nhiều bước, mỗi bước lại có một số lựa chọn. Thông thường với bài toán tối ưu, Quy hoạch động được xem là thuật toán tốt nhất cả về kĩ năng, tính đơn giản và hiệu quả. Ngược lại, tại mỗi bước, thuật toán tham lam luôn luôn tìm cách chọn đáp án tốt nhất có thể được. Điều đó có nghĩa là nó tạo ra các đáp án 'tối ưu địa phương' và hy vọng rằng nó sẽ dẫn tới phương án tối ưu cho cả bài toán ban đầu. Chúng ta hãy cùng xem cách giải quyết một bài toán tối ưu bằng thuật toán Tham lam nhé!
Ta biết rằng, thuật toán tham lam không phải lúc nào cũng đưa ra được đáp án tối ưu. Tuy nhiên, ở nhiều bài toán thì lại khác. Ta sẽ nghiên cứu một bài toán đơn giản nhưng quan trọng, bài toán 'Lựa chọn công việc' bằng thuật toán tham lam để thấy được hiệu quả của thuật toán này.
1. Bài toán lựa chọn công việc.
Bài toán phát biểu như sau: Giả sử ta có một tập S = { 1, 2,…, n} các công việc, tại mỗi thời điểm chỉ có thể lựa chọn một công viêc nhất định. Mỗi công việc i có thời gian bắt đầu là si và thời gian kết thúc là âi, với si≤ âi. Nếu được chọn, công việc i chiếm hết khoảng thời gian [si,âi]. Công việc i và công việc j gọi là 'tương thích' nếu khoảng thời gian [si,âi] và [sj,âj] là không gối chồng lên nhau (tức là si ≤âj hoặc sj ≤âi). Hãy chọn ra lượng công việc lớn nhất có thể thực hiện được. Chúng ta sẽ nhận thấy rằng thuật toán tham lam là phương pháp đơn giản và khá đơn giản để lựa chọn một tập hợp lớn nhất các công việc có thể thực hiện được.
Thuật toán tham lam cho bài toán này tôi chỉ viết ở dạng mã giả (pseudocode). Giả sử ta sẽ lưu thời gian bắt đầu công việc và kết thúc công việc ở hai mảng s và mảng â các công việc được đưa vào theo thứ tự tăng dần theo thời gian kết thúc công việc (nếu không ta có thể dùng các thuật toán để sắp xếp chúng theo thứ tự tăng dần!)
â1≤â2 ≤...≤ân . (1)
Procedure GREEDY-ACTIVITY-SELECTOR(s,f);
Begin
1 n ←length[s];
2 A ←{1};
3 j←1;
4 for i ←2 to n
5 do if si←âj
then begin
6 A ←hợp {i};
7 j←i;
end;
8 return A;
End;
Quá trình thực hiện của thuật toán được tiến hành dựa trên thời gian kết thúc của các công việc đã được sắp xếp như đã chỉ ra ở (1). Tập A để ghi nhận các công việc được chọn. Chỉ số j để ghi nhận công việc mới nhất được thêm vào A, fj là thời gian kết thúc của công việc mới thêm vào A. Vì các công việc trong A được sắp xếp không giảm theo thời gian kết thúc công việc nên fj là thời gian kết thúc muộn nhất của các công việc trong A:
âj = max{fk: Kthuộc A}.(2)
Dòng 2 - 3 lựa chọn công việc 1và đưa vào A, j =1. Dòng 4 − 7, xét qua tất cả các công việc và thêm vào A nếu nó tương thích với tất cả các công việc đã được chọn trong A. Để xét một công việc i có tương thích với các công việc trong A hay không ta chỉ cần xét xem thời gian bắt đầu si là không nhỏ hơn fj(thời gian kết thúc của công việc mới thêm vào A). Nếu nó thoả mãn thì thêm vào A ngược lại thì không thêm. Cứ như vậy, thủ tục GREEDY-ACTIVITY-SELECTOR làm việc khá hiệu quả, với độ phức tạp chỉ là O(n), với giả thiết ban đầu là công việc đã được sắp xếp theo thời gian kết thúc công việc tăng dần. Ta có thể mô tả thuật toán hoạt động theo hình vẽ dưới đây:
Hình 1: Quá trình thực hiện của thủ tục GREEDY-ACTIVITY-SELECTOR với 11 công việc như trên hình vẽ. Mỗi dòng tương ứng với với một lần thực hiện trong vòng lặp của dòng 4 − 7 trong thuật toán. Các công việc được chọn đưa vào A được thể hiện bằng hình chữ nhật màu đen. Nếu thời gian bắt đầu si của công việc i nhó hơn thời gian kết thúc fj của công việc j thì nó không được chọn Ngược lại, nó được đưa vào trong A.
2. Chứng minh tính đúng đắn của thuật toán
Thuật toán tham lam không phải lúc nào cũng đưa ra được đáp án tối ưu. Tuy nhiên, thủ tục GREEDY-ACTIVITY-SELECTOR luôn tìm được đáp án tối ưu cho mỗi trường hợp đầu vào của bài toán. Ta có khẳng định sau: Thuật toán GREEDY-ACTIVITY-SELECTOR luôn chọn đuợc số lượng công việc lớn nhất có thể.
Chứng minh: Giả sử tập các công việc là S = {1, 2,… , n}. Giả sử rằng các hoạt động này được sắp xếp theo thứ tự tăng dần của thời gian kết thúc công việc. Theo đó, công việc 1 có thời gian kết thúc sớm nhất. Ta sẽ chỉ ra rằng sẽ có một phương án tối ưu bắt đầu từ lựa chọn tham lam đó là lựa chọn công việc 1.
Giả sử rằng A là tập con của S là một phương án tối ưu với tập dữ liệu cho trước và các công việc trong A cũng được sắp xếp theo thứ tự tăng dần về thời gian kết thúc công việc. Giả sử công việc được chọn đầu tiên trong A là công việc k.Nếu k = 1 thì phương án tối ưu bắt đầu từ lựa chọn tham lam. Nếu k khác 1 (k > 1), ta sẽ chỉ ra rằng tồn tại một phương án tối ưu B bắt đầu từ lựa chọn tham lam, lựa chọn công việc 1. Lấy B = A − {k} hợp {1}. Vì f1 ≤fk,mọi công việc trong B là tách rời nhau (tương thích) và B có cùng lực lượng với A nên B cũng là một phương án tối ưu. Vậy B là phương án tối ưu có lựa chọn tham lam.
Hơn nữa, khi đã chọn công việc 1, công việc tiếp theo của bài toán là tìm phương án tối ưu để lựa chọn các công việc trong S tương thích với công việc 1. Điều đó có nghĩa là nếu A là một phương án tối ưu của bài toán ban đầu với tập công việc là S thì A’ = A − {1} phải là phương án tối ưu cho bài toán lựa chọn công việc với tập công việc là S’ = {i thuộc S: Si≥f1}. Tại sao? Tại vì nếu chúng ta có thể tìm một phương án B’ mà có nhiều công việc hơn A’ thì thêm công việc 1 vào B’ ta thấy B có nhiều công việc hơn A thì mâu thuẫn với giả thiết A là phương án tối ưu với tập S. Như vậy, với mỗi lựa chọn tham lam, ta lại đưa bài toán ban đầu về bài toán nhỏ hơn có cùng dạng với bài toán ban đầu. Theo phương pháp quy nạp theo số lần lựa chọn tham lam, việc tạo ra các lựa chọn tham lam ở mỗi bước cho ta phương án tối ưu cho bài toán ban đầu.
Như vậy, thuật toán đã được chứng minh là tối ưu. Công việc còn lại là chuyển thuật toán thành chương trình, đây không phải là việc khó khăn nữa. Các bạn thử xem nhé!
