BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
-----------------*@*---------------------
LUẬN ÁN THẠC SỸ TIN HỌC
ĐỀ TÀI
ỨNG DỤNG FIBONACCI HEAP CẢI TIẾN THUÂÂT
TOÁN DIJKSTRA
Hà Nội, 7/2015
2
MỤC LỤC
MỞ ĐẦU..........................................................................................................1
CHƯƠNG 1. FIBONACCI HEAP.................................................................2
1.1. Tổng quan về cấu trúc dữ liệu heap........................................................2
1.2. Fibonacci heap........................................................................................3
1.2.1. Giới thiệu Fibonacci heap (Đống Fibonacci)...................................3
1.2.2. Cấu trúc Fibonacci heap...................................................................4
1.2.3. Các thao tác trên Fibonacci heap......................................................6
1.3. Kết luận chương....................................................................................19
CHƯƠNG 2. ỨNG DỤNG FIBONACCI HEAP CẢI TIẾN THUÂÂT
TOÁN DIJKSTRA........................................................................................20
2.1. Sơ đồ thuật toán Dijkstra kết hợp với Fibonacci Heap.........................20
2.2. Ứng dụng Dijkstra Fibonacci heap giải bài toán tìm đường đi ngắn nhất
.....................................................................................................................21
2.2.1 Một số kiểu dữ liệu và các biến trong chương trình........................21
2.2.2. Một số hàm và thủ tục trong chương trình.....................................22
2.3.Sơ đồ thuật toán.....................................................................................25
2.4. Các kết quả thực nghiệm.......................................................................25
2.5. Kết luận chương....................................................................................27
KẾT LUẬN....................................................................................................28
TÀI LIỆU THAM KHẢO............................................................................29
1
MỞ ĐẦU
Trong những năm gần đây trong các kỳ thi học sinh giỏi Quốc Gia,
Quốc tế môn Tin học, có rất nhiều bài toán đòi hỏi học sinh phải ứng dụng các
cấu trúc dữ liê êu trừu tượng trong lâ êp trình thì mới có thể giải quyết triê êt để
được các bài toán đó. Heap là mô êt trong những cấu trúc dữ liê êu trừu tượng
như thế, tuy nhiên có nhiều loại heap khác nhau và đô ê phức tạp trong mô êt số
thao tác đối với chúng cũng có thể khác nhau. Trong tài liê êu giáo khoa
chuyên tin của các tác giả Đỗ Đức Đông, Nguyễn Thanh Hùng, Lê Minh
Hoàng đã trình bày kỹ về binary heap, đây là tài liê êu quý giúp ích rất nhiều
cho các học sinh chuyên Tin của Viê êt Nam ta. Qua nghiên cứu, tìm hiểu các
tài liê êu chúng tôi nhâ nê thấy còn mô êt số loại heap nữa chưa có tài liê êu nào
trong nước đề câ êp đến mô êt cách hoàn chỉnh. Vì vâ êy trong đề tài này chúng
tôi sẽ trình bày về Fibonacci heap nhằm cung cấp thêm mô tê sự lựa chọn cho
các em học sinh chuyên Tin trong khi lâ êp trình. Chắc chắn đề tài không tránh
khỏi những thiếu sót nhất định, rất mong nhâ nê được những ý kiến đóng góp
quý báu của các thầy cô, các em học sinh và các bạn đô cê giả.
Ý nghĩa khoa học của đề tài:
Fibonacci heap có thể được ứng dụng để giải quyết các bài toán cả trong
nghiên cứu lý thuyết và trong thực tiễn. Hiện tại cấu trúc dữ liê êu này chưa
phổ biến ở Việt Nam, vì thế đề tài này có thể sẽ là mô êt tài liê êu có ích cho các
em học sinh và những người quan tâm có thêm một công cụ mạnh để giải
quyết một số bài toán có liên quan trong lập trình.
Đề tài gồm có hai chương:
- Chương 1 trình bày về Fibonacci heap
- Chương 2 là phần ứng dụng Fibonacci heap vào viê êc cải tiến thuâ êt
toán Dijkstra giải bài toán tìm đường đi ngắn nhất trên đồ thị.
2
CHƯƠNG 1
FIBONACCI HEAP
1.1. Tổng quan về cấu trúc dữ liệu heap
Ta có thể dùng mảng hoặc danh sách móc nối để biểu diễn một hàng
đợi ưu tiên, khi đó các thao tác Insert và Update có thể thực hiện với độ phức
tạp là O(1), tuy nhiên các thao tác Find min (Find max) và Extract lại có độ
phức tạp là O(n). Vì vậy, trong thực tế người ta hay dùng cấu trúc dữ liệu trừu
tượng heap (đống) để biểu diễn hàng đợi ưu tiên.
Heap là một cấu trúc dữ liệu trừu tượng, bao gồm một tập n phần tử,
mỗi phần tử có một giá trị khóa xác định. Các phép toán trên một heap được
mô tả trong bảng dưới đây :
Make_ heap
Trả về một heap mới rỗng.
Insert (x,h)
Chèn một giá phần tử x mới,có khóa xác định vào heap
Find_ min
Trả về phần tử có khóa nhỏ nhất, không làm thay đổi heap
Extract_ min
Trả về phần tử có khóa nhỏ nhất và xóa nó ra khỏi heap
Trong một số bài toán còn có thêm các phép toán sau :
Union(h1,h2)
Hợp nhất hai heap h1, h2 thành heap mới, đồng thời xóa h1,
h2
Decrease(∆,x,h) Giảm khóa của phần tử x một lượng ∆ trong heap
Delete(xh)
Xóa phần tử X ra khỏi heap
Heap còn có thể gọi là hàng đợi có độ ưu tiên (priority queue) hay các
đống khả trộn (mergeable heaps).
Một số loại heaps, và thời gian thao tác các phép toán được trình bày
trong bảng dưới đây [2]:
Heaps
Thao tác
Linked Binary
Bionimal
Fibonacci Relax
3
list
make heap
O(1)
O(1)
O(1)
O(1)
O(1)
Insert (x,h)
O(1)
O(logN)
O(logN)
O(1)
O(1)
Find min
O(N)
O(1)
O(logN)
O(1)
O(1)
extract min
O(N)
O(logN)
O(logN)
O(logN)
O(logN)
Union(h1,h2)
O(1)
O(N)
O(logN)
O(1)
O(1)
O(1)
O(logN)
O(logN)
O(1)
O(1)
O(N)
O(logN)
O(logN)
O(logN)
O(logN)
Decrease(∆,x,h
)
Delete(x,h)
Trong phần tiếp theo chúng ta sẽ nghiên cứu kỹ về Fibonacci heap.
1.2. Fibonacci heap
1.2.1. Giới thiệu Fibonacci heap (Đống Fibonacci)
Cấu trúc dữ liệu Fibonacci heap (Đống Fibonacci) được hai giáo sư
Fredman và Tarjan đưa ra vào năm 1986, nhằm áp dụng vào các bài toán tối
ưu trên đồ thị, độ phức tạp của các thuật toán giải một số bài toán điển hình
khi sử dụng Fibonacci heap được thống kê dưới đây [2]:
O(nlogn + m): Cho bài toán tìm đường đi tối ưu xuất phát từ một đỉnh.
O(n2logn + nm): Cho bài toán tìm đường đi tối ưu giữa mọi cặp đỉnh.
O(n2logn + nm): Cho bài toán so khớp hai nhánh có trọng số .
Trước khi định nghĩa Fibonacci heap, ta đưa ra một số khái niệm:
Cây có gốc: Là một cây tự do mà ở đó có một trong các đỉnh được phân
biệt với các đỉnh còn lại và được gọi là gốc.
Cây có thứ tự: Là cây có gốc, mà các nút con trực thuộc một nút cha
được sắp xếp theo một thứ tự xác định.
4
Cây sắp xếp theo đống: Là cây có gốc, và nếu nút x là nút bất kỳ thì nó
có giá trị khóa lớn hơn hoặc bằng (nhỏ hơn hoặc bằng) khóa của cha nó. Từ
đó nút gốc là nút có khóa nhỏ nhất (lớn nhất).
Định nghĩa : Fibonacci heap là một tập hợp các cây được sắp xếp theo
đống. Các cây trong Fibonacci heap không bị ràng buộc về thứ tự[2].
Hình1.1: Fibonacci heap gồm 5 cây sắp xếp theo đống với 14 nút
1.2.2. Cấu trúc Fibonacci heap
Hình 1.2 mô tả cách biểu diễn cấu trúc heap. Mỗi nút x chứa một biến
trỏ p[x] trỏ đến cha của nó và một biến trỏ child[x] trỏ đến một con bất kỳ của
nó. Các con của x được nối kết theo một danh sách nối kết đôi theo vòng tròn
mà ta gọi là danh sách con của x. Mỗi nút y trong danh sách con có các biến
trỏ left[y] và right[y] trỏ đến anh em ruột trái và phải của nó. Nếu nút y là duy
nhất thì left[y] = right[y] = y. Thứ tự xuất hiện các nút trong danh sách con là
tùy ý.
Việc thể hiện danh sách con bằng danh sách nối đôi vòng tròn có 2 ưu
điểm: Thứ nhất, có thể gỡ bỏ một nút ra khỏi danh sách với độ phức tạp là
O(1). Thứ hai, có thể ghép nối 2 danh sách với độ phức tạp tính toán là O(1).
Ngoài ra mỗi nút x còn có :
degree[x]: Lưu số nút trong danh sách con của x.
5
bool mark[x]: Kiểm tra x đã mất một con hay chưa kể từ lần cuối cùng
x trở thành con của một nút khác.
Các gốc của tất cả các cây trong Fibonacci heap được nối kết với nhau
bằng các biến trỏ left, right của chúng tạo thành một danh sách nối kết đôi
vòng tròn gọi là danh sách gốc. Biến trỏ min[H] trỏ đến nút có khóa nhỏ nhất
trong danh sách gốc, từ đây ta sẽ coi min[H] là đại diện của H nói cách khác
là minH quản lý H. Số lượng các nút trong H sẽ được lưu trong biến nH.
Hình 1.2: Mô phỏng cấu trúc Fibonacci heap
Cấu trúc dữ liệu miêu tả một nút trong Fibonacci heap[1]:
node = record
key : integer;
degree : integer;
parent : ^node;
child : ^node;
left : ^node;
right : ^node ;
mark : boolean;
end;
Hàm tiềm năng
Để phân tích đánh giá độ phức tạp trong các phép toán đối với
Fibonacci heap ta sử dụng phương pháp phân tích tiềm năng, khi đó hao phí
khấu trừ của một thuật toán được xem là độ phức tạp của thuật toán đó [1].
Đối với Fibonacci heap, ta sử dụng hàm tiềm năng Φ(H) = t(H) + 2m(H),
6
trong đó: t(H) là số lượng nút trong danh sách gốc, m(H) là số lượng các nút
đánh dấu. Ta mặc nhận rằng ở trạng thái ban đầu Φ(H) = 0.
Ở ví dụ trên : Φ(H) = 5 + 2 3 = 11.
1.2.3. Các thao tác trên Fibonacci heap
Ý tưởng chính trong các thao tác trên Fibonacci heap đó là trì hoãn các
công việc chưa cần thiết nếu có thể, chờ đến lúc buộc phải thực hiện thì thực
hiện cùng một lúc nhiều công việc, điều đó giúp giảm bớt các phép tính toán.
Nếu số lượng các cây trong một Fibonacci heap không lớn, ta có thể nhanh
chóng xác định nút cực tiểu mới bằng thủ tục EXTRACT_ MIN. Ta sẽ không
gắng thống nhất các cây trong Fibonacci heap khi chèn một nút mới hoặc hợp
nhất hai đống. Việc thống nhất các cây trong đống chỉ phải làm khi gặp thủ
tục EXTRACT_MIN, là thủ tục tìm nút cực tiểu và xóa nó khỏi đống.
(1) Tạo một Fibonacci heap mới
Để tạo một Fibonacci heap rỗng ta dùng thủ tục FIB_HEAP_ MAKE,
thủ tục này phân bổ và trả về đối tượng Fibonacci heap, trong đó n[H] = 0,
min[H] = NIL, ngay sau lời gọi thủ tục này thì chưa có cây nào trong H.
Vì thế t(H) = 0, m(H) = 0, nên Φ(H) = 0. Như vậy, mức hao phí khấu
trừ (độ phức tạp tính toán) của FIB_HEAP_MAKE bằng với mức hao phí thực
tế O(1) của nó.
(2) Chèn một nút mới
Thủ tục dưới đây chèn nút x với khóa là key[x] vào Fibonacci heap H
được quản lý bởi biến con trỏ min[H]:
7
Procedure FIB_HEAP_INSERT (var x, min[H] : tro); [1]
// tro là một kiểu con trỏ, trỏ vào các node: tro = ^node;
begin
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. ghép nối danh sách gốc chứa x với danh sách gốc H;
8. if min[H] = NIL hoặc x^.key < minH^.key
9. then minH := x;
10. n[H] = n[H]+1;
end;
Các lệnh từ dòng 1- 6, khởi tạo cấu trúc của nút x, khiến nó trở thành
danh sách nối đôi theo vòng tròn, dòng 7 bổ sung nút x vào danh sách gốc của
H. Như vậy nút x trở thành một cây nút đơn được sắp xếp theo đống trong
Fibonacci heap. Nó không có cây con và không được đánh dấu. Các dòng 8 9 cập nhật min[H]. Dòng 10 tăng số lượng nút trong H.
Có thể nhận ra rằng FIB_HEAP_INSERT(c,min[H]) sẽ không gắng
thống nhất các cây trong đống. Nếu k phép toán FIB_HEAP_INSERT thực
hiện thì sẽ có k cây mới được bổ sung vào danh sách gốc.
Hình 1.3: Minh họa chèn thêm nút có key 21 vào Fibonacci heap
8
Để xác định mức hao phí khấu trừ của FIB_HEAP_INSERT, gọi H là
Fibonacci heap ban đầu và H’ là Fibonacci heap kết quả, thì t(H’) = t(H)+1,
m(H’) = m(H), sự gia tăng trong hàm tiềm năng là : Φ(H’) - Φ(H) = 1 Bởi
mức hao phí thực tế là O(1), nên mức hao phí khấu trừ là O(1) + 1 = O(1).
Mã nguồn thao tác FIB_HEAP_INSERT:
procedure FIB_HEAP_INSERT(var x, minH: tro); [1]
begin
degree[x] := 0;
p[x] := NIL;
child[x] := NIL;
left[x] := x;
right[x] := x;
mark[x] := false;
if minH <> nil // bắt đầu ghép nối danh sách gốc chứa x với danh sách gốc H;
then
begin
x^.left := minH.left;
minH^.left^.right := x;
x^.right := minH;
minH^.left := x;
if minH^.key > x^.key
then minH := x;
end
else minH := x; // kết thúc ghép nối danh sách gốc chứa x với danh sách gốc H;
n[H] = n[H]+1;
end;
Ở đây nút mới x đã được chèn vào bên trái minH, thực tế trong lập trình
ta có thể chèn x vào bên phải minH thì kết quả vẫn giống nhau.
(3) Tìm nút cực tiểu
Nút cực tiểu của Fibonacci heap được trỏ bởi min[H], do đó ta có thể
tìm nút cực tiểu với độ phức tạp tính toán thực tế (hao phí thực tế) là O(1). Do
9
tiềm năng của H không thay đổi, nên mức hao phí khấu trừ của phép toán này
bằng với mức hao phí thực tế của nó là O(1).
(4) Hợp nhất hai Fibonacci heap [2]
Thủ tục dưới đây hợp nhất 2 Fibonacci heap H1 và H2 thành H, đồng
thời hủy H1, H2.
procedure FIB_HEAP_UNION(var min[H1], min[H2], minH : tro);
begin
1. n[H] := 0;
2. min[H] := min[H1];
3. ghép nối danh sách gốc của H2 với danh sách gốc của H;
4. if (min[H1] = NIL) hoặc (min[H2]^.key < min[H1]^.key) then
5. min[H] := min[H2];
6. n[H] := n[H1] + n[H2];
7. giải phóng các đối tượng H1 và H2;
end;
Các dòng 1-3 ghép nối các danh sách gốc của H1 và H2 thành một danh
sách gốc mới H. Các dòng 2, 4, 5 ấn định nút cực tiểu của H, dòng 6 cập nhật
lại số nút của H. Ta có thể thấy trong thủ tục FIB-HEAP-UNION(H1, H2)
không cần thực hiện thống nhất cây.
Sự thay đổi tiềm năng : Φ(H) – (Φ(H1) + Φ(H2)) = 0. Do đó mức hao
phí khấu trừ của FIB_HEAP_UNION bằng với mức hao phí thực tế O(1).
(5) Trích nút cực tiểu[1]
Đây là thủ tục phức tạp nhất của Fibonacci heap. Thủ tục này thực hiện
xóa nút cực tiểu ra khỏi H, đồng thời thực hiện việc thống nhất các cây đã bị
trì hoãn ở các phép toán khác.
10
Đoạn mã giả dưới đây thực hiện trích nút cực tiểu, có sử dụng thủ tục
CONSOLIDATE(H) để thống nhất cây.
procedure FIBO_HEAP_EXTRACT_MIN;
// input: Đống được đại diện bởi biến toàn cục min[H].
// output: Nút có key nhỏ nhất.
begin
1. z := min[H] ;
2. if z <> NIL then
3. for x thuộc con của z do
4.
begin cộng x vào danh sách gốc của H
5.
x.parent := NIL;
6.
end;
7. Gỡ bỏ z ra khỏi danh sách gốc của H;
8. if z = z^.right
9. then min[H] := NIL
10. else min[H] := z^.right;
11. Consolidate(H);
12. n[H] := n[H]-1
end;
FIB_HEAP_EXTRACT_MIN làm việc bằng cách: Trước tiên biến các
nút con của nút cực tiểu thành các gốc, gỡ bỏ nút cực tiểu ra khỏi danh sách
gốc. Sau đó thống nhất danh sách gốc bằng cách kết nối các gốc có số con
bằng nhau cho đến khi số con của các nút trong danh sách gốc là khác nhau.
Dòng 1 dùng biến trỏ z, cho z trỏ vào nút cực tiểu, biến trỏ này được trả
lại ở cuối. Nếu z=NIL, thì Fibonacci heap đã rỗng và ta đã hoàn tất công việc.
Ngược lại, ta xóa nút z ra khỏi H bằng cách khiến tất các con của z thành các
gốc của H, trong các dòng 4 - 9. Nếu z= right[z] hay danh sách chỉ có một nút
duy nhất, thì ta chỉ việc biến H thành rỗng, ngược lại, tạm thời cho biến trỏ
gốc min[H] vào một nút bất kì trong danh sách gốc, ở đây là right[z], sau đó
rút gọn các cây trong Fibonacci heap gọi là thống nhất Fibonacci heap. Điều
này được thực hiện bằng thủ tục CONSOLIDATE.
Nguyên tắc làm việc của thủ tục CONSOLIDATE:
(1) Tìm hai gốc x, y có cùng số nút con trong danh sách con, và key[x]
≤ key[y].
11
(2) Gỡ bỏ y ra khỏi danh sách gốc, cho y làm con của x. Việc này sẽ
được thực hiện bởi thủ tục FIB_HEAP_LINK.
Thủ tục CONSOLIDATE sử dụng thêm một mảng phụ A[0..D(H)], với
D(H) = log2N [1], với ý nghĩa A[i] = y thì y là một gốc có degree[y]=I
(MIHAEL L. FREDMAN, ROBERT ENDRE TARJAN đã chứng minh được là
degree[y] <= D(H)).
procedure COSONLIDATE(var minH : tro);
begin
1. For i = 0 to D(H) do A[i] := NIL;
2. For mỗi nút w trong danh sách gốc của H do
3. Begin
4.
x := w;
5.
d := x^.degree;
6.
While A[d] <> NIL do
7.
Begin
8.
Y:= A[d];
9.
if x^.key > y^. key then tráo đổi x ↔ y;
10.
FIB_HEAP_LINK(H,y,x);
11.
A[d] := NIL;
12.
d := d+1;
13.
End;
14.
A[d] :=x;
15. End;
16. Min[H] := NIL;
17. For i := 0 to D(H) do
18.
If (A[i] <> NIL) then
19.
Begin
20.
Cộng A[i] vào danh sách gốc của H;
21.
If (min[H]=NIL) hoặc ([A[i]]^.key < min[H]^.key)
22.
then Min[H] := A[i];
23.
end;
end;
procedure FIBO_HEAP_LINK(var minH,y,x : tro); [1]
begin
1. Xóa nút y ra khỏi danh sách ban đầu của nó;
2. y^.parent := x;
3. Nối y vào danh sách con của x;
4. x^.degree := x^.degree + 1;
end;
12
Dòng đầu tiên khởi tạo mảng A[i] = NIL, tức là chưa có cây nào có số
con bằng i. Xét một cây con có gốc w trong danh sách gốc, gọi d là số con của
w. Nếu A[d]=NIL thì ta gán A[d]= w. Ngược lại, dòng 6-13: ta chọn cây có
gốc nhỏ hơn trong hai cây w và A[d] làm gốc, và ghép cây còn lại vào danh
sách con của cây kia, kết quả trả về cây trỏ bởi x. Cây x sẽ là cây có số con là
d + 1, tiếp tục xét với cây trỏ bởi A[d+1] và x, nếu A[d+1]=NIL thì dừng lại.
Kết thúc quá trình này ta sẽ được một danh sách gốc mới, trong đó mỗi
gốc có số lượng nút con là khác nhau. Công việc còn lại chỉ là thực hiện cập
nhật nút minH được thực hiện trong các dòng từ 16 – 23.
Hình 1.4 dưới đây mô tả hoạt động của FIB_HEAP_EXTRACT_MIN,
quá trình biến đổi của Fibonacci heap được giải thích như sau:
(a) Một Fibonacci heap.
(b) Trạng thái Fibonacci heap khi gỡ bỏ nút cực tiểu z ra khỏi danh sách
gốc và bổ sung con của nó vào danh sách gốc.
(c) - (e) Mảng A và các cây trong 3 lần lặp đầu tiên của vòng lặp for
trong thủ tục CONSOLIDATE. Danh sách gốc ban đầu tại nút cực tiểu tạm
thời (sau khi bỏ nút cực tiểu mới), tiếp theo tại biến trỏ right.
(f) - (h) Tình huống đầu tiên khi đi qua vòng lặp while, nút cây có gốc
23 được nối vào cây gốc 7 tạo cây mới có degree =1, do đã tồn tại cây có
degree =1 (a[1]) nên tiếp tục ghép cây trỏ bởi a[1] có gốc là 17 vào cây gốc
7. Tương tự đến bước (h) cây có gốc 24 tiếp tục được nối vào cây gốc 7 tạo
cây có degree = 3, và được A[3] trỏ đến.
(i) - (l) Tình huống trong 4 lần lặp tiếp theo của vòng lặp for.
(m) Trạng thái Fibonacci heap sau khi kết thúc, với biến trỏ mới min[H].
13
14
Hình 1.4: Mô tả hoạt động của FIB_HEAP_EXTRACT_MIN
Mức hao phí của phép toán trích nút cực tiểu bao gồm: O(D(H)) của
phép toán duyệt các nút con của nút cực tiểu thực hiện bởi vòng for trong thủ
15
tục FIB_HEAP_EXTRACT_MIN, D(H) trong việc khởi tạo mảng A trong
thủ tục CONSOLIDATE, D(H) trong vòng for thực hiện cập nhật lại min[H]
(dòng 17 - 23 của thủ tục CONSOLIDATE), cuối cùng là vòng for dòng 2 - 15.
Để đánh giá mức hao phí của vòng for này ta xét: Kích cỡ của danh sách gốc
vào lúc gọi CONSOLIDATE tối đa là D(H) + t(H)-1, bởi nó bao gồm t(H) nút
trong danh sách gốc ban đầu, trừ cho nút gốc đã trích cộng với các con của
nút đã trích mà tối đa là D(H). Mỗi lần qua vòng lặp while của các dòng 6 - 12,
một gốc sẽ được nối với gốc khác, và như vậy tổng lượng công việc được
thực hiện trong vòng lặp for tối đa tỉ lệ với D(H) + t(H). Vậy tổng hao phí
thực tế là O(D(H) + t(H))[1].
Giá trị hàm tiềm năng trước khi trích nút cực tiểu là t(H) + 2m(H) và
giá trị hàm tiềm năng sau đó tối đa là (D(H) +1) + 2m(H), bởi số lượng nút
trong danh sách gốc sau khi trích nút tối đa là D(H) + 1 và số lượng nút đánh
dấu không thay đổi.
Mức hao phí khấu trừ: O(D(H) + t(H)) + ((D(H) + 1) + 2m(H)) -(t(H)
+ 2m(H)) = O(D(H)) = O(logn).
(6) Giảm một khóa và xóa một nút
Giảm khóa một nút
Mã giả dưới đây thực hiện phép toán giảm một khóa [1]
procedure FIB_HEAP_DECREASE_KEY(var minH, x: tro; k: longint);
begin
1. if k > x^.key then
2. writeln(‘Khóa mới lớn hơn khóa hiện hành’);
3. x^.key := k;
4. y := x^.parent;
5. if (y <> NIL) và (x^.key < y^.key) then
6.
begin
7.
CUT(minH,x,y)
8.
CASCADING_CUT(minH,y);
9.
end;
10. if x^.key < minH^.key then
11.
minH := x;
16
end;
procedure CUT(var minH,x,y : tro);
begin
1. Gỡ bỏ x ra khỏi danh sách con của y, giảm lượng degree[y] một đơn vị;
2. Cộng x và danh sách gốc của H;
3. p[x] := NIL;
4. x^.mark := FALSE;
end;
procedure CASCADING_CUT(var minH, y: tro);
begin
1. z := p[y];
2. if z <> NIL then
3.
if mark[y] = FALSE then
4.
mark[y] := TRUE
5. else
6.
begin CUT(minH, y, z)
7.
CASCADING_CUT(H, z)
8.
end;
end;
Thủ tục FIB_HEAP_DECREASE_KEY làm việc như sau: Các dòng 13 đảm bảo khóa mới không lớn hơn khóa hiện tại, và sau đó gán khóa mới
cho x. Nếu x là một gốc hoặc key[x] ≥ key[y] với y là cha của x thì không cần
thay đổi cấu trúc của Fibonacci heap - các dòng 4 - 5 kiểm tra điều kiện này.
Ngược lại, thứ tự đống bị vi phạm, ta cần phải tổ chức lại. Ta bắt đầu
bằng cách cắt nối kết giữa x và cha y của nó, biến x thành một gốc.
Ta dùng trường mark để được cận thời gian tốt hơn. Xét một nút x đã
từng bị chuyển thành con của nút khác. Ta đánh dấu mark[x] = true khi nó
mất con thứ nhất, khi x mất con thứ 2 ta bỏ đánh dấu nó đưa nó vào danh sách
gốc. Bởi khi gỡ một nút x và ghép vào danh sách gốc, thì có thể tác động đến
trường mark của các nút cha, ông, cụ.. của nó, cho nên ta sử dụng một thao
tác đệ quy cắt liên hoàn CASCADING_CUT để thực hiện kiểm tra đối với
các nút cha, ông…
Sau khi xảy ra xong tất cả tác vụ cắt liên hoàn, các dòng 8, 9 của
FIB_DECREASE_KEY hoàn tất bằng cách cập nhất lại nút minH.
17
Ta sẽ chứng tỏ mức hao phí khấu trừ của FIB_HEAP_DECREASE_KEY
chỉ là O(1).
Thủ tục FIB_HEAP_DECREASE_KEY có độ phức tạp là O(1) (các lệnh từ
1 - 4) cộng với việc thực hiện các tác vụ cắt liên hoàn. Giả sử thủ tục
CASCADING_CUT được gọi đệ qui c lần, mỗi lệnh CASCADING_CUT có độ
phức tạp là O(1). Như vậy mức hao phí thực tế của thủ tục FIB_HEAP_
DECREASE_KEY là O(c).
Tiếp theo ta sẽ tính sự thay đổi tiềm năng cho H là Fibonaci heap ngay
trước phép toán FIB_HEAP_DECREASE_KEY. Mỗi lệnh gọi đệ quy của
CASCADING_CUT, tăng tối đa c cây ở gốc, giảm tối đa c-2 nút đánh dấu, từ
đó suy ra sự thay đổi về tiềm năng là:
((t(H) + c) + 2(m(H) – c + 2)) - (t(H) + 2m(H)) = 4 - c
Như vậy chi phí khấu trừ của FIB_HEAP_DECREASE_KEY là :
O(c) + 4 - c = O(1).
Như vậy, ta có thể hiểu được tại sao hàm tiềm năng lại bao gồm 2 lần
số lượng nút đánh dấu: Khi một nút đánh dấu y được cắt bởi một tác vụ cắt
liên hoàn, nó được xóa đánh dấu, do đó tiềm năng được rút gọn đi 2 gồm: một
thanh toán cho thao tác cắt và xóa đánh dấu, hai là bù cho đơn vị gia tăng
trong tiềm năng do nút y trở thành gốc.
18
Hình 1.5. Mô tả thao tác FIB_HEAP_DECREASE_KEY
(a) Fibonacci heap ban đầu
(b) Nút có khóa 46 giảm xuống 15, trở thành một gốc, cha của nó 24
được đánh dấu.
(c)-(e) Nút có khóa 35 giảm xuống thành 5, các nút cha 26, 24 được cắt
liên hoàn. Cuối cùng cập nhật lại nút minH.
Xóa một nút
Ta có thể dễ dàng xóa một nút ra khỏi Fibonacci heap với độ phức tạp
là O(logn), như trong mã giả dưới đây. Mặc nhận rằng không có giá trị khóa
nào là -∞ trong Fibonacci heap.
- Xem thêm -
.DOC 
39 
650 
143 
