Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 12 có nội dung trình bày về NP-đầy đủ, khái niệm bài toán, hình thức hóa khái niệm bài toán, bài toán trừu tượng, bài toán quyết định, bài toán tối ưu, mã hóa bài toán, mã hóa chuẩn, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | NP-Ñaày Ñuû Ch. 12 NP-Completeness 1 Vaøi khaùi nieäm cô baûn ª Baøi toaùn caùc tham soá caùc tính chaát maø lôøi giaûi caàn phaûi thoûa maõn ª Moät thöïc theå instance cuûa baøi toaùn laø baøi toaùn maø caùc tham soá coù trò cuï theå. Ch. 12 NP-Completeness 2 Hình thöùc hoùa khaùi nieäm baøi toaùn ª Ví duï baøi toaùn SHORTEST-PATH laø khoâng hình thöùc baøi toaùn tìm ñöôøng ñi ngaén nhaát giöõa hai ñænh cho tröôùc trong moät ñoà thò voâ höôùng khoâng coù troïng soá G V E . hình thöùc Moät thöïc theå cuûa baøi toaùn laø moät caëp ba goàm moät ñoà thò cuï theå vaø hai ñænh cuï theå. Moät lôøi giaûi laø moät daõy caùc ñænh cuûa ñoà thò . Baøi toaùn SHORTEST-PATH laø quan heä keát hôïp moãi thöïc theå goàm moät ñoà thò vaø hai ñænh vôùi moät ñöôøng ñi ngaén nhaát neáu coù trong ñoà thò noái hai ñænh SHORTEST-PATH I S Ch. 12 NP-Completeness 3 Baøi toaùn tröøu töôïng ª Ñònh nghóa moät baøi toaùn tröøu töôïng Q laø moät quan heä nhò phaân treân moät taäp I ñöôïc goïi laø taäp caùc thöïc theå instances cuûa baøi toaùn vaø moät taäp S ñöôïc goïi laø taäp caùc lôøi giaûi cuûa baøi toaùn Q I S Ch. 12 NP-Completeness 4 Baøi toaùn quyeát ñònh ª Moät baøi toaùn quyeát ñònh Q laø moät baøi toaùn tröøu töôïng maø quan heä nhò phaân Q laø moät haøm töø I ñeán S 0 1 0 töông öùng vôùi no 1 töông öùng vôùi yes . ª Ví duï baøi toaùn quyeát ñònh PATH laø Cho moät ñoà thò G V E hai ñænh u v V vaø moät soá nguyeân döông k. Ñaët i G u v k moät thöïc theå cuûa baøi toaùn quyeát ñònh PATH PATH i 1 yes neáu toàn taïi moät ñöôøng ñi giöõa u vaø v coù chieàu daøi k PATH i 0 no trong caùc tröôøng hôïp khaùc. Ch. 12 NP-Completeness 5 Baøi toaùn toái öu ª Moät baøi toaùn toái öu laø moät baøi toaùn trong ñoù ta caàn xaùc ñònh trò lôùn nhaát hay trò nhoû nhaát cuûa moät ñaïi löôïng. ª Ñoái töôïng cuûa lyù thuyeát NP-ñaày ñuû laø caùc baøi toaùn quyeát ñònh neân ta phaûi eùp recast caùc baøi toaùn toái öu thaønh caùc baøi toaùn quyeát ñònh. Ví
