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

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!
Nội dung trích xuất từ tài liệu:
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 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 j1 4 for i  2 to n 5 do if si  fj 6 then A  A  {i} 7 ji 8 return A29.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 gian29.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