Bài giảng Giải thuật nâng cao - Giải thuật tham lam

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 4 • 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. or or or Một số Spanning Trees từ A Graph A Cây bao trùm tối tiểu 5 • 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 Cây bao trùm tối tiểu 6 • 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 • Thuật giải tìm MST trên đồ thị có hoặc không có trọng số: Prim, Kruskal, Boruvka. 5 7 2 1 3 4 2 1 3 Complete Graph Minimum Spanning Tree MST-Thuật giải Prim 7 • 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) MST-Thuật giải Prim 8 • 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 MST-Thuật giải Prim 9 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 10 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 11 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 12 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 13 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 14 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 15 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 16 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 17 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim 18 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J 4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J MST-Thuật giải Prim-Phân tích 19 • 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 MST-Thuật giải Krusal 20 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 MST-Thuật giải Krusal Giải thuật nâng cao-Lý thuyết số 21 MST-Thuật giải Krusal 22 edge dv (D,E) 1 (D,G) 2 (E,G) 3 (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 23 edge dv (D,E) 1  (D,G) 2 (E,G) 3 (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 24 edge dv (D,E) 1  (D,G) 2  (E,G) 3 (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 25 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 Accepting edge (E,G) would create a cycle MST-Thuật giải Krusal 26 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 27 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3 (B,C) 4 5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 28 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4 5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 29 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 30 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4  (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 31 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4  (B,F) 4  (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 32 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4  (B,F) 4  (B,H) 4  (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 33 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B F E D C G 3 2 4 6 3 4 3 4 8 4 3 10 edge dv (B,E) 4  (B,F) 4  (B,H) 4  (A,H) 5  (D,F) 6 (A,B) 8 (A,F) 10 MST-Thuật giải Krusal 34 edge dv (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B F E D C G 2 3 3 3 edge dv (B,E) 4  (B,F) 4  (B,H) 4  (A,H) 5  (D,F) 6 (A,B) 8 (A,F) 10 Done Total Cost =  dv = 21 4 } MST-Thuật giải Krusal-Phân tích 35 • 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. 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â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 Các khu phố Khu phố trong phạm vi 10km 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: Giải thuật nâng cao-Lý thuyết số 43 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 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 Giải thuật nâng cao-Lý thuyết số 46 one set for every vertex, containing the edges it covers VC one element for every edge SC 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