Bài giảng Giải thuật nâng cao: Giải thuật tham lam - Ngô Quốc Việt

GIẢI THUẬT THAM LAM TS. NGÔ QUỐC VIỆT 2015 Nội dung 1. Giới thiệu 2. Bài toán cây bao trùm tối thiểu (MST) 3. Huffman coding 4. Phủ tập hợp Giải thuật nâng cao-Lý thuyết số 2 Giới thiệu • Thuật giải tham lam xây dựng giải pháp từng bước, trong đó chọn lời bước kế tiếp dựa trên tiêu chí có lợi & hiển nhiên nhất. • Cách tiếp cận có thể cho lời giải không đúng trong một số trường hợp, nhưng phần lớn đạt được kết quả tối ưu. • Bài giảng minh họa greedy với: MST, Huffman coding, phủ tập hợp. Giải thuật nâng cao-Lý thuyết số 3 Cây bao trùm tối tiểu – Minimum spanning tree • Cho đồ thị G liên thông vô hướng, cây bao trùm (cây khung) được định nghĩa là đồ thị con dạng cây (không có chu trình) có mọi đỉnh của G và mọi đỉnh liên thông nhau. Một đồ thị có thể có nhiều cây bao trùm. Graph A Một số Spanning Trees từ A or or or 4 Cây bao trùm tối tiểu • Số lượng cây bao trùm của đồ thị G 1 퐺 푙à 푐â푦 푡 퐺 = 푛 퐺 đồ 푡ℎị 푣ò푛𝑔 퐶푛 푛−2 푛 퐺 đồ 푡ℎị đầ푦 đủ 퐾푛 • Đồ thị đầy đủ: mọi cặp đỉnh được nối bởi cạnh duy nhất. • Bigraph: tập đỉnh trong G chia thành hai tập rời nhau U, V. Mỗi cạnh chỉ nối giữa điểm trong U với điểm trong V. • Tìm cây bao trùm: theo chiều rộng, theo chiều sâu 5 Cây bao trùm tối tiểu • Cây bao trùm nhỏ nhất là cây bao trùm có tổng trọng số các cạnh nhỏ hơn tất cả các cây bao trùm khác Complete Graph Minimum Spanning Tree 7 2 2 5 3 3 4 1 1 • Thuật giải tìm MST trên đồ thị có hoặc không có trọng số: Prim, Kruskal, Boruvka. 6 MST-Thuật giải Prim • Tương tự thuật giải Dijkstra, với trọng số cạnh thay chiều dài đường đi 1. Tạo cây ban đầu với đỉnh bất kỳ thuộc graph. 2. Thêm cạnh vào cây : chọn cạnh có trọng số nhỏ nhất (chưa có trong cây đang tạo) nối với các đỉnh của cây và thêm vào cây 3. Lặp lại (đến khi mọi đỉnh trong cây) 7 MST-Thuật giải Prim • Input: đồ thị trọng số không rỗng với tập đỉnh V và cạnh E (trọng số có thể âm). • Khởi tạo: Vnew = {x}, với x is là node bất kỳ(starting point) từ V, Enew = {} • Lặp đến khi Vnew = V: • Chọn cạnh {u, v} với minimal weight sao cho u thuộc Vnew và v không thuộc (nếu có nhiều cạnh cùng trọng số, chọn ngãu nhiên một cạnh) • Thêm v vào Vnew, và {u, v} to Enew • Output: Vnew và Enew chứa minimal spanning tree 8 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 9 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 10 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 11 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 12 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 13 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 14 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 15 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 16 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 17 MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 4 E F 1 A 4 E 1 F D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I H 2 3 J 3 2 J 18 MST-Thuật giải Prim-Phân tích • Running Time: 푂(푚 + 푛 log 푛) (푚 = 푒푑𝑔푒푠, 푛 = 푛표푑푒푠) • Nếu không dùng heap, the run time sẽ là 푂(푛2). • Không cần sắp xếp theo trọng số cạnh trước. • Vì xét theo đỉnh  không cần xét khả năng tạo chu trình 19 MST-Thuật giải Krusal 1. Sắp xếp tăng dần theo trọng số cạnh 2. Chọn cạnh có trọng số nhỏ nhất. Kiểm tra nếu không tạo thành chu trình, chọn nó. Ngược lại chọn cạnh khác có trọng số nhỏ và không tạo chu trình. 3. Lặp bước 2 đến khi có (푉 − 1) cạnh trong cây bao trùm 20 MST-Thuật giải Krusal Giải thuật nâng cao-Lý thuyết số 21 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1 (B,E) 4 8 4 6 (D,G) 2 (B,F) 4 5 4 B D (E,G) 3 (B,H) 4 4 H (C,D) 3 (A,H) 5 2 1 3 (G,H) 3 (D,F) 6 G 3 E (C,F) 3 (A,B) 8 (B,C) 4 (A,F) 10 22 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4 8 4 6 (D,G) 2 (B,F) 4 5 4 B D (E,G) 3 (B,H) 4 4 H (C,D) 3 (A,H) 5 2 1 3 (G,H) 3 (D,F) 6 G 3 E (C,F) 3 (A,B) 8 (B,C) 4 (A,F) 10 23 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4 8 4 6 (D,G) 2  (B,F) 4 5 4 B D (E,G) 3 (B,H) 4 4 H (C,D) 3 (A,H) 5 2 1 3 (G,H) 3 (D,F) 6 G 3 E (C,F) 3 (A,B) 8 (B,C) 4 (A,F) 10 24 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4 8 4 6 (D,G) 2  (B,F) 4 5 4 B D (E,G) 3  (B,H) 4 4 H (C,D) 3 (A,H) 5 2 1 3 (G,H) 3 (D,F) 6 G 3 E (C,F) 3 (A,B) 8 (B,C) 4 (A,F) 10 Accepting edge (E,G) would create a cycle 25 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4 8 4 6 (D,G) 2  (B,F) 4 5 4 B D (E,G) 3  (B,H) 4 4 H (C,D) 3  (A,H) 5 2 1 3 (G,H) 3 (D,F) 6 G 3 E (C,F) 3 (A,B) 8 (B,C) 4 (A,F) 10 26 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4 8 4 6 (D,G) 2  (B,F) 4 5 4 B D (E,G) 3  (B,H) 4 4 H (C,D) 3  (A,H) 5 2 1 3 (G,H) 3  (D,F) 6 G 3 E (C,F) 3 (A,B) 8 (B,C) 4 (A,F) 10 27 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4 8 4 6 (D,G) 2  (B,F) 4 5 4 B D (E,G) 3  (B,H) 4 4 H (C,D) 3  (A,H) 5 2 1 3 (G,H) 3  (D,F) 6 G 3 E (C,F) 3  (A,B) 8 (B,C) 4 (A,F) 10 28 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4 8 4 6 (D,G) 2  (B,F) 4 5 4 B D (E,G) 3  (B,H) 4 4 H (C,D) 3  (A,H) 5 2 1 3 (G,H) 3  (D,F) 6 G 3 E (C,F) 3  (A,B) 8 (B,C) 4  (A,F) 10 29 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4  8 4 6 (D,G) 2  (B,F) 4 5 4 B D (E,G) 3  (B,H) 4 4 H (C,D) 3  (A,H) 5 2 1 3 (G,H) 3  (D,F) 6 G 3 E (C,F) 3  (A,B) 8 (B,C) 4  (A,F) 10 30 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4  8 4 6 (D,G) 2  (B,F) 4  5 4 B D (E,G) 3  (B,H) 4 4 H (C,D) 3  (A,H) 5 2 1 3 (G,H) 3  (D,F) 6 G 3 E (C,F) 3  (A,B) 8 (B,C) 4  (A,F) 10 31 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4  8 4 6 (D,G) 2  (B,F) 4  5 4 B D (E,G) 3  (B,H) 4  4 H (C,D) 3  (A,H) 5 2 1 3 (G,H) 3  (D,F) 6 G 3 E (C,F) 3  (A,B) 8 (B,C) 4  (A,F) 10 32 MST-Thuật giải Krusal 3 F 10 C edge dv edge dv A 4 3 (D,E) 1  (B,E) 4  8 4 6 (D,G) 2  (B,F) 4  5 4 B D (E,G) 3  (B,H) 4  4 H (C,D) 3  (A,H) 5  2 1 3 (G,H) 3  (D,F) 6 G 3 E (C,F) 3  (A,B) 8 (B,C) 4  (A,F) 10 33 MST-Thuật giải Krusal 3 F C edge dv edge dv A 3 (D,E) 1  (B,E) 4  4 (D,G) 2  (B,F) 4  5 B D (E,G) 3  (B,H) 4  H (C,D) 3  (A,H) 5  2 1 3 (G,H) 3  (D,F) 6 G E (C,F) 3  (A,B) 8 } (B,C) 4  (A,F) 10 Done Total Cost =  dv = 21 34 MST-Thuật giải Krusal-Phân tích • Running Time = O(m log n) (m = edges, n = nodes). QuickSort algorithm • Kiểm tra cạnh tạo ra chu trình có thể chậm. Tuy nhiên, sử dụng data structure “union-find” sẽ khắc phục nhược điểm. • Trong một số trường hợp (có đỉnh nối với cạnh dài nhất với đồ thị)  phải kiểm tra mọi cạnh. 35 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ố 36 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ố 37 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ố 38 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 C Giải thuật nâng cao-Lý thuyết số 39 Phủ tập hợp-giải thuật greedy-ví dụ • Cho 푈 = *1,2,3,4,5+, 푆 = *푆1, 푆2, 푆3+, 푆1 = *4,1,3+, 퐶표푠푡(푆1) = 5, 푆2 = *2,5+, 퐶표푠푡(푆2) = 10, 푆3 = *1,4,3,2+, 퐶표푠푡(푆3) = 3. Minh họa với Greedy • Lần lặp 1: 푆1 = 퐶표푠푡(푆1)/|푆1 – 퐶| = 5/3; 푆2 = 퐶표푠푡(푆2)/|푆2 – 퐶| = 10/2; 푆3 = 퐶표푠푡(푆3)/ |푆3 – 퐶| = ¾  chọn S3. • Lần lặp 2: S1 = Cost(S1)/|S1 – C| = 5/0; S2 = Cost(S2)/|S2 – C| = 10/1  chọn S2. • Trường hợp này greedy có nghiệm tối ưu Giải thuật nâng cao-Lý thuyết số 40 Phủ tập hợp-giải thuật greedy-ví dụ • 푈 = *1,2,3,4,5,6,7,8,9,10,11,12,13+; S1 = {1, 2} S2 = {2, 3, 4, 5} S3 = {6, 7, 8, 9, 10, 11, 12, 13} S4 = {1, 3, 5, 7, 9, 11, 13} S5 = {2, 4, 6, 8, 10, 12, 13}. Giả sử cost của các subset là giống nhau • Kết quả của greedy algorithm là C= {S3, S2, S1}, so với nghiệm tối ưu {S4, S5}. Giải thuật nâng cao-Lý thuyết số 41 Phủ tập hợp-giải thuật greedy-ví dụ IBM finds computer viruses (wikipedia) • Elements: 5000 virus máy tính • Sets: 9000 substring, mỗi substring khoảng 20++ bytes thể hiện virus. • Xác định phủ tập hợp khoảng 180 substrings phủ toàn bộ U. Chỉ cần search trong 180 substring để xác định có virus hay không? Giải thuật nâng cao-Lý thuyết số 42 SC là bài toán NP-complete • Định lý: Set Cover (SC) là NP-complete • Chứng minh: INSTANCE: Given a universe U of n elements, a collection of subsets of U, S = {S1, , Sm}, and a positive integer b QUESTION: Is there a , |C| ≤ b, such that (Note: The subcollection {Si | } satisfying the above condition is called a set cover of U Giải thuật nâng cao-Lý thuyết số 43 SC là bài toán NP-complete (tt) • Cần chứng minh SC thuộc NP. Cho subcollection C, dễ dàng kiểm chứng rằng nếu |C| ≤ b và union của các tập trong C chứa mọi phần tử của U. • Để 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ố 44 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à poly-time ứng với size 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 and một set trong S. Giải thuật nâng cao-Lý thuyết số 45 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ố 46 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ố 47 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ố 48 Giải pháp 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ố 49 Solutions • Trường hợp non-uniform cost • Phương pháp tương tự. Tại mỗi bước lặp, thay 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ố 50 Solutions 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ố 51