›
›

Giáo trình Toán rời rạc - Bài 18: Đường đi trên đồ thị - Trần Vĩnh Đức

Download
Đường đi trên đồ thị (Version 0.2)  
Trần Vĩnh Đức  
HUST  
Ngày 24 tháng 7 năm 2018  
1 / 52  
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.  
2 / 52  
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  
DFS và đường đi  
S
A
B
E
S
A
B
C
D
E
D
C
Đường đi trên cây DFS thường không phải là đường đi ngắn nhất.  
4 / 52  
Khoảng cách  
Khoảng cách giữa hai đỉnh là độ dài của đường đi ngắn nhất giữa  
chúng.  
v
Khoảng cách (S − v)  
A
B
E
S
A
B
C
D
E
D
C
5 / 52  
Mô hình vật lý của đồ thị  
Giả sử rằng mọi cạnh có cùng độ dài. Ta nhấc đỉnh S lên:  
S
A
B
E
S
A
E
C
D
C
D
B
6 / 52  
Tìm kiếm theo chiều rộng (Breadth-First Search)  
S
Chia đồ thị thành các mức:  
▶
▶
S là mức có khoảng cách 0.  
Các đỉnh có khoảng cách tới  
S bằng 1.  
A
E
C
D
▶
▶
Các đỉnh có khoảng cách tới  
S bằng 2  
B
...  
Ý tưởng thuật toán: Khi mức d đã được xác định, mức d + 1 có  
thể thăm bằng cách duyệt qua các hàng xóm của mức d.  
7 / 52  
Ý 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.  
8 / 52  
Bài tập  
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
E
S
Đỉnh thăm Hàng đợi  
[S]  
S
D
C
B
9 / 52  
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  
10 / 52  
Bài tập  
Hãy chạy thuật toán BFS cho đồ thị dưới đây và ghi ra nội dung  
của hàng đợi Q sau mỗi bước:  
Thứ tự thăm đỉnh Hàng đợi  
A
B
E
S
S
[S]  
D
C
11 / 52  
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  
Độ dài của cạnh  
Sacramento  
95  
133  
San  
Francisco  
Reno  
271  
290  
409  
445  
Bakersfield  
291  
112  
Los  
Angeles  
Las  
Vegas  
275  
Trong các bài toán thực tế, mỗi cạnh e thường gắn với độ dài le.  
13 / 52  
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?  
14 / 52  
Tách cạnh thành các cạnh với độ dài đơn vị  
2
B
D
E
2
1
B
D
E
3
A
1
A
2
C
C
4
Thay cạnh e = (u, v) bởi le cạnh độ dài 1, bằng cách thêm le − 1  
đỉnh tạm giữa u và v.  
15 / 52  
Vấn đề  
A
A
100  
200  
S
50  
S
B
B
Cả 99 bước di chuyển đầu tiên đều xử lý S − A và S − B trên các  
đỉnh tạm.  
16 / 52  
Giải pháp: Đặt Alarm clock!  
▶
▶
▶
Với đỉnh A, đặt hẹn T = 100  
Với đỉnh B, đặt hẹn T = 200  
Bị đánh thức khi A được thăm lúc  
T = 100  
Ước lượng lại thời gian đến của B là  
T = 150; và đặt lại Alarm cho B.  
A
100  
200  
50  
S
▶
B
17 / 52  
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).  
18 / 52  
Ví dụ  
Thời gian  
A
B
C
D
E
0
−
−
−
−
0
1
2
4
5
0
2
2
2
1
−
−
4
−
5
2
4
2
1
B
D
E
1
3
1
A
2
5
C
4
5
5
4
0
2
1
4
19 / 52  
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.  
20 / 52  
Tải về để xem bản đầy đủ
pdf 52 trang Thùy Anh 13120 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 18: Đường đi trên đồ thị - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_toan_roi_rac_bai_18_duong_di_tren_do_thi_tran_vin.pdf