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

Thái Nguyên, ngày 10 tháng 4 năm 2015

trình khác.

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

Thái Nguyên, ngày 10 tháng 4 năm 2015

bạn độc giả, tôi xin chân thành cảm ơn.

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

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ị.

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

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ó

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

đặt ra.

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

với một cặp đỉnh [3].

5

a) Đồ thị vô hướng (6 đỉnh, 9 cạnh). b) Đồ thị có hướng (5 đỉnh, 7 cung).

Hình 1.1. Hai loại đồ thị cơ bản:

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 đó

[3].

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

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

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 đó

[3].

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

nếu luôn tìm được đường đi giữa hai đỉnh bất kì của nó.

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ố hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

s S là giá trị trọng số của tập S.

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ó

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

một ý nghĩa thực tế vô cùng to lớn. Trong chương một này chỉ tập trung

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

nó được định nghĩa là , 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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

trước [3]. Khi đó ta có thể đặt vấn đề tìm đường đi cơ bản tối ưu, tuy nhiên

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 :

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Thao tác 1: Cố định nhãn

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.

u := FindMin();

Đánh dấu u đã cố định; Repair(u); // tiến hành sửa nhãn cho các đỉnh kề u

Mô hình :

Repeat if u = t then exit ; 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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

ở đầu danh sách. Có thể hình dung hàng đợi như một hàng người xếp hàng

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.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

+ Extract: Trả về phần tử có độ ưu tiên nhỏ nhất (lớn nhất) trong hàng

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Delete(xh) Xóa phần tử X ra khỏi heap

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.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

O(n2logn + nm): Cho bài toán so khớp hai nhánh có trọng số .

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 ý.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Việc thể hiện danh sách con bằng danh sách nối đôi vòng tròn có 2 ưu

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.

Hình 1.4. Mô phỏng cấu trúc Fibonacci heap [4]

key : integer; degree : integer; parent : ^node; child : ^node; left : ^node; right : ^node ; mark : boolean;

node = record end;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Cấu trúc dữ liệu miêu tả một nút trong Fibonacci heap[4]:

17

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 đó [4]. Đối với Fibonacci heap, ta sử dụng hàm tiềm năng Φ(H) = t(H) + 2m(H), 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.5.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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

được quản lý bởi biến con trỏ min[H]:

18

Procedure FIB_HEAP_INSERT (var x, min[H] : tro); [4]

// 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.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Hình 1.5: Minh họa chèn thêm nút có key 21 vào Fibonacci heap[4]

19

Để 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).

procedure FIB_HEAP_INSERT(var x, minH: tro); [4]

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;

Mã nguồn thao tác FIB_HEAP_INSERT:

Ở đâ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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

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

20

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 [6]

Thủ tục dưới đây hợp nhất 2 Fibonacci heap H1 và H2 thành H, đồng

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;

thời hủy H1, H2.

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[4]

Đâ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ị

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

trì hoãn ở các phép toán khác.

21

Đ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

procedure FIBO_HEAP_EXTRACT_MIN; [4]

// 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;

CONSOLIDATE(H) để thống nhất cây.

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.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

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

22

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].

(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

procedure COSONLIDATE(var minH : tro); [4]

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

D(H) = log2N [4], với ý nghĩa A[i] = y thì y là một gốc có degree[y]=i.

23

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); [4] 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;

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 16 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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

gốc và bổ sung con của nó vào danh sách gốc.

24

(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.

(m) Trạng thái Fibonacci heap sau khi kết thúc, với biến trỏ mới min[H].

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

(i) - (l) Tình huống trong 4 lần lặp tiếp theo của vòng lặp for.

25

Hình 1.6. Mô tả hoạt động của FIB_HEAP_EXTRACT_MIN [4]

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

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ủ

26

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))[4].

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.

+ 2m(H)) = O(D(H)) = O(logn).

