Bài giảng Giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị
Giaûi thuaät tìm kieám trong ñoà thò
Bieåu dieãn caùc ñoà thò
ª Hai caùch bieåu dieãn moät ñoà thò G = (V, E):
– Bieåu dieãn danh saùch keà (adjacency list)
°
maûng Adj goàm |V| danh saùch, 1 danh saùch cho moãi ñænh trong
V.
°
u V, Adj[u] chöùa taát caû caùc ñænh v (hoaëc caùc con troû ñeán
chuùng) sao cho (u, v) E.
– Nhaän xeùt
Bieåu dieãn danh saùch keà caàn (V + E) memory. (Ñeå ñôn giaûn,
kyù hieäu V vaø E thay vì |V| vaø |E|.)
°
7.11.2004
Ch. 8: Elementary Graph Algorithms
2
Bieåu dieãn caùc ñoà thò
(tieáp)
– Bieåu dieãn ma traän keà (adjacency matrix)
°
Ñaùnh soá ñænh 1, 2,..., |V|
A = (aij ), ma traän |V| |V|
aij = 1 neáu (i, j) E
°
0
trong caùc tröôøng hôïp coøn laïi.
– Nhaän xeùt
°
°
°
Bieåu dieãn ma traän keà caàn (V 2) memory.
Ñoà thò thöa (sparse), |E | << |V| 2 : neân duøng danh saùch keà .
ñoà thò ñaëc (dense), |E | |V| 2 : neân duøng ma traän keà .
7.11.2004
Ch. 8: Elementary Graph Algorithms
3
Bieåu dieãn moät ñoà thò voâ höôùng
Bieåu dieãn
baèng moät danh saùch keà
Bieåu dieãn
baèng moät ma traän keà
Moät ñoà thò voâ höôùng
7.11.2004
Ch. 8: Elementary Graph Algorithms
4
Bieåu dieãn moät ñoà thò coù höôùng
Bieåu dieãn baèng
moät danh saùch keà
Bieåu dieãn baèng moät
ma traän keà
Moät ñoà thò coù höôùng
7.11.2004
Ch. 8: Elementary Graph Algorithms
5
Tìm kieám theo chieàu roäng
Tìm kieám theo chieàu roäng (breadth-first-search, BFS)
ª Moät ñoà thò G = (V, E)
– moät ñænh nguoàn s
– bieåu dieãn baèng danh saùch keà
ª Moãi ñænh u V
– color[u]: WHITE, GREY, BLACK
– p[u]: con troû chæ ñeán ñænh cha meï (predecessor hay parent) cuûa u
neáu coù.
– d[u]: khoaûng caùch töø s ñeán u maø giaûi thuaät tính ñöôïc.
ª first-in first-out queue Q
– head[Q]
– thao taùc ENQUEUE(Q, v)
– thao taùc DEQUEUE(Q).
7.11.2004
Ch. 8: Elementary Graph Algorithms
6
Tìm kieám theo chieàu roäng
(tieáp)
BFS(G, s)
1 for each vertex u V[G] − {s}
2
3
4
do color[u] WHITE
d[u]
p[u] NIL
5 color[s] GRAY
6 d[s] 0
7 p[s] NIL
7.11.2004
Ch. 8: Elementary Graph Algorithms
7
Tìm kieám theo chieàu roäng
(tieáp)
8 Q {s}
9 while Q
10
do u head[Q]
11
12
13
14
15
16
17
18
for each v Adj[u]
do if color[v] = WHITE
then color[v] GRAY
d[v] d[u] + 1
p[v] u
ENQUEUE(Q, v)
DEQUEUE(Q)
color[u] BLACK
7.11.2004
Ch. 8: Elementary Graph Algorithms
8
Thao taùc cuûa BFS leân moät ñoà thò voâ höôùng -- Ví duï
s
r
t
u
0
s
Q
(a)
0
w
v
y
x
s
r
t
u
0
1
w r
Q
Q
(b)
(c)
1 1
1
v
w
x
y
s
r
t
u
0
1
2
r t x
1 2 2
1
w
v
y
2
x
7.11.2004
Ch. 8: Elementary Graph Algorithms
9
Thao taùc cuûa BFS leân moät ñoà thò voâ höôùng -- Ví duï (tieáp)
s
r
t
u
0
1
2
Q
(d)
t x v
2 2 2
1
w
2
v
y
2
x
s
r
t
u
0
1
2
3
x v u
Q
Q
(e)
(fø)
1
w
2
v
2 2 3
2
x
y
s
r
t
u
0
1
2
3
v u y
1
w
2 3 3
2
v
3
y
2
x
7.11.2004
Ch. 8: Elementary Graph Algorithms
10
Thao taùc cuûa BFS leân moät ñoà thò voâ höôùng -- Ví duï (tieáp)
r
s
t
u
0
1
2
3
(g)
Q
Q
Q
u y
3 3
1
w
2
v
3
2
x
y
r
s
t
u
0
1
2
3
y
(h)
(i)
3
1
w
2
v
3
y
2
x
r
s
t
u
0
1
2
3
1
w
2
v
3
y
2
x
7.11.2004
Ch. 8: Elementary Graph Algorithms
11
Phaân tích BFS
ª Thôøi gian chaïy cuûa BFS laø O(V + E ) vì
– moãi ñænh cuûa ñoà thò ñöôïc sôn traéng ñuùng moät laàn, do ñoù
°
moãi ñænh ñöôïc enqueued nhieàu laém laø moät laàn (maøu ñænh →
xaùm) vaø dequeued nhieàu laém laø moät laàn (maøu ñænh → ñen).
Moãi thao taùc enqueue hay dequeue toán O(1) thôøi gian neân caùc
thao taùc leân queue toán O(V) thôøi gian.
°
Danh saùch keà cuûa moãi ñænh ñöôïc duyeät chæ khi ñænh ñöôïc
dequeued neân noù ñöôïc duyeät nhieàu laém laø moät laàn. Vì chieàu
daøi toång coäng cuûa caùc danh saùch keà laø (E) neân thôøi gian ñeå
duyeät caùc danh saùch keà laø O(E).
7.11.2004
Ch. 8: Elementary Graph Algorithms
12
Ñöôøng ñi ngaén nhaát
Ñònh nghóa
ª Khoaûng caùch ñöôøng ñi ngaén nhaát (s, v) (shortest path distance) töø s
ñeán v
– laø soá caïnh toái thieåu laáy trong moïi ñöôøng ñi töø s ñeán v, neáu coù
ñöôøng ñi töø s ñeán v.
– laø neáu khoâng coù ñöôøng ñi töø s ñeán v.
ª Moät ñöôøng ñi ngaén nhaát (shortest path) töø s ñeán v laø moät ñöôøng ñi töø s
ñeán v coù chieàu daøi laø (s, v).
7.11.2004
Ch. 8: Elementary Graph Algorithms
13
Ñöôøng ñi ngaén nhaát
Lemma 23.1
°
G = (V, E) laø moät ñoà thò höõu höôùng hay voâ höôùng,
moät ñænh s V baát kyø
°
ñoái vôùi moät caïnh baát kyø (u, v) E, ta coù (s, v) (s, u) + 1.
Chöùng minh
u
khi u ñeán ñöôïc töø s
s
v
– Neáu u ñeán ñöôïc töø s thì v cuõng ñeán ñöôïc töø s. Ñöôøng ñi töø s ñeán v
goàm moät ñöôøng ñi ngaén nhaát töø s ñeán u vaø caïnh (u,v) coù chieàu daøi
laø (s, u) + 1. Dó nhieân laø (s, v) (s, u) + 1.
– Neáu u khoâng ñeán ñöôïc töø s thì (s, u) = , vaäy baát ñaúng thöùc cuõng
ñuùng trong tröôøng hôïp naøy.
7.11.2004
Ch. 8: Elementary Graph Algorithms
14
Ñöôøng ñi ngaén nhaát
Lemma 23.2
°
G = (V, E) laø moät ñoà thò höõu höôùng hay voâ höôùng.
Chaïy BFS leân G töø moät ñænh nguoàn s.
°
khi BFS xong, coù d[v] (s, v) taïi moïi ñænh v.
Chöùng minh
. “Inductive hypothesis”: vôùi moïi v V, sau moãi laàn moät ñænh
naøo ñoù ñöôïc ñöa vaøo queue thì d[v] (s, v).
– “Basis”: sau khi s ñöôïc ñöa vaøo Q. Kieåm tra . laø ñuùng.
– “Inductive step”: xeùt moät ñænh traéng v ñöôïc tìm thaáy khi thaêm
doø töø moät ñænh u. Töø . coù d[u] (s, u).
d[v] = d[u] + 1, doøng 14
(s, u) + 1
(s, v), Lemma 23.1
Sau ñoù v ñöôïc ñöa vaøo Q vaø d[v] khoâng thay ñoåi nöõa. Vaäy .
ñöôïc duy trì.
7.11.2004
Ch. 8: Elementary Graph Algorithms
15
Ñöôøng ñi ngaén nhaát
Lemma 23.3
°
chaïy BFS leân moät ñoà thò G = (V, E)
°
trong khi thöïc thi BFS, queue Q chöùa caùc ñænh v1 , v2 ,…, vr, vôùi v1
laø ñaàu vaø vr laø ñuoâi cuûa Q.
°
d[vr ] d[v1] + 1,
°
d[vi ] d[vi +1 ], vôùi i = 1, 2,…, r − 1.
ª Ví duï
1
v1 ... vr
x v u
2 2 3
0
2
2
3
Q
1
w
2
v
y
x
7.11.2004
Ch. 8: Elementary Graph Algorithms
16
Ñöôøng ñi ngaén nhaát
Chöùng minh
°
“Induction leân soá caùc thao taùc leân queue”
. “Inductive hypothesis”: (xem Lemma) sau moãi thao taùc leân
queue.
– “Basis”: queue chæ chöùa s. Kieåm tra Lemma laø ñuùng.
7.11.2004
Ch. 8: Elementary Graph Algorithms
17
Ñöôøng ñi ngaén nhaát
Chöùng minh (tieáp theo)
– “Inductive step”
°
Sau khi dequeue moät ñænh baát kyø. Kieåm tra Lemma laø ñuùng
duøng inductive hypothesis:
– dequeue v1 , ñaàu môùi cuûa queue laø v2
– d[vr] d[v1] + 1 d[v2] + 1
– caùc baát ñaúng thöùc coøn laïi khoâng bò aûnh höôûng tôùi.
°
Sau khi enqueue moät ñænh baát kyø. Kieåm tra Lemma laø ñuùng
duøng inductive hypothesis
– enqueue v, noù thaønh vr + 1 trong queue
– xem code thaáy: caïnh (u, v) ñang ñöôïc thaêm doø vôùi u =
v1, v1 laø ñaàu cuûa queue, töø ñoù
d[vr + 1] = d[v] = d[u] + 1 = d[v1] + 1,
d[vr ] d[v1] + 1 = d[u] + 1 = d[v] = d[vr + 1]
caùc baát ñaúng thöùc coøn laïi khoâng bò aûnh höôûng tôùi.
7.11.2004
Ch. 8: Elementary Graph Algorithms
18
Ñöôøng ñi ngaén nhaát
Ñònh lyù 23.4 Tính ñuùng ñaén (correctness) cuûa BFS
°
G = (V, E) laø moät ñoà thò höõu höôùng hay voâ höôùng
chaïy BFS leân G töø moät ñænh nguoàn s
°
trong khi BFS chaïy
°
°
°
BFS tìm ra moïi ñænh cuûa G tôùi ñöôïc töø s
khi BFS xong, d[v] = (s, v) cho moïi v V
ñoái vôùi moïi ñænh v s tôùi ñöôïc töø s, moät trong caùc ñöôøng ñi ngaén
nhaát töø s ñeán v laø ñöôøng ñi ngaén nhaát töø s ñeán p[v] theo sau laø
caïnh (p[v], v).
Chöùng minh
Tröôøng hôïp ñænh v khoâng ñeán ñöôïc töø s:
°
(a) d[v] (s, v) = (Lemma 23.2)
(b) Doøng 14 chæ ñöôïc thöïc thi khi v coù d[v] < , do ñoù neáu khoâng
ñeán ñöôïc v töø s thì d[v] = vaø v seõ khoâng ñöôïc tìm thaáy.
7.11.2004
Ch. 8: Elementary Graph Algorithms
19
Ñöôøng ñi ngaén nhaát
Chöùng minh (tieáp)
ª Tröôøng hôïp ñænh v ñeán ñöôïc töø s: ñònh nghóa Vk = {v V : (s, v) = k}
– “Induction on k”.
°
“Inductive hypothesis”: vôùi moïi v Vk , trong khi thöïc thi BFS
thì coù ñuùng moät thôøi ñieåm maø
– v ñöôïc sôn xaùm
– d[v] ñöôïc gaùn trò k
– Neáu v s thì p[v] ñöôïc gaùn trò u vôùi u Vk− 1
– v ñöôïc ñöa vaøo queue Q.
“Basis”: k = 0, kieåm tra laø ñuùng
“Inductive step”
°
°
– Xeùt v Vk baát kyø, k 1.
– Coù u Vk − 1 sao cho: u laø head cuûa queue vaø (u, v) ñöôïc
thaêm doø.
ª Phaàn coøn laïi: ...
7.11.2004
Ch. 8: Elementary Graph Algorithms
20
Tải về để xem bản đầy đủ
42 trang
27/04/2022
6080
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị", để 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:
- bai_giang_giai_thuat_chuong_8_giai_thuat_tim_kiem_trong_do_t.ppt
