THUẬT TOÁN THAM LAM (GREEDY ALGORITHM)

Thuật toán tham lam
PHẦN 1: BÀI TOÁN CHỌN HOẠT ĐỘNG
1.1.Giới thiệu bài toán
Bài toán sắp xếp lịch cho nhiều hoạt động với ý nghĩa để có thể sử dụng chung một tài
nguyên (mỗi thời điểm chỉ có một hoạt động sử dụng tài nguyên chung), với mục tiêu là
sắp xếp sao càng có nhiều hoạt động tương thích sử dụng tài nguyên càng tốt.
Giả sử ta có một tập hợp S = {a
1,
a
2,
a
n
} là tập các hoạt động muốn sử dụng tài nguyên,
ví dụ một hội trường, chỉ mỗi một hoạt động tại mỗi thời điểm. Mỗi hoạt động a
i
sẽ có thời
điểm bắt đầu là s
i
và thời điểm kết thúc là f
i,
với điều kiện 0 ≤ s
i
< f
i
< ∞. Nếu

hoạt động a
i
được

chọn, thì nó sẽ độc chiếm tài nguyên trong khoảng thời gian [s
i,
f
i
). Hoạt động a
i
và a
j
được

gọi là tương thích lẫn nhau nếu như khoảng thời gian [s
i,
f
i
) và [a
j,
f
j
) là không giao
nhau (Ví dụ a
i
và a
j
là tương thích nếu s
i
≥ f
j
hoặc s
j
≥ f
i
). Trong bài toán

chọn hoạt động ta
phải chọn tập con lớn nhất của các hoạt động tương thích lẫn nhau. Chẳng hạn, xem tập S
của các hoạt động sau, mà ta có thể sắp xếp tăng dần theo thời điểm kết thúc.
i 1 2 3 4 5 6 7 8 9 10 11
S
i
1 3 0 5 3 5 6 8 8 2 12
F
i
4 5 6 7 8 9 10 11 12 13 14
Ta sẽ thấy một cách ngắn gọn là tại sao nó thuận lợi để xem xét các hoạt động trong
trình tự sắp xếp. Chẳng hạn như, một tập con {a
3,
a
9,
a
11
} bao gồm những hoạt động tương
thích lẫn nhau. Nó không phải là tập con lớn nhất, vì một tập con {a
1
, a
4,
a
8
, a
11
} là lớn hơn.
Thật ra {a
1
, a
4,
a
8
, a
11
} là tập con lớn nhất của các hoạt động tương thích lẫn nhau; một tập
con lớn nhất khác là {a
2
, a
4,
a
9
, a
11
}.
Ta sẽ giải quyết bài toán này trong một vài bước. Ta bắt đầu bởi việc đưa ra công thức
của giải pháp quy hoạch động đối với bài toán này trong đó ta tổng hợp các giải pháp tối
ưu đối với hai bài toán con để thiết lập giải pháp tối ưu của bài toán gốc. Ta có các lựa
chọn khi quyết định các bài toán để sử dụng trong một giải pháp tối ưu. Sau đó, ta sẽ nhận
thấy rằng ta chỉ cần một lựa chọn duy nhất - lựa chọn tham lam - và sau khi ta lựa chọn chỉ
còn một bài toán con, một bài toán con còn lại sẽ rỗng. Dựa trên những nhận xét này, ta sẽ
xây dựng một giải thuật tham lam đệ quy để giải quyết bài toán lập lịch hoạt động. Ta sẽ
hoàn thành quá trình xây dựng giải thuật tham lam bởi việc biến đổi giải thuật đệ quy sang
Trang 3
Thuật toán tham lam
giải thuật lặp. Mặc dù những bước ta thực hiện trong phần này thể hiện mối liên quan
nhiều hơn là tiêu biểu cho sự phát triển của phương pháp tham lam, chúng minh hoạ cho
mối quan hệ của phương pháp tham lam và quy hoạch động.
1.2. Cấu trúc con tối ưu của bài toán chọn hoạt động
Như đã đề cập ở trên, ta bắt đầu bằng phương quy hoạch động để giải quyết bài toán
lựa chọn hoạt động. Như ở chương 15, bước đầu tiên là tìm ra cấu trúc con tối ưu và sau đó
sử dụng nó để xây dựng một giải pháp tối ưu cho bài toán từ các giải pháp tối ưu cho các
bài toán con.
Ta nhận thấy rằng ở chương 15 ta cần định nghĩa một không gian thích hợp của bài
toán con. Ta hãy bắt đầu bằng việc định nghĩa các tập hợp:
S
ij
= {a
k
∈S : f
i
≤ s
k
<

f
k
≤ s
j
}
Sao cho S
ij
là một tập con của các hoạt động trong tập S mà có thể bắt đầu sau khi hoạt
động a
i
kết thúc và kết thúc trước hoạt động a
j
bắt đầu. Thật ra, S
ij
chứa tất cả các hoạt động
tương thích với a
i
và a
j
và cũng tương thích với tất cả các hoạt động hoàn thành không trễ
hơn a
i
và tất cả các hoạt động bắt đầu không sớm hơn a
j
bắt đầu. Để thuận tiện trong việc
biểu diễn bài toán, không mất tính tổng quát, ta thêm vào những hoạt động giả sử a
0
và a
n+1
với qui ước rằng f
0
= 0 và S
n+1
= ∞. Sau đó S = S
0 n+1
, và phạm vi của i và j được cho bởi 0 ≤
i, j ≤n+1.
Ta có thể giới hạn hơn nữa

