đặt vấn đề tìm đường đi cơ bản tối ưu, tuy nhiên Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 bài toán sẽ rất phức tạp, vì vậy trong luận văn này chúng ta sẽ giả thiết trong G các cung đều có trọng số không âm. Trường hợp trong đồ thị G trọng số các cung không âm, có nhiều thuật toán tìm đường đi tối ưu nổi tiếng như thuật toán For_Bellman, thuật toán Dijkstra, thuật toán Floyd. Trong phần còn lại của chương này của luận văn chúng ta sẽ nghiên cứu về thuật toán Dijkstra và sử dụng Fibonacci heap để cải tiến thuật toán Dijkstra. Thuật toán Dijkstra 1.
Phát biểu bài toán “Cho đồ thị có hướng có trọng số G = (V, E), hãy tìm một đường đi tối ưu xuất phát từ đỉnh s thuộc V, đến một đỉnh t cũng thuộc V.” Bài toán có thể được tìm thấy rất nhiều trong thực tế, chẳng hạn trong mạng lưới giao thông đường bộ, đường thủy, đường không, trong truyền tải dữ liệu của một mạng máy tính.Mô tả thuật toán Trong trường hợp trọng số trên cung không âm, bài toán trên có thể giải quyết hiệu quả bằng thuật toán Dijkstra mô tả như sau [3] : Bước 1: Khởi tạo Mỗi đỉnh v thuộc V, gọi d[v] là khoảng cách từ s đến v. Bước 2: Lặp cho đến khi t trở thành đỉnh cố định Bước lặp bao gồm 2 thao tác : Thao tác 1: Cố định nhãn Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Chọn đỉnh u tự do có nhãn d[u] nhỏ nhất và cố định nhãn cho nó. Thao tác 2: Sửa nhãn Đối với mỗi đỉnh v tự do, kề với u. Nếu d[v] > d[u]+c[u,v] thì ta sẽ sửa nhãn cho v: d[v] := d[u]+c[u,v] và lưu u là đỉnh kề trước v trên đường đi tối ưu (c[u,v] là trọng số của cung (u, v)) Bước 3: Xuất kết quả Trả lại d[t] là độ dài đường đi tối ưu, kết hợp truy vết để tìm đường đi.
Mô hình : Repeat u := FindMin(); if u = t then exit ; Đánh dấu u đã cố định; Repair(u); // tiến hành sửa nhãn cho các đỉnh kề u Until False; [3] Độ phức tạp của FindMin() là O(n), của Repair(u) là O(n). Số lần lặp của bước 2 sẽ là số cung trong đường đi tối ưu, tức là khoảng O(n). Thuật toán Dijkstra cài đặt như trên sẽ có độ phức tạp O(n2), kết quả này là không khả thi cho đồ thị có số đỉnh n lớn. Thuật toán Dijkstra kết hợp với Fibonacci heap Do độ phức tạp của thuật toán Dijkstra là O(n2) nên khi số đỉnh của đồ thị lớn, chương trình chạy rất chậm, trong phần 1.5 này chúng ta sẽ sử dụng Fibonacci heap để cải tiến thuật toán này.
Hàng đợi ưu tiên 1. Khái niệm hàng đợi, hàng đợi ưu tiên Hàng đợi (queue): Là một kiểu danh sách mà việc bổ sung một phần tử được thực hiện ở cuối danh sách còn việc loại bỏ một phần tử được thực hiện ở đầu danh sách. Có thể hình dung hàng đợi như một hàng người xếp hàng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 mua vé: Người xếp hàng trước sẽ được mua vé trước, người đứng đầu tiên mua vé xong đi ra thì người thứ hai tiến lên thay vị trí người đứng đầu, còn người mới đến sẽ đứng vào cuối hàng. Vì nguyên tắc vào trước ra trước nên hàng đợi còn được gọi là danh sách kiểu FIFO (First in first out).
Có 6 thao tác cơ bản đối với hàng đợi [2]: Init: Tạo một ngăn xếp rỗng. isEmpty: Cho biết hàng đợi có rỗng hay không. isFull: Cho biết hàng đợi có đầy không. Get: Đọc giá trị của phần tử ở đầu hàng đợi.
Push: Đẩy (bổ sung) một phần tử vào hàng đợi. Pop: Lấy một phần tử ra khỏi hàng đợi. Ta có thể biểu diễn hàng đợi bằng mảng hoặc dang sách móc nối [2]. Hàng đợi ưu tiên: Hàng đợi có độ ưu tiên, gọi tắt là hàng đợi ưu tiên (priority queue) là một cấu trúc dữ liệu quan trọng dùng trong việc cài đặt nhiều thuật toán.
Hàng đợi ưu tiên là một kiểu danh sách chứa các phần tử của một tập hữu hạn S nào đó, mỗi phần tử của S được gán cho một mức độ ưu tiên nào đó. Ta đánh số các phần tử của S lần lượt từ 1 đến n và đồng nhất mỗi phần tử với chỉ số của nó, khi đó độ ưu tiên của phần tử i là một số thực p[i] ( i = 1, 2,. Với một hàng đợi ưu tiên có các thao tác chính sau đây [2]: + Insert(i): Đẩy phần tử i vào hàng đợi ưu tiên nếu nó chưa có trong hàng đợi. + Find min(Find max): Trả về phần tử có độ ưu tiên nhỏ nhất (lớn nhất) trong hàng đợi ưu tiên.
+ Extract: Trả về phần tử có độ ưu tiên nhỏ nhất (lớn nhất) trong hàng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 đợi ưu tiên, và loại bỏ nó khỏi hàng đợi ưu tiên. Hàng đợi ưu tiên là một biến thể của hàng đợi, nó khác ở chỗ là hàng đợi thông thường hoạt động theo kiểu vào trước ra trước còn trong hàng đợi ưu tiên thủ tục Extract luôn lấy ra phần tử có độ ưu tiên nhỏ nhất (lớn nhất). 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 : Hợp nhất hai heap h1, h2 thành heap mới, đồng thời xóa h1, Union(h1,h2) 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 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 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 [6]: Heaps Linked Thao tác Binary Bionimal Fibonacci Relax 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) Decrease(∆,x,h) O(1) O(logN) O(logN) O(1) O(1) Delete(x,h) O(N) O(logN) O(logN) O(logN) O(logN) Trong phần tiếp theo chúng ta sẽ nghiên cứu kỹ về Fibonacci heap.
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 [6]: 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ố. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 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. 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ự[6].3: Fibonacci heap gồm 5 cây sắp xếp theo đống với 14 nút [4] 1. Cấu trúc Fibonacci heap Hình 1.4 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 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 16 đ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. 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.