Bài giảng Giải thuật - Chương 2: Bài toán chọn hoạt động
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
2
3
4
5
6
7
8
n length[s]
A {1}
j 1
for i 2 to n
do if si fj
then A A {i}
j i
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
voøng laëp for vôùi i = 3
i
1
si
1
3
0
5
3
5
6
8
8
2
fi
4
1
1
1
1
1
1
1
1
1
1
4
2
5
5
3
6
4
4
4
4
4
4
4
6
4
7
5
8
7
6
9
8
7
10
11
12
13
8
9
9
8
8
8
8
10
10
11 12 14
11
11
4
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
4 trang
16320
Free
Bạn đang xem tài liệu "Bài giảng Giải thuật - Chương 2: Bài toán chọn hoạt động", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_giai_thuat_chuong_2_bai_toan_chon_hoat_dong.ppt