phạm vi của i và j như sau. Giả sử rằng các hoạt động đó
được sắp xếp theo một thứ tự

tăng dần của thời điểm kết thúc:
f
0
≤ f
1
≤ f
2
≤ ≤f
n
≤ f
n+1
.

(16.1)
Ta dễ dàng thấy rằng S
ij
= Ø với i ≥ j. Tại sao? Giả sử rằng tồn tại hoạt động a
k
∈
S
ij
sao
cho i ≥ j, vì vậy a
i
kế tiếp a
j
trong thứ tự sắp xếp. Sau đó ta sẽ có
f
i
≤ s
k
< f
k
≤ s
j
< f
j
. Vì vậy, f
i
< f
j,
điều này mâu thuẫn với giả thiết rằng

a
i
kế tiếp a
j
trong thứ
tự sắp xếp. Ta có thể kết luận rằng,

ta sắp xếp các hoạt động theo thứ tự tăng dần của thời
điểm kết thúc, phạm vi

của các

bài toán con của ta là chọn một tập con cực đại của các hoạt
động tương thích lẫn nhau từ S
ij
với

0 ≤

i

< j

≤ n+1, biết rằng tất cả các S
ij
khác là đều rỗng.
Trang 4
Thuật toán tham lam
Để nhận ra

được cấu trúc con của bài toán chọn hoạt động,

ta xét một bài toán con khác
rỗng S
ij
, và giả sử rằng một giải pháp đối với S
ij
tồn tại một hoạt động a
k,
mà

f
i
≤ s
k
< f
k
≤ s
j.
Việc chọn hoạt động a
k
sẽ phát sinh ra hai bài toán con, S
ik
(những hoạt động mà bắt đầu
sau khi a
i
kết thúc và kết thúc trước khi a
k
bắt đầu) và S
kj
(những hoạt động mà bắt đầu sau
khi a
k
kết thúc và kết thúc trước khi a
j
bắt đầu), mỗi hoạt đó bao gồm một tập con của các
hoạt động trong S
ij
. Giải pháp của ta đối với bài toán S
ij
là tổng hợp hai giải pháp cho hai
bài toán con S
ik
và S
kj,
ứng với hoạt động

a
k
. Vì vậy số các hoạt động trong giải pháp đối
với S
ij
của ta là kích thước của bài toán S
ik
, cộng với kích thước của bài toán

S
kj
, cộng với
một (cho a
k
).
Cấu trúc con

tối ưu của bài toán này là như sau. Nếu A
ij
là giải pháp tối ưu cho bài toán
có chứa các hoạt động a
k
. Thì giải pháp

A
ik
cho S
ik
và A
kj
cho S
kj
được sử dụng trong S
ij
cũng tối ưu. Lý luận cắt và dán thông thường áp dụng. Thật vậy, nếu tồn tại một giải pháp
A'
ik
cho S
ik
chứa

nhiều hoạt động hơn A
ik
, ta có thể thay A
ik
bởi A'
ik
trong

A
ij
, ta sẽ tìm ra một
giải pháp khác đối với S
ij
có

nhiều hoạt động hơn A
ij
. Điều này trái với giả thiết ta co rằng
A
ij
là giải pháp tối ưu đối với S
ij
. Tương tự, nếu ta có một giải pháp A'
kj
đối với S
kj
với
nhiều hoạt động hơn A
kj
, ta có thể thay thế A
kj
bởi A'
kj
để đưa ra một giải pháp cho S
ij
với
nhiều hoạt động hơn A
ij
.
Bây giờ ta sử dụng cấu trúc con tối ưu để chỉ ra rằng có thể xây dựng một giải pháp tối
ưu cho bài toán từ những giải pháp tối ưu đối với những bài toán con. Ta đã thấy rằng

