Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 14: Đồ thị (Phần 2)

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 14: Đồ thị (Phần 2)

1. Bài 14: Đồ thị (2/2) Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
2. Nội dung chính 1. Đồ thị và các khái niệm liên quan 2. Cài đặt đồ thị  Tìm đường đi ngắn nhất  Từ một đỉnh nguồn 3. Một số bài toán tiêu  Giữa mọi cặp đỉnh biểu  Tìm cây bao trùm ngắn  Đi qua/duyệt đồ thị nhất  BFS, DFS  Prim  Sắp xếp topo trên đồ thị  Kruskal định hướng không có 4. Đồ thị và C++ chu trình 2 diepht@vnu
3. 3.1. Đi qua đồ thị
4. 3.2. Sắp xếp topo
5. Đồ thị định hướng không chu trình  Thuật ngữ  directed acyclic graph (DAG)  acyclic digraph  Nhiều dạng quan hệ trên một tập đối tượng có thể biểu diễn bởi DAG. Ví dụ:  Quan hệ thứ tự bộ phận a b trên một tập A  Quan hệ thứ tự thời gian giữa các nhiệm vụ c d trong một đề án  Quan hệ thứ tự thời gian giữa các môn học e f trong một chương trình học 5 diepht@vnu
6. LTNC Toán cao cấp LTHĐT CTDL > Trí tuệ LTTT nhân tạo 6 diepht@vnu
7. Sắp xếp topo (topological sort)  Cho G = (V,E) là một DAG, ta cần sắp xếp các đỉnh của đồ thị thành một danh sách  sao cho nếu có cung (u,v) thì u cần phải đứng trước v trong danh sách đó. a b c d (a, c, b, d, e, f) hoặc (a, b, d, c, e, f) e f  Dùng kĩ thuật tìm kiếm theo độ sâu? 7 diepht@vnu
8. Ý tưởng toposort dựa trên DFS Algorithm DFS(v) • Thực hiện // Tìm kiếm theo độ sâu xuất phát từ v. Input: Đỉnh v chưa được thăm DFSTraversal trên đồ for (mỗi đỉnh u kề v) thị G, thêm lệnh if ( u chưa được thăm) Đánh dấu u đã được thăm; L.append(v) vào cuối DFS(u) hàm DFS(v) Algorithm DFSTraversal(G) • Đảo ngược L // Đi qua đồ thị G=(V, E) theo độ sâu for (mỗi v ∈V) Đánh dấu v chưa được thăm; for (mỗi v ∈V) if (v chưa được thăm) [Tác giả: Tarjan] Thăm v và đánh dấu v đã được thăm; DFS(v); 8 diepht@vnu
9. Minh họa TopoSort(G) DFS(a) DFS(c) a b DFS(e) L = (e) L = (e, c) c d DFS(d) DFS(f) L = (e, c, f) L = (e, c, f, d) L = (e, c, f, d, a) e f DFS(b) L = (e, c, f, d, a, b) L = (b, a, d, f, c, e) 9 diepht@vnu
10. 3.3. Tìm đường đi ngắn nhất
11. Tổng quan  Tìm đường đi ngắn nhất trong đồ thị  Không trọng số: Dùng BFS  Có trọng số  Trọng số có thể âm: Không xét  Bellman-Ford  Trọng số không âm  độ dài cung (u, v) là c(u,v)  không có cung từ u tới v thì c(u,v) = +∞  Xét hai vấn đề  Tìm đường đi ngắn nhất từ một đỉnh nguồn tới các đỉnh còn lại.  single-source shortest path problem  Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.  all-pairs shortest path problem 11 diepht@vnu
12. Thuật toán Dijkstra cho bài single-source  Ví dụ: tìm đường đi ngắn nhất từ đỉnh nguồn là đỉnh 0 0 9  Thiết kế dựa vào kỹ thuật tham ăn 2  Xác định đường đi ngắn nhất từ đỉnh 3 5 2 nguồn a tới các đỉnh còn lại qua các bước 1 4  Mỗi bước ta xác định đường đi ngắn 1 nhất từ a tới một đỉnh  1 Lưu các đỉnh đã xác định đường đi ngắn 8 4 nhất từ a tới chúng vào tập S  Ban đầu tập S chỉ chứa một đỉnh nguồn a 12 diepht@vnu
13. Thuật toán Dijkstra  Gọi đường đi từ a tới đỉnh b là đường đi đặc biệt nếu đường đi đó chỉ đi qua các đỉnh trong S  Dùng mảng D: Độ dài đường đi đặc biệt từ a tới b lưu trong D[b]  Ban đầu S = {a}, D[a] = 0, D[b] = c(a, b) với b≠a S a=v0 vk-1 b=vk 13 diepht@vnu
14. Thuật toán Dijkstra  Dùng mảng D: Độ dài đường đi đặc biệt từ a tới b lưu trong D[b]  Ban đầu S = {a}, D[a] = 0, D[b] = c(a, b) với b≠a  Tại mỗi bước  Chọn một đỉnh u không thuộc S mà D[u] nhỏ nhất và thêm u vào S . xem D[u] là độ dài đường đi ngắn nhất từ a tới u  Sau đó, xác định lại các D[b] với b ở ngoài S D[b] = min(D[b], D[u] + c(u, b))  Lặp lại cho tới khi S gồm tất cả các đỉnh của đồ thị 14 diepht@vnu
15. Minh họa thuật toán Dijkstra: Ban đầu  S = {0} 0  D[0] = 0 9 2  D[1] = ∞ 3 5 2  D[2] = 9  D[3] = 2 1 4 1  D[4] = 5 1 8 4 15 diepht@vnu
16. Minh họa thuật toán Dijkstra: Thêm 3 vào S  S = {0, 3} 0  D[0] = 0 9 2  D[1] = min(∞, D[3] + 1) = 3 3 5 2  D[2] = min(9, D[3] + ∞) = 9  D[3] = 2 1 4 1  D[4] = min(5, D[3] + ∞) = 5 1 8 4 16 diepht@vnu
17. Minh họa thuật toán Dijkstra: Thêm 1 vào S  S = {0, 3, 1} 0  D[0] = 0 9 2  D[1] = 3 3 5 2  D[2] = min(9, D[1] + 4) = 7  D[3] = 2 1 4 1  D[4] = min(5, D[1] + ∞) = 5 1 8 4 17 diepht@vnu
18. Minh họa thuật toán Dijkstra: Thêm 4 vào S  S = {0, 3, 1, 4} 0  D[0] = 0 9 2  D[1] = 3 3 5 2  D[2] = min(7, D[4] + 1) = 6  D[3] = 2 1 4 1  D[4] = 5 1 8 4 18 diepht@vnu
19. Minh họa thuật toán Dijkstra: Thêm 2 vào S  S = {0, 3, 1, 4, 2} 0  D[0] = 0 9 2  D[1] = 3 3 5 2  D[2] = 6  D[3] = 2 1 4 1  D[4] = 5  D[b] lưu độ dài đường đi 1 4 8 ngắn nhất từ a=0 tới b, với mọi b∈V 19 diepht@vnu
20. Các vấn đề khác  Ghi lại vết đường đi ngắn nhất từ nguồn tới các đỉnh khác  Tính đúng đắn của thuật toán Dijkstra  Dùng hàng ưu tiên lưu tập đỉnh ngoài S để tăng hiệu quả O(|V|log|V| + |E|log|V|) 20 diepht@vnu
21. Thuật toán Floyd cho bài all-pairs  Thiết kế dựa trên kỹ thuật quy hoạch động  Ký hiệu Sk là tập các đỉnh từ 0 đến k  Sk = {0,1, ,k}, k <= n-1  Gọi Ak(i,j) là độ dài đường đi ngắn nhất từ đỉnh i tới đỉnh j nhưng chỉ đi qua các đỉnh trong tập Sk  Khi k = n-1 thì Sn-1 = V An-1(i,j) chính là đường đi ngắn nhất từ i tới j trong đồ thị đã cho  Khi k = -1, Sk rỗng A-1(i,j) = c(i,j) 21 diepht@vnu
22. Minh họa: k = -1 S-1 rỗng, A-1(i,j) cho trong bảng 15 0 3 0 1 2 3 5 0 0 5 ∞ ∞ 1 50 0 15 5 5 15 5 50 30 2 30 ∞ 0 15 3 15 ∞ 5 0 15 1 2 22 diepht@vnu
23. Công thức tính Ak từ Ak-1  Nhận xét quan trọng  Nếu đỉnh k nằm trên đường đi ngắn nhất từ đỉnh i tới đỉnh j thì đoạn đường từ i tới k và đoạn đường từ k tới j phải là đường đi ngắn nhất từ i tới k và từ k tới j tương ứng  Nếu Ak(i,j) là độ dài đường đi không qua đỉnh k, tức là đường đi này chỉ đi qua các đỉnh trong Sk-1 thì Ak(i,j) = Ak-1(i,j)  Nếu Ak(i,j) là độ dài của đường đi qua đỉnh k thì trên đường đi này đoạn từ i tới k có độ dài là Ak-1(i,k), còn đoạn đường từ k tới j có độ dài là Ak-1(k,j)  Do đó Ak(i,j) = min( Ak-1(i,j) , Ak-1(i,k) + Ak-1(k,j) ) 23 diepht@vnu
24. Minh họa: k=0 ? 0 1 2 3 15 0 0 5 ∞ ∞ 0 3 1 50 0 15 5 A-1 5 2 30 ∞ 0 15 5 15 3 15 ∞ 5 0 5 50 30 0 1 2 3 15 1 2 0 0 5 ∞ ∞ 50 A0 1 0 15 5 2 30 35 0 15 3 15 20 5 0 24 diepht@vnu
25. Minh họa: k=0 ? 0 1 2 3 15 0 0 5 ∞ ∞ 0 3 1 50 0 15 5 A0 5 2 30 35 0 15 5 15 3 15 20 5 0 5 50 30 0 1 2 3 15 1 2 0 0 5 20 10 50 0 15 5 A1 1 2 30 35 0 15 3 15 20 5 0 25 diepht@vnu
26. Minh họa: k=0 ? 0 1 2 3 15 0 0 5 20 10 0 3 1 50 0 15 5 A1 5 2 30 35 0 15 5 15 3 15 20 5 0 5 50 30 0 1 2 3 15 1 2 0 0 5 20 10 A2 1 45 0 15 5 2 30 35 0 15 3 15 20 5 0 26 diepht@vnu
27. Minh họa: k=0 ? 0 1 2 3 15 0 0 5 20 10 0 3 1 45 0 15 5 A2 5 2 30 35 0 15 5 15 3 15 20 5 0 5 50 30 0 1 2 3 15 1 2 0 0 5 15 10 A3 1 20 0 10 5 2 30 35 0 15 3 15 20 5 0 27 diepht@vnu
28. 3.4. Tìm cây bao trùm ngắn nhất
29. Bài toán  G = (V,E) là đồ thị vô hướng liên thông  G’ = (V,T) có T ⊆ E , liên thông và không có chu trình được gọi là cây bao trùm của G  Cây này có |V| - 1 cạnh  Ta cần tìm cây bao trùm ngắn nhất của một đồ thị G vô hướng liên thông có trọng số không âm  tức là cây bao trùm có tổng độ dài các cạnh là nhỏ nhất  Thuật ngữ: minimum spanning tree (MST) 29 diepht@vnu
30. Minh họa một cây bao trùm ngắn nhất 4 0 4 9 3 1 7 3 6 5 8 8 5 1 2 2 (a) 0 3 1 4 3 6 5 5 1 2 2 (b) 30 diepht@vnu
31. Ý tưởng  Thiết kế theo kỹ thuật tham ăn  Xây dựng tập T các cạnh dần từng bước xuất phát từ T rỗng  Trong mỗi bước lặp, ta sẽ chọn cạnh (u,v) ngắn nhất trong các cạnh còn lại để đưa vào tập T  Prim: T ∪ (u, v) phải liên thông, không có chu trình  Kruskal: T ∪ (u, v) không có chu trình  Sử dụng KDLTT họ các tập con không cắt nhau (disjoint set ADT) [chương 13] 31 diepht@vnu
32. Minh họa 4 0 4 9 3 1 7 3 6 5 8 8 5 1 2 2 32 diepht@vnu
33. Các vấn đề khác  Độ phức tạp thời gian  Tính đúng đắn 33 diepht@vnu
34. Tóm tắt 3.2. Sắp xếp topo trên DAG: Thuật toán của Tarjan 3.3. Tìm đường đi ngắn nhất  Single-source: Thuật toán tham ăn Dijsktra  All-pairs: Thuật toán quy hoạch động Floyd 3.4. Tìm cây bao trùm ngắn nhất  Thuật toán tham ăn Prim  Thuật toán tham ăn Kruskal 34 diepht@vnu