1. Trang Chủ
  2. Toán học
  3. Bài giảng Toán rời rạc: Đường đi trên đồ thị (Version 0.2) - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Đường đi trên đồ thị (Version 0.2) - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Đường đi trên đồ thị (Version 0.2) cung cấp cho người học những nội dung kiến thức như: Khoảng cách và tìm kiếm theo chiều rộng, thuật toán Dijkstra, cài đặt hàng đợi ưu tiên, đường đi ngắn nhất khi có cạnh độ dài âm, đường đi ngắn nhất trong một DAG. Mời các bạn cùng tham khảo. Đường đi trên đồ thị (Version 0.2) Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 52 Tài liệu tham khảo ▶ S. Dasgupta, C. H. Papadimitriou, a

Thể loại Tài liệu miễn phí Toán học

Số trang 52

Ngày tạo 10/10/2021 11:31:02 PM +00:00

Loại tệp PDF

Kích thước 2.05 M

Tên tệp

Tải Bài giảng Toán rời rạc: Đường đi trên đồ thị (Vers... (.pdf)

Xem mẫu

  1. Đường đi trên đồ thị (Version 0.2) Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 52
  2. Tài liệu tham khảo ▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2016. ▶ Chú ý: Nhiều hình vẽ trong tài liệu được lấy tùy tiện mà chưa xin phép. CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 52
  3. Nội dung Khoảng cách và tìm kiếm theo chiều rộng Thuật toán Dijkstra Cài đặt hàng đợi ưu tiên Đường đi ngắn nhất khi có cạnh độ dài âm Đường đi ngắn nhất trong một DAG CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. In Figure 4.2, for example, vertex B is at distance 2 from S, and there are two shorte DFStovàit. đường paths When S is điheld up, the strings along each of these paths become ta aph and (b) its depth-first search tree. Figure 4.1 (a) A simple graph and (b) its depth-first search tree. (b) S (a) (b) S A E S A A D A D B E B E B D C B C C 104 Đường đi trên cây DFS thường không phải là đường đi ngắn nhất. CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 52
  5. vertex s high enough, the other balls that get pulled up along with it are precisely theKhoảng cách from s. And to find their distances from s, you need only vertices reachable measure how far below s they hang. In Figure 4.2, for example, vertex B is at distance 2 from S, and there are two shortest paths to it. When S is held up, the strings along each of these paths become taut. Khoảng cách giữa hai đỉnh là độ dài của đường đi ngắn nhất giữa Figure 4.1 (a) A simple graph and (b) its depth-first search tree. chúng. (a) (b) v Khoảng cách (S − v) S E S A A A D B C B E D C B D E C 104 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 52
  6. Mô hình vật lý của đồ thị Algorithms 105 Algorithm Giả sử rằng mọi cạnh có cùng độ dài. Ta nhấc đỉnh S lên: A physical model Figure 4.2 of a graph. A physical model of a graph. S S S E A S A A C D EA C D E C D B C B B B On the other hand, edge (D, E ) plays no role in any shortest path and the hand, edgeslack. remains (D, E ) plays no role in any shortest path and therefore k. CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 52
  7. Algorithms 105 Tìm kiếm theo chiều rộng (Breadth-First Search) A physical model of a graph. Chia đồ thị thành các mức: S ▶ S là mức có khoảng cách 0. E S A ▶ Các đỉnh có khoảng cách tới S bằng 1. A C D E ▶ Các đỉnh có khoảng cách tới D CS bằng 2 B ▶ ... B Ý tưởng thuật toán: Khi mức d đã được xác định, mức d + 1 có er hand, thể edge thăm (D, bằngE )cách plays no qua duyệt rolecác in any hàngshortest xóm củapath mức and d. therefore ck. adth-first search .2, the lifting of s partitions CuuDuongThanCong.com the graph into layers: s itself, the nodes at7 / 52 https://fb.com/tailieudientucntt
  8. Ý tưởng loang theo chiều rộng Khởi tạo: Hàng đợi Q chỉ chứa đỉnh s, là đỉnh duy nhất ở mức 0. Với mỗi khoảng cách d = 1, 2, 3, . . . , ▶ sẽ có thời điểm Q chỉ chứa các đỉnh có khoảng cách d và không có gì khác. ▶ Khi đó các đỉnh có khoảng cách d này sẽ được loại bỏ dần từ đầu hàng đợi, ▶ và các hàng xóm chưa được thăm sẽ được thêm vào cuối hàng đợi. CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 52
  9. n Figure 4.2, for example, vertex B is at distance 2 from S, and there are two aths to it. When S is held up, the strings along each of these paths beco Bài tập igure 4.1 (a) A simple graph and (b) its depth-first search tree. Chạy thuật toán BFS cho đồ thị dưới đây bắt đầu từ đỉnh S. Ghi ra hàng đợi Q sau mỗi lần thăm đỉnh. (a) (b) S E S A Đỉnh thăm Hàng đợi A S [S] B D C B C 04 CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 52
  10. procedure bfs(G, s) Input: đồ thị G = (V, E), có hướng hoặc vô hướng; một đỉnh s ∈ V Output: Với mỗi đỉnh u đến được từ s, dist(u) = khoảng cách từ s tới u. for all u ∈ V: dist(u) = ∞ dist(s) = 0 Q = [s] (hàng đợi chỉ chứa s) while Q khác rỗng: u = eject(Q) (loại bỏ u khỏi hàng đợi) for all edges (u, v) ∈ E: if dist(v) = ∞: inject(Q, v) (thêm v vào hàng đợi) dist(v) = dist(u) + 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 52
  11. vertex s high enough, the other balls that get pulled up along with it are precisely the vertices reachable from s. And to find their distances from s, you need only measure how far below s they hang. In Figure 4.2, for example, vertex B is at distance 2 from S, and there are two shortest paths to it. When S is held up, the strings along each of these paths become taut. Bài tập Hãy chạy thuật toán BFS cho đồ thị dưới đây và ghi ra nội dung Figure 4.1 (a) của hàng đợiAQsimple graph sau mỗi and (b) its depth-first search tree. bước: (a) (b) S E S A Thứ tự thăm đỉnh Hàng đợi S A [S] D B E D C B C 104 CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 52
  12. Nội dung Khoảng cách và tìm kiếm theo chiều rộng Thuật toán Dijkstra Cài đặt hàng đợi ưu tiên Đường đi ngắn nhất khi có cạnh độ dài âm Đường đi ngắn nhất trong một DAG CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. (each stretch of highway) is important. For the remainder of this chapter, we will deal with this more general scenario, annotating every edge e ∈ E with a length le . Độ dài của cạnh If e = (u, v), we will sometimes also write l(u, v) or luv . Figure 4.5 Edge lengths often matter. Sacramento 95 San 133 Francisco Reno 290 271 409 445 Bakersfield 291 112 Los Las Angeles 275 Vegas These le ’s do not have to correspond to physical lengths. They could denote time (driving time between cities) or money (cost of taking a bus), or any other quantity Trong các bài toán thực tế, mỗi cạnh e thường gắn với độ dài le . that we would like to conserve. In fact, there are cases in which we need to use negative lengths, but we will briefly overlook this particular complication. CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 52
  14. Câu hỏi Liệu ta có thể sửa thuật toán BFS để nó chạy được trên đồ thị tổng quát G = (V, E) trong đó mỗi cạnh có độ dài nguyên dương le ? CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 52
  15. Fordummy any edgenodes between e = (u, v) of E , ureplace and v.it by le edges of length 1, by adding le − 1 dummy nodes between u and v. Tách cạnh thành Graph G ′ các contains ′ cạnh all the với Vđộthatdài vertices đơnus,vịand the distances interest betwee themGarecontains Graph exactlyallthe thesame vertices as in that V G interest . Most us, and thethe ′ importantly, distances edges between of G all have un them length. exactly are the same Therefore, as incompute we can G . Most importantly, distances intheG edges of G ′ allBFS by running haveon unit G ′. length. Therefore, we can compute distances in G by running BFS on G ′ . Figure Figure 4.64.6Breaking Breaking edges edges into unit-length into unit-length pieces. pieces. 2 2 BB 2 2 D D B B D D AA 1 3 32 A 1 2 A 1 1 C E C 4 4 E C C E E Alarm clocks Thay cạnhclocks IfAlarm efficiency ewere not v) = (u, bởi lwe an issue, e cạnh độ dài could stop Butbằng here.1, when cách thêm G has very −1 leedges, long the đỉnh G ′ it engenders If tạm efficiency u vàisnot giữa were thickly v. populated an issue, with stop we could dummy nodes, here. But and whentheGBFS hasspends very long edge most the of G ′itsit time diligently engenders is computing distances with thickly populated to these nodes nodes, dummy that we and don’tthe careBFS spen about at all. most of its time diligently computing distances to these nodes that we don’t ca Toabout all. concretely, consider the graphs G and G ′ of Figure 4.7, and imagine atmore see this that the BFS, started at node s of G ′ , advances by one unit of distance per minute. For ′ Tofirst the see99this more itconcretely, minutes consideralong tediously progresses the graphs G and S − A and S −G of endless B, an Figure 4.7, and imagin desert ′ ofthat dummythe BFS, started nodes. at node Is there some sway of Gwe, advances can snoozeby one unit through theseof distance per minute. F boring phases thehave and first an CuuDuongThanCong.com 99 minutes alarm wakeithttps://fb.com/tailieudientucntt tediously us up whenever progresses along interesting something S − A andisS happening— − B, an endless dese 15 / 52
  16. Vấn đề Algorith Algorithms 109 Figure 4.7 BFS on G ′ is mostly uneventful. The dotted lines show some “wavefronts.” Figure 4.7 BFS on G ′ is mostly uneventful. The dotted lines show some early “wavefronts.” G: G: G: 100100 A A G: A A S S 50 50 S S 200 200 B B B More generally, at any given moment the breadth-first search is advancing along certain edges of G , and there is an alarm for every endpoint node toward which it More generally, Cả is99moving, bước set at go any di tochuyển given off atđầu moment tiên đềutime the estimated xửofthe Sbreadth-first − at lýarrival Athat S − search và node. B trên Some of is cácadvancin these certain might đỉnh tạm.edges be of G , overestimatesand there because is BFS an may alarm later for find every shortcuts,endpoint as a result node of futuretoward arrivals elsewhere. is moving, set to go In off the preceding example, a quicker at the estimated time of route to B was arrival atrevealed upon Some that node. arrival at A. However, nothing interesting can possibly happen before an alarm goes might off. be Theoverestimates sounding of the next because alarm mustBFS may signal therefore later the find shortcuts, arrival as a result o of the wavefront arrivals elsewhere. to a real node u ∈ VInby the preceding BFS. example, At that point, BFS might a quicker also startroute to Balong advancing was reveal someatnew arrival A. edges out of u, However, and alarms nothing need to be can interesting set for their endpoints. possibly happen before an ala off. The sounding The following of the “alarm clock next alarmfaithfully algorithm” must therefore signal simulates the the arrival execution of the w of BFS on ′ G. to a real node u ∈ V by CuuDuongThanCong.com BFS. At that point, BFS might also start advancin https://fb.com/tailieudientucntt 16 / 52
  17. Giải pháp: Đặt Alarm clock! Chapter 4 Figure 4.7 BFS on G ′ is m “wavefronts.” ▶ Với đỉnh A, đặt hẹn T = 100 G: G ▶ Với đỉnh B, đặt hẹn T = 200 100 A ▶ Bị đánh thức khi A được thăm lúc S 50 T = 100 ▶ Ước lượng lại thời gian đến của B là 200 B T = 150; và đặt lại Alarm cho B. More generally, at any given certain edges of G , and there is moving, set to go off at th might be overestimates beca arrivals elsewhere. In the prec CuuDuongThanCong.com https://fb.com/tailieudientucntt arrival at A. However, nothin 17 / 52
  18. Thuật toán Alarm Clock Đặt một alarm clock cho đỉnh s tại thời điểm T = 0 Lặp lại cho đến khi không còn alarm: Giả sử alarm kêu tại thời điểm T cho đỉnh u. Vậy thì: - Khoảng cách từ s tới u là T. - Với mỗi hàng xóm v của u trong G: * Nếu vẫn chưa có alarm cho v, đặt alarm cho v tại thời điểm T + l(u, v). * Nếu alarm của v đã đặt, nhưng lại muộn hơn so với T + l(u, v), vậy thì đặt lại alarm cho v bằng T + l(u, v). CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 52
  19. long edges into unit-length pieces by introducing “dummy” nodes. Figure 4.6 shows an example of this transformation. To construct the new graph G ′ , For any edge e = (u, v) of E , replace it by le edges of length 1, by adding le − 1 dummy nodes between u and v. Ví dụ G ′ contains all the vertices V Graph that interest us, and the distances between them are exactly the same as in G . Most importantly, the edges of G ′ all have unit length. Therefore, we can compute distances in G by running BFS on G ′ . Thời gian A B C D E Figure 4.6 Breaking edges into unit-length pieces. 0 − − − − 2 0 0B 2 1 − D − 2 B D 1 2 1 − 5 A 1 3 A 2 2 2 4 5 1 C E C E4 4 4 5 5 5 Alarm clocks 0 2 1 4 4 If efficiency were not an issue, we could stop here. But when G has very long edges, the G ′ it engenders is thickly populated with dummy nodes, and the BFS spends most of its time diligently computing distances to these nodes that we don’t care about at all. To see this more concretely, consider the graphs G and G ′ of Figure 4.7, and imagine that the BFS, started at node s of G ′ , advances by one unit of distance per minute. For the first 99 minutes it tediously progresses along S − A and S − B, an endless desert of dummy nodes. Is there some CuuDuongThanCong.com way we can snooze through these boring phases https://fb.com/tailieudientucntt 19 / 52
  20. Hàng đợi ưu tiên Tại sao cần hàng đợi ưu tiên? Để cài đặt hệ thống Alarm. Hàng đợi ưu tiên là gì? Là một tập với mỗi phần tử được gắn với giá trị số (còn gọi là khóa) và có các phép toán sau: Insert. Thêm một phần tử mới vào tập. Decrease-key. Giảm giá trị khóa của một phần tử cụ thể. Delete-min. Trả lại phần tử có khóa nhỏ nhất và xóa nó khỏi tập. Make-queue. xây dựng hàng đợi ưu tiên cho tập phần tử và giá trị khóa cho trước. Khóa của mỗi phần tử (đỉnh) ở đây chính là alarm của đỉnh đó. Insert và Descrease-key để đặt alarm; Delete-min để xác định thời điểm alarm tiếp theo kêu. CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 52
nguon tai.lieu . vn
Toán học Môi trường Vật lý Sinh học Địa Lý Hoá học Nông - Lâm - Ngư Cơ khí - Chế tạo máy Tiếng Anh phổ thông Khoa học ứng dụng Nông - Lâm Kiến thức tổng hợp Giáo dục học Xã hội học