Mức hao phí khấu trừ: O(D(H) + t(H)) + ((D(H) + 1) + 2m(H)) -(t(H)

(6) Giảm một khóa và xóa một nút

Giảm khóa một nút

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Mã giả dưới đây thực hiện phép toán giảm một khóa [4]

27

6. begin

7. CUT(minH,x,y)

8. CASCADING_CUT(minH,y);

9. end;

10. if x^.key < minH^.key then

11. minH := x;

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;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

28

Thủ tục FIB_HEAP_DECREASE_KEY làm việc như sau: Các dòng 1-

3 đả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.

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ừ

CASCADING_CUT được gọi đệ qui c lần, mỗi lệnh CASCADING_CUT có độ

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

DECREASE_KEY là O(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_

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à:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

((t(H) + c) + 2(m(H) – c + 2)) - (t(H) + 2m(H)) = 4 - c

29

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.

Hình 1.7. Mô tả thao tác FIB_HEAP_DECREASE_KEY [4]

(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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

liên hoàn. Cuối cùng cập nhật lại nút minH.

30

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

procedure FIB_HEAP_DELETE(var minH, x : tro); [4]

begin

1. FIB_HEAP_DECREASE_KEY(minH, x, - ∞);

2. FIB_HEAP_EXTRACT_MIN(minH);

end;

nào là -∞ trong Fibonacci heap.

FIB_HEAP_DELETE(H, x) biến nút x thành nút cực tiểu bằng cách

gán cho nó khóa - ∞ thông qua thủ tục FIB_HEAP_DECREASE_KEY, sau đó

loại nó ra khỏi Fibonacci heap bằng thủ tục FIB_HEAP_EXTRACT_MIN.

Chi phí khấu trừ của FIB_HEAP_DELETE là tổng chi phí khấu trừ O(1)

của FIB_HEAP_DECREASE_KEY và O(logn) của FIB_HEAP_EXTRACT_MIN.

1.5.3. Sơ đồ thuật toán Dijkstra kết hợp với Fibonacci Heap

Ở mục 1.4.2 chúng ta đã đưa ra sơ đồ thuật toán Dijkstra nguyên thủy

procedure dijkstra;

// input: Đồ thị G, các biến toàn cục s, t;

// ouput: Khoảng cách từ s đến t;

begin

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;

end;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

với độ phức tạp O(n2) đó là:

31

Bây giờ chúng ta sẽ tổ chức mảng nhãn d theo cấu trúc Fibonacci heap,

procedure dijkstra_fibo_heap;

// input: Đồ thị G, đống H. S, t là các biến toàn cục.

// output: Khoảng cách từ s đến t.

begin

Repeat

P := FIB_HEAP_EXTRACT_MIN(H);

u := p^. u; // u là một trường mới của các nút trong Fibonacci heap để lưu nhãn

//của đinh (tên đỉnh) mà nút đại diện.

if u = t then exit;

Đánh dấu u đã cố định ;

for (v thuộc ke(u)) do

if (d[v] > d[u] + c[u,v] ) then

begin

d[v] := d[u] + c[u,v];

FIB_HEAP_DECREASE_KEY(H, ptr[v], d[v]) ;// ptr[v] là nút trong

//H có nhãn là v.

end;

Until false;

end;

khi đó mô hình thuật toán Dijkstra có thể viết lại như sau:

EXTRACT_MIN(H) trích nút cực tiểu có độ phức tạp là O(logn), vì thế tính

Vòng lặp Repeat thực hiện lặp tối đa là n lần, thao tác FIB_HEAP_

trong toàn bộ vòng repeat thì tổng số thao tác này có độ phức tạp là O(nlogn).

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Thao tác FIB_HEAP_DECREASE_KEY(H, ptr[ v], d[v]) có độ phức

32

tạp là O(1), số lần lặp trong một vòng for chỉ bằng số lượng đỉnh kề u, vì vậy

nếu chúng ta sử dụng danh sách liên kết để tổ chức các cạnh thì độ phức tạp

của tất cả các vòng lặp for trong vòng lặp repeat sẽ là O(m).

Từ hai nhận xét trên suy ra thuật toán Dijkstra Fibonacci heap có độ

phức tạp là cỡ O(nlogn +m), với m là số cạnh của đồ thị. Với những đồ thị

thưa thì đây sẽ là một thuật toán rất tốt.

1.6. Kết luận chương

Ở chương 1 này chúng ta đã sử dụng Fibonacci heap để cải tiến, nâng

cao hiệu quả của thuật toán Dijkstra. Hiệu quả của thuật toán Dijkstra cải tiến

so với thuật toán nguyên thủy đã được minh chứng trong mục 1.5. Trong thực

tế nếu dùng thuật toán Dijkstra nguyên thủy, chúng ta chỉ có thể áp dụng trên

những đồ thị mà số đỉnh N cỡ vài ba chục nghìn trở xuống, còn nếu dùng

Dijkstra Fibonacci heap chúng ta có thể áp dụng cho đồ thị có số đỉnh N lớn

hơn nhiều lần, thậm chí N có thể lên đến hàng triệu. Ngoài việc ứng dụng để

cải tiến Thuật toán Dijkstra ta còn có thể ứng dụng Fibonacci heap vào việc

giải một số bài toán khác như bài toán sắp xếp, bài toán tìm cây khung cực

tiểu, bài toán so khớp hai nhánh có trọng số…

Tuy có ưu thế về tốc độ (độ phức tạp tính toán) đối với hầu hết các thao

tác với heap nhưng Fibonacci heap vẫn chưa được nhiều người lập trình sử

dụng, lý do là vì để cài đặt Fibonacci heap chúng ta phải dùng danh sách móc

nối và nói chung là việc cài đặt phức tạp hơn. Tuy nhiên trong trường hợp

không bị giới hạn về thời gian lập trình và cần xử lý những đồ thị thưa, ta có

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

thể dùng Fibonacci heap để tăng thêm hiệu quả của thuật toán.

33

CHƯƠNG 2

THUẬT TOÁN ĐÀN KIẾN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI

TỐI ƯU

Tối ưu đàn kiến (ACO) là một thuật toán dựa trên ý tưởng mô phỏng

cách tìm đường đi từ tổ tới nguồn thức ăn của các con kiến trong tự nhiên.

Đến nay thuật toán này đã được cải tiến đa dạng và có nhiều ứng dụng. Trước

khi giới thiệu thuật toán ACO, luận văn sẽ giới thiệu phương thức trao đổi

thông tin gián tiếp của kiến tự nhiên và mô hình kiến nhân tạo.

2.1. Từ kiến tự nhiên đến kiến nhân tạo

Khi di chuyển trên đường đường đi, đàn kiến trao đổi thông tin gián

tiếp với nhau và hoạt động theo phương thức tự tổ chức. Mặc dù hình thức

trao đổi thông tin đơn giản nhưng đã giúp cho đàn kiến có thể thực hiện được

những công việc phức tạp vượt xa khả năng của từng con kiến, đặc biệt là khả

năng tìm đường đi ngắn nhất từ tổ đến nguồn thức ăn - mặc dù chúng không

có khả năng đo độ dài đường đi. Đầu tiên chúng ta sẽ xem xét cách đàn kiến

tìm đường đi như thế nào và tại sao chúng lại có thể giải quyết được các vấn

đề tối ưu hóa.

2.1.1. Kiến tự nhiên

Trên đường đi, mỗi con kiến để lại dọc đường một chất hóa học gọi là

vết mùi (pheromone) dùng để đánh dấu đường đi [5]. Bằng cách cảm nhận vết

mùi, kiến có thể lần theo đường đi đến nguồn thức ăn đã được các con kiến đi

trước khám phá, kiến làm điều này theo phương thức chọn ngẫu nhiên có định

hướng theo nồng độ vết mùi. Kiến chịu ảnh hưởng vết mùi của các con kiến

khác chính là ý tưởng thiết kế thuật toán ACO[5].

Thí nghiệm trên cây cầu đôi

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Có nhiều quan sát và thực nghiệm nghiên cứu về hành vi để lại vết mùi

34

và đi theo vết mùi của loài kiến. Thực nghiệm, được thiết kế bởi Deneubourg

và các đồng nghiệp [5] được tiến hành như sau: Họ dùng một chiếc cầu đôi

nối từ tổ kiến tới nguồn thức ăn, như minh họa trong hình 2.1.

Thí nghiệm thứ nhất: Đặt độ dài hai đường đi là bằng nhau (hình

2.1(a), ban đầu các chú kiến lựa chọn đường đi trên hai nhánh cầu một cách

ngẫu nhiên, cả hai nhánh cầu đều có kiến đi. Tuy nhiên sau một thời gian các

chú kiến bắt đầu chuyển sang đi dồn vào một nhánh cầu và cuối cùng tất cả đàn

(a) (b)

Hình 2.1. Thực nghiệm cây cầu đôi

(a): Độ dài hai nhánh cầu bằng nhau. (b): Độ dài hai nhánh cầu khác nhau

kiến cùng đi tập trung vào cùng một nhánh. Kết quả trên được lý giải như sau:

Ban đầu hai nhánh cầu dài bằng nhau và đều chưa có vết mùi, do đó kiến lựa

chọn đường đi một cách ngẫu nhiên vì vậy cả hai nhánh cầu đều có kiến đi.

Một cách ngẫu nhiên sẽ có một nhánh nào đó có nhiều kiến chọn đi hơn

nhánh kia, khi đó nồng độ mùi trên nhánh này sẽ nhiều hơn. Do kiến có xu

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

hướng chọn nhánh có nồng độ mùi cao hơn để đi, vì vậy càng lúc càng có

35

nhiều kiến lựa chọn nhánh có nồng độ mùi cao hơn để đi và đến một lúc nào

đó cả đàn kiến sẽ đi tập trung vào cùng một nhánh có nồng độ mùi cao hơn.

Thí nghiệm thứ hai: Thiết kế một nhánh dài gấp đôi nhánh kia (hình

2.1(b)), trong trường hợp này, ban đầu kiến chọn đi qua hai nhánh là như

nhau, sau một thời gian tất cả các con kiến đều chọn đoạn đường ngắn hơn.

Cách giải thích cũng như trong thực nghiệm thứ nhất, ban đầu đàn kiến lựa

chọn hai nhánh đi như nhau, một nửa số kiến đi theo nhánh ngắn và một nửa

đi theo nhánh dài (mặc dù trên thực tế, do tính ngẫu nhiên có thể một nhánh

nào đó được nhiều kiến lựa chọn hơn nhánh kia). Nhưng thực nghiệm này có

điểm khác biệt quan trọng với thực nghiệm thứ nhất: Những kiến lựa chọn đi

theo nhánh ngắn sẽ nhanh chóng quay trở lại tổ, số lần kiến qua lại trên nhánh

ngắn sẽ nhanh chóng tăng lên kéo theo nồng độ mùi ở nhánh ngắn sẽ cao hơn

nhánh dài, kiến sẽ thấy nồng độ mùi trên nhánh ngắn cao hơn nồng độ mùi

trên nhánh dài, do đó sẽ ưu tiên lựa chọn đi theo nhánh ngắn hơn. Tuy nhiên,

trong thời gian đầu không phải tất cả các kiến đều đi theo nhánh ngắn hơn.

Phải mất một khoảng thời gian tiếp theo nữa đàn kiến mới lựa chọn đi theo

nhánh ngắn. Điều này minh chứng đàn kiến đã sử dụng phương thức thăm dò,

tìm đường mới.

Một điểm quan trọng nữa là quan sát xem sẽ xảy ra điều gì khi quá

trình tìm kiếm đang hội tụ, lại xuất hiện một đường mới từ tổ đến nguồn thức

ăn. Việc này được thực nghiệm như sau: ban đầu từ tổ đến nguồn thức ăn chỉ

có một nhánh dài và sau 30 phút, thêm một nhánh ngắn (xem hình 2.2).

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Hình 2.2. Thí nghiệm bổ sung, ban đầu chỉ có 1 nhánh, sau 30 phút thêm một nhánh ngắn

36

Trong trường hợp này, nhánh ngắn thường không được kiến chọn mà

chúng tập trung đi trên nhánh dài. Điều này có thể giải thích như sau: nồng độ

vết mùi trên cạnh dài cao và sự bay hơi của vết mùi diễn ra chậm nên đại đa

số các con kiến vẫn lựa chọn nhánh dài (có nồng độ vết mùi cao). Hành vi này

tiếp tục được củng cố và kiến chọn đi theo nhánh dài, ngay cả khi có một

nhánh ngắn xuất hiện.

Việc bay hơi vết mùi là cơ chế tiện lợi cho việc tìm đường mới, nghĩa

là việc bay hơi có thể giúp kiến quên đi đường đi tối ưu cục bộ đã được tìm

thấy trước đây để tìm khám phá đường đi mới, tốt hơn.

2.1.2. Kiến nhân tạo

Thực nghiệm cây cầu đôi cho thấy đàn kiến tự nhiên có thể sử dụng

luật di chuyển theo xác suất, dựa trên thông tin địa phương để tìm được

đường đi ngắn nhất giữa hai địa điểm. Vết mùi của đàn kiến cho phép liên

tưởng tới cách học tăng cường (reinforcement learning) trong bài toán chọn

tác động tối ưu [1], gợi mở mô hình mô phỏng cho bài toán tìm đường đi

ngắn nhất giữa hai nút (tương ứng là tổ và nguồn thức ăn) trên đồ thị, trong đó

các tác tử (agent) là đàn kiến nhân tạo.

Tuy nhiên, trong các bài toán ứng dụng các đồ thị thường phức tạp hơn.

Từ mỗi đỉnh có thể có nhiều cạnh, nên nếu mô phỏng thực sự hành vi của đàn

kiến tự nhiên thì nhiều con kiến sẽ đi luẩn quẩn và do đó hiệu quả thuật toán

sẽ rất kém. Vì vậy, người ta dùng kỹ thuật đa tác tử (multiagent) mô phỏng

đàn kiến nhân tạo, trong đó mỗi con kiến nhân tạo có khả năng nhiều hơn so

với kiến tự nhiên. Kiến nhân tạo (về sau trong luận văn ta sẽ gọi đơn giản là

kiến) có bộ nhớ riêng, có khả năng ghi nhớ các đỉnh đã thăm trong hành trình

và tính được độ dài đường đi nó đã đi qua. Ngoài ra, kiến có thể trao đổi

thông tin với nhau, thực hiện tính toán cần thiết, cập nhật mùi…

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Sử dụng mô hình kiến nhân tạo này, Dorigo (1991) đã xây dựng thuật

37

toán hệ kiến (AS) giải bài toán người chào hàng. Hiệu quả của thuật toán này

so với các thuật toán mô phỏng tự nhiên khác như SA và GA đã được kiểm

chứng bằng thực nghiệm. Thuật toán này về sau được phát triển và có nhiều

ứng dụng phong phú, được gọi chung là thuật toán ACO[1].

2.2. Thuật toán ACO tổng quát giải bài toán ngươi chào hàng

Các thuật toán ACO chỉ thực sự ưu việt trong việc tìm lời giải gần đúng

cho các bài toán tìm đường đi tối ưu trên đồ thị thuộc loại NP-khó, còn những

bài toán tìm đường đi tối ưu có độ phức tạp đa thức như đã trình bày ở

chương 1 thì các thuật toán như thuật toán Dijkstra, Dijkstra Fibonacci heap

hiệu quả hơn. Vì vậy phần còn lại của chương này sẽ tập trung nghiên cứu về

các thuật toán ACO và ứng dụng chúng để giải bài toán người chào hàng là

một bài toán tìm đường đi tối ưu thuộc loại NP - khó.

2.2.1. Bài toán người chào hàng

Bài toán người chào hàng (Traveling Salesman Problem -TSP) là bài

toán tối ưu tổ hợp điển hình, được nghiên cứu nhiều và được xem là bài toán

chuẩn để đánh giá hiệu quả các thuật toán giải bài toán tối ưu tổ hợp mới. Bài

toán được phát biểu như sau: Có một tập gồm n thành phố (hoặc điểm tiêu

thụ) được đánh số từ 1 đến n. Độ dài đường đi trực tiếp nối thành phố i đến

thành phố j là c(i,j) . Một người chào hàng muốn tìm một hành trình ngắn

nhất từ nơi ở của mình (thuộc một trong n thành phố nói trên) qua mỗi thành

phố đúng một lần để giới thiệu sản phẩm cho khách hàng, sau đó trở về thành

phố xuất phát.

Như vậy, bài toán này chính là bài toán tìm chu trình Hamilton có độ

dài ngắn nhất trên đồ thị có trọng số G = (V,E), trong đó V là tập đỉnh với

nhãn là số hiệu các thành phố, E là tập các cung đường nối trực tiếp hai thành

phố, độ dài các cung chính là độ dài các đường nối trực tiếp hai thành phố.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Hiện tại thuật toán giải bài toán này (với n lớn) vẫn chưa có.

38

2.2.2. Thuật toán ACO tổng quát giải bài toán TSP

Thuật toán sẽ sử dụng một điều kiện kết thúc nào đó (có thể theo số

bước lặp hoặc/và giới hạn thời gian chạy), ta dùng đàn kiến có m con, tiến

hành thực hiện một vòng lặp quá trình xây dựng lời giải trên đồ thị có trọng

số như sau: Tại mỗi lần lặp, mỗi chú kiến k sẽ chọn đỉnh s nào đó làm thành

phần khởi tạo: s := u0 và thực hiện xây dựng đường đi bằng thủ tục chọn ngẫu

nhiên. Dựa trên các lời giải tìm được, đàn kiến sẽ thực hiện cập nhật mùi theo

cách một quy tắc nào đó.

Thủ tục chọn ngẫu nhiên [5]: Giả sử kiến k đã tìm được phần đầu của

là tập tất cả các đỉnh mà kiến k đường đi từ s là s = uo, u1,.., uq= i. Gọi

chưa đi qua và thỏa mãn (i, v) , khi đó khả năng đỉnh v được E  v

chọn làm đỉnh tiếp theo trên đường đi có xác suất sẽ là:

] (Dĩ nhiên các đỉnh u

p(v) = [(T(i, v))x (h(i,v))y ]/[

không thuộc thì xác suất p(u) = 0) [5].

Trong đó ta ký hiệu: T(v1,v2) là giá trị số thực chỉ nồng độ mùi trên cung

(v1.v2)  (v1.v2)E, h(v1, v2) =  (v1.v2)E là một số thực gọi là

thông tin heurtistic giúp kiến lựa chọn đường một cách chính xác hơn khi

quyết định chọn đi từ một đỉnh u sang một đỉnh v nào đó (c(v1,v2) là độ dài cung (v1,v2)).

Quá trình mở rộng tiếp tục cho tới khi kiến k tìm được lời giải chấp

nhận được (một chu trình Hamilton).

Thủ tục cập nhật mùi[5]: Sau mỗi bước lặp (tức là m chú kiến đã kết

thúc việc tìm lời giải) chương trình sẽ cập nhật lại vết mùi trên các cạnh. Điều

này mô phỏng trong thực tế nồng độ mùi trên các cạnh mà kiến đi qua sẽ tăng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

lên một lượng nào đó do kiến tiết ra, đồng thời theo thời gian nồng độ mùi

39

trên các cạnh cũng bị giảm đi do sự bay hơi của mùi. Tuy nhiên có nhiều quy

tắc cập nhật mùi khác nhau, từ đó cũng sinh ra các thuật toán khác nhau và

người ta thường đặt tên thuật toán theo tên của quy tắc cập nhật mùi. Trong

phần tiếp theo sẽ trình bày một số quy tắc thông dụng, chủ yếu chúng đều có

dạng:

Ti,j = (1- p)Ti,j + (i,j) [5] đối với những cạnh được cập nhật, trong đó p

là hằng số biểu thị tỉ lệ lượng mùi bị bay hơi, (i,j) là lượng mùi được thêm

vào (bớt đi) khi kiến đi qua một cạnh.

Procedure ACO;

Begin

Khởi tạo tham số, mùi, khởi tạo m con kiến;

repeat

for k = 1 to m do Kiến k xây dựng lời giải;

Cập nhật mùi;

Cập nhật lời giải tốt nhất;

until (Điều kiện kết thúc);

Đưa ra lời giải tốt nhất;

End;

Lược đồ tổng quát của thuật toán ACO như sau [1]:

2.3. Các thuật toán ACO giải bài toán TSP

Trong mục này sẽ trình bày 3 thuật toán ACO cụ thể để giải bài toán

TSP là: Ant System(AS), Ant Colony System(ACS), Max-Min Ant System

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

(MMAS)

40

2.3.1. Thuật toán AS

Hai bước cơ bản trong thuật toán AS là xây dựng lời giải của kiến và

cập nhật mùi. Trong AS, dựa vào lời giải tìm được dựa trên thuật toán

heuristic (chẳng hạn thuật toán tham ăn) khi xác định vết mùi khởi tạo. Giá

, trong đó m là số trị vết mùi khởi tạo cho tất cả các cung là: Ti,j = T0 =

kiến, cnn là độ dài lời giải tìm được của thuật toán heuristic [1]. Lý do lựa

chọn này là nếu khởi tạo vết mùi T0 quá thấp thì quá trình tìm kiếm có khuynh

hướng hội tụ về hành trình đầu tiên tìm được, dẫn đến việc tìm kiếm sa lầy

vào vùng này, làm cho chất lượng lời giải không tốt. Nếu khởi tạo vết mùi

quá cao thì thường phải mất nhiều vòng lặp để bay hơi mùi trên các cung

không tốt và cập nhật bổ sung thêm mùi cho các cung tốt mới để có thể hướng

việc tìm kiếm đến vùng không gian có chất lượng tốt [1].

(1) Xây dựng lời giải: Trong thuật toán AS, m kiến đồng thời xây dựng

lời giải. Ban đầu, các con kiến được đặt tại đỉnh xuất phát s nào đó. Ở mỗi

bước tiếp theo, kiến sử dụng xác suất theo phương thức tỉ lệ ngẫu nhiên để

chọn đỉnh tiếp theo. Cụ thể, khi kiến k đang ở đỉnh i, nó sẽ lựa chọn đỉnh v

nếu v là đỉnh chưa đi qua và có cung nối từ đỉnh i tới v với xác suất là [5]:

] (2.1)

p(v) = [(T(i, v))x (h(i,v))y ]/[

Theo quy tắc ngẫu nhiên này, xác suất lựa chọn cung (i, v) tăng theo

giá trị thông tin mùi T(i, v) và thông tin heuristic h(i,v). Vai trò của hai tham số x

và y như sau: Nếu x = 0 thì thành phố gần nhất sẽ được ưu tiên lựa chọn, khi

đó thuật toán tương đương với thuật toán chọn ngẫu nhiên theo ưu tiên tỉ lệ

nghịch đảo độ dài cung, không có học tăng cường. Nếu y = 0 thì chỉ có thông

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

tin học tăng cường biểu thị qua vết mùi được sử dụng, không có thông tin

41

heuristic. Nếu x lớn, thuật toán nhanh chóng bị tắc nghẽn (tất cả kiến sẽ lựa

chọn cù ng một hành trình) và lời giải tìm được hội tụ về lời giải tối ưu

cục bộ [1].

Khi cài đặt kiến k sẽ được cấp cho một bộ nhớ Mk dùng để chứa thông

tin về các thành phố đã đi qua, các thành phố lân cận chưa đi qua, thông tin

này còn cho phép tính được độ dài hành trình của kiến k, tìm ra các cung trên

hành trình,...

Có hai cách để thực hiện xây dựng lời giải là xây dựng song song và

xây dựng tuần tự. Theo cách xây dựng song song, tại mỗi bước tất cả m kiến

sẽ di chuyển sang đỉnh tiếp theo. Trong cách xây dựng tuần tự, lần lượt từng

kiến xây dựng lời giải (kiến này xây dựng xong rồi mới đến kiến tiếp theo).

Trong AS, cả hai cách xây dựng này là như nhau, không có ảnh hưởng gì đến

kết quả. Điều này sẽ không đúng với thuật toán ACS.

(2) Cập nhật mùi : Sau khi tất cả các kiến xây dựng xong hành trình,

vết mùi sẽ được cập nhật như sau: Trước tiên, tất cả các cung sẽ bị bay hơi

theo một tỉ lệ không đổi, sau đó các cung có kiến đi qua sẽ được thêm một

lượng mùi.

Việc bay hơi mùi trên tất cả các cung được thực hiện theo công thức sau:

T(u,v) := (1 - p)T(u,v), trong đó p là hệ số bay hơi, 0 < p  1.Tham số p

được dùng để tránh sự tích tụ quá nhiều mùi trên một cung và giúp kiến có

khả năng “quên” đi các quyết định sai lầm trước đó [5].

Sau khi tính lượng mùi bay hơi, lượng mùi kiến k sẽ để lại trên cung mà

nó đi qua được tính theo công thức:

uv, trong đó Tk

uv =

với ck là độ dài đường đi T(u,v) := T(u,v) + Tk

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Tk do kiến k xây dựng [5]. Như vậy cung nào thuộc đường đi ngắn hơn và có

42

nhiều kiến sử dụng sẽ được bổ sung mùi nhiều hơn, do đó trong các bước lặp

sau sẽ được nhiều kiến lựa chọn hơn.

Khi kích thước bài toán tăng, thuật toán AS tuy có hiệu quả hơn các

thuật toán metaheuritistic khác tuy nhiên còn một số điểm mà AS chưa thực

sự hiệu quả, ví dụ như khi tính lượng mùi bay hơi sau mỗi lần lặp thuật toán

AS phải duyệt để tính cho tất cả các cung, việc làm này mất rất nhiều phép

tính toán và nhiều khi đó là những phép tính toán vô ích vì có nhiều cung

không có kiến nào đi qua trong suốt cả vòng lặp. Vì vậy trong mục 2.3.3 tiếp

theo chúng ta sẽ nghiên cứu một thuật toán ACO khác hiệu quả hơn đó là

thuật toán ACS.

2.3.2. Thuật toán ACS

Thuật toán ACS (Ant Colony System) do Dorigo và Gambardella đề

xuất năm 1997 [5], ACS khác với AS ở ba điểm chính sau đây:

Thứ nhất, ACS khai thác kinh nghiệm tìm kiếm mạnh hơn trong AS,

thông qua việc sử dụng quy tắc lựa chọn dựa trên thông tin tích lũy nhiều hơn.

Thứ hai, trong ACS cơ chế bay hơi mùi và để lại mùi chỉ trên các cung

thuộc vào lời giải tốt nhất đến lúc đó (Global-best: G-best).

Thứ ba, tăng cường việc thăm dò đường mới. Mỗi lần kiến đi qua cung

nào thì vết mùi sẽ bị giảm trên cung đó. Sau đây chúng ta sẽ tìm hiểu chi tiết

những điểm khác đã nêu.

Xây dựng lời giải

Trong thuật toán ACS, kiến k đang đứng ở đỉnh i sẽ lựa chọn di chuyển

đến đỉnh v theo qui tắc:

v = argmaxl {T(i,l)[h(i,l)]y} nếu q  q0, ngược lại v = j (2.2)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

trong đó q là một biến ngẫu nhiên, phân bố đều trong [0, 1], q0 là một tham số

43

cho trước (0  q0 1) và j là một biến ngẫu nhiên được lựa chọn theo phân bố

xác suất như trong (2.1) với x = 1[5].

Ta có thể hiểu công thức (2.2) là: Nếu q  q0, kiến k sẽ lựa chọn đi

đến đỉnh v = l sao cho T(i,l)[h(i,l)]y là lớn nhất (xác suất này là q0), trường hợp

này ta nói kiến khai thác thông tin đã học. Nếu q > q0, kiến k sẽ chọn đỉnh v = j

như trong AS xác xuất cách chọn này là (1 - q0).

Điều chỉnh tham số q0 sẽ cho phép thay đổi mức độ khai thác và lựa

chọn tập trung tìm kiếm quanh lời giải G-best hoặc khám phá các hành

trình khác.

Cập nhật mùi toàn cục

Trong ACS chỉ có duy nhất một kiến tìm được lời giải G-best được

phép để lại mùi sau mỗi lần lặp. Cụ thể, với các cung (i,j) thuộc lời giải G-

best =

best được cập nhật như sau:

best (2.3), trong đó Tij

, CG-best là T(i,j) := (1- p)T(i,j) + p Tij

độ dài lời giải G-best [5].

Cần chú ý là trong ACS vết mùi được cập nhật bao gồm cả bay hơi và

để lại mùi và chỉ cho các cung thuộc TG-best (không phải cho tất cả các cung

như trong AS). Tham số p là tham số bay hơi. Kết quả của việc cập nhật này

là vết mùi được thay đổi theo trung bình trọng số của vết mùi cũ và lượng mùi

được để lại. Trong thực nghiệm, người ta cũng còn sử dụng lời giải tốt nhất

trong bước lặp hiện tại (Iteration-best: I-best) để cập nhật mùi [1].

Cập nhật mùi cục bộ

Ngoài việc cập nhật mùi toàn cục, ACS còn sử dụng cơ chế cập nhật

mùi cục bộ. Việc cập nhật mùi cục bộ được thực hiện ngay khi cung (i,j) có

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

kiến đi qua theo công thức:

44

T(i,j) := (1 - ) T(i,j) + T0 (2.4)

trong đó  (0<<1) và T0 là hai tham số. Giá trị T0 chính là giá trị khởi tạo mùi

cho tất cả các cung. Theo thực nghiệm giá trị tốt cho  bằng 0.1, giá trị là T0

là , trong đó n là số thành phố, Cnn là độ dài hành trình theo thuật toán

heuristic tham lam [5]. Hiệu quả của viê ̣c cập nhật mùi cục bộ thể hiện ở chỗ

mỗi khi kiến đi qua cung (i,j) thì vết mùi trên cung (i,j) bị giảm, làm cho kiến

ít lựa chọn lại cung này. Nói cách khác, việc cập nhật mùi cục bộ làm tăng

khả năng khám phá các cung chưa được sử dụng. Trên thực tế, hiệu quả của

cách cập nhật mùi này chính là ở chỗ không bị tắc nghẽn (nghĩa là, các kiến

không bị dồn vào một đường đi nào) như trong AS.

Đối với AS, kiến xây dựng hành trình song song hay tuần tự thì tác

động đều như nhau còn trong ACS, mỗi cách xây dựng hành trình có tác động

khác nhau đến những lần lặp sau vì ACS sử dụng cơ chế cập nhật mùi cục bộ.

Trong thực nghiệm, thuật toán ACS yêu cầu mọi kiến đồng thời xây dựng

hành trình, mặc dù không có kết quả thực nghiệm chứng tỏ sự lựa chọn nào

tốt hơn [1].

2.3.3. Thuật toán Max-Min (MMAS)

Thuật toán MMAS (Max-Min Ant System) do Stutzle và Hoos đề xuất

năm 2000 [1] có bốn điểm khác so với thuật toán AS [5]:

Thứ nhất, để tăng cường khai thác lời giải tốt nhất tìm được, thuật toán

MMAS đã cho các cung thuộc vào lời giải I-best hoặc G-best được cập nhật

mùi. Điều này có thể dẫn đến hiện tượng tắc nghẽn: Tất cả các kiến sẽ cùng đi

một hành trình, bởi vì lượng mùi trên các cung thuộc hành trình tốt được cập

nhật quá nhiều, mặc dù hành trình này không phải là hành trình tối ưu.

Thứ hai, để khắc phục nhược điểm trong thay đổi thứ nhất, MMAS đã

đưa ra miền giới hạn cho vết mùi: Vết mùi sẽ bị hạn chế trong khoảng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

[Tmin,Tmax].

45

Thứ ba, là vết mùi ban đầu được khởi tạo bằng Tmax và hệ số bay hơi

nhỏ nhằm tăng cường khám phá trong giai đoạn đầu.

Thứ tư, là mùi sẽ được khởi tạo lại khi có hiện tượng tắc nghẽn hoặc

không tìm được lời giải tốt hơn sau một số bước.

Cập nhật mùi [5]

Sau khi tất cả kiến xây dựng xong lời giải, vết mùi được cập nhật bằng

thủ tục bay hơi giống như AS theo công thức T(u,v) := (1-p)T(u,v), và thêm một

best (2.5)

lượng mùi cho tất cả các cung thuộc lời giải tốt như sau:

best =

best =

T(u,v):=T(u,v) + Tuv

khi dùng I- trong đó Tuv khi dùng G-best hoặc Tuv

best để cập nhật mùi. Sau đó vết mùi sẽ bị giới hạn trong đoạn [Tmin,Tmax]

như sau:

T(u,v):= T(u,v) nếu T(u,v)  [Tmin, Tmax]

T(u,v):= Tmin nếu T(u,v) < Tmin

T(u,v):= Tmax nếu T(u,v) > Tmax (2.6)

Nhìn chung, MMAS dùng cả I-best và G-best thay phiên nhau. Rõ

ràng, việc lựa chọn tần số tương đối cho hai cách cập nhật mùi ảnh hưởng đến

hướng tìm kiếm. Nếu luôn cập nhật bằng G-best thì việc tìm kiếm sẽ sớm

định hướng quanh G-best còn khi cập nhật bằng I-best thì số lượng cung được

cập nhật mùi nhiều do đó việc tìm kiếm giảm tính định hướng hơn.

Giới hạn vết mùi

Trong MMAS sử dụng giới hạn trên Tmax và giới hạn dưới Tmin đối với

vết mùi của tất cả các cung để tránh tình trạng tắc nghẽn. Đặc biệt, việc giới

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

hạn vết mùi sẽ có ảnh hưởng đến giới hạn xác suất p(u,v) trong đoạn [pmin, pmax]

46

phục vụ lựa chọn đỉnh v, khi kiến đang ở đỉnh u với 0  Pmin  P(u,v)  Pmax  1.

Chỉ khi = 1 thì Pmin = Pmax = 1 [5].

Nhận thấy, trong một thời gian dài, cận trên của vết mùi là trong

đó C* là độ dài hành trình tối ưu. Dựa trên kết quả đó, MMAS cập nhật lại cận

(W là một tham số) mỗi khi tìm trên Tmax = và cận dưới Tmin =

được lời giải tốt hơn. Kết quả thực nghiệm chỉ ra rằng: Để tránh tắc nghẽn,

cận dưới Tmin đóng vai trò quan trọng hơn cận trên Tmax. Tuy nhiên, Tmax hữu

ích trong việc thiết đặt giá trị vết mùi khi khởi tạo lại [1].

Khởi trị và khởi tạo lại vết mùi

Khi bắt đầu thuật toán, vết mùi trên tất cả các cung được khởi tạo bằng

cận trên của vết mùi Tmax. Cách khởi tạo như vậy, kết hợp với tham số bay hơi

nhỏ sẽ cho phép làm chậm sự khác biệt vết mùi giữa các cung. Do đó, giai

đoạn đầu của MMAS mang tính khám phá [5].

Để tăng cường khả năng khám phá, MMAS khởi tạo lại vết mùi mỗi

khi gặp tình trạng tắc nghẽn hoặc sau một số bước lặp mà vẫn không tìm được

lời giải tốt hơn.

MMAS là thuật toán được nghiên cứu nhiều nhất trong số các thuật

toán ACO và nó có rất nhiều mở rộng. Một trong các cải tiến là khi khởi tạo

lại vết mùi, cập nhật mùi dựa trên lời giải tốt nhất tìm được tính từ khi khởi

tạo lại vết mùi thay cho G-best [1].

2.4. Một số vấn đề trong việc áp dụng ACO tìm đường đi tối ưu

2.4.1. ACO kết hợp với tìm kiếm cục bộ

Nhiều tài liệu [1], [5] chỉ ra rằng với các thuật toán metaheuristic, một

cách tiếp cận đầy hứa hẹn cho phép nhận được lời giải có chất lượng cao là

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

kết hợp với thuật toán tìm kiếm cục bộ.

47

Mô hình ACO có thể bao gồm cả tìm kiếm cục bộ [5]. Sau khi kiến

xây dựng xong lời giải, có thể áp dụng tìm kiếm cục bộ để nhận được lời giải

tối ưu địa phương. Việc cập nhật mùi được thực hiện trên các cung thuộc lời

giải tối ưu địa phương này. Kết hợp xây dựng lời giải với tìm kiếm cục bộ sẽ

là một cách tiếp cận có triển vọng. Thực nghiệm cho thấy khả năng kết hợp

tìm kiếm cục bộ cải tiến được lời giải là khá cao.

2.4.2. Thông tin heuristic

Thuật toán ACO mà không sử dụng tìm kiếm cục bộ thì thông tin

heuristic sẽ rất cần thiết để có được lời giải tốt [5]. Trên thực tế, ở giai đoạn

đầu vết mùi được khởi tạo như nhau. Khi đó vết mùi không thể giúp kiến tìm

đường đi dẫn tới các lời giải tốt, vì chưa khác nhau nhiều.Vai trò chính của

thông tin heuristic là để khắc phục điều này, giúp kiến có thể xây dựng được

các hành trình tốt ngay trong giai đoạn đầu. Trong nhiều trường hợp, nhờ sử

dụng tìm kiếm cục bộ, kiến vẫn có thể tìm được lời giải tốt ngay trong giai

đoạn đầu, không cần sử dụng thông tin heuristic nào cả, mặc dù có làm cho

quá trình tìm kiếm chậm hơn [5].

2.4.3. Số lượng kiến

Như đã nói ở trên, nếu không sử dụng tìm kiếm cục bộ và thông tin

heuristic ít (hoặc không có), trong giai đoạn đầu vết mùi không thể giúp kiến

tìm đường đi dẫn tới các lời giải tốt [1]. Nếu sử dụng số lượng kiến ít, trong

giai đoạn đầu sẽ không tìm được lời giải tốt và như vậy, việc cập nhật mùi

được cập nhật dựa trên các lời giải không tốt [1]. Khi đó, sẽ hướng việc tìm

kiếm xung quanh lời giải không tốt và do đó thuật toán sẽ không hiệu quả. Có

thể khắc phục phần nào nhược điểm này bằng cách tăng số kiến, để tăng khả

năng tìm được lời giải tốt ở mỗi vòng lặp [1]. Khi có sử dụng tìm kiếm cục bộ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

hoặc thông tin heuristic mạnh, sử dụng nhiều kiến là lãng phí [1].

48

2.4.4. Tham số bay hơi

Ở mỗi vòng lặp, khi xây dựng được lời giải tốt (sử dụng tìm kiếm cục

bộ hoặc thông tin heuristic mạnh), tham số bay hơi sẽ được xác lập có giá trị

lớn, điều này giúp kiến quên đi những lời giải đã xây dựng, tập trung công

việc tìm kiếm xung quanh lời giải tốt mới được xây dựng. Trong trường hợp

ngược lại, ở mỗi vòng lặp, khả năng kiến tìm được lời giải tốt không cao thì

tham số bay hơi phải được thiết lập với giá trị nhỏ [5].

2.4.5. Một số đề xuất cải tiến

Chúng ta có thể thấy rằng việc cập nhật lượng mùi bay hơi trong hai

thuật toán AS và MMAS sau mỗi lần lặp được tiến hành trên tất cả các cung,

điều này làm tăng khối lượng tính toán của thuật toán lên rất nhiều từ đó làm

giảm hiệu quả của thuật toán. Thực tế trong một lần lặp lượng mùi trên một

cung chỉ được dùng đến khi cung đó kề với ít nhất một đỉnh trên đường đi của

các chú kiến. Khi kích thước đồ thị lớn và đồ thị thưa hoặc khi các chú kiến

đã dần đi cùng một đường thì số cung không thỏa mãn điều kiện vừa nêu là

rất lớn, việc cập nhật lượng mùi bay hơi cho các cung này là chưa cần thiết vì

vậy ta có thể trì hoãn việc làm này khi có thể để giảm bớt các phép tính toán.

Cụ thể ta có thể cải tiến việc cập nhật mùi như sau:

- Với mỗi cung (i,j) ta dùng một biến CNM(i,j) ghi nhận lần lặp mới

nhất mà nó được cập nhật lượng mùi bay hơi.

CNM(i,j) = q1, nghĩa là lần lặp mới nhất mà cung (i,j) được cập nhật

mùi là lần lặp thứ q1.

- Sau mỗi lần lặp ta không cập nhật lại lượng mùi bay hơi ở các cung.

- Trong một vòng lặp, giả sử đó là vòng lặp thứ q2, nếu kiến k đang ở

đỉnh i và cần tìm đỉnh để đi tiếp, khi đó ta mới tiến hành cập nhật lượng mùi

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

cho các cung (i, j)  theo công thức sau:

49

T(i,j) := (1-p)q2 –q1T(i,j) (2.7)

Trong công thức (2.7) ta có thể hiểu đơn giản q2- q1 là số lần cập nhật

lượng mùi bay hơi cho cung (i,j) đã bị trì hoãn trước đó. Việc tính lũy thừa

của (1-p)k ta sẽ tính sẵn trong một mảng để giảm tính toán.

2.5. Kết luận chương

Thuật toán ACO là một thuật toán metaheuristic được sử dụng rộng rãi

để giải các bài toán tối ưu tổ hợp khó, tính hiệu quả của nó đã được minh

chứng qua thực nghiệm. Thuật toán này mô phỏng cách tìm đường đi của kiến

tự nhiên, trong đó lời giải chấp nhận được của bài toán được các con kiến xây

dựng nhờ thủ tục chọn ngẫu nhiên trên đồ thị có trọng số. Việc tìm kiếm đỉnh

mới của đường đi dựa trên kết hợp thông tin heuristic và thông tin học tăng

cường biểu thị bởi vết mùi.

Khi áp dụng thuật toán ACO, ba yếu tố sau đây có vai trò quan trọng:

(1) Xây dựng đồ thị trọng số;

(2) Xác định thông tin heuristic;

(3) Chọn quy tắc cập nhật mùi.

Trong đó hai yếu tố đầu phụ thuộc vào từng bài toán cụ thể, còn yếu tố

thứ ba có nhiều đề xuất và nghiên cứu cải tiến, tuy nhiên chúng ta vẫn còn có

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

thể nghiên cứu sâu hơn nhằm đưa ra các cải tiến hiệu quả.

50

CHƯƠNG 3

Ứ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

Trong chương này chúng ta sẽ ứng dụng thuật toán Dijkstra Fibonacci

heap, thuật toán ACO để giải 2 bài toán tìm đường đi tối ưu trên mạng giao

thông. Nội dung các bài toán và các sơ đồ thuật toán giải các bài toán này

được trình bày dưới đây

3.1. Ứng dụng Dijkstra Fibonacci heap

13.1.1. Phát biểu bài toán 1

Cho một mạng giao thông gồm N nút, các nút được đánh số từ 1 đến N.

Từ nút i đến nút j có không quá một đường đi một chiều với độ dài là c(i, j).

Cho trước hai nút giao thông s và t, hãy tìm đường đi ngắn nhất từ s đến t.

3.1.2. Mô hình hoá bài toán

Ta có thể coi mạng giao thông trong bài toán 1 như là một mô hình đồ

thị có hướng, có trọng số như sau: Mỗi nút giao thông là một đỉnh của đồ thị,

mỗi đoạn đường một chiều nối trực tiếp hai nút giao thông là một cung của đồ

thị. Việc tìm đường đi ngắn nhất từ nút giao thông s đến t trở thành việ tìm

đường đi ngắn nhất từ đỉnh s đến t trên trên đồ thị có hướng G = (V, E), với V

là tập các đỉnh ứng với các nút giao thông, E là tập các cung ứng với các đoạn

đường một chiều nối trực tiếp hai nút như đã nói ở trên.

3.1.3. Mô tả input, output

Đồ thị được cho ở dạng danh sách cung để có thể thử nghiệm với các

đồ thị có số đỉnh lớn. Mặt khác để thuận lợi khi nhập dữ liệu chúng ta sẽ cho

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

input trong các file text.

51

Cụ thể:

Input: Được cho trong file text có tên là DONG.INP có dạng như sau:

Dòng đầu là 4 số nguyên dương N,M, s, t, trong đó N là số đỉnh, M là số cung

của đồ thị, s là đỉnh xuất phát, t là đỉnh đích cần đến. M dòng tiếp theo, mỗi

dòng ghi 3 số nguyên dương u, v, l với ý nghĩa có cung từ u đến v có độ dài

(trọng số) là l.

Output: Kết quả ghi ra file text có tên DONG.OUT có dạng như sau:

Dòng đầu là một số nguyên T là độ dài đường đi ngắn nhất tìm được.

Các dòng sau ghi số hiệu các đỉnh của đường đi ngắn nhất từ s đến t.

3.1.4. Một số kiểu dữ liệu và các biến trong chương trình

type tro = ^node;

node = record

sohieu, degree: longint;

key: int64;

parent, child, left, right: tro;

mark : boolean;

end;

Chương trình sử dụng một kiểu con trỏ được khai báo dạng sau:

Trường sohieu của một node là tên của đỉnh mà node đó đại diện, các

trường khác trong node hiểu như đã trình bày ở chương 1.

Chương trình sử dụng biến mảng d dạng d: array[1..nmax] of tro;

Mảng này thực chất là chứa n biến trỏ, mỗi biến trỏ trỏ vào một node

của Fibonacci heap, d[i] trỏ vào node đại diện cho đỉnh i của đồ thị, trường

key của node này là nhãn khoảng cách từ đỉnh s đến đỉnh i. Việc dùng mảng d

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

này cho phép chương trình có thể truy nhập vào các nút trong Fibonacci heap

52

khi biết sohieu của node này.

Các biến mảng adj[i], head[j] dùng để lưu đồ thị ở dạng danh sách kề

kiểu móc nối.

3.1.5. Một số hàm và thủ tục trong chương trình

Thủ tục Enter: Thủ tục này có nhiệm vụ đọc dữ liệu từ tệp input, sau

khi thực hiện thủ tục này số đỉnh của đồ thị được lưu trong biến n, số cung

lưu trong biến m. Đồ thị được lưu trữ dưới dạng danh sách kề như sau:

Với mỗi đỉnh i thì các đỉnh kề với i được xác định thông qua head[i],

nếu h[i] = k  0 thì adj[k]. v là đỉnh kề thứ nhất của i. Địa chỉ của đỉnh kề tiếp

theo của i là adj[k].link: Nếu adj[k].link = k1  0 thì đỉnh kề thứ 2 của i là

adj[k1].v. Quá trình tìm đỉnh kề với i kết thúc khi địa chỉ tìm được bằng 0.

Như vậy nếu ngay từ đầu head[i] = 0 thì danh sách kề của i bằng rỗng, nghĩa

là từ i không có cung nối tới bất kỳ đỉnh nào cả.

Thủ tục INSERT(var x, minH:tro): Thủ tục này chèn một nút mới được

trỏ bởi con trỏ x vào Fibonacci heap được trỏ bởi minH. Trong thủ tục này x

và minH đều là các tham số hình thức (khi gọi thủ tục thì tham số hình thức

phải thay bằng các biến tương ứng).

Thủ tục FIB_HEAP_LINK(var y, x:tro): Biến gốc y (được trỏ bởi con

Thủ tục CUT(var minH, x, y : tro): Đưa nút x ra khỏi danh sách con

trỏ y) làm con của gốc x (y và x đều là các tham số hình thức).

của nút y, biến x thành một gốc. MinH, x, y đều là các tham số hình thức.

Thủ tục CASCADING_CUT(var minH, y : tro): Thủ tục cắt liên hoàn

như đã trình bày ở chương 1.

Thủ tục FIB_HEAP_DECREASE_KEY(var minH, x: tro; k: longint):

Thủ tục này sẽ thay x^.key bằng một giá trị mới nhỏ hơn là k, nếu k nhỏ hơn

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

khóa của nút y là cha của x thì sẽ cắt nhánh cây gốc x bằng thủ tục CUT(x, y).

53

Thủ tục Consolidate(var minH : tro): Thủ tục này sẽ thống nhất danh

sách gốc, nghĩa là sẽ ghép hai gốc có cùng số con thành một gốc, việc này sẽ

được lặp cho đến khi không tồn tại hai gốc có số nút con bằng nhau.

Thủ tục FIB_HEAP_EXTRACT_MIN(var z : tro): 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 gốc

đã bị trì hoãn ở các phép toán khác. Đoạn mã nguồn sau mô tả thủ tục

procedure FIB_HEAP_EXTRACT_MIN(var z : tro);

// input: Fibonacci heap H.

//output: Nút có khóa cực tiểu của H.

var x, tam, tt, tam2 : tro;

i: longint;

begin

z := minH;

if z <> NIL then

begin

nH := nH - 1;

x:= z^.child;

if x <> nil then // biến các con của z thành gốc

begin

tam := x;tam^.parent := nil;

while tam^.right <> x do

begin

tam := tam^.right;

tam^.parent := nil;

end;

x^.left^.right := minH^.right;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

FIB_HEAP_EXTRACT_MIN

54

minH^.right^.left := x^.left;

minH^.right := x;

x^.left := minH;

end;

z^.right^.left := z^.left; // gỡ z khỏi danh sách gốc

z^.left^.right := Z^.right;

if z = z^.right then // Fibonacci heap chỉ có duy nhất mình nút z

minH := NIL

else minH := z^.right;

if (minH <> nil) and (minH <> minH^.right)

then Consolidate(minH);

end

else writeln('dong rong');

end;

Hàm Relax(u, v: longint; w: longint): Hàm này trả lại giá trị true

nếu nhãn khoảng cách từ s đến v lớn hơn khoảng cách từ s đến u cộng với

khoảng cách trực tiếp từ u đến v. Ngoài ra khi hàm có giá trị là true thì đỉnh u

được ghi nhận là đỉnh đứng ngay trước v trên đường đi ngắn nhất từ s đến t.

Procedure Dijkstra; // input: Đồ thị có hướng G, s, t. // output: Khoảng cách từ s đến t.

var j, i: longint; tt, tam, ta : tro;

begin

repeat

u:= nil;

FIB_HEAP_EXTRACT_MIN(u);

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Thủ tục Dijkstra Fibonacci heap có thể viết lại như sau:

55

if (u = nil) or (u^.sohieu = t) then

Break;

i := head[u^.sohieu];

while i <> 0 do

begin

if Relax(u^.sohieu, adj[i].v, adj[i].w) then

FIB_HEAP_DECREASE_KEY(minH,d[adj[i].v], d[u^.sohieu]^.key +adj[i].w);

i := adj[i].link;

end;

until (u = nil) or (nh = 0);

end;

Thủ tục Init: Thủ tục này tạo ra một Fibonacci heap gồm N nút, được

quản lý bởi biến toàn cục minH.

Thủ tục PrintResult: Đưa ra output.

3.1.6.Sơ đồ thuật toán

// input: Đồ thị có hướng G, s, t.

// output: Khoảng cách và đường đi từ s đến t.

BEGIN

Enter;

Init;

dijkstra;

PrintResult;

END.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Sơ đồ thuật toán giải bài toán tìm đường đi ngắn nhất có dạng sau:

56

3.1.7. Các kết quả thực nghiệm giải bài toán 1

Thực nghiệm kiểm tra chương trình trên 11 bộ test có tên lần lượt là

Test00, Test01,.., Test09, Test10. Các file input, output được lưu trong các

thư mục có tên ở cột thứ nhất. Hình thức một file output đã mô tả ở mục

3.1.3, dưới đây là nội dung file output của bộ test thứ nhất - Test00:

341

1 25097 23364 18174 7928 10086 38541 4461 11683 34627 30000

Kết quả (thời gian chạy chương trình) thực nghiệm khi chạy chương

trình giải bài toán 1 được thống kê trong bảng 3.1 dưới đây (đơn vị thời gian

tính bằng giây, N là số đỉnh, M là số cạnh):

N

M

Thời gian chạy chương trình dùng Dijkstra heap

Thời gian chạy chương trình dùng Dijkstra thường

Tên test

Bảng 3.1. Thống kê kết quả thực nghiệm chương trình giải bài toán 1

Test00 40000 1600000 1.900 11.807

Test01 100 1000 0.056 0.040

Test02 1000 20000 0.067 0.110

Test03 10000 60000 0.094 0.174

Test04 20000 200000 0.412 3.994

Test05 40000 600000 0.980 9.758

Test06 80000 1000000 1.398 6.196

Test07 100000 2000000 2.587 19.570

Test08 300000 3000000 2.923 70.682

Test09 1000000 5000000 7.573 > 3000

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Test10 20000 400000 0.269 2.148

57

Tên các test ở cột 1 của bảng trên thực chất là tên thư mục chứa test đó,

điều cần quan tâm nhất ở đây là thời gian chạy của hai chương trình ở cột 4 và

cột 5. Số liệu ở bảng trên đã chứng minh tính ưu việt của thuật toán Dijkstra

Fibonacci heap so với thuật toán Dijkstra nguyên thủy.

Nhìn chung khi đồ thị thưa và số đỉnh càng lớn thì thuật toán Dijkstra

Fibonacci heap càng tỏ ra ưu việt hơn so với thuật toán Dijkstra nguyên thủy.

Tuy nhiên khi số đỉnh ít thì có khi thuật toán Dijkstra nguyên thủy chạy lại

nhanh hơn (test01). Sở dĩ có hiện tượng này là vì: Độ phức tạp của thuật toán Dijkstra nguyên thủy là O(N2) suy ra số phép tính toán của thuật toán này cỡ C1N2, độ phức tạp của thuật toán Dijkstra Fibonacci heap là O(Nlog N + M)

suy ra số phép tính toán thực tế của thuật toán là cỡ C2(Nlog N + M) với C1,

C2 là các hằng số. Do Dijkstra Fibonacci heap phải thao tác với Fibonacci

< C2(Nlog N + M), nếu điều này xảy ra thì thuật toán

heap tương đối phức tạp nên thực tế C2 > C1 vì thế khi N nhỏ có thể xảy ra trường hợp C1N2

Dijkstra nguyên thủy chạy nhanh hơn.

Các tệp input trong các bộ test được tạo ra hoàn toàn ngẫu nhiên, thuật

toán tạo các file input như sau:

- N, M, s, t nhập từ bàn phím.

- Dùng một mảng c lưu bán bậc ra của các đỉnh, ban đầu c[i]:= 0

i=1..N. Thực hiện M lần sinh số ngẫu nhiên nguyên dương thuộc [1, N] bằng

hàm random, khi sinh được số i thì c[i] được tăng 1 đơn vị.

- Tạo các cung xuất phát từ các đỉnh i như sau:

Với mỗi đỉnh i: Dùng một mảng daxet để quản lý các đỉnh đã có cung

nối từ đỉnh i tới, ban đầu daxet[j]:=false  j<>i, daxet[i] := true. Thực hiện

c[i] lần sinh số nguyên ngẫu nhiên u thuộc [1, N] sao cho daxet[u] = false.

Với mỗi u sinh được ta có một cung (i,u), trọng số của cung này cũng được

sinh ngẫu nhiên. Sau khi ghi cung (i,u) này ra tệp input ta sẽ gán cho daxet[u]

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

bằng true để không lặp lại các cung.

58

Thuật toán như đã mô tả ở trên cho phép ta tạo ra các file input lưu các

đồ thị ở dạng danh sách cung với số đỉnh lớn tới hàng triệu và không có cung

nào bị lặp.

3.2. Ứng dụng Dijkstra Fibonacci heap, ACO giải bài toán TSP

mở rộng

3.2.1. Phát biểu bài toán 2

Cho một mạng giao thông gồm N nút, các nút được đánh số từ 1 đến

N. Từ nút i đến nút j có không quá một đường đi một chiều với độ dài là c(i,j).

Một người bán hàng, xuất phát từ nút giao thông s, phải đưa hàng đến

k nút giao thông phân biệt cho trước rồi quay trở về s.

Hãy tìm một hành trình cho người bán hàng sao cho độ dài của hành

trình này là ngắn nhất có thể được.

3.2.2. Mô hình hoá bài toán

Ta có thể coi mạng giao thông trong bài toán 2 như là một mô hình đồ

thị có hướng, có trọng số như sau: Mỗi nút giao thông là một đỉnh của đồ thị,

mỗi đoạn đường một chiều nối trực tiếp hai nút giao thông là một cung của đồ

thị. Việc tìm đường đi ngắn nhất từ nút giao thông s, qua k nút giao thông cho

trước rồi trở về s được quy về bài toán tìm đường đi ngắn nhất từ đỉnh s, qua k

đỉnh cho trước rồi quay về đỉnh s trên trên đồ thị có hướng G = (V ,E), với V

là tập các đỉnh ứng với các nút giao thông, E là tập các cung ứng với các đoạn

đường một chiều nối trực tiếp hai nút như đã nói ở trên.

3.2.3. Mô tả input, output

Đồ thị được cho ở dạng danh sách cung mặt khác để thuận lợi khi nhập

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

dữ liệu chúng ta sẽ cho input trong các file text. Cụ thể:

59

Input: Được cho trong file text có tên là TSP.INP có dạng như sau:

Dòng đầu là 4 số nguyên dương N, M, s, k, trong đó N là số đỉnh, M là số

cung của đồ thị, s là đỉnh xuất phát còn K là số đỉnh cho trước phải đi qua. M

dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương u, v, l với ý nghĩa có cung từ

u đến v có độ dài (trọng số) là l. Dòng cuối cùng ghi k số nguyên dương phân

biệt là tên các đỉnh cần phải đi qua.

Output: Kết quả ghi ra file text có tên TSP.OUT có dạng như sau:

Dòng đầu là một số nguyên T là độ dài đường đi ngắn nhất tìm được.

Các dòng sau ghi số hiệu các đỉnh của đường đi ngắn nhất xuất phát từ s thỏa

mãn yêu cầu của bài toán.

3.2.4. Thuật toán tổng quát giải bài toán 2

Thuật toán tổng quát giải bài toán 2 gồm hai bước cơ bản sau:

Bước 1: Xây dựng đồ thị G1 = (V1, E1) như sau:

V1 gồm k +1 đỉnh của đồ thị đã cho là s và k đỉnh cố định phải đi qua

theo yêu cầu của bài toán.

E1 được xây dựng như sau: Hai đỉnh i, j thuộc E1 thì trọng số của cung (i,

j) là C(i,j) = D(i,j), trong đó D(i,j) là khoảng cách từ i đến j trên đồ thị G đã cho.

Để cha ̣y đươ ̣c vớ i N, M lớ n ta sẽ dùng Dijkstra Fibonacci heap để tính D(i, j).

Bước 2: Dùng thuật toán ACO (MMAS) tìm chu trình xuất phát từ s đi

qua mỗi đỉnh đúng một lần trên đồ thị G1 (việc làm này chính là giải bài toán

người chào hàng trên đồ thị G1).

3.2.5. Một số hàm và thủ tục trong chương trình

Chương trình sử dụng thuật toán Dijkstra Fibonacci heap nên các thủ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

tục thực hiện các thao tác đối với Fibonacci heap như đã trình bày trong mục

60

3.1.5 cũng được sử dụng trong chương trình giải bài toán 2. Ngoài ra chương

trình còn sử dụng thêm một số thủ tục sau:

Thủ tục Make_graph: Xây dựng đồ thị G1. Thủ tục này hoạt động

như sau: Từ mỗi đỉnh u trên đồ thị G1 ta dùng thủ tục Dijkstra Fibonacci heap

tìm khoảng cách từ đỉnh đó đến tất cả các đỉnh còn lại trên đồ thị G, từ đó ta

cũng tính được khoảng cách từ u đến các đỉnh trên G1.

procedure make_graph;

// input: Đồ thị G. Output: đồ thị G1.

var i:integer;

begin

for i:= 1 to k1 + 1 do

for j := 1 to k1 + 1 do c[i,j] := vocung;

for i := 1 to k1+1 do

begin

init(tendinh[i]);

dijkstra(tendinh[i]);

for j:= 1 to k1 + 1 do

if i = j then

c[i,j] := vocung

else c[i,j] := d[tendinh[j]]^.key;

end;

end;

Đoạn mã chương trình dưới đây mô tả thủ tục Make_graph:

Thủ tục tkcb: Thủ tục này dùng để tìm một chu trình trong G1 bằng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

thuật toán tham lam để làm cơ sở cho việc khởi tạo Tmax, Tmin.

61

Thủ tục lotteryweel(k : longint): Thủ tục này chính là Thủ tục chọn

ngẫu nhiên đã trình bày ở chương 2, thủ tục này cho phép xác định đỉnh kế

tiếp sẽ đi khi một con kiến đang ở đỉnh k.

Thủ tục pheromoneupdat: Cập nhật lại vết mùi như đã trình bày ở

chương 2.

Thủ tục init1: Khởi tạo vết mùi và giá trị ban đầu cho một số đại lượng.

Thủ tục MMAS_cycle: Thủ tục này dùng để tìm chu trình ngắn nhất

trong G1, xuất phát từ s thỏa mãn yêu cầu của bài toán. Đoạn mã nguồn dưới

procedure MMAS_cycle;

var l: int64;d : longint; s:real;

Begin

init1;

repeat

inc(buoclap);

for i:= 1 to m do

begin

libest := vocung;

w[1] :=1;

fillchar(daxet,sizeof(daxet),false);

fillchar(p,sizeof(p),0);

daxet[1] := true;

l:= 0;

for j:= 2 to n do

begin

lotteryWheel(j);

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

đây mô tả thủ tục MMAS_cycle:

62

l := l + c[w[j-1],w[j]];

end;

l := l + c[w[n],1];

if l< libest then

begin

libest := l;

ibest := w;

end;

end;

if libest < lgbest then

begin lgbest := libest;

gbest := ibest;

tmax:= m/lgbest;

tmin:= tmax/10;

end;

pheromoneupdat;

until (buoclap >= N_C);

End;

3.2.6. Sơ đồ tổng quát của thuật toán giải bài toán 2.

Begin

Enter;

Make_graph;

MMAS_cycle;

PrintResult;

End.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

63

3.2.7. Các kết quả thực nghiệm giải bài toán 2

Thực nghiệm tiến hành trên 3 bộ test, mỗi bộ test được chương trình thực

hiện 06 lần. Mỗi lần thực hiện, chương trình sẽ tự động khởi tạo lại cường độ vết

mùi nếu qua 10000 vòng lặp mà độ dài G-best không thay đổi. Kết quả được

thống kê trong bảng 3.2. Trong bảng 3.2: N là số đỉnh (nút giao thông), M là số

cung (số các đường một chiều nối trực tiếp hai nút giao thông), K là số nút giao

thông buộc phải đi qua, NC là số vòng lặp trong vòng repeat, X, Y hiểu như

trong công thức (2.1), SK là số kiến tham gia tìm lời giải.

Tên test

N

M

K

NC

X Y SK

ĐỘ DÀI ĐƯỜNG ĐI

1000 10994 21 200000

1

2 15

Test00

1000 10994 21

10000

1 16 15

1000 10994 21 200000

1 16 15

1000 10994 41 400000

1

2 20

Test01

1000 10994 41 400000

1

6 20

1000 10994 41 400000

1 12 20

1200 26181 51

1

1

2 25

Test02

1200 26181 51 100000

1

2 25

1200 26181 51 400000

1

2 25

116793, 118358, 117187, 116778, 116458, 116587 111766, 111968, 111415, 111944, 112052,112147 106916, 108236, 106410, 106270, 105933, 106936 208911, 208911, 208911, 208911, 208911, 208911 208911, 208911, 208911, 208911, 208911, 208911 208819, 204349, 208911, 202159, 208766, 207800 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549, 119549,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

Bảng 3.2. Thống kê kết quả thực nghiệm chương trình giải bài toán 2

64

Dưới đây là kết quả chụp lại màn hình trong một lần chạy thử

chương trình với bộ test00:

Thống kê kết quả ở bảng 3.2 cho ta một số nhận xét sau:

+ Thuật toán luôn có tính hội tụ (số vòng lặp càng nhiều thì lời giải thu

được càng có xu hướng tốt hơn (test00, test01).

+ Khi độ dài G-best lớn làm cho Tmin, Tmax rất bé, vì thế mùi ở đa số các

cung nhanh chóng giảm về Tmin, do đó nếu tỉ lệ giữa Y và X nhỏ thì khả năng

tìm được lời giải tốt hơn G-best hiện có là rất khó, do đó khả năng hội tụ rất

chậm. Ví dụ ở test00 khi y = 2, x = 1 số vòng lặp lên đến 200000 nhưng kết

quả vẫn không tốt bằng khi cho y = 16, x = 1 mà số vòng lặp chỉ là 10000.

Hay như ở test01: Khi x = 1, y = 2 hoặc y = 6, kết quả cho thấy G-best không

thay đổi khi số vòng lặp lên tới 400000 (khi số vòng lặp = 1 kết quả vẫn như

vậy), tuy nhiên khi tăng y lên 12 thì thu được G-best tốt hơn như đã thấy.

Tác giả đề xuất một cách khắc phục tình trạng độ dài G-best quá lớn là

co độ dài G–best theo một hệ số c với c là một tham số. Tuy nhiên vấn đề này

cần được nghiên cứu kỹ thêm nữa.

+ Khi số đỉnh trong G1 lớn, do G1 là đồ thị đầy đủ nên số cung rất lớn

nên số cách đi cũng rất lớn, dẫn đến khả năng tìm được đường đi tốt hơn G-

best hiện có là rất thấp nếu thủ tục tkcb dùng thông tin heuristic mạnh tìm

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

được lời giải ban đầu tốt. Kết quả ở test02 thể hiện điều này.

65

Các tệp input trong các test thử nghiệm chương trình này được tạo ngẫu

nhiên theo thuật toán sau:

- N, M, s, K nhập từ bàn phím.

- Xây dựng ma trận trọng số c của đồ thị G như sau: Ban đầu c[i,j] := 0

 i, j = 1.. N. Thực hiện M lần tìm cặp số nguyên dương ngẫu nhiên u, v thỏa

mãn 1 ≤ u ≠ v ≤ N và c[u,v] = 0 (dùng vòng lặp repeat để tìm cặp u, v). Với

mỗi cặp (u,v) như vậy ta gán cho c[u,v] một trọng số dương nào đó bằng hàm

random.

- Để đảm bảo đồ thị liên thông mạnh, xuất phát từ đỉnh 1 ta duyệt một

vòng qua tất cả các đỉnh theo thứ tự tăng dần rồi quay về 1, nếu c[i, i+1] = 0

thì c[i, i +1] được gán cho một trọng số không âm (thường là khá lớn để các

cung này ít khả năng được chọn) và tăng M lên 1 đơn vị, làm tương tự với

cung (N, 1).

- Dựa vào ma trận trọng số c vừa xây dựng, in ra tệp input biểu diễn đồ

thị G ở dạng danh sách cạnh.

3.3. Kết luận chương

Chương 3 của luận văn đã áp dụng thuật toán Dijkstra Fibonacci heap

và thuật toán MMAS để giải quyết hai bài toán có nhiều ứng dụng trong thực

tế đó là bài toán tìm đường đi ngắn nhất giữa hai điểm trên mạng giao thông

và bài toán TSP mở rộng. Với bài toán tìm đường đi ngắn nhất, khi áp dụng

Dijkstra Fibonacci heap thì hiệu quả hơn rất nhiều so với khi áp dụng thuật

toán Dijkstra nguyên thủy. Trong trường hợp số đỉnh lớn và đồ thị thưa

chương trình áp dụng Dijkstra Fibonacci heap có thể chạy nhanh hơn hàng

trăm lần.

Đối với bài toán TSP mở rộng nếu tìm lời giải chính xác thì ta phải xét

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

tất cả các hoán vị của k +1 nên độ phức tạp của thuật toán là (k +1)!. Vì vậy

66

chương trình chỉ có thể thực hiện với k nhỏ cỡ vài chục. Khi áp dụng thuật

toán MMAS, tuy kết quả chỉ là gần đúng nhưng chương trình có thể thực hiện

được với k lên đến hàng nghìn. Khi kết hợp cả MMAS và Dijkstra Fibonacci

heap thì ở phần xây dựng đồ thị G1 độ phức tạp chỉ là O(k  (n log n +m)),

còn nếu dùng thuật toán khác như thuật toán Floyd thì độ phức tạp là O(k n3)

hoặc nếu dùng thuật toán Dijkstra bình thường thì độ phức tạp là O(kn2). Vì

vậy khi đồ thị thưa thì việc dùng Dijkstra Fibonacci heap cũng giúp nâng cao

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

hiệu quả của thuật toán rất nhiều.

67

KẾT LUẬN

Đề tài đã trình bày, ứng dụng hai thuật toán tìm đường đi tối ưu:

- Thuật toán Dijkstra Fibonacci heap tương đối 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. Điểm mấu chốt của Fibonacci heap là nó trì hoãn một số thao tác

chưa cần thực hiện khi còn có thể, mục đích của việc này là nhằm chờ đến lúc

buộc phải thực hiện các công việc đã trì hoã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. Mặt khác, nếu số lượng

các cây trong một Fibonacci heap không lớn thì có thể nhanh chóng xác định

nút cực tiểu mới bằng thủ tục EXTRACT_MIN. Luận văn đã ứng dụng thành

công Dijkstra Fibonacci heap vào việc giải bài toán tìm đường đi ngắn nhất

trên mạng giao thông, hiệu quả của nó đã được trình bày trong chương 3.

- Thuật toán ACO là thuật toán tối ưu gần đúng, tuy nhiên nó có thể

được ứng dụng để giải quyết các bài toán thực tiễn một cách hiệu quả. Thuật

ACO kết hợp thông tin heuristic và thông tin về cường độ vết mùi nhờ mô

phỏng hoạt động của đàn kiến có các ưu điểm nổi trội sau: Việc tìm kiếm

ngẫu nhiên dựa trên các thông tin heuristic cho phép tìm kiếm linh hoạt và

mềm dẻo trên miền rộng hơn thuật toán heuristic sẵn có, do đó cho ta lời giải

tốt hơn và có thể tìm được lời giải tối ưu. Việc sử dụng thông tin về cường độ

vết mùi cho phép ta từng bước thu hẹp không gian tìm kiếm mà vẫn không

loại bỏ các lời giải tốt, do đó nâng cao chất lượng thuật toán.

Đề tài đã sử dụng kết hợp hai thuật toán Dijkstra Fibonacci heap và

ACO (MMAS) giải quyết thành công bài toán TSP mở rộng - đây là một bài

toán thường hay gặp trong thực tế. Quá trình thực nghiệm chương trình giải

quyết bài toán này đã cho chương trình chạy thử trên 03 bộ test, các kết quả

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

nhận được cho thấy thuật toán dùng trong chương trình là hiệu quả.

68

Hướng phát triển của đề tài: Việc nghiên cứu các cấu trúc dữ liệu trừu

tượng và ứng dụng chúng để cải tiến các thuật toán, việc tìm tòi nâng cấp các

thuật toán, ứng dụng các thuật toán mới vào việc giải quyết các bài toán thực

tiễn là những vấn đề đang được nhiều người quan tâm. Trong khuôn khổ của

một luận văn nên đề tài này mới chỉ nghiên cứu một cấu trúc dữ liệu trừu

tượng là Fibonacci heap và ứng dụng để cải tiến thuật toán Dijkstra tìm đường

đi tối ưu. Về thuật toán tối ưu đàn kiến cũng mới dừng lại ở những nghiên cứu

ứng dụng ban đầu. Trong tương lai đề tài này có thể được mở rộng nghiên

cứu sâu rộng hơn về các cấu trúc dữ liệu trừu tượng và các ứng dụng của

chúng. Thuật toán tối ưu đàn kiến là thuật toán tương đối mới, quy tắc cập

nhật mùi quyết định lớn đến hiệu quả của thuật toán, vì thế đề tài cũng có thể

được phát triển theo hướng nghiên cứu xây dựng các quy tắc cập nhật mùi

mới tốt hơn và ứng dụng thuật toán này vào việc giải quyết một số các bài

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn

toán trong các lĩnh vực như sinh học, tin học, điện điện tử ...

69

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Đỗ Đức Đông (2012), Phương pháp tối ưu đàn kiến và ứng dụng - Luận án tiến

sĩ công nghệ thông tin, Trường đại học công nghệ - Đại học Quốc gia Hà Nội.

[2] Đỗ Xuân Lôi (1995), Cấu trúc dữ liệu và giải thuật, Nhà xuất bản khoa học và

kỹ thuật.

[3] Nguyễn Đức Nghĩa, Nguyễn Tô Thành (1997), Toán rời rạc, Nhà xuất bản giáo

dục.

Tiếng Anh

[4] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest (1990),

Introduction to Algorithms, Cambridge, Massachusetts.

[5] Marco Dorigo and Thomas Stutzle (2004), Ant Colony Optimization,The MIT

Press,Cambridge, Masachusetts.

[6] MIHAEL L. FREDMAN, ROBERT ENDRE TARJAN (1987), Fibonacci

Heaps and Their Uses in Improved Network Optimization Algorithms.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn