Bài giảng Giải thuật - Chương 6: Fibonacci heap

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öï U₀goàm moät nuùt duy nhaát.

– Moät caây nhò thöùc khoâng thöù töï U_kñöôïc taïo bôûi hai caây nhò thöùc

khoâng thöù töï U_{k - 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öï U_k, 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 U₀, U₁,..., U_{k - 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 H₁vaø H₂

– traû veà H, Fibonacci heap keát quaû

FIB-HEAP-UNION(H₁, H₂)

1 H  MAKE-FIB-HEAP()

2 min[H]  min[H₁]

3 noái danh saùch caùc goác cuûa H₂vôùi danh saùch caùc goác cuûa H

4 if (min[H₁] = NIL) or (min[H₂]  NIL and min[H₂]  min[H₁])

5

then min[H]  min[H₂]

6 n[H]  n[H₁] + n[H₂]

7 giaûi phoùng (free) caùc ñoái töôïng H₁vaø H₂

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[H₁] < min[H₂]

min[H₁]

min[H₂]

FIB-HEAP-UNION[H₁, H₂]

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) - ((H₁) + (H₂))

= (t(H) + 2m(H)) - ((t(H₁) + 2m(H₁)) + (t(H₂) + 2m(H₂)))

= 0, vì t(H) = t(H₁) + t(H₂) vaø

m(H) = m(H₁) + m(H₂)

– 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