Xem mẫu
- 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 i coù 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 i vaø j laø 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 1
- Giaûi thuaät greedy cho baøi toaùn choïn hoaït ñoäng
° Giaûi thuaät
– Giaû söû: f1 f2 … fn .
GREEDY-ACTIVITY-SELECTOR(s, f)
1 n length[s]
2 A {1}
3 j1
4 for i 2 to n
5 do if si fj
6 then A A {i}
7 ji
8 return A
29.01.04 2
- Chaïy GREEDY-ACTIVITY-SELECTOR leân moät ví duï
2
voøng laëp for vôùi i = 2
1
3
i si fi voøng laëp for vôùi i = 3
1
1 1 4 4
1
2 3 5 5
3 0 6 1 4
4 5 7 6
1 4
5 3 8 7
6 5 9 1 4
7 6 10 8
1 4
8 8 11 9
9 8 12 1 4 8
10 2 13 10
1 4 8
11 12 14 11
1 4 8
1 4 8 11
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 thôøi gian
29.01.04 3
- 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öõ A S 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öõ k laø hoaït ñoäng ñaàu tieân trong A.
Neáu k = 1 thì ta xong. Neáu k 1, ta xeùt B = A {k} {1}. Vì f1 fk,
neân B cuõng laø lôøi giaûi toái öu.
– Neáu A laø 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’ = {i S : si f1}.
29.01.04 4
nguon tai.lieu . vn
