Bài giảng Giải thuật - Chương 6: Fibonacci Heaps
• Cấu trúc của Fibonacci heap (tiếp)
ª Hiện thực Fibonacci heap trong bộ nhớ:
Mỗi nút x có các trường
– p[x]: con trỏ đến nút cha của nó.
– child[x]: con trỏ đến một con nào đó trong các con của nó.
° Các con của x được liên kết với nhau trong một danh sách vòng liên kết kép (circular, doubly linked list), gọi là danh sách các con của x.
° Mỗi con y trong danh sách các con của x có các con trỏ
– left[y], right[y] chỉ đến các anh em bên trái và bên phải của y.
Nếu y là con duy nhất của x thì left[y] = right[y] = y.
) 11 n [ H ] n [ H ] 1 12 return z 7.10.2004 20 Chương 6: Fibonacci Heaps Củng cố (consolidate) Thủ tục phụ: củng cố danh sách các gốc của một Fibonacci heap H liên kết mọi cặp gốc có cùng bậc thành một gốc mới cho đến khi mọi gốc có bậc khác nhau. C ONSOLIDATE ( H ) 1 for i 0 to D ( n [ H ]) 2 do A [ i ] NIL 3 for mổi nút w trong danh sách các gốc của H 4 do x w 5 d degree [ x ] 6 while A [ d ] NIL 7 do y A [ d ] 8 if key [ x ] > key [ y ] 9 then tráo x y 10 F IB -H EAP -L INK ( H , y , x ) 11 A [ d ] NIL 12 d d + 1 13 A [ d ] x 7.10.2004 21 Chương 6: Fibonacci Heaps Củng cố (consolidate) (tiếp) 14 min [ H ] NIL 15 for i 0 to D ( n [ H ]) 16 do if A [ i ] NIL 17 then thêm A [ i ] vào danh sách các gốc của H 18 if min [ H ] = NIL or key [ A [ i ]] < key [ min [ H ]] 19 then min [ H ] A [ i ] 7.10.2004 22 Chương 6: Fibonacci Heaps Liên kết hai gốc có cùng bậc Thủ tục C ONSOLIDATE liên kết các gốc có cùng bậc mãi cho đến khi mọi gốc có được sau đó đều có bậc khác nhau. Dùng thủ tục F IB -H EAP -L INK ( H , y , x ) để tách gốc y khỏi danh sách gốc của H , sau đó liên kết gốc y vào gốc x , gốc x và gốc y có cùng bậc. F IB -H EAP -L INK ( H , y , x ) 1 đem y ra khỏi danh sách các gốc của H 2 làm y thành con của x , tăng degree [ x ] 3 mark [ y ] FALSE 7.10.2004 23 Chương 6: Fibonacci Heaps Thực thi F IB -H EAP -E XTRACT -M IN : ví dụ 7.10.2004 24 Chương 6: Fibonacci Heaps Thực thi F IB -H EAP -E XTRACT -M IN : ví dụ (tiếp) 7.10.2004 25 Chương 6: Fibonacci Heaps Chi phí thực sự của F IB -H EAP -E XTRACT -M IN Gọi H là Fibonacci heap ngay trước khi gọi F IB - H EAP - E XTRACT - M IN , số nút của H là n . Chi phí thực sự bao gồm: O ( D ( n )): vì có nhiều lắm là D ( n ) con của nút nhỏ nhất cần được xử lý bỡi: F IB - H EAP - E XTRACT - M IN các dòng 1-2 và 14-19 của C ONSOLIDATE O ( D ( n ) + t ( H )): vì khi gọi C ONSOLIDATE chiều dài của danh sách gốc nhiều lắm là D ( n ) + t ( H ) 1, mà thời gian chạy vòng lặp for dòng 3-13 nhiều lắm là tỉ lệ với chiều dài của danh sách gốc này. Vậy chi phí thực sự của F IB - H EAP - E XTRACT - M IN là O ( D ( n ) + t ( H )). 7.10.2004 26 Chương 6: Fibonacci Heaps Chi phí khấu hao của F IB -H EAP -E XTRACT -M IN Gọi H’ là Fibonacci heap sau khi gọi F IB - H EAP - E XTRACT - M IN lên H . Nhắc lại: hàm thế năng của H được định nghĩa là ( H ) = t ( H ) + 2 m ( H ) Biết: chi phí khấu hao = chi phí thực sự + ( H’ ) ( H ) Đã tính: phí tổn thực sự của F IB - H EAP - E XTRACT - M IN là O ( D ( n ) + t ( H )). Sau khi gọi F IB - H EAP - E XTRACT - M IN lên H , số gốc (hay số cây) của H’ nhiều lắm là D ( n ) + 1, và không có nút nào được đánh dấu. Vậy ( H’ ) = ( D ( n ) + 1) + 2 m ( H ). 7.10.2004 27 Chương 6: Fibonacci Heaps Chi phí khấu hao của F IB -H EAP -E XTRACT -M IN (tiếp) Do đó chi phí khấu hao của F IB - H EAP - E XTRACT - M IN là O ( D ( n ) + t ( H )) + ( ( D ( n ) + 1) + 2 m ( H )) ( t ( H ) + 2 m ( H )) = O ( D ( n )) + O ( t ( H )) t ( H ) = O ( D ( n )) , vì có thể scale up đơn vị của thế năng để khống chế hằng số ẩn trong O ( t ( H )). (Ví dụ: với O ( t ( H )) = 99 t ( H ) + 77 thì có thể chọn 1 đơn vị thế năng = 78 ) đến từ thế năng 7.10.2004 28 Chương 6: Fibonacci Heaps Giảm khóa của một nút Thủ tục để giảm khóa của một nút: F IB -H EAP -D ECREASE -K EY giảm khóa của nút x trong Fibonacci heap H thành trị mới k nhỏ hơn trị cũ của khóa. F IB -H EAP -D ECREASE -K EY ( H , x , k ) 1 if k > key [ x ] 2 then error “khóa mới lớn hơn khóa hiện thời” 3 key [ x ] k 4 y p [ x ] 5 if y NIL and key [ x ] < key [ y ] 6 then C UT ( H , x , y ) 7 C ASCADING -C UT ( H , y ) 8 if key [ x ] < key [ min [ H ]] 9 then min [ H ] x 7.10.2004 29 Chương 6: Fibonacci Heaps Giảm khóa của một nút (tiếp) Thủ tục phụ để cắt liên kết giữa x và y , cha của nó, sau đó làm x thành một gốc. C UT ( H , x , y ) 1 đem x ra khỏi danh sách các con của y , giảm degree [ y ] 2 thêm x vào danh sách các gốc của H 3 p [ x ] NIL 4 mark [ x ] FALSE 7.10.2004 30 Chương 6: Fibonacci Heaps Giảm khóa của một nút (tiếp) Thủ tục phụ để xử lý cha của nút bị cắt dựa trên trường mark [ x ]. C ASCADING -C UT ( H , y ) 1 z p [ y ] 2 if z NIL 3 then if mark [ y ] = FALSE 4 then mark [ y ] TRUE 5 else C UT ( H , y , z ) 6 C ASCADING -C UT ( H , z ) 7.10.2004 31 Chương 6: Fibonacci Heaps Giảm khoá của một nút: ví dụ (a) Heap ban đầu (b) Giảm khóa 46 thành 15 (c)-(e) Giảm khóa 35 thành 5 7.10.2004 32 Chương 6: Fibonacci Heaps Chi phí thực sự của F IB -H EAP -D ECREASE -K EY Gọi H là Fibonacci heap ngay trước khi gọi F IB - H EAP - D ECREASE - K EY, số nút của H là n . Chi phí thực sự của F IB - H EAP - D ECREASE - K EY bao gồm: O (1): dòng 1-5 và 8-9, thời gian thực thi các cascading cuts. Giả sử C ASCADING -C UT được gọi đệ quy c lần. Thời gian thực thi C ASCADING -C UT là O (1) không kể các gọi đệ quy. c lần 7.10.2004 33 Chương 6: Fibonacci Heaps Chi phí thực sự của F IB -H EAP -D ECREASE -K EY (tiếp) Vậy phí tổn thực sự của F IB - H EAP - D ECREASE - K EY là O ( c ). 7.10.2004 34 Chương 6: Fibonacci Heaps Chi phí khấu hao của F IB -H EAP -D ECREASE -K EY Gọi H’ là Fibonacci heap sau khi gọi F IB - H EAP - D ECREASE -K EY lên H . Nhắc lại: hàm thế năng của H được định nghĩa là ( H ) = t ( H ) + 2 m ( H ) chi phí khấu hao = chi phí thực sự + ( H’ ) ( H ) Đã tính: chi phí thực sự của F IB - H EAP - D ECREASE -K EY là O ( c ). Sau khi gọi F IB - H EAP - D ECREASE -K EY lên H , thì H’ có t ( H ) + c cây. ( H’ ) ( H ) ( t ( H ) + c ) + 2( m ( H ) c + 2) ( t ( H ) + 2 m ( H )) 4 c . số lần gọi CUT bằng số lần gọi C ASCADING -C UT = c , mà mỗi lần thực thi CUT thì 1 nút trở thành cây mỗi lần thực thi C ASCADING -C UT ngoại trừ lần cuối của gọi đệ quy thì 1 nút được unmarked và lần cuối của gọi đệ quy C ASCADING -C UT có thể marks 1 nút. 7.10.2004 35 Chương 6: Fibonacci Heaps Chi phí khấu hao của F IB -H EAP -D ECREASE -K EY (tiếp) Do đó chi phí khấu hao của F IB - H EAP - D ECREASE -K EY là O ( c ) + 4 c = O (1), vì có thể scale up đơn vị của thế năng để khống chế hằng số ẩn trong O ( c ). đến từ thế năng 7.10.2004 36 Chương 6: Fibonacci Heaps Xóa một nút Thủ tục để xóa một nút: F IB -H EAP -D ELETE Xóa một nút x khỏi một Fibonacci heap H . F IB -H EAP -D ELETE ( H , x ) 1 F IB -H EAP -D ECREASE -K EY ( H , x , ) 2 F IB -H EAP -E XTRACT -M IN ( H ) 7.10.2004 37 Chương 6: Fibonacci Heaps Chận trên lên bậc lớn nhất Lemma (sách: Lemma 21.1) Cho x là một nút bất kỳ trong một Fibonacci heap, và giả sử degree [ x ] = k . Gọi y 1 , y 2 ,..., y k là các con của x được xếp theo thứ tự lúc chúng được liên kết vào x , từ lúc sớm nhất đến lúc trễ nhất. Thì degree [ y 1 ] 0 và degree [ y i ] i - 2 với i = 2, 3,..., k . ... x y 1 y 2 y k 7.10.2004 38 Chương 6: Fibonacci Heaps Chận trên lên bậc lớn nhất (tiếp) Chứng minh Rõ ràng là degree [ y 1 ] 0. i 2: Khi y i được liên kết vào x thì y 1 , y 2 ,..., y i - 1 là trong tập các con của x nên khi đó degree [ x ] i - 1. Nút y i được liên kết vào x chỉ khi nào degree [ x ] = degree [ y i ], vậy khi đó degree [ y i ] cũng i - 1. Kể từ khi đó đến nay, nút y i mất nhiều lắm là một con, vì nếu nó mất hai con thì nó đã bị cắt khỏi x . Vậy degree [ y i ] ( i - 1) - 1 i - 2 . 7.10.2004 39 Chương 6: Fibonacci Heaps Chận trên lên bậc lớn nhất (tiếp) Định nghĩa Với k = 0, 1, 2,... định nghĩa F k là s ố Fibonacci thứù k : Lemma (sách: Lemma 21.2, bài tập) Với mọi số nguyên k 0, Lemma (Bài tập 2.2-8) Với mọi số nguyên k 0, ta có F k + 2 f k , trong đó f = (1 + 5 ) / 2, tỉ số vàng . 0 nếu k = 0, F k = 1 nếu k = 1, F k - 1 + F k - 2 nếu k 2. 7.10.2004 40 Chương 6: Fibonacci Heaps Chận trên lên bậc lớn nhất (tiếp) Lemma (sách: Lemma 21.3) Cho x là một nút bất kỳ trong một Fibonacci heap, và cho k = degree [ x ]. Thì size( x ) F k + 2 f k , trong đó f = (1 + 5 ) / 2. Chứng minh Gọi s k là trị nhỏ nhất có thể được của size( z ) trên mọi nút z mà degree [ z ] = k . Rõ ràng là s 0 = 1, s 1 = 2, s 2 = 3. Ta có s k size( x ) 7.10.2004 41 Chương 6: Fibonacci Heaps Chận trên lên bậc lớn nhất Chứng minh (tiếp) vì s k là tăng đơn điệu theo k , nên từ degree [ y i ] i - 2 (Lemma 21.1) ta có . Vậy ... x y 1 y 2 y k 7.10.2004 42 Chương 6: Fibonacci Heaps Chận trên lên bậc lớn nhất Chứng minh (tiếp) dùng quy nạp theo k để chứng minh rằng s k F k + 2 , với k 0: Bước cơ bản: với k = 0 và k = 1 là rõ ràng. Bước quy nạp: Giả thiết quy nạp: k 2 và s i F i + 2 với i = 0, 1,, k - 1. Từ trên ta có vậy: size( x ) s k F k + 2 f k . 7.10.2004 43 Chương 6: Fibonacci Heaps Chận trên lên bậc lớn nhất (tiếp) Hệ luận Bậc lớn nhất D ( n ) của nút bất kỳ trong một Fibonacci heap có n nút là O (lg n ). Chứng minh Dùng Lemma 21.3. 7.10.2004 44 Chương 6: Fibonacci Heaps
File đính kèm:
- bai_giang_giai_thuat_chuong_6_fibonacci_heaps.ppt