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à s
i
và thời gian kết thúc là â
i
, với s
i
≤ â
i
. Nếu được chọn, công việc i chiếm hết khoảng thời
gian [s
i
,â
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 [s

(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, f
j
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 f
j
là thời gian kết thúc muộn nhất của các công việc trong A:
â
j
= max{f
k
: 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

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ì
f
1
≤f
k
,

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≥f
1
}. 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é!