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.
AMBIENT/
Chủ đề:
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ị
- Giải thuật tìm kiếm trong đồ thị
- 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
- 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
- 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
- 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
- Tìm kiếm theo chiều rộng
Tìm kiếm theo chiều rộng (breadthfirstsearch, 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.
ª firstin firstout queue Q
– head[Q]
– thao tác ENQUEUE(Q, v)
– thao tác DEQUEUE(Q).
7.11.2004 Ch. 8: Elementary Graph Algorithms 6
- 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
- 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
- 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
- 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
- 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
- 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
- Đườ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
- Đườ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
- Đườ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
- Đườ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
- Đườ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
- Đườ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
- Đườ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]
- Đườ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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
