Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhất
lượt xem 13
download
Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhất giới thiệu đến bạn đọc về những cách giải bài toán tìm cây khung nhỏ nhất, giải thuật tổng quát, thực thi giải thuật của Kruskal. Với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích dành cho các bạn.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhất
- Cây Khung Nhỏ Nhất
- Cây khung nhỏ nhất ª Cho – một đồ thị liên thông, vô hướng G = (V, E ) – một hàm trọng số w : E R ª Tìm một tập con không chứa chu trình T E nối tất cả các đỉnh sao cho tổng các trọng số w(T) = (u, v) T w(u, v) • là nhỏ nhất. – Tập T làø một cây, và được gọi là một cây khung nhỏ nhất. ª Bài toán tìm cây khung nhỏ nhất: bài toán tìm T. 13.11.2004 Ch. 9: Cay khung nho nhat 2
- Cây khung nhỏ nhất (tiếp) ª Giải bài toán tìm cây khung nhỏ nhất – Giải thuật của Kruskal – Giải thuật của Prim. 13.11.2004 Ch. 9: Cay khung nho nhat 3
- Cây khung nhỏ nhất: ví dụ 8 7 b c d 4 2 9 a 11 i 4 14 e 7 6 8 10 h g f 1 2 ° Tập các cạnh xám là một cây khung nhỏ nhất ° Trọng số tổng cộng của cây là 37. ° Cây là không duy nhất: nếu thay cạnh ( b, c) bằng cạnh (a, h) sẽ được một cây khung khác cũng có trọng số là 37. 13.11.2004 Ch. 9: Cay khung nho nhat 4
- Cạnh an toàn ª Cho một đồ thị liên thông, vô hướng G = (V, E ) và một hàm trọng số w : E R. Tìm một cây khung nhỏ nhất cho G! ª Giải bài toán bằng một chiến lược greedy: nuôi một cây khung lớn dần bằng cách thêm vào cây từng cạnh một. ª Định nghĩa cạnh an toàn Nếu A là một tập con của một cây khung nhỏ nhất nào đó, nếu (u, v) là một cạnh của G sao cho tập A {(u, v)} vẫn còn là một tập con của một cây khung nhỏ nhất nào đó, thì (u, v) là một cạnh an toàn cho A. 13.11.2004 Ch. 9: Cay khung nho nhat 5
- Một giải thuật tổng quát (generic) ª Một giải thuật tổng quát (generic) để tìm một cây khung nhỏ nhất – Input: một đồ thị liên thông, vô hướng G một hàm trọng số w trên các cạnh của G – Output: Một cây khung nhỏ nhất cho G. GENERICMST(G, w) 1 A 2 while A không là một cây khung nhỏ nhất 3 do tìm cạnh (u, v) an toàn cho A 4 A A {(u, v)} 5 return A 13.11.2004 Ch. 9: Cay khung nho nhat 6
- Phép cắt Các khái niệm quan trọng ª Một phép cắt (S, V S) của G = (V, E ) là một phân chia (partition) của V. Ví dụ: S = {a, b, d, e} trong đồ thị sau. ª Một cạnh (u, v) E xuyên qua (cross) một phép cắt (S, V S) nếu một đỉnh của nó nằm trong S và đỉnh kia nằm trong V S. Ví dụ: cạnh (b, c). 8 7 b c d 4 2 9 a 11 i 4 14 e S 7 6 10 8 V S h g f 1 2 13.11.2004 Ch. 9: Cay khung nho nhat 7
- Cạnh nhẹ (light edge) Các khái niệm quan trọng (tiếp) ª Một phép cắt bảo toàn tập các cạnh A (respects A) nếu không có cạnh nào của A xuyên qua phép cắt. ª Một cạnh là một cạnh nhẹ vượt qua phép cắt nếu trọng số của nó là nhỏ nhất trong mọi trọng số của các cạnh xuyên qua phép cắt. Ví dụ: cạnh (c, d). 8 7 b c d 4 2 9 a 11 i 4 e S 7 6 14 8 10 V S h g f 1 2 13.11.2004 Ch. 9: Cay khung nho nhat 8
- Nhận ra một cạnh an toàn Định lý 24.1 Cho ° G = (V, E) là một đồ thị liên thông, vô hướng ° w là một hàm trọng số trên E ° A là một tập con của một cây khung nhỏ nhất cho G ° (S, V S) là một phép cắt bất kỳ của G bảo toàn A ° (u, v) là một cạnh nhẹ vượt qua (S, V S) cạnh (u, v) là an toàn cho A. Chứng minh 13.11.2004 Ch. 9: Cay khung nho nhat 9
- Nhận ra một cạnh an toàn (tiếp) ° S: tập các đỉnh đen, V S: tập các đỉnh trắng ° Các cạnh của một cây khung nhỏ nhất T được vẽ ra trong hình, còn các cạnh của G thì không ° A: tập các cạnh xám ° Cạnh (u, v) là cạnh nhẹ xuyên qua phép cắt (S, V S). ° p là đường đi duy nhất từ u đến v trong T. x u y p v 13.11.2004 Ch. 9: Cay khung nho nhat 10
- Nhận ra một cạnh an toàn (tiếp) ° Định nghĩa cây khung T’ = T (x, y) (u, v) T’ là cây khung nhỏ nhất vì w(T’) = w(T) w(x, y) + w(u, v) w(T), vì w(u, v) w(x, y) ° (u, v) là an toàn cho A vì A (u, v) T’ . x p u y v 13.11.2004 Ch. 9: Cay khung nho nhat 11
- Nhận ra một cạnh an toàn (tiếp) Hệ luận 24.2 Cho ° G = (V, E ) là một đồ thị liên thông, vô hướng với một hàm trọng số w trên E ° A là một tập con của E sao cho A nằm trong một cây khung nhỏ nhất cho G ° C = (V , E ) là một thành phần liên thông (cây) trong rừng G = C C A (V, A). Thì, nếu (u, v) là một cạnh nhẹ nối C với một thành phần khác trong GA (u, v) là an toàn cho A. Chứng minh Phép cắt (VC , V VC ) bảo toàn A, do đó (u, v) là một cạnh nhẹ đối với phép cắt này. 13.11.2004 Ch. 9: Cay khung nho nhat 12
- Giải thuật của Kruskal ª Giải thuật của Kruskal – dựa trên giải thuật GENERICMST, mà A ban đầu là một rừng mà mỗi cây chỉ chứa một đỉnh của G. MSTKRUSKAL(G, w) 1 A 2 for mỗi đỉnh v V[G] 3 do MAKESET(v) 4 xếp các cạnh E theo thứ tự trọng số w không giảm 5 for mỗi cạnh (u, v) E, theo thứ tự trọng số không giảm 6 do if FINDSET(u) FINDSET(v) 7 then A A {(u, v)} 8 UNION(u, v) 9 return A ª mỗi tập rời nhau chứa các đỉnh của một cây trong rừng hiện thời. 13.11.2004 Ch. 9: Cay khung nho nhat 13
- Thực thi giải thuật của Kruskal Các cạnh được xếp theo thứ tự trọng số không giảm: 1 2 2 4 4 6 7 7 8 8 9 10 11 14 8 7 8 7 (a) b c d (b) b c d 4 2 9 4 2 9 a 11 i 4 14 e a 11 i 4 14 e 7 6 7 6 8 10 8 10 h g f h g f 1 2 1 2 13.11.2004 Ch. 9: Cay khung nho nhat 14
- Thực thi giải thuật của Kruskal (tiếp) 1 2 2 4 4 6 7 7 8 8 9 10 11 14 8 7 8 7 (c) b c d (d) b c d 4 2 9 4 2 9 a 11 i 4 14 e a 11 i 4 14 e 7 6 7 6 8 10 8 10 h g f h g f 1 2 1 2 13.11.2004 Ch. 9: Cay khung nho nhat 15
- Thực thi giải thuật của Kruskal (tiếp) 8 7 8 7 (e) b c d (f) b c d 4 2 9 4 2 9 a 11 i 4 14 e a 11 i 4 14 e 7 6 7 6 8 10 8 10 h g f h g f 1 2 1 2 8 7 8 7 (g) b c d (h) b c d 4 2 9 4 2 9 a 11 i 4 14 e a 11 i 4 14 e 7 6 7 6 8 10 8 10 h g f h g f 1 2 1 2 13.11.2004 Ch. 9: Cay khung nho nhat 16
- Thực thi giải thuật của Kruskal (tiếp) 8 7 8 7 (i) b c d (j) b c d 4 2 9 4 2 9 a 11 i 4 14 e a 11 i 4 14 e 7 6 7 6 8 10 8 10 h g f h g f 1 2 1 2 8 7 8 7 (k) b c d (l) b c d 4 2 9 4 2 9 a 11 i 4 14 e a 11 i 4 14 e 7 6 7 6 8 10 8 10 h g f h g f 1 2 1 2 13.11.2004 Ch. 9: Cay khung nho nhat 17
- Thực thi giải thuật của Kruskal (tiếp) 1 2 2 4 4 6 7 7 8 8 9 10 11 14 8 7 8 7 (m) b c d (n) b c d 4 2 9 4 2 9 a 11 i 4 14 e a 11 i 4 14 e 7 6 7 6 8 10 8 10 h g f h g f 1 2 1 2 13.11.2004 Ch. 9: Cay khung nho nhat 18
- Phân tích giải thuật của Kruskal ª Dùng cấu trúc dữ liệu các tập rời nhau (disjoint sets), chương 22, với các heuristics – Hợp theo thứ hạng (unionbyrank) – Nén đường dẫn (pathcompression). ª Nhận xét (cần đến khi đánh giá thời gian chạy) – Giải thuật gọi V lần MAKESET và gọi tổng cộng O(E) lần các thao tác MAKESET, UNION, FINDSET. – Vì G liên thông nên E V 1. 13.11.2004 Ch. 9: Cay khung nho nhat 19
- Phân tích giải thuật của Kruskal (tiếp) ª Thời gian chạy của MSTKRUSKAL gồm – Khởi động: O(V) – Sắp xếp ở dòng 4: O(E lg E) – Dòng 58: O(E (E, V)) (xem nhận xét), = O(E lg E) vì (E, V) = O(lg E). • Vậy thời gian chạy của MSTKRUSKAL là O(E lg E). 13.11.2004 Ch. 9: Cay khung nho nhat 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Phân tích thiết kế hệ thống mạng - ThS. Lê Xuân Thành
52 p | 723 | 95
-
Bài giảng Phân tích thiết kế hệ thống: Bài giảng 5 - TS. Đào Nam Anh
87 p | 192 | 31
-
Bài giảng Phân tích thiết kế thuật toán: Chương 3 - Nguyễn Văn Linh
87 p | 189 | 22
-
Bài giảng Phân tích thiết kế thuật toán: Chương 1 - Nguyễn Văn Linh
56 p | 230 | 22
-
Bài giảng Phân tích thiết kế hệ thống: Bài giảng 3 - TS. Đào Nam Anh
60 p | 129 | 21
-
Bài giảng Phân tích thiết kế hệ thống: Bài giảng 6 - TS. Đào Nam Anh
22 p | 128 | 16
-
Bài giảng Phân tích thiết kế hệ thống: Bài giảng 2 - TS. Đào Nam Anh
28 p | 136 | 15
-
Bài giảng Phân tích thiết kế hệ thống: Bài giảng 4 - TS. Đào Nam Anh
12 p | 155 | 15
-
Bài giảng Phân tích thiết kế hệ thống: Bài giảng 7 - TS. Đào Nam Anh
39 p | 111 | 13
-
Bài giảng Phân tích thiết kế giải thuật: Chương 2 - Trịnh Huy Hoàng
98 p | 116 | 11
-
Bài giảng Phân tích thiết kế giải thuật: Chương 1 - Trịnh Huy Hoàng
72 p | 117 | 8
-
Bài giảng Phân tích thiết kế hướng đối tượng: Chương 5 - Lê Thị Minh Nguyện
11 p | 99 | 8
-
Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng
90 p | 107 | 7
-
Bài giảng Phân tích thiết kế hệ thống thông tin: Bài 11 - TS. Trần Mạnh Tuấn
29 p | 52 | 7
-
Bài giảng Phân tích thiết kế hệ thống thông tin: Bài 9 - TS. Trần Mạnh Tuấn
46 p | 59 | 6
-
Bài giảng Phân tích thiết kế đảm bảo chất lượng phần mềm: Phần 1
115 p | 34 | 6
-
Bài giảng Phân tích thiết kế hướng đối tượng: Chương 4 - Lê Thị Minh Nguyện
14 p | 81 | 5
-
Bài giảng Phân tích thiết kế và giải thuật - Chương 2: Kỹ thuật thiết kế giải thuật
80 p | 48 | 2
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