Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng trình bày về các bài toán áp dụng cho phương pháp tham lam, như bài toán Cây bao trùm nhỏ nhất, bài toán tô màu và bài toán các khoảng không giao nhau. Tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin. . | 2/2/2017 Analysis and Design of Algorithms Lecture 6,7 The Greedy algorithms Lecturer: Ha Dai Duong duonghd@mta.edu.vn 2/2/2017 1 Nội dung 1. 2. 3. 4. 5. 6. 7. Lược đồ chung Bài toán cái túi Bài toán người du lịch Đường đi ngắn nhất Cây bao trùm nhỏ nhất Bài toán tô màu Bài toán các khoảng không giao nhau 2/2/2017 2 Bài toán • Cho đơn đồ thị G=(V,E) – V: Tập các đỉnh – E: Tập các cạnh • Cây T gọi là cây bao trùm của G nếu T là đồ thị con của G và chứa tất cả các đỉnh thuộc G (có số đỉnh =V) • Tìm cây bao trùm có trọng số nhỏ nhất (Minimal Spanning Tree) MST 2/2/2017 3 1 2/2/2017 Thuật toán Prim • T = GT(VT,ET) là cây khung tối thiểu cần tìm • Ý tưởng – Chọn 1 đỉnh tùy ý vào V T – Khi |VT| < |V| • Tìm cạnh (s,t) s VT, t V\VT có trọng số nhỏ nhất (tham lam) nối VT và V\VT • Thêm đỉnh t vào V T, (s,t) vào ET 2/2/2017 4 Minh họa • Cho đồ thị 6 G = (V,E) = 2/2/2017 5 Khởi tạo • Bắt đầu từ đỉnh 1 1 6 Đồ thị G 2/2/2017 MST T 6 2 2/2/2017 Bước 1 • Bắt đầu từ đỉnh 1 1 1 2 6 Đồ thị G MST T 2/2/2017 7 Bước 2 • Bắt đầu từ đỉnh 1 1 1 2 2 3 6 Đồ thị G MST T 2/2/2017 8 Bước 3 • Bắt đầu từ đỉnh 1 1 6 1 2 2 3 4 4 Đồ thị G 2/2/2017 MST T 9 3 2/2/2017 Bước 4 • Bắt đầu từ đỉnh 1 1 2 4 6 1 3 2 5 3 4 Đồ thị G MST T 2/2/2017 10 Bước 5 • Bắt đầu từ đỉnh 1 1 2 4 6 1 3 2 5 3 4 4 7 Đồ thị G MST T 2/2/2017 11 Bước 6 • Bắt đầu từ đỉnh 1 1 2 4 6 1 3 5 Đồ thị G 3 4 4 2/2/2017 2 7 7 3 MST T 12 4 2/2/2017 Kết quả • MST T= (VT,ET) – VT=V = {1,2,3,4,5,6,7} – ET={(1,2), 1 (2,3), 4 (1,4), 4 (4,5), (4,7), (6,7),} - W(T) = 17 (Trọng số cây T) 1 3 4 2 5 7 2 3 7 3 MST T 2/2/2017 13 Cài đặt • Biểu diễn G qua ma trận trọng số cạnh • Mảng Closest[i]: Giá trị của nó đỉnh kề gần i nhất. • Mảng lowcost[i]: cho trọng số của .
