intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths

Chia sẻ: Đinh Trường Gấu | Ngày: | Loại File: PPT | Số trang:45

Thêm vào BST
Báo xấu
94
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung "Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths" tập trung vào những kiến thức cơ bản nhất về những cách giải bài toán các đường đi ngắn nhất từ một đỉnh nguồn, biểu diễn các đường đi ngắn nhất. Mời các bạn tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths

  1. Single­Source Shortest Paths
  2. Các đường đi ngắn nhất từ một đỉnh nguồn ª  Bài toán các đường đi ngắn nhất: một số thuật ngữ.   Cho một đồ thị có trọng số, có hướng G = (V, E), với một hàm trọng  số w : E    –  Trọng số của một đường đi p =  v0 , v1,…, vk  • w(p) =  w(vi   1 , vi ) i = 1…k  –  Trọng số của đường đi ngắn nhất (shortest path weight) từ u đến  p v (u, v) =   min{w(p) : u       v }  nếu có đường đi từ u đến v        các trường hợp khác –  Đường đi ngắn nhất từ u đến  t v là bất kỳ đườ v ng đi p nào từ u đến  v sao cho w(p) =  (u, v). 6 u 3 2 1 4 2 7 3 5 6 20.11.2004 x y 2
  3. Các đường đi ngắn nhất từ một đỉnh nguồn (tiếp) ª  Bài toán các đường đi ngắn nhất từ một nguồn duy nhất (Single­ source shortest­paths problem): – Cho đồ thị G = (V, E) và một đỉnh nguồn s   V. – Tìm đường đi ngắn nhất từ s đến mọi đỉnh v   V. 6 s 3 2 1 4 2 7 3 5 6 20.11.2004 Ch. 10: Single­Source Shortest Paths 3
  4. Cạnh có trọng số âm ª Giả thiết: Trọng số của cạnh có thể âm – Chu trình có thể có trọng số âm – Nếu tồn tại một chu trình có trọng số âm đến được (reachable) từ  s thì trọng số của đường đi ngắn nhất không được định nghĩa:  không đường đi nào từ s đến một đỉnh nằm trên chu trình có thể là  đường đi ngắn nhất. 4 3 1 a b h i 3 4 2 s c 6 d g 5 8 0 5 11 8 3 3 2 3 7 e f j 6 số trong mỗi đỉnh là trọng số đường đi ngắn nhất từ đỉnh nguồn s. 20.11.2004 Ch. 10: Single­Source Shortest Paths 4
  5. Cạnh có trọng số âm (tiếp) – Nếu tồn tại một chu trình có trọng số âm trên một đường đi từ s  đến v, ta định nghĩa  (s, v) =   . – Trong ví dụ sau, các đỉnh h, i, j không đến được từ s nên có trọng  số đường đi ngắn nhất là   (chứ không là   mặc dù chúng nằm  trên một chu trình có trọng số âm). a b 4 3 1 h i 3 4 2 s c 6 d g 5 8 0 5 11 8 3 3 2 3 7 e f j 6 20.11.2004 Ch. 10: Single­Source Shortest Paths 5
  6. Biểu diễn các đường đi ngắn nhất ª Đồ thị G = (V, E ) – Với mọi đỉnh v, đỉnh cha (predecessor) của v là một đỉnh khác hay  là NIL.   Duy trì  [v], con trỏ đến đỉnh cha. Dùng   để suy ra đường đi  ngắn nhất từ s đến v. – Đồ thị con G    (V  , E  ) (predecessor subgraph) • V    = {v   V :  [v]   NIL}   {s} • E   = {( [v], v)   E : v   V     {s}} [v] v 20.11.2004 Ch. 10: Single­Source Shortest Paths 6
  7. Biểu diễn các đường đi ngắn nhất (tiếp) ª Cho G = (V, E) là một đồ thị có hướng, có trọng số;   G không chứa chu trình trọng số âm đến được từ đỉnh nguồn s   V.    Cây các đường đi ngắn nhất với gốc tại s là đồ thị có hướng G’ =  (V’, E’), với V’   V và E’   E sao cho 1. V’ là tập các đỉnh đến được (reachable) từ s trong G 2. G’ là cây có gốc với gốc là s 3. Với mọi v   V’, đường đi đơn duy nhất từ s đến v là đường đi  ngắn nhất từ s đến v trong G . 20.11.2004 Ch. 10: Single­Source Shortest Paths 7
  8. Cây các đường đi ngắn nhất có gốc tại đỉnh nguồn s Ví dụ: trong (b) và (c) là hai cây các đường đi ngắn nhất có gốc tại đỉnh nguồn s của đồ thị trong (a) u v u v 6 6 3 9 3 9 s 3 s 3 0 2 1 4 2 7 0 2 1 4 2 7 3 3 5 5 5 11 5 11 6 6 x y x y (a) u v (b) 6 3 9 s 3 0 2 1 4 2 7 3 5 (c) 5 11 6 x y 20.11.2004 Ch. 10: Single­Source Shortest Paths 8
  9. Cấu trúc của đường đi ngắn nhất ª Lemma 25.1 (Đường đi con của đường đi ngắn nhất cũng là  đường đi ngắn nhất)   Cho – Đồ thị có trọng số, có hướng G = (V, E) với hàm trọng số   w : E    – p =  v1 , v2 ,…, vk  đường đi ngắn nhất từ v1 đến vk – Với mọi i, j mà 1   i   j   k, gọi pij =  vi , vi + 1 ,…, vj   là đường đi  con (subpath) của p từ vi  đến vj  . pij  là một đường đi ngắn nhất từ vi  đến vj  . pjk vk p1i vj v1 vi pij 20.11.2004 Ch. 10: Single­Source Shortest Paths 9
  10. Cấu trúc của đường đi ngắn nhất (tiếp)   Chứng minh   Phản chứng.  p’ij vk pjk p1i vj v1 vi pij 20.11.2004 Ch. 10: Single­Source Shortest Paths 10
  11. Cấu trúc của đường đi ngắn nhất (tiếp) ª Hệ luận 25.2   Cho – Đồ thị có trọng số, có hướng G = (V, E) với hàm trọng số   w : E    – p là đường đi ngắn nhất từ s đến v, và có thể được phân thành p’   s      u   v.   Trọng số của đường đi ngắn nhất từ s đến v là (s, v) =  (s, u) + w(u, v). v p’ u s 20.11.2004 Ch. 10: Single­Source Shortest Paths 11
  12. Cấu trúc của đường đi ngắn nhất (tiếp)   Chứng minh v p’ u s 20.11.2004 Ch. 10: Single­Source Shortest Paths 12
  13. Cấu trúc của đường đi ngắn nhất (tiếp) ª Lemma 25.3   Cho – Đồ thị có trọng số, có hướng G = (V, E) với hàm trọng số   w : E    – Đỉnh nguồn s   Với mọi cạnh (u, v)   E, ta có  (s, v)    (s, u) + w(u, v). v u s 20.11.2004 Ch. 10: Single­Source Shortest Paths 13
  14. Kỹ thuật nới lỏng ª Kỹ thuật nới lỏng (relaxation) – Duy trì cho mỗi đỉnh v một thuộc tính d[v] dùng làm chận trên cho  trọng số của một đường đi ngắn nhất từ s đến v. – biến d[v] được gọi là ước lượng đường đi ngắn nhất (shortest  path estimate) – Khởi động các ước lượng đường đi ngắn nhất và các predecessors  bằng thủ tục sau INITIALIZE­SINGLE­SOURCE(G, s) 1 for each vertex v   V[G] 2         do d[v]    3        [v]   NIL 4 d[s]   0 20.11.2004 Ch. 10: Single­Source Shortest Paths 14
  15. Kỹ thuật nới lỏng (tiếp) ª Thực thi nới lỏng lên một cạnh (u, v): kiểm tra xem một đường đi  đến v thông qua cạnh (u, v) có ngắn hơn một đường đi đến v đã tìm  được hiện thời hay không. Nếu ngắn hơn thì cập nhật d[v] và  [v]. s 0 2 5 9 u v RELAX(u, v, w) 1 if d[v]   d[u] + w(u, v) 2     then d[v]   d[u] + w(u, v) 3               [v]   u 20.11.2004 Ch. 10: Single­Source Shortest Paths 15
  16. Thực thi nới lỏng lên một cạnh u v u v 2 2 5 9 5 6 RELAX(u, v, w) RELAX(u, v, w) u v u v 2 2 5 7 5 6 (a) (b) Trị của d[v] giảm sau khi Trị của d[v] không thay đổi sau khi gọi RELAX(u, v, w) gọi RELAX(u, v, w) 20.11.2004 Ch. 10: Single­Source Shortest Paths 16
  17. Kỹ thuật nới lỏng (tiếp) ª Các giải thuật trong chương này gọi INITIALIZE­SINGLE­SOURCE và  sau đó gọi RELAX một số lần để nới lỏng các cạnh. – Nới lỏng là cách duy nhất được dùng để thay đổi các ước lượng  đường đi ngắn nhất và các predecessors. – Các giải thuật khác nhau ở thứ tự và số lần gọi RELAX lên các  cạnh. 20.11.2004 Ch. 10: Single­Source Shortest Paths 17
  18. Các tính chất của kỷ thuật nới lỏng ª Lemma 25.4   Cho – Đồ thị có trọng số, có hướng G = (V, E )ø, với hàm trọng số   w : E    – Cạnh (u, v)   E.   Ngay sau khi gọi RELAX(u, v, w) ta có d[v]   d[u] + w(u, v) . 20.11.2004 Ch. 10: Single­Source Shortest Paths 18
  19. Các tính chất của kỷ thuật nới lỏng (tiếp) ª Lemma 25.5   Cho – Đồ thị có trọng số, có hướng G = (V, E)ø, với hàm trọng số   w : E    – Đỉnh nguồn s. – G được khởi động bởi INITIALIZE­SINGLE­SOURCE(G, s).  – Với mọi v   V, d[v]    (s, v), bất biến này được duy trì đối với  mọi dãy các bước nới lỏng lên các cạnh của G – Một khi d[v] đạt đến cận dưới  (s, v) của nó thì nó sẽ không bao  giờ thay đỗi. 20.11.2004 Ch. 10: Single­Source Shortest Paths 19
  20. Các tính chất của kỷ thuật nới lỏng (tiếp) ª Hệ luận 25.6   Cho – Đồ thị có trọng số, có hướng G = (V, E)ø, với hàm trọng số   w : E    – Đỉnh nguồn s – Không có đường đi từ s đến một đỉnh v   V.   Sau khi G được khởi động bởi INITIALIZE­SINGLE­SOURCE(G, s), ta có – đẳng thức d[v] =  (s, v) – đẳng thức này được duy trì thành bất biến đối với mọi dãy các  bước nới lỏng lên các cạnh của G. 20.11.2004 Ch. 10: Single­Source Shortest Paths 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
11=>2