›

Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Đường đi ngắn nhất - Lê Nguyên Khôi

pdf 31 trang huongle 5980
Download
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 - Đường đi ngắn nhất - 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:

  • pdfbai_giang_thiet_ke_danh_gia_thuat_toan_duong_di_ngan_nhat_le.pdf

Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Đường đi ngắn nhất - Lê Nguyên Khôi

  1. ế ế ậ ườ ắ ấ ườ ạ ọ ệ
  2. ộ  ng i  Tính ch t ng i ng n nh t  ng i ng n nh t t mt nh  Thu t toán Dijkstra  ng i ng n nh t gi a mi nh  Thu t toán Floyd–Warshall 1
  3. ườ ị a  Trong th vô h ng = ,  ng i  là dãy các nh , , ,  2 nh liên ti p , c ni bi 1 cnh trong .  c gi là ng i t n  Chu trình  là ng i , , , vi > 1  trong ó nh u tiên phân bi t và =  Vi th có h ng, trong mt ng i hay chu trình, 2 nh liên ti p (, ) ph i là mt cung thu c 2
  4. ườ ọ ố th có h ng = v i hàm tr ng s cung . Tr ng s c a ng i c nh ngh a: Ví d : 3
  5. ườ ắ ấ ị a ng i ng n nh t ( NN) t n là ng i có tr ng s nh nh t t n . Tr ng s ng i ng n nh t t n c nh ngh a: , = min : đườngđitừđến Chú ý: , = ∞không tn ti ng i t n . 4
  6. ườ ắ ấ ấ Cu trúc con ti u  Mt ng i con c a m t ng i ng n nh t là m t ng i ng n nh t  , , , là NN t n  = , , , là ng i con ca t n vi 0 ≤ ≤ ≤  = , , , là NN t n 5
  7. ườ ắ ấ ấ Cu trúc con ti u – ch ng minh  Chia thành các on con  Khi ó, + +  Gi s có ng t n , vi tr ng s ′ ′ <  Khi ó, là ng i t n vi tr ng s nh hơn  Mâu thu n vi gi thi t là NN t n 6
  8. ườ ắ ấ ấ Bt ng th c tam giác  V i m i nh , ta có + 7
  9. ườ ắ ấ ấ Tr ng s âm  N u th có chu trình v i tr ng s âm, m t s ng i ng n nh t có th không tn ti 8
  10. ườ ắ ấ ừ ộ ỉ ồ  Bài toán. T m t nh ngu n ∈ , tìm ng i ng n nh t (tr ng s , ) tới m i nh ọ đỉ ∈  N u t t c các tr ng s , không âm, thì mi ng i ng n nh t tn ti  Áp dng chi n l c tham n có th tìm c li gi i ti u  Do NN có tính ch t cu trúc con ti u 9
  11. ườ ắ ấ ừ ộ ỉ ồ  Chi n l c tham n: 1. Duy trì m t t p là các nh sao cho dài ng i ng n nh t t là xác nh 2. M i b c, thêm vào t p nh ∈ − sao cho ng i t n là nh nh t 3. Cp nh t kho ng cách t n các nh li n k 10
  12. ậ a  G i ng i t t i nh là ng i c bi t n u ng i ó ch i qua các nh trong  Dùng m ng : dài ng i t t i l u trong []  Ban u , 0, , v i ≠ = = 11
  13. ậ a  Dùng m ng : dài ng i t t i l u trong []  Ban u , 0, , v i ≠  Ti mi b c:  Ch n mt nh không thu c sao cho nh nh t, thêm vào . Khi ó là ng i ng n nh t t n  Sau ó xác nh li các vi ngoài = min ,[]+(,)  Lp li cho ti khi gm tt c các nh ca th 12
  14. ậ a ọa Ban u 0 {0} 2 9 0 0 3 5 2 1 ∞ 2 = 9 1 4 1 3 = 2 1 4 = 5 8 4 13
  15. ậ a ọa Thêm 3 vào 0 = {0, 3} 2 9 0 = 0 3 5 2 1 = min ∞,[3]+1 =3 2 = min 9,[3]+∞ =9 1 4 1 3 = 2 1 4 = min 5,[3]+∞ =5 8 4 14
  16. ậ a ọa Thêm 1 vào 0 = {0, 3, 1} 2 9 0 = 0 3 5 2 1 = 3 2 = min 9,[1]+4 =7 1 4 1 3 = 2 1 4 = min 5,[1]+∞ =5 8 4 15
  17. ậ a ọa Thêm 4 vào 0 = {0, 3, 1, 4} 2 9 0 = 0 2 1 = 3 3 5 2 = min 7,[4]+1 =6 1 4 1 3 = 2 1 4 = 5 8 4 16
  18. ậ a ọa Thêm 2 vào 0 = {0, 3, 1, 4,2} 2 9 0 = 0 3 2 1 = 3 5 2 = 6 1 4 1 3 = 2 1 4 = 5 8 4 lu dài ng i ng n nh t t 0 t i v i m i ∈ V 17
  19. ậ a ậ {} 18
  20. ậ a ả [] ← for each ∈ – {} do [] ← ∞ ← ∅ ← while ≠ ∅ do ← XTRT − MIN() ← ∪ for each ∈ do if []> []+ () then []← []+ () 19
  21. ồ ị ọ ố Gi s (, ) = 1 cho mi (, ) ∈ . Có áp dng c thu t toán Dijkstra không?  S dng hàng i FIFO thay vì hàng i u tiên Tìm ki m theo b rng (BFS) while ≠ ∅ do ← DEQUEUE() for each ∈ do if = ∞ then []← []+1 ENQUEUE(, ) Phân tích: Th i gian = ( + ) 20
  22. ế ề ộ ọa 21
  23. ườ ắ ấ ữa ọ ặ ỉ T mt nh ngu n  Thu t toán Dijkstra’s Gi a mi cp nh  Thu t toán Dijkstra’s ln Chi n l c tham n  Thu t toán Floyd-Warshall Chi n l c quy ho ch ng 22
  24. ậ aa nh ngh a tr ng s ng i ng n nh t t ti ch i qua các nh trong tp nh 1,2, , Khi ó, , = , ban u = 23
  25. ậ aa  Nu nh nm trên ng i ng n nh t t ti thì ng i t ti và ng i t ti là ng i ng n nh t  Nu là dài ng i không qua , tc là ng i này ch i qua các nh trong , khi ó  Nu là dài ng i qua , thì trên ng i này on t ti có dài , còn on t ti có dài  Do ó min , + 24
  26. ậ aa ọa 0, t p r ng, 15 1 4 5 1 2 3 4 5 1 0 5 ∞ ∞ 50 30 15 5 2 50 0 15 5 3 30 ∞ 0 15 15 2 3 4 15 ∞ 5 0 25
  27. ậ aa ọa min , + 1 2 3 4 1 0 5 ∞ ∞ 15 2 50 0 15 5 1 4 3 30 ∞ 0 15 5 4 15 ∞ 5 0 5 15 5 50 30 1 2 3 4 1 0 5 ∞ ∞ 15 2 3 2 50 0 15 5 3 30 35 0 15 4 15 20 5 0 26
  28. ậ aa ọa min , + 1 2 3 4 1 0 5 ∞ ∞ 15 2 50 0 15 5 1 4 3 30 35 0 15 5 4 15 20 5 0 5 15 5 50 30 1 2 3 4 1 0 5 20 10 15 2 3 2 50 0 15 5 3 30 35 0 15 4 15 20 5 0 27
  29. ậ aa ọa min , + 1 2 3 4 1 0 5 20 10 15 2 50 0 15 5 1 4 3 30 35 0 15 5 4 15 20 5 0 5 15 5 50 30 1 2 3 4 1 0 5 20 10 15 2 3 2 45 0 15 5 3 30 35 0 15 4 15 20 5 0 28
  30. ậ aa ọa min , + 1 2 3 4 1 0 5 20 10 15 2 45 0 15 5 1 4 3 30 35 0 15 5 4 15 20 5 0 5 15 5 50 30 1 2 3 4 1 0 5 15 10 15 2 3 2 20 0 10 5 3 30 35 0 15 4 15 20 5 0 29
  31. ậ aa ả for ← 1 to do for ← 1 to do for ← 1 to do if > + then ← +  Th i gian ch y  ơ n gi n  Hi u qu 30