Phân tích thiết kế thuật giải - Thuật giải tham lam

THUẬT GIẢI THAM LAM TS. NGÔ QUỐC VIỆT- 2015 PHÂN TÍCH THIẾT KẾ THUẬT GIẢI Nội dung 2 1. Giới thiệu 2. Các thuật giải tham lam 3. Bài tập 4. Hỏi đáp. Giới thiệu 3  Thuật giải tham lam (greedy algorithm)  Là một phương pháp tìm kiếm lời giải “tối ưu”.  Thuật giải tham lam tiếp cận theo cách: ở mỗi bước chọn lời giải tốt nhất  Được gọi là tối ưu cục bộ. Phần lớn tìm được lời giải tối ưu.  Tuy nhiên có thể vì lựa chọn này dẫn đến lời giải sau cùng không tối ưu toàn cục. Một số thuật giải Greedy 4  Fractional knapsack algorithm  Huffman codes  Kruskal's MST algorithm  Prim's MST algorithm  Dijkstra's SSSP algorithm Thuật giải tham lam- Minh hoạ 1 5  Bài toán đổi tiền lẻ: cho một tập các đồng xu có mệnh giá khác nhau. Cần đổi N đồng lấy các đồng xu sao cho số đồng xu ít nhất.  Ví dụ: 24 = 10+ 10 + 1 + 1 + 1 + 1. Tuy nhiên nếu có đồng 8 xu thì cách chọn trên không tối ưu.  Tiếp cận theo thuật giải tham: chọn đồng xu mệnh giá lớn nhất có thể tại mỗi bước. Thuật giải tham lam- Minh hoạ 1 6  Sắp xếp tập đồng xu giảm dần Thuật giải tham lam- Minh hoạ 2 7  Bài toán lịch làm việc:  Việc j bắt đầu tại sj và kết thúc tại fj.  Mỗi thời điểm làm một việc.  Hai công việc không được làm chồng chéo.  Yêu cầu: làm nhiều việc nhất có thể (tình theo thời gian, chứ không phải số đầu việc) Thuật giải tham lam- Minh hoạ 2 8  Tiếp cận tham lam cho bài toán này. Xét các thứ tự có thể.  Bắt đầu sớm nhất: xếp tăng dần theo si.  Kết thúc sớm nhất: xếp tăng dần theo fi.  Khoảng ngắn nhất: xếp tăng dần theo (fi-si)  Ít chồng chéo nhất: với việc j, đếm số lượng (gọi là cj) việc có chồng chéo với việc j. Xếp tăng dần theo cj. Thuật giải tham lam- Minh hoạ 2 9  Giả sử chọn: sắp xếp tăng dần theo fi. Việc j có thể thêm vào nếu không chồng chéo với việc cuối cùng vừa thêm vào A. Thuật giải tham lam- Minh hoạ 3 10  Bài toán xếp lịch giảng dạy n môn học vào m phòng học.  Môn j bắt đầu tại sj và kết thúc tại fj.  Mục tiêu: tìm số phòng tối thiểu để có thể dạy tất cả các môn sao cho một môn không dạy ở hai phòng cùng lúc trong ngày.  Ví dụ có 4 phòng học, và 10 môn. Thuật giải tham lam- Minh hoạ 3 11  Cách sắp xếp khác Thuật giải tham lam- Minh hoạ 3 12  Xếp môn học tăng dần theo si.Xếp vô phòng học 1 trước, khi phòng học này đầy, xét đến phòng học kế tiếp Thuật giải tham lam- Minh hoạ 4 13  Bài toán xếp lịch nhằm giảm tối đa việc trễ giao hàng. Mô tả:  Việc j cần tj thời gian và phải giao tại thời điểm dj.  Nếu j bắt đầu lúc sj, thì sẽ kết thúc tại fj = sj+tj.  Độ trễ lj=max(0, fj-dj).  Mục tiêu: sắp xếp các việc sao cho giảm tối đa L=max(lj). Thuật giải tham lam- Minh hoạ 4 14 Ví dụ: sắp lịch cho 6 việc có thời gian làm và thời hạn giao hàng như sau Một cách sắp xếp Thuật giải tham lam- Minh hoạ 4 15  Sắp xếp các việc theo tiêu chuẩn nào đó (tăng dần theo thời gian xử lý, theo thời hạn giao hàng, )  Thực hiện xếp vô hàng đợi các việc thoả mãn ràng buộc (không chồng chéo) theo thứ tự đã chọn. Ví dụ thuật giải tham cho các việc xếp tăng dần theo deadline như sau Thuật giải tham lam- Minh hoạ 4 16 Thuật giải tham lam- Minh hoạ 4 17  Cải tiến xếp lịch sao cho không có thời gian rảnh. Ví dụ:  Thực hiện bằng cách bổ sung thêm bước hoán vị ‘nghịch thế’ sau khi đã xếp lịch bằng thuật giải tham. Chú ý hoán vị các nghịch thế kề nhau (giống Buble sort) nếu cần. 0-1 vs. Fractional Knapsack 18  0-1 Knapsack Problem:  Các vật không thể chia nhỏ  Hoặc là chọn vật hoặc không chọn cho vào ba lô  Giải bằng DP hoặc Greedy  Fractional Knapsack Problem:  Vật có thể được chia nhỏ (có thể lấy một phần cho vào ba lô)  Giải thông qua greedy algorithm Greedy Fractional Knapsack Algorithm 19  Sắp xếp các items theo giá trị trên mỗi đơn vị giảm dần  While ba lô còn trống do  Xét next item trong danh sách đã xếp giảm dần  Lấy càng nhiều càng tốt  O(n log n) running time ? Greedy Fractional Knapsack Algorithm 20 Algorithm fractionalKnapsack(S, W) Input: set S of items w/ benefit bi and weight wi; max. weight W Output: amount xi of each item i to maximize benefit w/ weight at most W for each item i in S xi  0 vi  bi / wi {value} w  0 {total weight} while w < W remove item i w/ highest vi xi  min{wi , W - w} w  w + min{wi , W - w} Greedy 0-1 Knapsack – Ví dụ 21  3 item  item 1 weighs 10 kg, worth $60 ($6/kg)  item 2 weighs 20 kg, worth $100 ($5/kg)  item 3 weighs 30 kg, worth $120 ($4/kg)  Ba lô chứa tối đa 50kg  Kết quả theo thuật giải Greedy  Lấy item 1  Lấy item 2  Không còn chỗ cho item 3  không hiệu quả  Dùng DP để giải quyết Greedy Fractional Knapsack – Ví dụ 22  Greedy choice:  Compute the benefit per pound  Sort the items based on these values  Take as much as you can from the top items in the list 50 10 20 30 50 Item 1 Item 2 Item 3 $60 $100 $120 10 20 $60 $100 + $240 $6/kg $5/kg $4/kg W 2/3 Of 30 $80 + Cây bao trùm tối tiểu – Minimum spanning tree 23  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 24  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 25  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 26  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 kz 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 27  Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).  Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}  Repeat until Vnew = V:  Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)  Add v to Vnew, and {u, v} to Enew  Output: Vnew and Enew describe a minimal spanning tree MST-Thuật giải Prim 28 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 29 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 30 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 31 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 32 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 33 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 34 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 35 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 36 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 37 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 38  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 39 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ó 3. Lặp bước 2 đến khi có (𝑉 − 1) cạnh trong cây bao trùm MST-Thuật giải Krusal 40 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 41 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 42 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 43 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 44 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 45 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 46 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 47 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 48 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 49 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 50 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 51 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 52 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 53  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. Thuật giải tham lam-Tóm tắt 54  Giải bài toán tìm cực đại/cực tiểu.  Xây dựng công thức tối ưu cục bộ  Phần lớn thực hiện bằng cách sắp xếp, sau đó thực hiện tối ưu ở từng bước. Thuật giải tham lam-Áp dụng giải quyết các bài toán khác 55  Bài toán tìm đường đi ngắn nhất (thuật giải Dijkstra, A*)