Luận văn Thạc sĩ Khoa học Máy tính: Thuật toán Dijkstra Fibonacci heap, thuật toán ACO tìm đường đi tối ưu và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:74

Thêm vào BST

Báo xấu

39
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn nghiên cứu thuật toán Dijkstra tìm đường đi tối ưu trên đồ thị, nghiên cứu về Fibonacci heap và ứng dụng cấu trúc dữ liệu này để cải tiến thuật toán Dijkstra. Nghiên cứu về thuật toán tối ưu đàn kiến, ứng dụng thuật toán này để giải quyết bài toán tìm đường đi tối ưu trên đồ thị. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học Máy tính: Thuật toán Dijkstra Fibonacci heap, thuật toán ACO tìm đường đi tối ưu và ứng dụng

i ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG NGHIÊM QUANG KHẢI THUẬT TOÁN DIJKSTRA FIBONACCI HEAP, THUẬT TOÁN ACO TÌM ĐƯỜNG ĐI TỐI ƯU VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
ii LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là kết quả nghiên cứu của riêng tôi. Các thông tin trích dẫn trong luận văn lấy từ các nguồn đã được công khai hoặc đã được sự đồng ý của tác giả. Các kết quả nêu trong luận văn là kết quả nghiên cứu riêng của tác giả luận văn, chưa có ai công bố trong các công trình khác. Thái Nguyên, ngày 10 tháng 4 năm 2015 Học viên Nghiêm Quang Khải Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
iii LỜI CẢM ƠN Được sự phân công của trường Đại Học Công Nghệ Thông Tin Và Truyền Thông - Đại Học Thái Nguyên và sự đồng ý của thầy giáo hướng dẫn PGS - TS Đoàn Văn Ban, tôi đã thực hiện đề tài “Thuật toán Dijkstra Fibonacci heap, thuật toán ACO tìm đường đi tối ưu và ứng dụng”. Để hoàn thành được đề tài này, tôi đã nhận được sự hướng dẫn tận tình chu đáo của thầy hướng dẫn PGS – TS Đoàn Văn Ban, qua đây cho phép tôi được bày tỏ lòng biết ơn chân thành tới Thầy và gia đình Thầy. Tôi cũng xin được tỏ lòng cảm ơn đối với các thầy các cô đã tận tình hướng dẫn, giảng dạy lớp cao học 12G trong suốt hai năm qua, cám ơn những tri thức các thầy cô đã truyền thụ, cảm ơn những tình cảm chân thành các thầy cô đã dành cho lớp. Xin chân thành cám ơn những ý kiến đóng góp quý báu của các thầy cô giáo và các bạn đồng nghiệp đối với đề tài này. Chắc chắn đề tài này sẽ không tránh khỏi những thiếu sót, rất mong nhận được các ý kiến đóng góp của các thầy cô, các bạn đồng nghiệp và các bạn độc giả, tôi xin chân thành cảm ơn. Thái Nguyên, ngày 10 tháng 4 năm 2015 Học viên Nghiêm Quang Khải Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
iv MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ........................................................................................................... iii MỞ ĐẦU .....................................................................................................................1 CHƯƠNG 1 ................................................................................................................4 CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI TỐI ƯU TRÊN ĐỒ THỊ ............................4 1.1. Các khái niệm cơ bản của lý thuyết đồ thị .......................................................4 1.1.1. Định nghĩa đồ thị ......................................................................................4 1.1.2. Các thuật ngữ cơ bản .................................................................................5 1.1.3. Đường đi, chu trình, đồ thị liên thông .......................................................6 1.1.4. Đồ thị có trọng số ......................................................................................7 1.2. Cây ....................................................................................................................8 1.3. Bài toán đường đi tối ưu trên đồ thị .................................................................8 1.4. Thuật toán Dijkstra.........................................................................................10 1.4.1. Phát biểu bài toán.....................................................................................10 1.4.2.Mô tả thuật toán ........................................................................................10 1.5. Thuật toán Dijkstra kết hợp với Fibonacci heap............................................11 1.5.1. Hàng đợi ưu tiên ......................................................................................11 1.5.2. Fibonacci heap .........................................................................................14 1.5.3. Sơ đồ thuật toán Dijkstra kết hợp với Fibonacci Heap ............................30 1.6. Kết luận chương .............................................................................................32 CHƯƠNG 2 ..............................................................................................................33 THUẬT TOÁN ĐÀN KIẾN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI TỐI ƯU ...........33 2.1. Từ kiến tự nhiên đến kiến nhân tạo ................................................................33 2.1.1. Kiến tự nhiên ...........................................................................................33 2.1.2. Kiến nhân tạo ...........................................................................................36 2.2. Thuật toán ACO tổng quát giải bài toán ngươi chào hàng ............................37 2.2.2. Thuật toán ACO tổng quát giải bài toán TSP ..........................................38 2.3. Các thuật toán ACO giải bài toán TSP ..........................................................39 2.3.1. Thuật toán AS ..........................................................................................40 2.3.2. Thuật toán ACS .......................................................................................42 2.3.3. Thuật toán Max-Min (MMAS) ................................................................44 2.4. Một số vấn đề trong việc áp dụng ACO tìm đường đi tối ưu .........................46 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
v 2.4.1. ACO kết hợp với tìm kiếm cục bộ ...........................................................46 2.4.2. Thông tin heuristic ...................................................................................47 2.4.3. Số lượng kiến ...........................................................................................47 2.4.4. Tham số bay hơi ......................................................................................48 2.4.5. Một số đề xuất cải tiến .............................................................................48 2.5. Kết luận chương .............................................................................................49 CHƯƠNG 3 ..............................................................................................................50 ỨNG DỤNG THUẬT TOÁN DIJKSTRA FIBONACCI HEAP, THUẬT TOÁN ACO GIẢI CÁC BÀI TOÁN TÌM ĐƯỜNG ĐI TRÊN MẠNG GIAO THÔNG....50 3.1. Ứng dụng Dijkstra Fibonacci heap ................................................................50 13.1.1. Phát biểu bài toán 1 ..................................................................................50 3.1.2. Mô hình hoá bài toán ...............................................................................50 3.1.3. Mô tả input, output ..................................................................................50 3.1.4. Một số kiểu dữ liệu và các biến trong chương trình ...............................51 3.1.5. Một số hàm và thủ tục trong chương trình ..............................................52 3.1.6.Sơ đồ thuật toán ........................................................................................55 3.1.7. Các kết quả thực nghiệm giải bài toán 1..................................................56 3.2. Ứng dụng Dijkstra Fibonacci heap, ACO giải bài toán TSP mở rộng ..........58 3.2.1. Phát biểu bài toán 2..................................................................................58 3.2.2. Mô hình hoá bài toán ...............................................................................58 3.2.3. Mô tả input, output ..................................................................................58 3.2.4. Thuật toán tổng quát giải bài toán 2 ........................................................59 3.2.5. Một số hàm và thủ tục trong chương trình ..............................................59 3.2.6. Sơ đồ tổng quát của thuật toán giải bài toán 2. ........................................62 3.2.7. Các kết quả thực nghiệm giải bài toán 2..................................................63 3.3. Kết luận chương .............................................................................................65 KẾT LUẬN ...............................................................................................................67 TÀI LIỆU THAM KHẢO .........................................................................................69 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
1 MỞ ĐẦU Thuật toán tìm đường đi tối ưu có nhiều ứng dụng trong thực tế, nếu xây dựng được các thuật toán tốt sẽ giúp tiết kiệm được rất nhiều tiền bạc, thời gian, công sức của con người. Một số bài toán thực tế điển hình cần phải sử dụng thuật toán tìm đường đi tối ưu như: - Tìm đường đi từ địa điểm A đến địa điểm B sao cho độ dài đường đi là tối ưu hoặc nhanh nhất hoặc giá cước là nhỏ nhất. - Tìm đường đi ngắn nhất xuất từ một điểm cho trước, đi qua một số địa điểm cố định cho trước rồi quay trở về điểm xuất phát. - Tương tự ta cũng có bài toán tìm đường đi cho gói tin được gửi từ nút A đến nút B trên mạng máy tính sao cho giá cước là nhỏ nhất hoặc nhanh nhất... - Tìm đường đi tối ưu cho robot, cho tên lửa hành trình, máy bay, phi thuyền v.v cũng là những bài toán đang được quan tâm. Đã có nhiều công trình nghiên cứu về lĩnh vực này và có nhiều thuật toán nổi tiếng đã được phát minh như: Thuật toán Bellman – Ford, thuật toán Dijkstra, thuật toán Floyd, thuật toán Johnson… Tuy nhiên việc nghiên cứu cải tiến nâng cao hiệu quả của các thuật toán tìm đường đi tối ưu luôn nhận được sự quan tâm của nhiều người, nhiều tổ chức, cơ quan. Vì lý do nói trên và được sự gợi ý của PGS – TS Đoàn Văn Ban, tác giả đã chọn đề tài này để nghiên cứu trong luận văn tốt nghiệp thạc sĩ của mình.  Phạm vi nghiên cứu của đề tài Các khái niệm cơ bản về đồ thị, các thuật toán tìm đường đi tối ưu trên đồ thị, cấu trúc dữ liệu Fibonacci heap, ứng dụng cấu trúc dữ liệu này vào việc cải tiến nâng cao hiệu quả của thuật toán tìm đường đi tối ưu trên đồ thị. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
2 Ứng dụng các thuật toán tìm đường đi tối ưu trên đồ thị đã nghiên cứu để giải quyết một số bài toán tìm đường đi tối ưu trong mạng giao thông.  Hướng nghiên cứu của đề tài - Nghiên cứu thuật toán Dijkstra tìm đường đi tối ưu trên đồ thị, nghiên cứu về Fibonacci heap và ứng dụng cấu trúc dữ liệu này để cải tiến thuật toán Dijkstra. - Nghiên cứu về thuật toán tối ưu đàn kiến, ứng dụng thuật toán này để giải quyết bài toán tìm đường đi tối ưu trên đồ thị. - Ứng dụng hai thuật toán trên giải quyết một số bài toán tìm đường đi tối ưu trên mạng giao thông.  Đề tài gồm có 3 chương: Chương 1: Trình bày một số khái niệm cơ bản về đồ thị, một số dạng bài toán tìm đường đi tối ưu trên đồ thị, phần chủ yếu của chương này là trình bày về Fibonacci heap và dùng cấu trúc dữ liệu này để cải tiến nâng cao hiệu quả thuật toán Dijkstra. Chương 2: Trình bày về thuật toán tối ưu đàn kiến và thuật toán ACO giải bài toán tìm đường đi tối ưu. Thuật toán đàn kiến là một thuật toán tương đối mới và khả năng ứng dụng thực tế cao. Chương 3: Ứng dụng thuật toán Dijkstra đã cải tiến và thuật toán đàn kiến vào việc giải một số bài toán tìm đường đi tối ưu trên mạng giao thông.  Ý nghĩa khoa học của đề tài: - Thuật toán Dijkstra Fibonacci heap là thuật toán mạnh, nó 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 thuật toán này chưa phổ biến ở Việt Nam, vì thế đề tài này có thể sẽ có ích cho những người quan tâm đến lĩnh vực này. Đề tài cũng có Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
3 thể giúp cho các em học sinh Chuyên Tin 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. - Thuật toán ACO là thuật toán gần đúng, tuy nhiên nó rất hiệu quả trong việc giải quyết các bài toán thực tiễn . Đề tài đã ứng dụng thành công hai thuật toán nói trên vào việc giải quyết một số bài toán mà thực tiễn đang đặt ra. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
4 CHƯƠNG 1 CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI TỐI ƯU TRÊN ĐỒ THỊ 1.1. Các khái niệm cơ bản của lý thuyết đồ thị 1.1.1. Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Định nghĩa 1.1. Đơn đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh [3]. Định nghĩa 1.2. Đa đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh [3]. Định nghĩa 1.3. Đơn đồ thị có hướng G = (V,E) bao gồm V là tập các đỉnh, và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung [3]. Định nghĩa 1.4. Đa đồ thị có hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1 và e2 được gọi là cung lặp nếu chúng cùng tương ứng với một cặp đỉnh [3]. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
5 2 c 3 a 1 d 4 b 6 e 5 a) b) Hình 1.1. Hai loại đồ thị cơ bản: a) Đồ thị vô hướng (6 đỉnh, 9 cạnh). b) Đồ thị có hướng (5 đỉnh, 7 cung). 1.1.2. Các thuật ngữ cơ bản Định nghĩa 1.5. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G. Nếu e = (u,v) là cạnh của đồ thị thì chúng ta nói cạnh này là liên thuộc với hai đỉnh u và v, hoặc cũng nói là cạnh e là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u,v) [3]. Để có thể biết được bao nhiêu cạnh liên thuộc với một đỉnh, chúng ta đưa vào định nghĩa sau: Định nghĩa 1.6. Gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ kí hiệu là deg(v). Định lý 1.1. Giả sử G = (V, E) là đồ thị vô hướng với m cạnh. Khi đó 2m   deg(v) [3]. vV Hệ quả 1.1. Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn [3]. Định nghĩa 1.7. Nếu e = (u,v) là cung của đồ thị có hướng G thì chúng ta nói hai đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u và đỉnh v hoặc Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
6 cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u(v) sẽ được gọi là đỉnh đầu (cuối) của cung (u,v) [3]. Định nghĩa 1.8. Chúng ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là: deg+(v) (deg-(v)) [3]. Định lý 1.2. Giả sử G= (V, A) là đồ thị có hướng. Khi đó  deg vV  (v)   (deg  (v))  A [3]. vV 1.1.3. Đường đi, chu trình, đồ thị liên thông Định nghĩa 1.9. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x0, x1,.., xn-1, xn trong đó u = x0 , v = xn, (xi, xi+1)  E, i = 0, 1, 2,…, n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), .. , (xn-1, xn). Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại [3]. Định nghĩa 1.10. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị có hướng G = (V, A) là dãy x0, x1,.., xn-1, xn trong đó u = x0, v = xn , (xi , xi+1)  A, i = 0, 1, 2 , .. , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung: (x0, x1), (x1, x2), .., (xn-1, xn). Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cung nào bị lặp lại [3]. Định nghĩa 1.11. Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kì của nó. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
7 Định nghĩa 1.12. Chúng ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó W  V và F  E. Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy chúng ta sẽ gọi là các thành phần liên thông của đồ thị [3] . 1.1.4. Đồ thị có trọng số Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị được sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin với nhau được hay không. Khi đó, đồ thị được sử dụng để biễu diễn mạng truyền thông với các đỉnh là các nút mạng, các cạnh, các cung là các đường truyền dữ liệu giữa các nút mạng. Đồ thị có thể dùng để biễu diễn các đường đi trong một vùng: Các đỉnh tương ứng với các ngã 3, ngã 4, còn các cạnh, các cung tương ứng là các đường đi 2 chiều và đường đi 1 chiều. Để cấu trúc đồ thị có thể biễu diễn được các bài toán thực tế người ta đưa vào khái niệm đồ thị có trọng số, trên mỗi cạnh hay mỗi cung được gán một trọng số thể hiện chi phí cho việc thực hiện một mục đích nào đó trên cạnh hay trên cung đó. Định nghĩa 1.13. Đồ thị có trọng số là bộ 3 G = (V, E, w), trong đó w là hàm trọng số: w:E -> R, R: tập số thực, ngoài ra còn có thể kí hiệu w bằng c hoặc weight, cost. Cho S là một tập con của E  A, khi đó chúng ta kí hiệu w(S) = ∑w(s)| s  S là giá trị trọng số của tập S. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
8 1.2. Cây Định nghĩa 1.14: Ta gọi cây là một đồ thị vô hướng liên thông không có chu trình. Đồ thị không có chu trình gọi là rừng. Ví dụ: Trong hình 3 là một rừng gồm 3 cây T1, T2, T3. T1 T2 T3 Hình 1.2. Rừng gồm 3 cây T1, T2, T3 Có thể nói rằng cây là một cấu trúc đồ thị vô hướng đơn giản nhất. Định lý 1.3 sau đây nêu lên một số tính chất của cây. Định lý 1.3: Giả sử G = (V, E) là đồ thị vô hướng n đỉnh, khi đó các mệnh đề sau đây là tương đương: (1) G là cây. (2) G không chứa chu trình và có n-1 cạnh. (3) G liên thông và có n-1 cạnh. (4) G liên thông và mỗi cạnh của nó đều là cầu. (5) Hai đỉnh bất kỳ của G được nối với nhau bởi đúng một đường đi đơn. (6) G không chứa chu trình nhưng nếu cứ thêm vào nó một cạnh ta thu được đúng một chu trình [3]. 1.3. Bài toán đường đi tối ưu trên đồ thị Như đã nói ở phần mở đầu, bài toán tìm đường đi tối ưu trên đồ thị có một ý nghĩa thực tế vô cùng to lớn. Trong chương một này chỉ tập trung Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
9 nghiên cứu đường đi tối ưu trên đồ thị có hướng G = (V, E), |V|=n, |E|= m với mỗi cung được gán một trọng số, nghĩa là mỗi cung (u,v) E được đặt tương ứng với một số thực a(u,v) gọi là trọng số của nó. Trong ứng dụng cụ thể cho từng bài toán thì trọng số của một cung có thể là độ dài cung (u,v), có thể là chi phí đi từ u đến v cũng có thể là thời gian đi từ u đến v... Nếu (u, v) E ta sẽ đặt a(u, v) = . Nếu dãy v0, v1 , .. , vp là một đường đi trên G thì độ dài của p nó được định nghĩa là  a(v i 1 i 1 ,vi ) , nghĩa là độ dài của một đường đi chính là tổng các trọng số của các cung trên đường đi đó. Với đồ thị vô hướng ta hoàn toàn có thể chuyển thành đồ thị có hướng bằng cách thay mỗi cạnh (u, v) bằng hai cung (u, v) và cung (v, u) có cùng trọng số là trọng số của cạnh (u, v). Bài toán tìm đường đi tối ưu trên đồ thị có thể phát biểu dạng tổng quát như sau: Tìm đường đi có độ dài nhỏ nhất xuất phát từ đỉnh s  V (s là đỉnh xuất phát) đến đỉnh t  V (t là đỉnh đích). Đường đi như vậy ta gọi là đường đi tối ưu từ đỉnh s đến đỉnh t, độ dài của đường đi này ta gọi là khoảng cách từ s đến t và ký hiệu là d(s, t). Nếu không tồn tại đường đi từ s đến t ta đặt d(s, t) = . Trong một số trường hợp đường đi tối ưu từ s đến t còn bị ràng buộc thêm một số điều kiện khác nữa, ví dụ phải đi qua một số đỉnh cố định cho trước hoặc phải quay lại đỉnh xuất phát ... Dễ thấy rằng nếu trong G không tồn tại chu trình có độ dài âm (gọi tắt là chu trình âm) thì đường đi tối ưu từ s đến t không có đỉnh nào bị lặp lại. Đường đi không có đỉnh lặp lại gọi là đường đi cơ bản hoặc đường đi đơn. Trong trường hợp trong G có chu trình âm thì khoảng cách giữa hai điểm s và t có thể không xác định, bởi vì bằng cách đi vòng theo chu trình âm một số lần đủ lớn nào đó thì d(s,t) có thể nhỏ hơn bất kỳ một số thực nào đó cho trước [3]. Khi đó ta có thể đặ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.ltc.tnu.edu.vn
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. 1.4. Thuật toán Dijkstra 1.4.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. 1.4.2.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. Ban đầu d[s]:=0, d[v≠s] := ∞, ban đầu các đỉnh được coi là chưa cố định (mỗi đỉnh có một trong 2 trạng thái là tự do hoặc cố định, tự do nghĩa là d[v] còn có thể tối ưu hơn nữa, cố định tức là d[v] đã bằng độ dài đường đi tối ưu từ s đến t, không tối ưu được nữa). 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.ltc.tnu.edu.vn
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. 1.5. 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. 1.5.1. Hàng đợi ưu tiên 1.5.1.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.ltc.tnu.edu.vn
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, .., n). 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.ltc.tnu.edu.vn
13 đợi ưu tiên, và loại bỏ nó khỏi hàng đợi ưu tiên. + Update(i, new(p)): Cập nhật độ ưu tiên của phần tử i thành new(p). 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). 1.5.1.2. 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.ltc.tnu.edu.vn
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. 1.5.2. Fibonacci heap 1.5.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 [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.ltc.tnu.edu.vn
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]. Hình1.3: Fibonacci heap gồm 5 cây sắp xếp theo đống với 14 nút [4] 1.5.2.2. 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.ltc.tnu.edu.vn