Bài giảng Cấu trúc dữ liệu và giải thuật: Bài toán chọn hoạt động có nội dung trình bày về bài toán chọn hoạt động (activity-selection problem), giải thuật greedy cho bài toán chọn hoạt động, correctness của giải thuật greedy cho bài toán chọn hoạt động, . Mời các bạn cùng tham khảo chi tiết nội dung bài giả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. 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 j 1 4 for i 2 to n 5 do if si fj 6 then A A i 7 j i 8 return A 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 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 . 4
