›
›

Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất - Nguyễn Đức Nghĩa

Download
Chương 5  
BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 1  
Nội dung  
5.1. Bài toán đường đi ngắn nhất (ĐĐNN)  
5.2. Tính chất của ĐĐNN, Giảm cận trên  
5.3. Thuật toán Bellman-Ford  
5.4. Thuật toán Dijkstra  
5.5. Đường đi ngắn nhất trong đồ thị không có chu trình  
5.6. Thuật toán Floyd-Warshal  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 2  
5.1. Bài toán đường đi ngắn nhất  
❖Cho đơn đồ thị có hướng G = (V,E) với hàm trọng số  
w: E → R (w(e) được gọi là độ dài hay trọng số của  
cạnh e)  
❖Độ dài của đường đi P = v1 → v2 → … → vk là số  
k−1  
w(P) = w(v ,v )  
i
i+1  
i=1  
❖Đường đi ngắn nhất từ đỉnh u đến đỉnh v là đường đi có  
độ dài ngắn nhất trong số các đường đi nối u với v.  
❖Độ dài của đường đi ngắn nhất từ u đến v còn được gọi  
là khoảng cách từ u tới v và ký hiệu là (u,v).  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 3  
Ví dụ  
Cho đồ thị có trọng số G = (V, E), và đỉnh nguồn sV, hãy tìm  
đường đi ngắn nhất từ s đến mỗi đỉnh còn lại.  
3
d
a
3
4
6
5
đỉnh nguồn  
1
1
s
c
f
2
2
5
3
e
b
2
s
a
b
c
d
e
f
weight 0  
3
4
6
6
6
9
path s s,a s,a,b s,a,b,c s,a,d s,a,b,e s,a,b,e,f  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 4  
Các ứng dụng thực tế  
❖Giao thông (Transportation)  
❖Truyền tin trên mạng (Network routing) (cần hướng  
các gói tin đến đích trên mạng theo đường nào?)  
❖Truyền thông (Telecommunications)  
❖Speech interpretation (best interpretation of a spoken  
sentence)  
❖Điều khiển robot (Robot path planning)  
❖Medical imaging  
❖Giải các bài toán phức tạp hơn trên mạng  
❖...  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 5  
Các dạng bài toán ĐĐNN  
1. Bài toán một nguồn một đích: Cho hai đỉnh s  
và t, cần tìm đường đi ngắn nhất từ s đến t.  
2. Bài toán một nguồn nhiều đích: Cho s là  
đỉnh nguồn, cần tìm đường đi ngắn nhất từ s  
đến tất cả các đỉnh còn lại.  
3. Bài toán mọi cặp: Tìm đường đi ngắn nhất  
giữa mọi cặp đỉnh của đồ thị.  
❖ Đường đi ngắn nhất theo số cạnh - BFS.  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 6  
Nhận xét  
❖Các bài toán được xếp theo thứ tự từ đơn giản  
đến phức tạp  
❖Hễ có thuật toán hiệu quả để giải một trong ba  
bài toán thì thuật toán đó cũng có thể sử dụng để  
giải hai bài toán còn lại  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 7  
Giả thiết cơ bản  
❖Nếu đồ thị có chu trình âm thì độ dài đường đi giữa hai  
đỉnh nào đó có thể làm nhỏ tuỳ ý:  
-18  
b
d
c
Xét đường đi từ a đến e:  
5
P: a→ (d → b →c →d) → e  
w(P) = 7-10→ -∞, khi →+ ∞  
a
3
2
5
e
Giả thiết:  
Đồ thị không chứa chu trình độ dài âm (gọi tắt  
là chu trình âm)  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 8  
Trọng số âm  
Độ dài của đường đi ngắn nhất có thể là hoặc – .  
a
b
-4  
h
i
3
-1  
4
2
3
5
đỉnh  
nguồn  
s
6 d  
g
c
8
11  
0
5
-  
-8  
3
-3  
j
2
f
e 3  
-   
7
-   
không đạt tới được từ s  
chu trình âm  
-6  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 9  
5.1. Bài toán đường đi ngắn nhất (ĐĐNN)  
5.2. Tính chất của ĐĐNN, Giảm cận trên  
5.3. Thuật toán Bellman-Ford  
5.4. Thuật toán Dijkstra  
5.5. Đường đi ngắn nhất trong đồ thị không có chu trình  
5.6. Thuật toán Floyd-Warshal  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 10  
Các tính chất của ĐĐNN  
❖Tính chất 1. Đường đi ngắn nhất luôn có thể tìm trong  
số các đường đi đơn.  
• CM: Bởi vì việc loại bỏ chu trình độ dài không âm khỏi  
đường đi không làm tăng độ dài của nó.  
u
v
C
w(C) 0  
❖Tính chất 2. Mọi đường đi ngắn nhất trong đồ thị G  
đều đi qua không quá n-1 cạnh, trong đó n là số đỉnh.  
• Như là hệ quả của tính chất 1  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 11  
Các tính chất của ĐĐNN  
Tính chất 3: Giả sử P = ‹v1, v2, …, vk› là đđnn từ v1 đến vk. Khi  
đó, Pij = ‹vi, vi+1, …, vj› là đđnn từ vi đến vj, với 1 i j k.  
(Bằng lời: Mọi đoạn đường con của đường đi ngắn nhất đều là  
đường đi ngắn nhất)  
CM. Phản chứng. Nếu Pij không là đđnn từ vi đến vj, thì tìm được  
P’ij là đường đi từ vi đến vj thoả mãn w(P’ij) < w(Pij). Khi đó gọi P’  
là đường đi thu được từ P bởi việc thay đoạn Pij bởi P’ij, ta có  
w(P’) < w(P) ?!  
vi  
vj  
Pij  
vk  
v1  
P’ij  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 12  
Các tính chất của ĐĐNN  
Ký hiệu: δ(u, v) = độ dài đđnn từ u đến v (gọi là  
khoảng cách từ u đến v)  
p'  
Hệ quả: Giả sử P là đđnn từ s tới v, trong đó P = s  
Khi đó δ(s, v) = δ(s, u) + w(u, v).  
u →v.  
⎯⎯→  
Tính chất 4: Giả sử s V. Đối với mỗi cạnh (u,v) E, ta có  
δ(s, v) δ(s, u) + w(u,v).  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 13  
Đường đi ngắn nhất xuất phát từ một đỉnh  
Single-Source Shortest Paths  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 14  
Biểu diễn đường đi ngắn nhất  
Các thuật toán tìm đường đi ngắn nhất làm việc với hai mảng:  
d(v) = độ dài đường đi từ s đến v ngắn nhất hiện biết  
(cận trên cho độ dài đường đi ngắn nhất thực sự).  
p(v) = đỉnh đi trước v trong đường đi nói trên  
(sẽ sử dụng để truy ngược đường đi từ s đến v) .  
Khởi tạo (Initialization)  
for v V(G)  
do d[v]    
p[v] NIL  
d[s] 0  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 15  
Giảm cận trên (Relaxation)  
Sử dụng cạnh (u, v) để kiểm tra xem đường đi đến v đã tìm được  
có thể làm ngắn hơn nhờ đi qua u hay không.  
u
s
v
Relax(u, v)  
if d[v] > d[u] + w(u, v)  
z
p(v)  
then d[v] d[u] + w(u, v)  
p[v] u  
d[v] > d[u] + w(u, v)  
Các thuật toán tìm đđnn khác nhau ở  
số lần dùng các cạnh và trình tự duyệt  
chúng để thực hiện giảm cận  
.
p(v)  
u
s
v
z
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 16  
Nhận xét chung  
❖ ViÖc cµi ®Æt c¸c thuËt to¸n ®îc thÓ hiÖn nhê thñ tôc  
g¸n nh·n:  
• Mçi ®Ønh v sÏ cã nh·n gåm 2 thµnh phÇn (d[v], p[v]). Nh·n sÏ  
biÕn ®æi trong qu¸ tr×nh thùc hiÖn thuËt to¸n  
❖NhËn thÊy r»ng ®Ó tÝnh kho¶ng c¸ch tõ s ®Õn t, ë ®©y, ta  
ph¶i tÝnh kho¶ng c¸ch tõ s ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i  
cña ®å thÞ.  
❖HiÖn nay vÉn cha biÕt thuËt to¸n nµo cho phÐp t×m ®®nn  
nhÊt gi÷a hai ®Ønh lµm viÖc thùc sù hiÖu qu¶ h¬n nh÷ng  
thuËt to¸n t×m ®®nn tõ mét ®Ønh ®Õn tÊt c¶ c¸c ®Ønh cßn  
l¹i.  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 17  
Nội dung  
5.1. Bài toán đường đi ngắn nhất (ĐĐNN)  
5.2. Tính chất của ĐĐNN, Giảm cận trên  
5.3. Thuật toán BellmaFord  
5.4. Thuật toán Dijkstra  
5.5. Đường đi ngắn nhất trong đồ thị không có chu trình  
5.6. Thuật toán Floyd-Warshal  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 18  
Thuật toán Ford-Bellman  
Richard Bellman  
Lester R. Ford, Jr.  
1920-1984  
1927~  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 19  
Thuật toán Ford-Bellman  
❖ThuËt to¸n Ford - Bellman t×m ®êng ®i ng¾n nhÊt tõ  
®Ønh s ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i cña ®å thÞ.  
❖ThuËt to¸n lµm viÖc trong trêng hîp träng sè cña c¸c  
cung lµ tuú ý.  
❖Gi¶ thiÕt r»ng trong ®å thÞ kh«ng cã chu tr×nh ©m.  
❖§Çu vµo: §å thÞ G=(V,E) víi n ®Ønh x¸c ®Þnh bëi ma  
trËn träng sè w[u,v], u,v V, ®Ønh nguån s V;  
❖§Çu ra: Víi mçi v V  
• d[v] = (s, v);  
• p[v] - ®Ønh ®i tríc v trong ®®nn tõ s ®Õn v.  
Nguyễn Đức Nghĩa  
Toán rời rạc, Fall 2005  
Bài toán đường đi ngắn nhất 20  
Tải về để xem bản đầy đủ
ppt 78 trang myanh 20760 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất - Nguyễn Đức Nghĩa", để 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:

  • pptbai_giang_toan_roi_rac_phan_2_ly_thuyet_do_thi_chuong_5_bai.ppt