Bài giảng Giải thuật nâng cao: Giải thuật xấp xỉ - Ngô Quốc Việt

GIẢI THUẬT XẤP XỈ TS. NGÔ QUỐC VIỆT 2015 Nội dung 1. Nhắc lại NP và các vấn đề liên quan 2. Giới thiệu giải thuật xấp xỉ 3. Minh họa giải thuật xấp xỉ với bài toán phủ đỉnh, TSP. 4. Tóm tắt Giải thuật nâng cao-Giải thuật xấp xỉ 2 Bài toán NP • Giải thuật hiệu quả: xác định lời giải tối ưu trong thời gian đa thức • Tuy nhiên, hầu hết các bài toán tối ưu là NP khó. Nghĩa là không tồn tại giải thuật hiệu quả để giải. • NP là một trong những complexity class cơ bản. • NP: nondeterministic polynomial time. Giải thuật nâng cao-Giải thuật xấp xỉ 3 Bài toán NP • P: thuật giải thời gian đa thức. Lớp bài toán P có tính chất bao đóng chính xác (tính cộng, tính nhân). • NP: tập các bài toán quyết định (trả lời YES hoặc NO) theo đó một số instances cụ thể của bài toán đang xét được giải và kiểm chứng (verifier) trong thời gian đa thức. • NP = Problems with Efficient Algorithms for Verifying Proofs/Certificates/Witnesses • Định nghĩa: NP là lớp các vấn đề có efficient verifiers, i.e. có giải thuật đa thức để kiểm chứng lời giải đã cho là đúng Giải thuật nâng cao-Giải thuật xấp xỉ 4 Bài toán NP • Phần lớn các bài toán thực tế là NP. Có thể efficiently verify nếu given short proof là valid, nhưng không tìm được efficient algorithm để giải. • • Lớp NP là extremely interesting. • Hầu hết các vấn đề trong CS, math, biology, physics, chemistry, economics, management, sociology, business, v.v, đều thuộc lớp NP. • Xem thêm compendium of NP optimization problems. Giải thuật nâng cao-Giải thuật xấp xỉ 5 Verifier V của bài toán NP-ví dụ • Xét bài toán tìm subset có tổng bằng zero (hay hằng số bất kỳ). • Nhận xét: số lượng các subset của tập hợp là lũy thừa (bao nhiêu?) • Tuy nhiên: cho subset cụ thể  dễ dàng kiểm chứng (verify) tổng các phần tử của nó là zero. Giải thuật kiểm chứng tổng zero của một subset được gọi là verifier. Giải thuật nâng cao-Giải thuật xấp xỉ 6 Cận dưới của NP problem • Xem: https://www.youtube.com/watch?v=K2- Y4a3BtSE • Reductions: giải một yêu cầu dựa trên các hàm hay problem khác như Subroutine/Oracle/Black Box. Không quan tâm đến độ phức tạp subroutine. • Giải thuật reduction A có sử dụng hàm O được ký hiệu: 퐴푂 • Vấn đề Q là black-box reducible thành O và viết 푄 ≤푇 푂 iff tồn tại giải thuật A sao cho mọi input x, thì 푄 푥 = 퐴푂(푥) • Nếu A chạy trong thời gian đa thức thì được gọi là polynomial-time black-box reduction, ký hiệu 푃 푄 ≤푇 푂. (Subscript T thể hiện ”Turing”) Giải thuật nâng cao-Giải thuật xấp xỉ 7 Cận dưới của NP problem • Vấn đề Q là many-one reducible to problem O và viết 푄 ≤푚 푂 iff có giải thuật A sao cho mọi input x, thì 푄 푥 = 푂 퐴 푥 • Nếu reduction algorithm A là polynomial time thì được gọi là polynomial-time many-one reduction, 푃 ký hiệu 푄 ≤푚 푂 • Nếu có polynomial-time many-one reduction từ vấn đề A thành NP problem B, thì A thuộc lớp NP. Giải thuật nâng cao-Giải thuật xấp xỉ 8 NP-complete • NP-complete là tập các vấn đề vừa NP, vừa NP-khó. • A là NP-complete iff • A là bài toán NP, và • Mọi bài toán B thuộc lớp NP, thì B là polynomial- 푝 time many-one reducible to A 퐵 ≤푚 퐴 • Nếu problem là NP-complete, thì không tồn tại polynomial-time algorithm để tìm nghiệm tối ưu • Thường sử dụng giải thuật xấp xỉ, tham lam, heuristic, để giải các bài toán NP. Giải thuật nâng cao-Giải thuật xấp xỉ 9 NP & liên quan Giải thuật nâng cao-Giải thuật xấp xỉ 10 NP-complete: ví dụ heuristic/text/class/more-np.html https://en.wikipedia.org/wiki/List_of_NP- complete_problems Yêu cầu: Anh/Chị đọc và trình bày 2 bài viết trên Giải thuật nâng cao-Giải thuật xấp xỉ 11 Giới thiệu giải thuật xấp xỉ • Giải thuật xấp xỉ xác định lời giải xấp xỉ của các bài toán tối ưu • Thường dùng cho các vấn đề NP-khó • Khác với giải thuật heuristic (chỉ cần lời giải đủ tốt, và đủ nhanh) • Giải thuật xấp xỉ cần xác định rõ chất lượng xấp xỉ, độ phức tạp. • Ví dụ: giải thuật xấp xỉ cho bài toán phủ đỉnh. Giải thuật nâng cao-Giải thuật xấp xỉ 12 Định nghĩa giải thuật xấp xỉ • Giải thuật xấp xỉ  cho bài toán tối ưu là giải thuật hiệu quả (thời gian đa thức) cho mọi instance của vấn đề sao cho lời giải nằm trong ngưỡng  so với lời giải tối ưu thực sự. •  : là tỉ lệ xấp xỉ (approximation ratio), hay thừa số xấp xỉ (approximation factor). • Định nghĩa: approximation ratio 흆 풏 • Chi phí của optimal solution là C*, chi phí của approximation algorithm là C, thì 퐶 퐶∗ • 흆 풏 ≥ 푚푎푥( , ) 퐶∗ 퐶 • Gọi là: (n)-approximation algorithm. Giải thuật nâng cao-Giải thuật xấp xỉ 13 Định nghĩa giải thuật xấp xỉ • Vấn đề Maximization thì 퐶∗/휌(푛) ≤ 퐶 ≤ 퐶∗ • Vấn đề Minimization thì 퐶∗ ≤ 퐶 ≤ 휌(푛). 퐶∗ • ρ(n) không nhỏ hơn 1. • 1-approximation algorithm là optimal solution • Mục tiêu là tìm polynomial-time approximation algorithm với small constant approximation ratios Giải thuật nâng cao-Giải thuật xấp xỉ 14 Approximation scheme • Approximation scheme là approximation algorithm thêm tham số Є>0, sao cho với Є>0 xác định thì scheme là (1+Є)-approximation algorithm. • Polynomial-time approximation scheme: runs in time polynomial in the size of input. • Khi Є giảm, thì thời gian thực hiện có thể tăng 2 nhanh, ví dụ 푂 푛 휖 Giải thuật nâng cao-Giải thuật xấp xỉ 15 Phủ đỉnh • 퐺 = (푉, 퐸) là đồ thị, V={tập đỉnh}, E={tập cạnh} • 푆 ⊆ 푉 là một phủ, nếu ∀ (푢, 푣) ∈ 퐸, thì 푢 ∈ 푆, hoặc 푣 ∈ 푆 hoặc 푢, 푣 ∈ 푆. • Ví dụ: Phủ đỉnh S Giải thuật nâng cao-Giải thuật xấp xỉ 16 Một số ứng dụng của phủ đỉnh • Bioinformatics • Cơ sở cho novo genome assembly sử dụng phương pháp overlap-consensus (liên ứng). CABOG, Celera, xây dựng overlap graph của nhiều whole-genome shotgun reads, với each vertex ứng với read và cạnh biểu diễn mutual overlap giữa hai reads • SNP Assembly Problem • Computer network securities • Mô phỏng sự lan truyền của worm máy tính nhằm tìm giải pháp bảo vệ mạng máy tính lớn. Giải thuật nâng cao-Giải thuật xấp xỉ 17 Phủ đỉnh • OPTIMIZATION VERSION: • INPUT: graph G • OUTPUT: vertex cover S of minimum-size (số đỉnh ít nhất) • DECISION VERSION: • INSTANCE: graph G, integer k • QUESTION: does G have vertex cover of size  k Giải thuật nâng cao-Giải thuật xấp xỉ 18 Phủ đỉnh • Dạng bài toán NP-Complete • Sử dụng dạng giải thuật tham lam, hoặc xấp xỉ để giải quyết • Yêu cầu: Sử dụng chiến lược tham lam để giải bài phủ đỉnh. Trình bày thuật giải, cho biết độ phức tạp, và cài đặt chương trình minh họa. Giải thuật nâng cao-Giải thuật xấp xỉ 19 Phủ đỉnh-xấp xỉ Giải thuật 1 1. Chọn cạnh A bất kỳ, bỏ tất cả các cạnh có nối đến hai đỉnh của A ( kể cả cạnh A) 2. Chọn cạnh khác & lặp lại bước 1 đến khi mọi cạnh bị loại bỏ. vertex-cover tìm được theo giải thuật 1, thường gấp đôi phủ đỉnh tối ưu Giải thuật nâng cao-Giải thuật xấp xỉ 20 Phủ đỉnh-xấp xỉ-giải thuật 1 Near Optimal Optimal size=6 Size=3 Giải thuật nâng cao-Giải thuật xấp xỉ 21 Phủ đỉnh-xấp xỉ-giải thuật 1 1 2 3 4 5 6 7 Not cover 1 2 3 4 5 6 7 Giải thuật nâng cao-Giải thuật xấp xỉ 22 Phủ đỉnh-xấp xỉ-giải thuật 1 1 2 3 Cover Size=4 4 5 6 7 1 2 3 Cover Size=7 4 5 6 7 Giải thuật nâng cao-Giải thuật xấp xỉ 23 Phủ đỉnh-xấp xỉ-giải thuật 1 1 2 3 Cover Size=5 4 5 6 7 1 2 3 Cover Size=3 4 5 6 7 Giải thuật nâng cao-Giải thuật xấp xỉ 24 Phủ đỉnh-xấp xỉ-giải thuật 1 APPROX-VERTEX-COVER là 2-approximate algorithm • Gọi c là phủ đỉnh xấp xỉ, và c* là phủ đỉnh tối ưu, A là 푐 tập cạnh của lệnh 4. Cần chứng minh ≤ 2. 푐∗ • Lệnh 5 thêm cả hai đỉnh, trong khi chỉ cần thêm một hoặc hai đỉnh trên • Không có hai cạnh trong A, phủ cùng một đỉnh trong c* (vì đã bị xóa-lệnh 6)  푐∗ ≥ 퐴 푐 • Vì vậy: ≤ 2. 푐∗ Giải thuật nâng cao-Giải thuật xấp xỉ 25 Phủ đỉnh-xấp xỉ-giải thuật 1 1 2 3 훼 = 푀푎푥(6/3, 3/6) = 2 4 5 6 7 1 2 3 훼 = 푀푎푥(4/3, 3/4) = 1.33 4 5 6 7 Giải thuật nâng cao-Giải thuật xấp xỉ 26 Phủ đỉnh-xấp xỉ Giải thuật 2 1. Chọn đỉnh v có bậc lớn nhất, cho v vào S. 2. Xóa mọi cạnh có nối với v. 3. Tiếp tục bước 1, 2 đến khi không còn cạnh nào (ln n)-approximation Giải thuật 3 1. Tìm matching M tối đại trong G. 2. Với mỗi cạnh 푢, 푣 ∈ 푀, thêm hai đỉnh u, v vào S. Giải thuật nâng cao-Giải thuật xấp xỉ 27 Phủ tập hợp-ví dụ • Một khu quy hoạch (có nhiều khu phố) cần xác định các vị trí xây trường với hai ràng buộc • Trường phải trong khu phố (town) • Không học sinh/phụ huynh nào phải đi qua xa (vd: 10km) từ nhà đến trường Các khu phố Khu phố trong phạm vi 10km • Câu hỏi: cần xây tối thiểu bao nhiêu trường? • Yêu cầu trên có thể giải thông qua khái niệm phủ tập hợp. Giải thuật nâng cao-Lý thuyết số 28 Phủ tập hợp-định nghĩa • Cho tập phổ biến 푈 = 푢1, 푢2, , 푢푛 • Gọi 푆1, 푆2, , 푆푘 ⊆ 푈 là các tập con có các trọng số tương ứng 푐1, 푐2, , 푐푛 • Mục tiêu: cần tìm 퐼 = 1,2, , 푚 sao cho cực tiểu 푖 푐푖 và 푖 푆푖 = 푈. • Hỏi: U, Si, ci trong bài toán xây các trường? • 푈 ={các town trong khu quy hoạch} • Với mỗi khu phố x, Sx là tập các town trong phạm vi 10km. Trường tại x sẽ phủ các town này • cx=1, x ? Giải thuật nâng cao-Lý thuyết số 29 Phủ tập hợp-giải thuật greedy • Chọn Si chứa nhiều town nhất chưa được phủ • Lặp lại cho đến khi các Si được chọn phủ U. • Ví dụ xây trường • Chọn Sa, Sa chứa a, b, d, e, k, i, h. • Chọn Sf hoặc Sg, vì chứa f, g. • Chọn Sc và Sj chứa chính nó. • 푖 푐푖 = 4. • Nhận xét: có thể chọn giải pháp tốt hơn? • Xây trường tại b, e, và i là giải pháp tốt hơn Giải thuật nâng cao-Lý thuyết số 30 Phủ tập hợp-giải thuật greedy 1. 퐶 = *+ 2. While 퐶 ≠ 푈 Tìm tập S có cost nhỏ nhất 푐(푆) Đặt 훼 = 푆−퐶 Với mỗi 푒 ∈ 푆\C, đặt 푝푟푖푐푒(푒) = 훼 퐶 = 퐶 ∪ 푆 3. Ouput S Giải thuật nâng cao-Lý thuyết số 31 SC là bài toán NP-complete • Định lý: Set Cover (SC) là NP-complete • Chứng minh: INSTANCE: Cho universe U n phần tử, tập các subset của U, S = {S1, , Sm}, và số nguyên dương b QUESTION: Tồn tại tập 퐶 ⊆ 1,2, , 푚 , |C| ≤ b, sao cho 푆푖 = 푈 푖∈퐶 Subcollection 푆푖 | 푖 ∈ 퐶 thỏa điều kiện trên là set cover của U Giải thuật nâng cao-Lý thuyết số 32 SC là bài toán NP-complete (tt) 1. Cần chứng minh SC thuộc NP. Dễ dàng kiểm chứng điều kiện YES của instance trên. Nghĩa là, cho subcollection C, nếu |퐶| ≤ 푏 và hội của các tập trong C chứa mọi phần tử của U theo thời gian đa thức. 2. Để chứng minh định lý, cần phải chứng minh Vertex Cover (VC) ≤p Set Cover (SC) Cho instance C của VC (undirected graph G=(V,E) và số nguyên dương j), chúng ta cần xây dựng C’ của SC trong thời gian đa thức sao cho C là satisfiable iff C’ là satisfiable. Giải thuật nâng cao-Lý thuyết số 33 SC là bài toán NP-complete (tt) • Construction: Đặt U = E. Định nghĩa n phần tử của U và tập S như sau: • Đánh nhãn mọi đỉnh trong V từ 1 đến n. Đặt Si là tập các cạnh nối với đỉnh i. Sau đó, đặt b = j. Cách xây dựng này là thời gian đa thức ứng với kích thước của VC instance • Chú ý: mỗi cạnh ứng với mỗi phần tử trong U và mỗi đỉnh ứng với một set trong S. Giải thuật nâng cao-Lý thuyết số 34 Phủ đỉnh có trọng số • Tìm tập các đỉnh của graph sao cho mỗi cạnh chứa ít nhất một đỉnh trong tập. • Mỗi đỉnh có trọng số, cần tìm phủ đỉnh total weight nhỏ nhất. 1 • Các phủ đỉnh: *1,3,4+; *1,7,5+ 2 7 3 6 4 5 Giải thuật nâng cao-Giải thuật xấp xỉ 35 VERTEX-COVER p SET-COVER • Vertex Cover là trường hợp đặc biệt của Set Cover • Chuyển vertex cover sang set cover: 1. T = the set of edges E 2. Các subsets ứng với từng vertex, mỗi subset chứa tập các cạnh nối với corresponding vertex Giải thuật nâng cao-Giải thuật xấp xỉ 36 VERTEX-COVER p SET-COVER • T = { (1, 3), (3,7), (1, 7), (4, 5), (4, 6) } • Subsets: 1. S1 = { (1, 3), (1, 7) } w = 1 1 2. S3 = { (1, 3), (3, 7) } w = 3 2 7 3. S7 = { (1, 7), (3, 7) } w = 7 4. S4 = { (4, 5), (4, 6) } w = 4 3 5. S6 = { (4, 6) } w = 6 6 4 6. S5 = { (4, 5) } w = 5 5 Giải thuật nâng cao-Giải thuật xấp xỉ 37 VERTEX-COVER p SET-COVER one element for every edge VC SC one set for every vertex, containing the edges it covers Giải thuật nâng cao-Lý thuyết số 38 SC là bài toán NP-complete (tt) • Cần chứng minh C là satisfiable iff C’ là satisfiable. • Nghĩa là, cần chứng minh nếu original instance của VC là YES instance iff constructed instance of SC là YES instance. • (→) • Giả sử G có phủ đỉnh C kích thước tối đa là j. Theo cách xây dựng trên, C ứng với collection C’ của các subsets của U. Vì b = j, |C’| ≤ b. C’ phủ mọi elements trong U vì C “phủ ” mọi cạnh trong G. • Để thấy điều này, xét bất kỳ phần tử nào của U. Sao cho một phần tử là cạnh trong G. Vì C là set cover, có ít nhất một endpoint của cạnh này thuộc C. Giải thuật nâng cao-Lý thuyết số 39 SC là bài toán NP-complete (tt) • (←) • Giả sử có set cover C’ kích thước tối đa b trong constructed instance. Vì mỗi tập trong in C’ được kết hợp với đỉnh trong G, đặt C là tập các đỉnh này. Thì |C| = |C’| ≤ b = j. C là vertex cover của G vì C’ là set cover. • Để thấy điều này, xét cạnh bất kỳ e. Vì e thuộc U, nên C’ phải chứa ít nhất một tập set có chứa e. Theo cách xây dựng trên, chỉ một tập hợp chứa e ứng với các là các endpoint của e. Vậy C phải chứa ít nhất một endpoint của e. Giải thuật nâng cao-Lý thuyết số 40 Giải thuật Set Cover Algorithm 1: (trường hợp uniform cost) 1. C = empty 2. while U is not empty 3. pick a set Si such that Si covers the most elements in U 4. remove the new covered elements from U 5. C = C union Si 6. return C Giải thuật nâng cao-Lý thuyết số 41 Giải thuật Set Cover • Trường hợp non-uniform cost • Phươn pháp ương tự. Tại mỗi bước lặp, tah vì chọn tập Si sao cho Si phủ nhiều nhất các phần tử chưa được phủ, thì chọn tập Si có cost-effectiveness α nhỏ nhất, với α được định nghĩa : 푐 푆 훼 = 푖 퐴푖 ∩ 푈 • Câu hỏi: tại sao chọn smallest α? Tạy sao định nghĩa α như trên Giải thuật nâng cao-Lý thuyết số 42 Giải thuật Set Cover Algorithm 2: (trường hợp non-uniform cost) 1. C = empty 2. while U is not empty 3. pick a set Si such that Si has the smallest α 4. for each new covered elements e in U 5. set price(e) = α 6. remove the new covered elements from U 7. C = C union Si 8. return C Giải thuật nâng cao-Lý thuyết số 43 Giải thuật xấp xỉ cho Max-Cut • Cho đồ thị 퐺 = 푉, 퐸 . Yêu cầu tách thành hai tập đỉnh S, T sao cho số cạnh bị cắt (cut edge: một đỉnh trong S, đỉnh kia trong T) là nhiều nhất Giải thuật 2-approximation 1. S ← Ø , T ← V 2. Nếu chuyển một từ S sang T, hoặc ngược lại mà làm tăng số cut edges, thì thực hiện chuyển nút. Repeat 2. 3. Output số cut edges. Giải thuật nâng cao-Giải thuật xấp xỉ 44 Bài toán TSP • Cho đồ thị 퐺 = 푉, 퐸 có trọng số, vô hướng. Từ đỉnh bất kỳ đi đến mọi đỉnh khác và quay trở lại đỉnh xuất phát với chi phí thấp nhất 1 1 2 30 2 1 20 3 4 3 • TSP thuộc lớp NP-complete • Không tồn tại polynomial-time approximation algorithm với constant approximation ratio. Giải thuật nâng cao-Giải thuật xấp xỉ 45 Bài toán TSP • Có thể giải TSP theo 2 bước • Tìm MST cho đồ thị đang xét • Bắt đầu từ bất kỳ node và di chuyển trên các cung của MST, và thêm cung tắt để đi khi cần. red bold arcs form a tour start node Giải thuật nâng cao-Giải thuật xấp xỉ 46 Bài toán TSP • Thông thường, có thể giả thiết triangle inequality đúng cho cost function c: E  R xác định trên các cung của đồ thị G=(V,E) : v cuw  cuv + cvw for any u, v, w V w u • Định lý: If the cost function satisfies the triangle inequality, then the algorithm for TSP is a 2-approximation algorithm. Giải thuật nâng cao-Giải thuật xấp xỉ 47 Bài toán TSP . Với e là cung trên tour, thì (triangle inequality), red bold arcs 5 of tour c(e)  c(f1)++c(fk) Vd: c  c + c 6 15 13 35 3 c  c 23 23 1 . Mỗi cung của tree (**) là shortcut 4 start node nhiều nhất hai lần. 2 Vd: cung tree 3-5 là shortcut bởi cung tour 1-5 và 5-6 . . Nhận xét 푐표푠푡 푡푠푝 푡표푢푟 = 푐(푒) ≤ 2. 푐 푒 푒∈푇표푢푟 푒∈푀푆푇 = 2. 푐표푠푡(푀푆푇) Giải thuật nâng cao-Giải thuật xấp xỉ 48 Bài toán TSP Use Prim’s algorithm to get a MST a d e b f g c h • Trọng số cạnh là khoảng cách giữa hai đỉnh Giải thuật nâng cao-Giải thuật xấp xỉ 49 Bài toán TSP Use Prim’s algorithm to get a MST a d Chọn “a”là root e Preorder tree walk b f g c a b c h d e f g h • Trọng số cạnh là khoảng cách giữa hai đỉnh • Bất phương trình tam giác thỏa Giải thuật nâng cao-Giải thuật xấp xỉ 50 Bài toán TSP Use Prim’s algorithm to get a MST a d Chọn “a”là root e Preorder tree walk b f g c a b c h d e f g h The route là • Tổng trọng số gấp đôi lời giải tối ưu Giải thuật nâng cao-Giải thuật xấp xỉ 51 Bài toán TSP • Giải thuật APPROX-TSP-1 là polynomial-time 2- approximation algorithm. • APPROX-TSP-TOUR là O(V2) • C(MST) ≤ C(H*) H*: optimal soln Optimal C(W)=2C(MST) W: Preorder walk Pre-order C(W)≤2C(H*) C(H)≤C(W) H: approx soln & Solution C(H)≤2C(H*) triangle inequality Giải thuật nâng cao-Giải thuật xấp xỉ 52 Bài toán TSP APPROX-TSP-2(G, c) 1. Select a vertex r Є V[G] to be root. O(1) 2. Compute a MST T for G from root O(n lg n) r using Prim Alg. 3. Find a minimal-weight matching M O(n3) for vertices of odd degree in T. 4. Find an Euler cycle C in G’ = (V, T U O(n2) M). 5. L=list of vertices in preorder walk O(n) of C. 6. return the Hamiltonian cycle H in the order L. Giải thuật nâng cao-Giải thuật xấp xỉ 53 Chu trình Hamilton • Cho đồ thị 퐺 = 푉, 퐸 , tìm chu trình sao cho đi qua mỗi đỉnh đúng một lần • HAM-CYCLE trở thành Spanning Tree khi bỏ một cạnh bất kỳ • cost(MST) ≤ cost(min-HAM-CYCLE) Giải thuật nâng cao-Giải thuật xấp xỉ 54 Tóm tắt • Các khái niệm P, NP, NP-complete • Giải thuật xấp xỉ với hệ số xấp xỉ • Minh họa với các bài toán phủ đỉnh, TSP, chu trình Hamilton Giải thuật nâng cao-Giải thuật xấp xỉ 55