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

Chương này trang bị cho người học những kiến thức về giải thuật tham lam. Những nội dung chính trong chương này gồm có: giới thiệu chung về thuật giải tham lam, bài toán cây bao trùm tối thiểu (MST), huffman coding, phủ tập hợp. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Giải thuật nâng cao: Giải thuật tham lam - TS. Ngô Quốc ViệtGIẢI THUẬT THAM LAM TS. NGÔ QUỐC VIỆT 2015Nội dung1. Giới thiệu2. Bài toán cây bao trùm tối thiểu (MST)3. Huffman coding4. Phủ tập hợp Giải thuật nâng cao-Lý thuyết số 2Giớ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 5Câ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 đi1. 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ây3. 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 1A 4 E 1 F A 4 E F 1 D 2 3 10 D 2 3 G 5 10 G 5 5 6 3 5 6 3 4 I 4 H I 3 H 2 J 2 3 J 9 MST-Thuật giải Prim B 4 C 4 B 4 C ...