intTypePromotion=1

Bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị

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

0
63
lượt xem
4
download

Bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dưới đây là bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về những cách biểu diễn của một đồ thị, biểu diễn một đồ thị vô hướng, biểu diễn một đồ thị có hướng, tìm kiếm theo chiều rộng.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị

  1. Giải thuật tìm kiếm trong đồ thị
  2. Biểu diễn các đồ thị ª Hai cách biểu diễn một đồ thị G = (V, E): – Biểu diễn danh sách kề (adjacency list) ° mảng Adj gồm  V  danh sách, 1 danh sách cho mỗi đỉnh trong V. u   V, Adj[u] chứa tất cả các đỉnh v (hoặc các con trỏ đến  chúng) sao cho (u, v)   E. – Nhận xét ° Biểu diễn danh sách kề cần  (V + E) memory. (Để đơn giản,  ký hiệu V và E thay vì  V  và  E .) 7.11.2004 Ch. 8: Elementary Graph Algorithms 2
  3. Biểu diễn các đồ thị   (tiếp) – Biểu diễn ma trận kề (adjacency matrix) ° Đánh số đỉnh 1, 2,...,  V   ° A  = (aij  , ma trận |V     V   aij  = 1 nếu (i, j)   E 0 trong các trường hợp còn lại. – Nhận xét ° Biểu diễn ma trận kề cần  (V 2) memory. ° Đồ thị thưa (sparse),  E   
  4. Biểu diễn một đồ thị vô hướng Một đồ thị vô hướng Biểu diễn Biểu diễn bằng một danh sách kề bằng một ma trận kề 7.11.2004 Ch. 8: Elementary Graph Algorithms 4
  5. Biểu diễn một đồ thị có hướng Biểu diễn bằng Biểu diễn bằng một Một đồ thị có hướng  một danh sách kề ma trận kề 7.11.2004 Ch. 8: Elementary Graph Algorithms 5
  6. Tìm kiếm theo chiều rộng    Tìm kiếm theo chiều rộng (breadth­first­search, BFS) ª Một đồ thị G = (V, E) – một đỉnh nguồn s – biểu diễn bằng danh sách kề ª Mỗi đỉnh u   V –  color[u]: WHITE, GREY, BLACK –   [u]: con trỏ chỉ đến đỉnh cha mẹ (predecessor hay parent) của u  nếu có. –  d[u]: khoảng cách từ s đến u mà giải thuật tính được. ª first­in first­out queue Q – head[Q] – thao tác ENQUEUE(Q, v) – thao tác DEQUEUE(Q). 7.11.2004 Ch. 8: Elementary Graph Algorithms 6
  7. Tìm kiếm theo chiều rộng    (tiếp) BFS(G, s)   1 for each vertex u   V[G]   {s}   2        do color[u]   WHITE   3             d[u]      4              [u]   NIL   5 color[s]   GRAY   6 d[s]   0   7 [s]   NIL 7.11.2004 Ch. 8: Elementary Graph Algorithms 7
  8. Tìm kiếm theo chiều rộng    (tiếp)   8 Q   {s}   9 while Q    10        do u   head[Q]  11             for each v   Adj[u] 12                   do if color[v] = WHITE 13                            then color[v]    GRAY 14                                     d[v]   d[u] + 1 15                                      [v]   u 16                                     ENQUEUE(Q, v) 17             DEQUEUE(Q) 18             color[u]   BLACK 7.11.2004 Ch. 8: Elementary Graph Algorithms 8
  9. Thao tác của BFS lên một đồ thị vô hướng ­­ Ví dụ r s t u 0 (a) Q s 0 v w x y r s t u 1 0 (b) Q w r 1 1 1 v w x y r s t u 1 0 2 (c) Q r t x 1 2 1 2 2 v w x y 7.11.2004 Ch. 8: Elementary Graph Algorithms 9
  10. Thao tác của BFS lên một đồ thị vô hướng ­­ Ví dụ (tiếp) r s t u 1 0 2 (d) Q t x v 2 1 2 2 2 2 v w x y r s t u 1 0 2 3 (e) Q x v u 2 1 2 2 2 3 v w x y r s t u 1 0 2 3 (fø) Q v u y 2 1 2 3 2 3 3 v w x y 7.11.2004 Ch. 8: Elementary Graph Algorithms 10
  11. Thao tác của BFS lên một đồ thị vô hướng ­­ Ví dụ (tiếp) r s t u 1 0 2 3 (g) Q u y 2 1 2 3 3 3 v w x y r s t u 1 0 2 3 (h) Q y 2 1 2 3 3 v w x y r s t u 1 0 2 3 (i) Q        2 1 2 3 v w x y 7.11.2004 Ch. 8: Elementary Graph Algorithms 11
  12. Phân tích BFS ª Thời gian chạy của BFS là O(V + E ) vì – mỗi đỉnh của đồ thị được sơn trắng đúng một lần, do đó ° mỗi đỉnh được enqueued nhiều lắm là một lần (màu đỉnh    xám) và dequeued nhiều lắm là một lần (màu đỉnh   đen). Mỗi  thao tác enqueue hay dequeue tốn O(1) thời gian nên các thao  tác lên queue tốn O(V) thời gian. ° Danh sách kề của mỗi đỉnh được duyệt chỉ khi đỉnh được  dequeued nên nó được duyệt nhiều lắm là một lần. Vì chiều  dài tổng cộng của các danh sách kề là  (E) nên thời gian để  duyệt các danh sách kề là O(E). 7.11.2004 Ch. 8: Elementary Graph Algorithms 12
  13. Đường đi ngắn nhất   Định nghĩa ª  Khoảng cách đường đi ngắn nhất  (s, v) (shortest path distance) từ s  đến v – là số cạnh tối thiểu lấy trong mọi đường đi từ s đến v, nếu có  đường đi từ s đến v. – là   nếu không có đường đi từ s đến v. ª Một đường đi ngắn nhất (shortest path) từ s đến v là một đường đi từ  s đến v có chiều dài là  (s, v). 7.11.2004 Ch. 8: Elementary Graph Algorithms 13
  14. Đường đi ngắn nhất   Lemma 23.1 ° G = (V, E) là một đồ thị hữu hướng hay vô hướng, ° một đỉnh s   V bất kỳ  đối với một cạnh bất kỳ (u, v)   E, ta có  (s, v)    (s, u) + 1.   Chứng minh u khi u đến được từ s s v – Nếu u đến được từ s thì v cũng đến được từ s. Đường đi từ s đến  v gồm một đường đi ngắn nhất từ s đến u và cạnh (u,v) có chiều  dài là  (s, u) + 1. Dĩ nhiên là  (s, v)    (s, u) + 1. – Nếu u không đến được từ s thì  (s, u) =  , vậy bất đẳng thức  cũng đúng trong trường hợp này. 7.11.2004 Ch. 8: Elementary Graph Algorithms 14
  15. Đường đi ngắn nhất   Lemma 23.2 ° G = (V, E) là một đồ thị hữu hướng hay vô hướng. ° Chạy BFS lên G từ một đỉnh nguồn s.  khi BFS xong, có d[v]    (s, v) tại mọi đỉnh v.   Chứng minh  “Inductive hypothesis”: với mọi v   V, sau mỗi lần một đỉnh  nào đó được đưa vào queue thì d[v]    (s, v). – “Basis”: sau khi s được đưa vào Q. Kiểm tra   là đúng. – “Inductive step”: xét một đỉnh trắng v được tìm thấy khi thăm  dò từ một đỉnh u. Từ   có d[u]    (s, u). • d[v] = d[u] + 1, dòng 14 •            (s, u) + 1 •            (s, v), Lemma 23.1 • Sau đó v được đưa vào Q và d[v] không thay đổi nữa. Vậy    được duy trì. 7.11.2004 Ch. 8: Elementary Graph Algorithms 15
  16. Đường đi ngắn nhất   Lemma 23.3 ° chạy BFS lên một đồ thị G = (V, E) ° trong khi thực thi BFS, queue  Q chứa các đỉnh  v  , v  ,…, v , với  1 2 r v1 là đầu và vr  là đuôi của Q. ° d[vr ]   d[v1] + 1, ° d[vi ]   d[vi +1 ], với i = 1, 2,…, r   1. ª Ví dụ 1 0 2 3 v1  ...   vr Q x v u 2 1 2 2 2 3 v w x y 7.11.2004 Ch. 8: Elementary Graph Algorithms 16
  17. Đường đi ngắn nhất   Chứng minh ° “Induction lên số các thao tác lên queue”  “Inductive hypothesis”: (xem Lemma) sau mỗi thao tác lên  queue. – “Basis”: queue chỉ chứa  s. Kiểm tra Lemma là đúng. 7.11.2004 Ch. 8: Elementary Graph Algorithms 17
  18. Đường đi ngắn nhất   Chứng minh (tiếp theo) – “Inductive step” ° Sau khi dequeue một đỉnh bất kỳ. Kiểm tra Lemma là đúng  dùng inductive hypothesis: – dequeue v1 , đầu mới của queue là v2  – d[vr]   d[v1] + 1   d[v2] + 1 – các bất đẳng thức còn lại không bị ảnh hưởng tới. ° Sau khi enqueue một đỉnh bất kỳ. Kiểm tra Lemma là đúng  dùng inductive hypothesis – enqueue v, nó thành vr + 1 trong queue – xem code thấy: cạnh (u, v) đang được thăm dò với u =  v1, v1 là đầu của queue, từ đó • d[vr + 1] = d[v] = d[u] + 1 = d[v1] + 1, • d[vr ]   d[v1] + 1 = d[u] + 1 = d[v] = d[vr + 1] • các bất đẳng thức còn lại không bị ảnh hưởng tới. 7.11.2004 Ch. 8: Elementary Graph Algorithms 18
  19. Đường đi ngắn nhất   Định lý 23.4 Tính đúng đắn (correctness) của BFS ° G = (V, E) là một đồ thị hữu hướng hay vô hướng ° chạy BFS lên G từ một đỉnh nguồn s  trong khi BFS chạy ° BFS tìm ra mọi đỉnh của G tới được từ s ° khi BFS xong, d[v] =  (s, v) cho mọi v   V ° đối với mọi đỉnh v   s tới được từ s, một trong các đường đi ngắn  nhất từ s đến v là đường đi ngắn nhất từ s đến  [v] theo sau là  cạnh ( [v], v).   Chứng minh ° Trường hợp đỉnh v không đến được từ s:   (a) d[v]    (s, v) =   (Lemma 23.2)   (b) Dòng 14 chỉ được thực thi khi v có d[v] 
  20. Đường đi ngắn nhất   Chứng minh (tiếp) ª Trường hợp đỉnh v đến được từ s: định nghĩa Vk = {v   V :  (s, v) = k} – “Induction on k”. ° “Inductive hypothesis”: v ới m ọi  v   V  , trong khi thực thi BFS  k thì có đúng một thời điểm mà – v được sơn xám – d[v] được gán trị k – Nếu v   s thì  [v] được gán trị u với u   Vk   1 – v được đưa vào queue Q. ° “Basis”: k = 0, kiểm tra là đúng ° “Inductive step” – Xét v   Vk bất kỳ, k   1. – Có u   Vk   1 sao cho: u là head của queue và (u, v) được  thăm dò. ª Phần còn lại: ... 7.11.2004 Ch. 8: Elementary Graph Algorithms 20
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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