Mô tả:
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
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
voøng laëp for vôùi i = 3
1
4
1
5
1
4
6
1
4
7
1
4
8
1
4
9
1
4
8
10
1
4
8
11
1
29.01.04
1
2
8
1
0
4
4
8
3
4
5
6
7
8
9
11
10
11
12
13
14
thôøi gian
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
- Xem thêm -
.PDF 
4 
135 
103 
