29.01.04 1
Baøi toaùn choïn hoaït ñoäng (activity-selection problem)
°Cho
–Moät taäp caùc hoaït ñoäng S = {1, 2,…, n}
–Moät taøi nguyeân chung maø taïi moïi thôøi ñieåm noù ñöôïc duøng bôûi
nhieàu laém laø moät hoaït ñoäng
–Hoaït ñoäng icoù thôøi ñieåm baét ñaàu laø si vaø thôøi ñieåm chaám döùt laø
fi
–Neáu hoaït ñoäng i ñöôïc choïn thì i tieán haønh trong thôøi gian [si , fi )
–Hai hoaït ñoäng ivaø jlaø töông thích nhau (“compatible”) neáu
[si , fi ) vaø [sj , fj ) khoâng chaïm nhau.
°Baøi toaùn choïn hoaït ñoäng laø tìm moät taäp caùc hoaït ñoäng töông thích
nhau maø coù soá phaàn töû lôùn nhaát.
29.01.04 2
Giaûi thuaät greedy cho baøi toaùn choïn hoaït ñoäng
°Giaûi thuaät
–Giaû söû: f1f2… fn.
GREEDY-ACTIVITY-SELECTOR(s, f)
1nlength[s]
2A{1}
3j1
4for i2 to n
5do if sifj
6then AA{i}
7ji
8return A
29.01.04 3
Chaïy GREEDY-ACTIVITY-SELECTOR leân moät ví duï
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 sifi
voøng laëp for vôùi i= 2
voøng laëp for vôùi i= 3
29.01.04 4
Correctness cuûa giaûi thuaät greedy cho baøi toaùn choïn hoaït
ñoäng
°Ñònh lyù Giaûi thuaät GREEDY-ACTIVITY-SELECTOR tìm ñöôïc lôøi giaûi toái öu
cho baøi toaùn choïn hoaït ñoäng.
°Chöùng minh
–Goïi S= {1, 2,…, n} laø taäp hôïp caùc hoaït ñoäng. Caùc hoaït ñoäng ñöôïc xeáp
thöù töï theo thôøi ñieåm chaám döùt. Do ñoù hoaït ñoäng 1 coù thôøi ñieåm chaám
döùt sôùm nhaát.
–Ta chöùng minh coù lôøi giaûi toái öu baét ñaàu baèng hoaït ñoäng do choïn löïa
greedy, töùc laø baét ñaàu baèng hoaït ñoäng 1:
Giaû söõ AS laø lôøi giaûi toái öu, ta xeáp thöù töï caùc hoaït ñoäng trong A
theo thôøi ñieåm chaám döùt. Giaû söõ klaø hoaït ñoäng ñaàu tieân trong A.
Neáu k= 1 thì ta xong. Neáu k1, ta xeùt B= A{k} {1}. Vì f1fk,
neân Bcuõng laø lôøi giaûi toái öu.
–Neáu Alaø lôøi giaûi toái öu cho baøi toaùn nguyeân thuûy S, thì A’ = A{1} laø
lôøi giaûi toái öu cho baøi toaùn S’ = {iS: sif1}.