Phân tích và thiết kế thuật toán - Cây bao trùm nhỏ nhất

Nội dung text: Phân tích và thiết kế thuật toán - Cây bao trùm nhỏ nhất

1. 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. Lược đồ chung 2. Bài toán cái túi 3. Bài toán người du lịch 4. Đường đi ngắn nhất 5. Cây bao trùm nhỏ nhất 6. Bài toán tô màu 7. 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/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 VT – 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 VT, (s,t) vào ET 2/2/2017 4 Minh họa • Cho đồ thị G = (V,E) = 6 2/2/2017 5 Khởi tạo • Bắt đầu từ đỉnh 1 1 6 Đồ thị G MST T 2/2/2017 6 2
3. 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 2 1 2 3 6 Đồ thị G MST T 2/2/2017 8 Bước 3 • Bắt đầu từ đỉnh 1 1 2 1 2 3 6 4 4 Đồ thị G MST T 2/2/2017 9 3
4. 2/2/2017 Bước 4 • Bắt đầu từ đỉnh 1 1 2 1 2 3 6 4 3 4 5 Đồ thị G MST T 2/2/2017 10 Bước 5 • Bắt đầu từ đỉnh 1 1 2 1 2 3 6 4 3 4 5 4 7 Đồ thị G MST T 2/2/2017 11 Bước 6 • Bắt đầu từ đỉnh 1 1 2 1 2 3 6 4 3 4 5 7 4 3 7 Đồ thị G MST T 2/2/2017 12 4
5. 2/2/2017 Kết quả • MST T= (VT,ET) – VT=V = {1,2,3,4,5,6,7} 1 2 – ET={(1,2), 1 2 3 (2,3), 4 (1,4), 3 4 5 7 (4,5), (4,7), 4 3 (6,7),} 7 - W(T) = 17 (Trọng số cây T) 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 cạnh (i,closest[i]). 2/2/2017 14 2/2/2017 15 5
6. 2/2/2017 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 16 Thuật toán Kruskal • T = GT(VT,ET) là cây khung tối thiểu cần tìm • Khi G có n đỉnh thì T có n-1 cạnh • Ý tưởng (tham lam): Xây dựng tập n-1 cạnh của T theo nguyên tắc: – Khởi tạo ET={}, VT = V – Xét lần lượt các cạnh có trọng số nhỏ đến lớn nếu không tạo thành chu trình trong T thì thêm cạnh đó vào ET. 2/2/2017 17 Minh họa • Cho đồ thị G = (V,E) = 2/2/2017 18 6
7. 2/2/2017 Khởi tạo 1 4 6 7 2 3 5 Đồ thị G MST T 2/2/2017 19 Bước 1 1 1 4 6 7 2 3 5 Đồ thị G MST T 2/2/2017 20 Bước 2 1 1 4 6 1 7 2 3 5 Đồ thị G MST T 2/2/2017 21 7
8. 2/2/2017 Bước 3 1 2 1 4 6 1 7 2 3 5 Đồ thị G MST T 2/2/2017 22 Bước 4 1 2 1 4 6 1 3 7 2 3 5 Đồ thị G MST T 2/2/2017 23 Bước 5 1 2 1 4 6 1 3 3 7 2 3 5 Đồ thị G MST T 2/2/2017 24 8
9. 2/2/2017 Bước 6 1 2 1 4 6 1 3 3 5 7 2 3 5 Đồ thị G MST T 2/2/2017 25 Kết quả • MST T= (VT,ET) – V =V = {1,2,3,4,5,6,7} 1 2 T 1 4 – ET={(1,4), 6 1 (1,2), 3 3 5 7 (3,4), (4,6), 2 3 5 (5,6), (6,7),} - W(T) = 15 (Trọng số cây T) MST T 2/2/2017 26 Cài đặt • Mô tả G bằng ma trận trọng số cạnh A[i,j]. • D mảng 1 chiều, nếu D[i]=k thì đỉnh i thuộc vào cây thứ k, D[i] = 0 thì đỉnh i chưa thuộc vào cây. • Tìm min {A[i][j] } j = 1 n, i =1 n trừ các cạnh (i,j) mà D[i]=D[j]<>0 (những cạnh đó tạo thành chu trình). • Thêm cạnh vừa tìm vào cây T, lặp lại bước 2 khi T còn là rừng. 2/2/2017 27 9
10. 2/2/2017 Cài đặt • Xử lý cạnh (i,j) khi được thêm vào T: – Nếu D[i]=D[j]=0, cạnh (i,j) chưa thuộc vào cây nên khi lấy 2 đỉnh này vào tập cạnh ta cho chúng thuộc vào 1 cây mới. Khi đó k=k+1 và D[i]=D[j]=k. – Nếu D[i]=0 và D[j] Ghép i vào cùng cây chứa j, D[i]=D[j]. – Nếu D[i] Ghép j vào cùng cây chứa i, D[j]=D[i]. – Nếu D[i] 0, D[j] Ghép 2 cây thành 1. 2/2/2017 28 Cài đặt • Xử lý cạnh (i,j) khi được thêm vào T: – Nếu D[i]=D[j]=0, cạnh (i,j) chưa thuộc vào cây nên khi lấy 2 đỉnh này vào tập cạnh ta cho chúng thuộc vào 1 cây mới. Khi đó k=k+1 và D[i]=D[j]=k. – Nếu D[i]=0 và D[j] Ghép i vào cùng cây chứa j, D[i]=D[j]. – Nếu D[i] Ghép j vào cùng cây chứa i, D[j]=D[i]. – Nếu D[i] 0, D[j] Ghép 2 cây thành 1. 2/2/2017 29 Cài đặt • Xử lý cạnh (i,j) khi được thêm vào T: – Nếu D[i]=D[j]=0, cạnh (i,j) chưa thuộc vào cây nên khi lấy 2 đỉnh này vào tập cạnh ta cho chúng thuộc vào 1 cây mới. Khi đó k=k+1 và D[i]=D[j]=k. – Nếu D[i]=0 và D[j] Ghép i vào cùng cây chứa j, D[i]=D[j]. – Nếu D[i] Ghép j vào cùng cây chứa i, D[j]=D[i]. – Nếu D[i] 0, D[j] Ghép 2 cây thành 1. 2/2/2017 30 10
11. 2/2/2017 Cài đặt • Xử lý cạnh (i,j) khi được thêm vào T: – Nếu D[i]=D[j]=0, cạnh (i,j) chưa thuộc vào cây nên khi lấy 2 đỉnh này vào tập cạnh ta cho chúng thuộc vào 1 cây mới. Khi đó k=k+1 và D[i]=D[j]=k. – Nếu D[i]=0 và D[j] Ghép i vào cùng cây chứa j, D[i]=D[j]. – Nếu D[i] Ghép j vào cùng cây chứa i, D[j]=D[i]. – Nếu D[i] 0, D[j] Ghép 2 cây thành 1. 2/2/2017 31 Cài đặt typedef struct Egde { int x,y; }; void Kruskal(int A, int n){ char *D = new char[n]; Egde *L = new Egde[n-1]; int min, Dem = 0, Sum = 0, T = 0, Temp; for(int i=0; i 0 && min>A[i][j]&& !(D[i]!=0 && D[i]==D[j])) { min = A[i][j]; L[Dem].x = i; L[Dem].y = j; } 2/2/2017 32 /*Tạo ra cây mới*/ if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){ T++; D[L[Dem].x] = D[L[Dem].y] = T; } /*Đưa đỉnh tương ứng vào cây*/ if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0) D[L[Dem].x] = D[L[Dem].y]; /*Đưa đỉnh tương ứng vào cây*/ if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0) D[L[Dem].y] = D[L[Dem].x]; /*Ghép 2 cây thành 1 cây mới*/ if(D[L[Dem].x] != D[L[Dem].y] && D[L[Dem].y]!=0) { Temp = D[L[Dem].x]; for( i=0; i<n; i++) if(Temp==D[i]) D[i]=D[L[Dem].y]; } Sum+=min; Dem++; } while(Dem<n-1); } 2/2/2017 33 11
12. 2/2/2017 Nội dung 1. Lược đồ chung 2. Bài toán cái túi 3. Bài toán người du lịch 4. Đường đi ngắn nhất 5. Cây bao trùm nhỏ nhất 6. Bài toán tô màu 7. Bài toán các khoảng không giao nhau 2/2/2017 34 Vấn đề • Suppose that you are responsible for scheduling times for lectures in a university . • You want to make sure that any two lectures with a common student occur at different times to avoid a conflict. • We could put the various lectures on a chart and mark with an \X" any pair that has students in common. 2/2/2017 35 Vấn đề 2/2/2017 36 12
13. 2/2/2017 • A more convenient representation of this information is a graph: One vertex for each lecture and in which two vertices are joined if there is a conflict between them 2/2/2017 37 Bài toán • Bài toán: Tô mỗi đỉnh 1 màu sao cho 2 đỉnh kề nhau có màu khác nhau. Tìm cách tô tất cả đỉnh của đồ thị với số màu ít nhất. • Ý nghĩa: Xếp lịch thi cuối kỳ sao cho số buổi cần tổ chức là ít nhất. 2/2/2017 38 Tô màu tham lam • Ý tưởng – Qui ước màu là các số: 1, 2, 3, 1. Tô màu một đỉnh bất kỳ với màu 1 2. Với đỉnh v chưa tô màu: Tô nó với màu là số nhỏ nhất chưa dùng với các đỉnh kề và đã được tô màu của v. (Nếu tất cả các đỉnh kề của v đã tô màu -> v sẽ được tô với màu mới). 3. Lặp lại bước 2 cho đến khi tất cả các đỉnh được tô màu. 2/2/2017 39 13
14. 2/2/2017 Minh họa • Tô màu (tham lam) đồ thị sau • Giả sử tô theo thứ tự: G, L, H , P , M , A, I , S , C 2/2/2017 40 Minh họa Then we would color G with color 1 (green), L with color 2 (red) since adjacency with G prevents it from receiving color 1 (green), and we color H with color 3 (blue) since adjacency with G and L prevents it from receiving colors 1 and 2 (green and red) • Tô theo thứ tự: G, L, H , P , M , A, I , S , C 2/2/2017 41 Minh họa P and M also cannot receive colors 1 and 2 (green and red), so they are given color 3 (blue): • Tô theo thứ tự: G, L, H , P , M , A, I , S , C 2/2/2017 42 14
15. 2/2/2017 Minh họa Then A cannot receive colors 1 and 3 (green and blue), so we give it color 2 (red), while I cannot receive colors 2 and 3 (red and blue), so we give it color 1 (green) • Tô theo thứ tự: G, L, H , P , M , A, I , S , C 2/2/2017 43 Minh họa Vertex S cannot receive color 1, 2, or 3, and so we give it color 4 (say , yellow). Vertex C cannot receive color 2 or 4 (red or yellow), so we give it color 1 (green) • Tô theo thứ tự: G, L, H , P , M , A, I , S , C 2/2/2017 44 Minh họa 2 • Tô theo thứ tự: A, I , P , M , S , C , H , L, G 2/2/2017 45 15
16. 2/2/2017 Đánh giá 2/2/2017 46 Nội dung 1. Lược đồ chung 2. Bài toán cái túi 3. Bài toán người du lịch 4. Đường đi ngắn nhất 5. Cây bao trùm nhỏ nhất 6. Bài toán tô màu 7. Bài toán các khoảng không giao nhau 2/2/2017 47 Bài toán • Có n công việc cần thực hiện; ai - thời điểm bắt đầu, bi - thời điểm kết thúc công việc i (i=1 n) • Hãy chọn ra các công việc để một người có thể thực hiện được nhiều việc nhất. • Các dạng tương tự: Bài toán xếp thời gian biểu cho các hội thảo, bài toán lựa chọn hành động (Activity Selection) 2/2/2017 48 16
17. 2/2/2017 Thuật toán xếp lịch 1 • Ý tưởng (tham lam): – Gọi C là tập các công việc ban đầu – Gọi S là tập các công việc được lựa chọn – Sắp xếp các công việc theo thứ tự tăng dần của đầu mút trái (ai). – Lần lượt xét các đoạn trong danh sách theo thứ tự đã sắp xếp và bổ sung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. 2/2/2017 49 Thuật toán xếp lịch 1 • Chi tiết 2/2/2017 50 Minh họa • Cho 8 công việc 2 6 1 5 7 3 4 8 • Sắp xếp công việc theo thứ tự tăng dần của nút trái ta được thứ tự các công việc C = {3, 1, 2, 5, 6, 4, 8, 7} 2/2/2017 51 17
18. 2/2/2017 Khởi tạo 2 6 1 5 7 3 4 8 C = {3, 1, 2, 5, 6, 4, 8, 7} S = {} 2/2/2017 52 Lặp 2 6 1 5 7 3 4 8 C = {3, 1, 2, 5, 6, 4, 8, 7} SS S= = ={3, {3} {} 6} 2/2/2017 53 Kết quả TT1 2 6 1 5 7 3 4 8 C = {3, 1, 2, 5, 6, 4, 8, 7} 3 6 S = {3, 6} 2/2/2017 54 18
19. 2/2/2017 Dễ thấy 2 6 1 5 7 3 4 8 C = {3, 1, 2, 5, 6, 4, 8, 7} Phương án S = {1, 5, 7} 3 6 1 5 7 tốt hơn S = {3, 6} 2/2/2017 55 Thuật toán xếp lịch 2 • Ý tưởng (tham lam): – Gọi C là tập các công việc ban đầu – Gọi S là tập các công việc được lựa chọn – Sắp xếp các công việc theo thứ tự tăng dần của thời gian thực hiện công việc (bi - ai). – Lần lượt xét các đoạn trong danh sách theo thứ tự đã sắp xếp và bổ sung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. 2/2/2017 56 Thuật toán xếp lịch 3 • Ý tưởng (tham lam): – Gọi C là tập các công việc ban đầu – Gọi S là tập các công việc được lựa chọn – Sắp xếp các công việc theo thứ tự không giảm của đầu mút phải (bi). – Lần lượt xét các đoạn trong danh sách theo thứ tự đã sắp xếp và bổ sung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. 2/2/2017 57 19
20. 2/2/2017 Minh họa • Cho 8 công việc 2 6 1 5 7 3 4 8 • Sắp xếp công việc theo thứ tự không giảm của mút phải ta được thứ tự các công việc C = {1, 2, 3, 4, 5, 6, 8, 7} 2/2/2017 58 Khởi tạo 2 6 1 5 7 3 4 8 C = {1, 2, 3, 4, 5, 6, 8, 7} S = {} 2/2/2017 59 Lặp 2 6 1 5 7 3 4 8 C = {1, 2, 3, 4, 5, 6, 8, 7} SS =S S= {1,= ={1, {1} {}4, 4} 8} 2/2/2017 60 20
21. 2/2/2017 Kết quả TT3 2 6 1 5 7 3 4 8 C = {1, 2, 3, 4, 5, 6, 8, 7} 1 4 8 S = {1, 4, 8} 2/2/2017 61 Cài đặt • ACTIONSELECTION3(a[i], b[i]): . Sort (a[i],b[i]) in increasing order by b[i] . S = {1} . t = 1 . for i = 2 to n if b[t]≤a[i] //C[i] does not confict with C[t] t = i S = S ∪ {i} . return S 2/2/2017 62 Đánh giá • Độ phức tạp T(n) = ? • Mệnh đề: Thuật toán xếp lịch 3 cho lời giải tối ưu của bài toán 2/2/2017 63 21
22. 2/2/2017 Bài tập 1. Thực hiện từng bước giải thuật Prim trên các đồ thị sau: 2/2/2017 64 Bài tập 2. Mô tả chi tiết thuật toán Kruskal và thực hiện từng bước giải thuật đó trên các đồ thị sau và so sánh kết quả với bài 1 2/2/2017 65 Bài tập 3. Cài đặt thuật toán Prim. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết. 4. Cài đặt thuật toán Kruskal. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết. 5. Cài đặt thuật toán xếp lịch theo ý tưởng tham lam. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết. 6. Cài đặt thuật toán tô màu đồ thị. Đánh giá độ phức tạp bằng thực nghiệm và so sánh với lý thuyết. 2/2/2017 66 22
23. 2/2/2017 Nội dung đã học 1. Lược đồ chung 2. Bài toán cái túi 3. Bài toán người du lịch 4. Đường đi ngắn nhất 5. Cây bao trùm nhỏ nhất 6. Bài toán tô màu 7. Bài toán các khoảng không giao nhau 2/2/2017 67 23