giải
pháp nào đó cho bài toán con khác rỗng S
ij
có chứa hoạt động a
k
, và giải pháp tối ưu bất kỳ
đó chứa trong nó những giải pháp tối ưu đối với bài toán con S
ik
và S
kj
. Vì vậy, ta có thể
xây dựng một tập con cực đại của những hoạt động tương thích lẫn nhau trong S
ij
bởi việc
phân chia bài toán thành hai bài toán con (tìm tập con lớn nhất của các hoạt động tương
thích lẫn nhau trong S
ik
và S
kj
), tìm ra những tập con lớn nhất A
ik
và A
kj
của những hoạt
động tương thích lẫn nhau đối với những bài toán con này, và thành lập tập con lớn nhất

A
ij
của các hoạt động tương thích lẫn nhau như:
A
ij
= A
ik
U {a
k
} U A
kj
(16.2)
Giải pháp tối ưu cho bài toán chính là giải pháp cho S
0,n+1
.
Trang 5
Thuật toán tham lam
1.3. Giải pháp đệ quy
Bước thứ hai trong việc phát triển giải pháp quy hoạch động là định nghĩa một cách đệ
quy giá trị của giải pháp tối ưu. Đối với những bài toán chọn hoạt động, gọi c[i,j] là số các
hoạt động trong tập con lớn nhất chứa các hoạt động tương thích lẫn nhau trong S
ij
. Ta có
c[i,j] = 0 khi S
ij
= Ø, hoặc c[i,j] = 0 khi i ≥ j.
Xét một tập con S
ij
khác rỗng. Như ta đã thấy, nếu a
k
được sử dụng trong tập con lớn
nhất các hoạt động tương thích lẫn nhau của S
ij
, Ta cũng sử dụng các tập con lớn nhất của
các hoạt động tương thích lẫn nhau cho các bài toán con S
ik
và S
kj.
Dùng công thức (16.2),
ta có công thức c[i,j] = c[i,k] + c[k,j] + 1.
Công thức đệ quy này cho thấy rằng ta biết giá trị của k, mà ta không biết. Ta có i-j-1
giá trị có thể chấp nhận cho k, cụ thể là k = i+1, , j-1. Vì tập con lớn nhất của S
ij
phải
dùng một trong những giá trị này của k, ta phải kiểm tra tất cả chúng để tìm ra giá trị tốt
nhất. Vì vậy công thức đệ quy đầy đủ của c[i,j]

trở thành:
{ }





