Bài giảng Phân tích thiết kế giải thuật - Chương 6: Fibonacci Heaps
Fibonacci heap
ª ÖÙng duïng cuûa Fibonacci heap
– Giaûi thuaät Prim ñeå xaùc ñònh moät caây khung nhoû nhaát trong moät ñoà
thò coù troïng soá.
– Giaûi thuaät Dijkstra ñeå tìm moät ñöôøng ñi ngaén nhaát trong ñoà thò coù
höôùng vaø coù troïng soá döông.
7.10.2004
1
Chöông 6: Fibonacci Heaps
Caáu truùc cuûa Fibonacci heap
ª Ñònh nghóa
Moät Fibonacci heap laø moät taäp caùc caây maø moãi caây ñeàu laø heap-
ordered.
– Caây trong Fibonacci heap khoâng caàn thieát phaûi laø caây nhò thöùc.
– Caây trong Fibonacci heap laø coù goác nhöng khoâng coù thöù töï
(unordered).
7.10.2004
2
Chöông 6: Fibonacci Heaps
Caáu truùc cuûa Fibonacci heap (tieáp)
ª Hieän thöïc Fibonacci heap trong boä nhôù:
Moãi nuùt x coù caùc tröôøng
– p[x]: con troû ñeán nuùt cha cuûa noù.
– child[x]: con troû ñeán moät con naøo ñoù trong caùc con cuûa noù.
°
Caùc con cuûa x ñöôïc lieân keát vôùi nhau trong moät danh saùch
voøng lieân keát keùp (circular, doubly linked list), goïi laø danh
saùch caùc con cuûa x.
°
Moãi con y trong danh saùch caùc con cuûa x coù caùc con troû
– left[y], right[y] chæ ñeán caùc anh em beân traùi vaø beân phaûi
cuûa y.
Neáu y laø con duy nhaát cuûa x thì left[y] = right[y] = y.
7.10.2004
3
Chöông 6: Fibonacci Heaps
Caáu truùc cuûa Fibonacci heap
(tieáp)
Caùc tröôøng khaùc trong nuùt x
– degree[x]: soá caùc con chöùa trong danh saùch caùc con cuûa nuùt x
– mark[x]: coù trò bool laø TRUE hay FALSE,
chæ raèng x coù maát moät con hay khoâng keå töø laàn cuoái maø x ñöôïc
laøm thaønh con cuûa moät nuùt khaùc.
7.10.2004
4
Chöông 6: Fibonacci Heaps
Caáu truùc cuûa Fibonacci heap
(tieáp)
Neáu H laø Fibonacci heap
– Truy caäp H baèng con troû min[H] ñeán nuùt goác cuûa caây chöùa khoaù
nhoû nhaát goïi laø nuùt nhoû nhaát cuûa H.
°
Neáu H laø troáng thì min[H] = NIL.
– Taát caû caùc nuùt goác cuûa caùc caây trong H ñöôïc lieân keát vôùi nhau bôõi
caùc con troû left vaø right cuûa chuùng thaønh moät saùch lieân keát keùp
voøng goïi laø danh saùch caùc goác cuûa H.
– n[H]: soá caùc nuùt hieän coù trong H.
7.10.2004
5
Chöông 6: Fibonacci Heaps
Caáu truùc cuûa Fibonacci heap: ví duï
danh saùch
caùc goác
moät danh saùch
caùc con
7.10.2004
6
Chöông 6: Fibonacci Heaps
Haøm theá naêng
ª Duøng phöông phaùp theá naêng ñeå phaân tích hieäu suaát cuûa caùc thao taùc
leân caùc Fibonacci heap.
ª Cho moät Fibonacci heap H
– goïi soá caùc caây cuûa Fibonacci heap H laø t(H)
– goïi soá caùc nuùt x ñöôïc ñaùnh daáu (mark[x] = TRUE) laø m(H).
Haøm theá naêng cuûa H ñöôïc ñònh nghóa nhö sau
– (H) = t(H) + 2 m(H)
– theá naêng cuûa moät taäp caùc Fibonacci heap laø toång cuûa caùc theá naêng
cuûa caùc Fibonacci heap thaønh phaàn.
7.10.2004
7
Chöông 6: Fibonacci Heaps
Haøm theá naêng (tieáp)
ª Khi baét ñaàu haøm theá naêng coù trò laø 0, sau ñoù haøm theá naêng coù trò 0.
Do ñoù chi phí khaáu hao toång coäng laø moät caän treân cuûa chi phí thöïc söï
toång coäng cho daûy caùc thao taùc.
7.10.2004
8
Chöông 6: Fibonacci Heaps
Baäc toái ña
ª Goïi D(n) laø caän treân cho baäc lôùn nhaát cuûa moät nuùt baát kyø trong moät
Fibonacci heap coù n nuùt.
ª Seõ chöùng minh: D(n) = O(lg n).
7.10.2004
9
Chöông 6: Fibonacci Heaps
Caùc thao taùc leân heap hôïp nhaát ñöôïc
ª Neáu chæ duøng caùc thao taùc leân heap hôïp nhaát ñöôïc:
– MAKE-HEAP
– INSERT
– MINIMUM
– EXTRACT-MIN
– UNION
thì moãi Fibonacci heap laø moät taäp caùc caây nhò thöùc “khoâng thöù töï ”.
7.10.2004
10
Chöông 6: Fibonacci Heaps
Caây nhò thöùc khoâng thöù töï
ª Moät caây nhò thöùc khoâng thöù töï (unordered binomial tree) ñöôïc ñònh
nghóa ñeä quy nhö sau
– Caây nhò thöùc khoâng thöù töï U0 goàm moät nuùt duy nhaát.
– Moät caây nhò thöùc khoâng thöù töï Uk ñöôïc taïo bôûi hai caây nhò thöùc
khoâng thöù töï Uk - 1 baèng caùch laáy goác cuûa caây naøy laøm con (vò trí
trong danh saùch caùc con laø tuøy yù) cuûa goác cuûa caây kia.
ª Lemma 19.1 ñuùng cho caùc caây nhò thöùc cuõng ñuùng cho caùc caây nhò
thöùc khoâng thöù töï, nhöng vôùi thay ñoåi sau cho tính chaát 4:
4’. Ñoái vôùi caây nhò thöùc khoâng thöù töï Uk , nuùt goác coù baäc laø k, trò k
lôùn hôn baäc cuûa moïi nuùt baát kyø khaùc. Caùc con cuûa goác laø goác cuûa caùc
caây con U0 , U1 ,..., Uk - 1 trong moät thöù töï naøo ñoù.
7.10.2004
11
Chöông 6: Fibonacci Heaps
Taïo moät Fibonacci heap môùi
ª Thuû tuïc ñeå taïo moät Fibonacci heap troáng:
MAKE-FIB-HEAP
– caáp phaùt vaø traû veà ñoái töôïng Fibonacci heap H, vôùi
n[H] = 0,
min[H] = NIL
ª Phaân tích thuû tuïc MAKE-FIB-HEAP
– Chi phí thöïc söï laø O(1)
– Theá naêng cuûa Fibonacci heap roãng laø
(H) = t(H) + 2 m(H)
= 0 .
– Vaäy chi phí khaáu hao laø O(1).
7.10.2004
12
Chöông 6: Fibonacci Heaps
Cheøn moät nuùt vaøo Fibonacci heap
ª Thuû tuïc ñeå cheøn moät nuùt vaøo moät Fibonacci heap:
FIB-HEAP-INSERT
– cheøn nuùt x (maø key[x] ñaõ ñöôïc gaùn trò) vaøo Fibonacci heap H
FIB-HEAP-INSERT(H, x)
1 degree[x] 0
2 p[x] NIL
3 child[x] NIL
4 left [x] x
5 right [x] x
6 mark [x] FALSE
7 noái danh saùch caùc goác chöùa x vaøo danh saùch caùc goác cuûa H
8 if min[H] = NIL or key[x] < key [min[H]]
9
then min[H] x
10 n[H] n[H] + 1
7.10.2004
13
Chöông 6: Fibonacci Heaps
Ví duï cheøn moät nuùt vaøo Fibonacci heap
(tieáp)
min[H ]
23
7
3
17
30
24
52
46
18
39
26
38
41
35
FIB-HEAP-INSERT(H, x), vôùi key[x ] = 21
min[H ]
23
7
3
17
30
24
21
52
46
18
39
26
38
41
35
7.10.2004
14
Chöông 6: Fibonacci Heaps
Cheøn moät nuùt vaøo Fibonacci heap (tieáp)
ª Phaân tích thuû tuïc FIB-HEAP-INSERT:
Phí toån khaáu hao laø O(1) vì
– Goïi H laø Fibonacci heap ñaàu vaøo, vaø H’ laø Fibonacci heap keát
quaû.
– Ta coù: t(H’) = t(H) + 1,
m(H’) = m(H).
Vaäy hieäu theá (H’) - (H) baèng
((t(H) + 1) + 2m(H)) - (t(H) + 2m(H)) = 1.
– Phí toån khaáu hao baèng
phí toån thöïc söï + hieäu theá = O(1) + 1
= O(1).
7.10.2004
15
Chöông 6: Fibonacci Heaps
Tìm nuùt nhoû nhaát
ª Con troû min[H] chæ ñeán nuùt nhoû nhaát cuûa Fibonacci heap H.
ª Phaân tích:
– Phí toån thöïc söï laø O(1)
– Hieäu theá laø 0 vì theá naêng cuûa H khoâng thay ñoåi
– Vaäy phí toån khaáu hao laø O(1) (= phí toån thöïc söï).
7.10.2004
16
Chöông 6: Fibonacci Heaps
Hôïp nhaát hai Fibonacci heap
ª Thuû tuïc ñeå hôïp nhaát hai Fibonacci heap:
FIB-HEAP-UNION
– hôïp nhaát caùc Fibonacci heap H1 vaø H2
– traû veà H, Fibonacci heap keát quaû
FIB-HEAP-UNION(H1, H2)
1 H MAKE-FIB-HEAP()
2 min[H] min[H1]
3 noái danh saùch caùc goác cuûa H2 vôùi danh saùch caùc goác cuûa H
4 if (min[H1] = NIL) or (min[H2] NIL and min[H2] min[H1])
5
then min[H] min[H2]
6 n[H] n[H1] + n[H2]
7 giaûi phoùng (free) caùc ñoái töôïng H1 vaø H2
8 return H
7.10.2004
17
Chöông 6: Fibonacci Heaps
Hôïp nhaát hai Fibonacci heap
(tieáp)
ª Ví duï: giaû söû min[H1] < min[H2]
min[H1]
min[H2]
FIB-HEAP-UNION[H1, H2]
min[H]
7.10.2004
18
Chöông 6: Fibonacci Heaps
Hôïp nhaát hai Fibonacci heap (tieáp)
ª Phaân tích thuû tuïc FIB-HEAP-UNION:
Phí toån khaáu hao ñöôïc tính töø
– phí toån thöïc söï laø O(1)
– hieäu theá laø
(H) - ((H1) + (H2))
= (t(H) + 2m(H)) - ((t(H1) + 2m(H1)) + (t(H2) + 2m(H2)))
= 0, vì t(H) = t(H1) + t(H2) vaø
m(H) = m(H1) + m(H2)
– Vaäy phí toån khaáu hao = phí toån thöïc söï + hieäu theá
= O(1)
7.10.2004
19
Chöông 6: Fibonacci Heaps
Taùch ra nuùt nhoû nhaát
ª Thuû tuïc ñeå taùch ra nuùt nhoû nhaát:
FIB-HEAP-EXTRACT-MIN
– taùch nuùt nhoû nhaát khoûi Fibonacci heap H
FIB-HEAP-EXTRACT-MIN(H)
1 z min[H]
2 if z NIL
3
4
then for moåi con x cuûa z
do theâm x vaøo danh saùch caùc goác cuûa H
5
p[x] NIL
ñem z ra khoûi danh saùch caùc goác cuûa H
if z = right[z]
6
7
8
then min[H] NIL
else min[H] right[z]
CONSOLIDATE(H)
9
10
11
n[H] n[H] - 1
12 return z
7.10.2004
20
Chöông 6: Fibonacci Heaps
Tải về để xem bản đầy đủ
44 trang
16700
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phân tích thiết kế giải thuật - Chương 6: Fibonacci Heaps", để 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_phan_tich_thiet_ke_giai_thuat_chuong_6_fibonacci_h.ppt
