Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Đồ Thị - Lê Nguyên Khôi
22 trang
6810
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Đồ Thị - Lê Nguyên Khôi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_thiet_ke_danh_gia_thuat_toan_do_thi_le_nguyen_khoi.pdf
Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Đồ Thị - Lê Nguyên Khôi
- ế ế ậ ồ ị ườ ạ ọ ệ
- ộ Đị nh ngh ĩa Bi ểu di ễn Tìm ki ếm Sắp xếp topo 1
- ị a Đồ th ị = ( , ) bao gồm Tập các đỉ nh Tập ⊆ × cạnh Đồ th ị vô hướ ng Cặp cạnh không có th ứ tự , = ( , ) Đồ th ị đị nh hướ ng Cặp cạnh có th ứ tự , ≠ , Cả hai tr ườ ng hợp, ∈ ( ) Nếu liên thông, ≥ − 1 ⟹ log = log 2
- ể ễ Danh sách li ền kề Mảng 1 chi ều danh sách Mỗi danh sách cho một đỉ nh bao gồm Các đỉ nh sao cho , ∈ Ma tr ận li ền kề Mảng 2 chi ều × Đỉ nh đượ c đánh số 1, 2, , Giá tr ị 1 th ể hi ện có cạnh , ∈ 3
- ể ễ a Danh sách li ền kề Mảng 1 chi ều danh sách Mỗi danh sách cho một đỉ nh bao gồm Các đỉ nh sao cho , ͪ ∈ ̿ ̻͘͞ 1 Ɣ 2, 3 ̻͘͞ʞ2ʟ Ɣ ʜ3ʝ ̻͘͞ʞ3ʟ Ɣ ʜʝ ̻͘͞ʞ4ʟ Ɣ ʜ3ʝ 4
- ể ễ a ậ Ma tr ận li ền kề Mảng 2 chi ều × Đỉ nh đượ c đánh số 1, 2, , ͐ Giá tr ị 1 th ể hi ện có cạnh ͝, ͞ ∈ ̿ 5
- ể ễ Danh sách li ền kề Sử dụng khi đồ th ị th ưa nh ỏ hơn nhi ều so với Xác đị nh danh sách đỉ nh đi đượ c từ Ma tr ận li ền kề Sử dụng khi đồ th ị dầy gần bằng Xác đị nh có cạnh , ∈ Sử dụng cho cả đồ th ị vô hướ ng và có hướ ng 6
- ế Xác đị nh cấu trúc của đồ th ị Th ăm tất cả các đỉ nh của Mỗi đỉ nh th ăm một lần Sử dụng các cạnh trong 02 ph ươ ng pháp Theo bề rộng (Breath First Search – BFS) Theo bề sâu (Depth First Search – DFS) 7
- ế Từ lần lượ t th ăm tất cả các li ền kề mà ch ưa đượ c th ăm Sau đó, đỉ nh nào đượ c th ăm tr ướ c thì các đỉ nh k ề nó c ũng s ẽ đượ c th ăm tr ướ c Tiếp tục cho t ới khi không th ể th ăm đỉ nh nào n ữa 8
- ế ụ 1 2 3 4 5 7 8 6 9 10 11 12 13 9
- ế ả Algorithm BFS(u) Input: Đỉ nh u ch ưa đượ c th ăm Kh ởi t ạo hàng đợ i Q rỗng Đánh d ấu đỉ nh u đã đượ c th ăm Q.enqueue(u) while Q.empty() ≠ TRUE v Q.dequeue() for (m ỗi đỉ nh w kề v) if (w ch ưa đượ c th ăm) Đánh dấu w đã đượ c th ăm Q.enqueue(w) 10
- ế Thao tác trên hàng đợ i: ( ) Đỉ nh thêm/bớt ở hàng đợ i 1 lần duy nh ất Duy ệt danh sách li ền kề: ( ) Khi đỉ nh bị lo ại kh ỏi hàng đợ i Một lần duy nh ất Độ dài danh sách Kh ởi tạo: ( ) Đánh dấu các đỉ nh ch ưa th ăm Tổng th ời gian: ( + ) 11
- ế Ứ ụ Xác đị nh có đườ ng đi từ đế n không Ki ểm tra tính liên thông Xác đị nh thành ph ần liên thông 12
- ế Từ th ăm li ền kề Từ th ăm li ền kề Cứ th ể ti ếp tục khi có th ể đượ c Khi tới mà tại không th ăm ti ếp đượ c, quay lại tr ướ c đó, th ăm ′ khác của Tiếp t ục cho t ới khi không th ể th ăm đỉ nh nào n ữa 13
- ế ụ 1 2 3 5 4 6 7 8 9 10 11 12 13 14
- ế ả Algorithm DFS(u) Input: Đỉ nh v ch ưa đượ c th ăm Đánh d ấu đỉ nh u đã đượ c th ăm for (mỗi đỉ nh v kề u) if (v ch ưa đượ c th ăm) Đánh dấu v đã đượ c th ăm DFS(v) 15
- ế Ứ ụ Phân lớp cung Phát hi ện chu trình 16
- ắ ế Nhi ều danh quan hệ trên tập đố i tượ ng có th ể bi ểu di ễn bới đồ th ị đị nh hướ ng không chu trình Quan hệ th ứ tự bộ ph ận Quan hệ th ứ tự th ời gian gi ữa các nhi ệm vụ trong đề án Quan hệ th ứ tự th ời gian gi ữa các môn học trong một ch ươ ng trình học 17
- ắ ế ụ LTNC Toán cao cấp LTH ĐT CTDL > Trí tu ệ LTTT nhân tạo 18
- ắ ế = ( , ) là đồ th ị đị nh hướ ng không chu trình Sắp xếp các đỉ nh đồ th ị thành một danh sách Sao cho nếu có cung , thì cần đứ ng tr ướ c trong danh sách đó a b (a, c, b, d, e, f) ho ặc c d (a, b, d, c, e, f) e f 19
- ắ ế Sắp xếp topo dựa trên DFS Th ực hi ện DFS trên đồ th ị Khi kết thúc quá trình DFS trên một đỉ nh thì thêm vào cu ối danh sách Kết thúc DFS trên toàn đồ th ị, đả o ng ượ c danh sách, đượ c sắp xếp topo 20
- ắ ế ụ DFS(a) a b DFS(c) DFS(e) L = (e) L = (e, c) DFS(d) c d DFS(f) L = (e, c, f) L = (e, c, f, d) L = (e, c, f, d, a) DFS(b) e f L = (e, c, f, d, a, b) L = (b, a, d, f, c, e) 21
