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

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!
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 37 Giaûi Thuaät Xaáp Xæ Chapter 37Approximation 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.21.5.2004 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) .21.5.2004 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æ.21.5.2004 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 ngöõ NP-ñaày ñuû VERTEX-COVER = {G, k : ñoà thò G coù moät che phuû ñænh coù kích thöôùc k} .21.5.2004 Chöông 37 5 Approximation Algorithms Moät giaûi thuaät xaáp xæ cho baøi toaùn che phuû ñænh APPROX-VERTEX-COVER(G) 1 C 2 E’  E[G] 3 while E’   4 do xeùt (u, v) laø moät caïnh baát kyø cuûa E’ 5 C  C  {u, v} 6 taùch khoûi E’ taát caû caùc caïnh lieân thuoäc taïi u hay v 7 return C21.5.2004 Chöông 37 6 Approximation Algorithms Thöïc thi APPROX-VERTEX-COVER b c d b c d a e f g a e f gb c d b c da e f g a e f gb c d b c da e f g a e f g21.5.2004 Chöông 37 7 Approximation Algorithms Phaân tích APPROX-VERTEX-COVER Nhaän xeùt: Thôøi gian chaïy cuûa APPROX-VERTEX-COVER laø O(E). Ñònh lyù 37.1 APPROX-VERTEX-COVER laø moät giaûi thuaät 2-xaáp xæ trong thôøi gian ña thöùc.21.5.2004 Chöông 37 8 Approximation Algorithms Baøi toaùn ngöôøi baùn haøng rong vôùi baát ñaúng thöùc tam giaùc° Cho moät ñoà thò ñaày ñuû voâ höôùng G = (V, E) cuøng vôùi moät haøm chi phí c : E  Z+. Tìm moät chu trình hamilton (moät tour) cuûa G vôùi phí toån nhoû nhaát.° Ñieàu kieän: Haøm chi phí c: E  Z+ thoûa maõn baát ñaúng thöùc tam giaùc c(u, w)  c(u, v) + c(v, w), u, v, w  V . APPROX-TSP-TOUR(G, c) 1 choïn moät ñænh r  V[G] laøm moät ñænh “goác” 2 nuoâi lôùn moät caây khung nhoû nhaát T cho G töø goác r duøng giaûi thuaät MST-PRIM(G, c, r) 3 goïi L laø danh saùch caùc ñænh ñöôïc thaêm vieáng bôûi pheùp duyeät caây theo kieåu tieàn thöù töï 4 return chu trình hamilton H vieáng caùc ñænh theo thöù töï L21.5.2004 Chöông 37 9 Approximation Algorithms Thöïc thi APPROX-TSP-TOUR leân moät ví duï a d a d e e b f g b f g c c h h (a) ...