intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: 4584125 4584125 | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST
Báo xấu
148
lượt xem 14
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. GIẢI THUẬT THAM LAM TS. NGÔ QUỐC VIỆT 2015
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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
  10. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 10
  11. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 11
  12. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 12
  13. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 13
  14. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 14
  15. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 15
  16. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 16
  17. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 17
  18. MST-Thuật giải Prim B 4 C 4 B 4 C 2 1 4 2 1 A 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 18
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2