Bài toán lựa chọn công việc và thuật toán tham lam

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;