≠++
=
=
<<
φ
φ
ij
jki
ij
Sifjkckic
Sif
jic
1],[],[max
0
],[
(16.3)
1.4. Biến đổi một giải pháp quy hoạch động thành một giải pháp tham lam
Tại điểm này, nó sẽ là một bài tập dễ hiểu lập một cái bảng, từ dưới lên, thuật toán quy
hoạch động dựa trên công thức (16.3). Thực ra, bài tập 16.1-1 yêu cầu bạn thực hiện điều
này. Có hai sự xác định then chốt, tuy nhiên, điều này cho phép ta đơn giản hoá giải pháp
của ta.
Định lý 16.1
Xét một bài toán con khác rỗng

S
ij
,và nếu a
m
là một hoạt động trong S
ij
có thời điểm kết
thúc sớm nhất:

f
m
= min{f
k
: a
k
∈
S
ij
}. Thì:
1. Hoạt động a
m
được sử dụng trong một tập con lớn nhất nào đó của các hoạt động
tương thích lẫn nhau của S
ij
.
2. Bài toán con S
im
là rỗng, do đó nếu chọn a
m
thì chỉ còn duy nhất bài toán con khác
rỗng

S
mj.
Trang 6
Thuật toán tham lam
Chứng minh
Ta chứng minh phần hai trước vì đơn giản hơn. Giả sử rằng S
im
là khác rỗng, do đó có
một hoạt động a
k
nào đó sao cho f
i
≤ s
k
< f
k
≤ s
m
< f
m
. Mà a
k
cũng nằm trong S
ij
và nó có thời
gian kết thúc sớm hơn a
m,
điều này mâu thuẫn với việc chọn a
m
Ta kết luận rằng S
im
là rỗng.
Để chứng minh phần thứ nhất, ta giả sử rằng, A
ij
là một tập con lớn nhất của các hoạt
động tương thích lẫn nhau của S
ij,
và ta sắp xếp các hoạt động của A
ij
theo thứ tự tăng dần
của thời điểm kết thúc. Gọi a
k
là hoạt động đầu tiên trong A
ij.
Nếu

a
k
= a
m
, thì ta đã chứng
minh được, chỉ ra rằng a
m
được sử dụng trong tập con lớn nhất nào đó của các hoạt động
tương thích lẫn nhau của S
ij
. Nếu

a
k
≠ a
m
, ta

xây dựng tập con

A’
ij =
A
ij
– {a
k
} ∪ {a
m
}
.
các
hoạt động trong A’
ij
thì tách rời nhau, các hoạt động trong A
ij
thì, a
k
là hoạt động kết thúc
đầu tiên trong A
ij,
và fm ≤ fk. Chú ý rằng A’
ij
có số

hoạt động giống như A
ij,
ta thấy rằng A’
ij
cũng là một tập con lớn nhất của các hoạt động tương thích lẫn nhau của S
ij
mà có chứa a
m.
Tại sao định lý 16.1 có giá trị? Quay về phần 15.3 cấu trúc con tối ưu làm thay đổi cách
nhiều bài toán được sử dụng trong giải pháp tối ưu để đến bài toán gốc và trong nhiều cách
chọn ta có xác định những bài toán con để sử dụng. Trong giải pháp quy hoạch động, hai
bài toán con được sử dụng trong giải pháp tối ưu, và có j-i-1 cách chọn khi giải quyết bài
toán con S
ij.
Định lý 16.1 giảm cả số lượng lớn đáng kể này: chỉ duy nhất một bài toán con
được sử dụng trong giải pháp tối ưu (một bài toán con khác thì là rỗng), và khi giải quyết
bài toán con S
ij,
ta cần xem duy nhất một cách chọn: một cách với thời gian kết thúc sớm
nhất trong S
ij
. May mắn thay, ta có thể dễ dàng xác định đây là hoạt động nào.
Cùng với

việc giảm số các bài toán con và số cách chọn, định lý 16.1 cung cấp một lợi
ích khác: ta có thể giải quyết mỗi bài toán con theo kiểu từ trên xuống (top-down), hơn là
kiểu từ dưới lên (bottom-up) sử dụng điển hình trong quy hoạch động. Để giải quyết bài
toán con S
ij
, ta chọn hoạt động a
m
trong S
ij
với thời gian kết thúc sớm nhất và thêm vào giải
pháp này một tập của các hoạt động dùng trong giải pháp tối ưu đối với bài toán con S
ij
.
Bởi vì ta biết rằng, có chọn a
m,
ta sẽ được sử dụng một giải pháp nào đó cho

S
mj
trong giải
pháp tối ưu của ta cho S
ij
, ta không cần giải quyết S
mj
trước việc giải quyết S
ij
. Để giải
quyết S
ij,
ta có thể chọn a
m
trước tiên như hoạt động trong S
ij
với thời điểm kết thúc sớm
nhất và sau đó giải quyết S
mj
.
Trang 7
Thuật toán tham lam
Cũng chú ý rằng có một mô hình đối với những bài toán con mà ta giải quyết. Bài toán
ban đầu của ta là S =S
0,n+1
. Giả sử rằng

chọn a
m1
là hoạt động trong S
0,n+1
với thời điểm kết
thúc sớm nhất. (Từ việc sắp xếp các hoạt động theo thứ tự thời điểm kết thúc tăng dần và f
0
= 0,

ta phải có m
1
= 1.) Bài toán con tiếp theo là S
m1,n+1.
Bây giờ giả sử rằng ta chọn a
m2
là
hoạt động trong S
m1,n+1
với thời điểm kết thúc sớm nhất. (Nó không cần thiết trong trường
hợp m
2
= 2). Bài toán con tiếp theo là S
m2,n+1.
Tiếp theo, ta thấy rằng mỗi bài toán con sẽ có
dạng S
i
m
,n+1
cho

số hoạt động m
i
nào đó.

Tóm lại, mỗi bài toán con gồm có các

hoạt động
cuối cùng để kết thúc, và một số các hoạt động biến đổi từ bài toán con này đến bài toán
con khác.
Cũng có một mô hình đối với các hoạt động mà ta chọn. Bởi vì ta luôn luôn chọn hoạt
động với thời điểm kết thúc sớm nhất trong S
i
m
,n+1,
thời điểm kết thúc của các

hoạt động
được chọn qua tất cả các bài toán con sẽ làm

gia tăng nghiêm trọng thời gian. Tuy nhiên,

ta
có thể xem như mỗi hoạt động là một toàn diện, trong việc sắp xếp tăng dần của thời điểm
kết thúc.
Hoạt động a
m
mà ta chọn khi giải quyết một bài toán con thì luôn là một hoạt động với
thời điểm kết thúc sớm nhất mà có thể được lập lịch hợp lý. Hoạt động được chọn như vậy
là chọn lựa “tham lam” trong hướng này, qua trực giác, nó để lại nhiều cơ hội có thể cho
những hoạt động còn lại để lập lịch. Đó là, lựa chọn tham lam là một cách mà cực đại hoá
số lượng đáng kể của thời gian còn lại chưa

lập

lịch.
1.5. Giải pháp tham lam đệ quy
Bây giờ ta đã thấy cách tổ chức hiệu quả giải pháp quy hoạch động, và cách xử lý nó
theo phương pháp từ trên xuống, ta xem một giải thuật mà nó hoạt động một cách thuần
tuý trong thuật toán tham lam, kiểu từ trên xuống. Dễ hiểu, một giải thuật đệ quy như là
thủ tục RECURSIVE-ACTIVITY-SELECTOR. Nó lấy thời điểm bắt đầu và kết thúc của
các hoạt động, được trình bày như các mảng s và f, xem như những chỉ số bắt đầu i và n
mà nó định nghĩa bài toán con S
i,n+1
nó là để giải quyết. (Tham số n chỉ hoạt động thực tế
cuối cùng a
n
trong bài toán con và không chỉ hoạt động không có thật a
n+1
mà nó cũng ở
trong bài toán con). Nó trả về một tập lớn nhất của các hoạt động tương thích lẫn nhau
trong S
i,n+1
.Ta cho rằng n hoạt động đưa vào được sắp xếp theo thời điểm kết thúc tăng
Trang 8
Thuật toán tham lam
dần, theo công thức (16.1). nếu không, ta có thể sắp xếp chúng theo thứ tự này với độ phức
tạp O(nlgn), phá vỡ sự ràng buộc một cách tuỳ tiện. Lời gọi ban đầu là

RECURSIVE-
ACTIVITY-SELECTOR(s,f, 0, n).
RECURSIVE-ACTIVITY-SELECTOR(s,f,i,n)
1 mi+1
2 while m
≤
n and s
m
<f
i
Tìm hoạt động đầu tiên trong S
i,n+1
3 do m m+1
4 if m<n
5 Then return {a
m
}
∪
RECURSIVE-ACTIVITY-SELECTOR(s,f,m,n)
6 else return
∅
Minh hoạ 16.1 chỉ ra sự thực hiện của thuật toán. Trong việc gọi đệ quy của
RECURSIVE-ACTIVITY-SELECTOR(s,f,i,n), vòng lặp while của dòng 2-3 tìm kiếm hoạt
động đầu tiên trong vòng lặp ví dụ a
i+1
, a
i+2
, …, a
n,
cho đến khi nó tím thấy hoạt động đầu
tiên a
m
mà tương thích với a
i,
một

hoạt động như vậy có S
m
≥
f
i
. Nếu vòng lặp giới hạn bởi
nó tìm thấy một hoạt động như vậy giải thuật quay lại dòng 5 sự kết hợp của {am} và tập
con cực đại của S
m,n+1
quay lại bởi việc gọi đệ quy RECURSIVE-ACTIVITY-
SELECTOR(s,f,m,n). Một cách lựa chọn, vòng lặp có thể giới hạn bởi m>n, trong trường
hợp này ta đã có kiểm tra tất cả các hoạt động mà không tìm thấy một hoạt động nào tương
thích với a
i
. Trong trường hợp này S
i,n+1
=
∅
, vì vậy giải thuật sẽ trả về
∅
ở dòng 6.
1.6. Giải pháp tham lam lặp
Ta dễ dàng chuyển đổi giải thuật đệ quy thành giải thuật lặp. Giải thuật RECURSIVE-
ACTIVITY-SELECTOR thì hầu như “đệ qui yếu“ (xem bài toán 7-4): nó kết thúc với lời
gọi đệ quy chính nó theo một sự thực hiện kết hợp. Dễ dàng để thay đổi một giải thuật đệ
qui yếu thành giải thuật lặp, thật ra, một số trình biên dịch cho ngôn ngữ lập trình bất kỳ
thực hiện công việc này một cách tự động. Như đã được viết, RECURSIVE-ACTIVITY-
SELECTOR thực hiện cho các bài toán con S
i,n+1
…, những bài toán con mà có các hoạt
động kết thúc cuối cùng.
Giải thuật GREEDY-ACTIVITY-SELECTOR là một phiên bản lặp của giải thuật
RECURSIVE-ACTIVITY-SELECTOR, ở đây cũng giả sử các hoạt động đầu vào được
Trang 9
Thuật toán tham lam
sắp xếp theo thời điểm kết thúc tăng dần. Nó tập hợp các hoạt động được chọn vào một tập
A và quay lại tập này khi nó đã được thực hiện xong.
Trang 10
Thuật toán tham lam
Hình 16.1 Sự thực hiện của RECURSIVE-ACTIVITY-SELECTOR trong hoạt động 11
được cho sớm hơn. Các hoạt động đã được xem

trong mỗi lời đệ quy xuất hiện giữa những
đường kẻ ngang. Hoạt động không có thật a
0
kết thúc tại thời điểm 0, và trong lời gọi ban
đầu RECURSIVE-ACTIVITY-SELECTOR (s,f,0,11), hoạt động a
1
được chọn. Trong mỗi
lời gọi đệ quy, những hoạt động mà đã được chọn được tô đen, và các hoạt động tmàu tô
trắng đang được xem xét. Nếu thời gian bắt đầu của một hoạt động xảy ra trước thời gian
kêt thúc của hoạt động mới được chọn (mũi tên giữa chúng chỉ sang trái), nó bị loại. Trái
lại (mũi tên chỉ trực tiếp hay qua phải), nó được chọn. Lời gọi đệ quy cuối cùng,
RECURSIVE-ACTIVITY-SELECTOR (s, f, 0, 11) trả về Ø. Tập kết quả

của các hoạt động
được chọn là{a
1
, a
4
, a
8
, a
11
}.
GREEDY-ACTIVITY-SELECTOR(s,f)
1 n ← length[s]
2 A ← {a1}
3 i ← 1
4 for m ← 2 to n
5 do if sm≥fi
6 Then A ← A ∪ {am}
7 i ← m
8 Return A
Giải thuật thực hiện như sau. Biến i đánh số các phần tử thêm vào A gần nhất, tương
ứng đối với hoạt động a
i
trong phiên bản đệ quy. Giả sử các hoạt động được sắp xếp theo
thứ tự tăng dần của thời điểm kết thúc, f
i
luôn là thời điểm kết thúc lớn nhất

của hoạt động
nào đó trong A. Điều đó là:
f
i
= max{f
k
: a
k
∈
A}

(16.4)
Dòng 2-3 chọn hoạt động a
i,
ban đầu A chỉ chứa chỉ một hoạt động này, và khởi đầu i là
chỉ số hoạt động này. Vòng lặp for ở các dòng 4-7 tìm thấy hoạt động kết thúc sớm nhất
trong

S
i
,n+1. Vòng lặp xem xét mỗi hoạt động a
m
trong vòng lặp và thêm a
m
vào A nếu nó
Trang 11
Thuật toán tham lam
tương thích với tất cả các hoạt động được chọn trước đó. Một hoạt động như vậy là hoạt
động kết thúc sớm nhất

trong S
i
,n+1. Để thấy nếu hoạt động a
m
là tương thích với mỗi hoạt
động hiện tại trong A, nó đáp ứng bởi phương trình (16.4) để kiểm tra (dòng 5) rằng thời
điểm bắt đầu của nó S
m
thì không sớm hơn thời điểm kết thúc f
i
của hoạt động thêm vào A
gần đây nhất. nếu hoạt động a
m
tương thích, thì các dòng 6-7

thêm hoạt động a
m
vào A và
thiết lập i đến m. Tập A quay lại bởi lời gọi GREEDY-ACTIVITY-SELECTOR(s,f) là
chính xác tập được quay lại bởi lời gọi RECURSIVE-ACTIVITY-SELECTOR(s,f, 0, n ).
Giống như phiên bản đệ quy, GREEDY-ACTIVITY-SELECTOR lập lịch một tập của
n hoạt động với độ phức tạp là O(n) thời gian, giả sử rằng các hoạt động ban đầu đã được
sắp xếp

theo thời điểm kết thúc của chúng.
Trang 12

Xem chi tiết: THUẬT TOÁN THAM LAM (GREEDY ALGORITHM)