Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 37 có nội dung trình bày về giải thuật xấp xỉ, bài toán che phủ đỉnh, một giải thuật xấp xỉ cho bài toán che phủ đỉnh, bài toán người bán hàng rong tổng quát, bài toán che phủ tập, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Giaûi Thuaät Xaáp Xæ Chapter 37 Approximation Algorithms Tieáp caän moät baøi toaùn NP-ñaày ñuû Neáu moät baøi toaùn laø NP-ñaày ñuû thì khoâng chaéc raèng ta seõ tìm ñöôïc moät giaûi thuaät thôøi gian ña thöùc ñeå giaûi noù moät caùch chính xaùc. Tieáp caän moät baøi toaùn NP-ñaày ñuû 1 Neáu caùc input coù kích thöôùc nhoû thì moät giaûi thuaät chaïy trong thôøi gian soá muõ vaãn coù theå thoaû maõn yeâu caàu 2 Thay vì tìm caùc lôøi giaûi toái öu coù theå tìm caùc lôøi giaûi gaàn toái öu trong thôøi gian ña thöùc. Chöông 37 2 Approximation Algorithms Giaûi thuaät xaáp xæ Moät giaûi thuaät xaáp xæ laø moät giaûi thuaät traû veà lôøi giaûi gaàn toái öu. Giaû söû chi phí cuûa lôøi giaûi 0. Goïi C laø chi phí cuûa lôøi giaûi toái öu. Moät giaûi thuaät xaáp xæ cho moät baøi toaùn toái öu ñöôïc goïi laø coù tæ soá xaáp xæ r n approximation ratio ratio bound neáu vôùi moïi input coù kích thöôùc n thì chi phí cuûa lôøi giaûi do giaûi thuaät xaáp xæ tìm ñöôïc seõ thoaû max C C C C r n . Chöông 37 3 Approximation Algorithms Giaûi thuaät xaáp xæ Chi phí cuûa lôøi giaûi do giaûi thuaät xaáp xæ tìm ñöôïc thoûa vôùi tæ soá xaáp xæ r n max C C C C r n Baøi toaùn toái ña 0 C C vaäy max C C C C C C r n . Chi phí cuûa lôøi giaûi toái öu r n laàn chi phí cuûa lôøi giaûi gaàn ñuùng. Baøi toaùn toái thieåu 0 C C vaäy max C C C C C C r n . Chi phí cuûa lôøi giaûi gaàn ñuùng r n laàn chi phí cuûa lôøi giaûi toái öu. Moät giaûi thuaät xaáp xæ coù tæ soá xaáp xæ r n ñöôïc goïi laø moät giaûi thuaät r n -xaáp xæ. Chöông 37 4 Approximation Algorithms Baøi toaùn che phuû ñænh Nhaéc laïi Moät che phuû ñænh vertex cover cuûa moät ñoà thò voâ höôùng G V E laø moät taäp con V V sao cho neáu u v E thì u V hay v V hoaëc caû hai V . Kích thöôùc cuûa moät che phuû ñænh laø soá phaàn töû cuûa noù. Baøi toaùn che phuû ñænh laø tìm moät che phuû ñænh coù kích thöôùc nhoû nhaát trong moät ñoà thò voâ höôùng ñaõ cho. Baøi toaùn naøy laø daïng baøi toaùn toái öu cuûa ngoân .
