Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 12

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!
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: Chương 12 NP-Ñaày Ñuû13.11.2004 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å.13.11.2004 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  S13.11.2004 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S13.11.2004 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.13.11.2004 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í duï: ta ñaõ eùp baøi toaùn toái öu ñöôøng ñi ngaén nhaát thaønh baøi toaùn quyeát ñònh PATH baèng caùch laøm chaän k thaønh moät tham soá cuûa baøi toaùn.13.11.2004 Ch. 12: NP-Completeness 6 Maõ hoaù (encodings)ª Ñeå moät chöông trình maùy tính giaûi moät baøi toaùn tröøu töôïng thì caùc thöïc theå cuûa baøi toaùn caàn ñöôïc bieåu dieãn sao cho chöông trình maùy tính coù theå ñoïc vaø “hieåu” chuùng ñöôïc.ª Ta maõ hoùa (encode) caùc thöïc theå cuûa moät baøi toaùn tröøu töôïng ñeå moät chöông trình maùy tính coù theå ñoïc chuùng ñöôïc. – Ví duï: Maõ hoaù taäp N = {0, 1, 2, 3, 4,...} thaønh taäp caùc chuoãi {0, 1, 10, 11, 100,...}. Trong maõ hoaù naøy, e(17) = 10001. – Maõ hoùa moät ñoái töôïng ña hôïp (chuoãi, taäp, ñoà thò,...) baèng caùch keát hôïp caùc maõ hoùa cuûa caùc thaønh phaàn cuûa noù.13.11.2004 Ch. 12: NP-Completeness 7 Maõ hoaù (tieáp)ª Moät baøi toaùn cuï theå laø moät baøi toaùn maø taäp caùc thöïc theå cuûa noù laø taäp caùc chuoãi nhò phaân.ª Moät giaûi thuaät giaûi moät baøi toaùn cuï theå trong thôøi gian O(T(n)) neáu, khi ñöa noù moät thöïc theå i coù ñoä daøi n =  i  , thì noù seõ cho ra lôøi giaûi trong thôøi gian O(T(n)).ª Moät baøi toaùn cuï theå laø coù theå giaûi ñöôïc trong thôøi gian ña thöùc neáu toàn taïi moät giaûi thuaät giaûi noù trong thôøi gian O(nk) vôùi moät haèng soá k naøo ñoù.13.11.2004 Ch. 12: NP-Completeness 8 Lôùp Pª Ñònh nghóa: Lôùp P (complexity class P) laø taäp caùc baøi toaùn quyeát ñònh cuï theå coù theå giaûi ñöôïc trong thôøi gian ña thöùc.13.11.2004 Ch. 12: NP-Completeness 9 Baøi toaùn tröøu töôïng vaø baøi toaùn cuï theåª Ta duøng maõ hoaù ñeå aùnh xaï caùc baøi toaùn tröøu töôïng ñeán caùc baøi toaùn cuï theå. – Cho moät baøi toaùn quyeát ñònh tröøu töôïng Q, Q aùnh xaï moät taäp caùc thöïc theå I ñeán {0, 1}, ta coù the ...