ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
THÔNG TIN VÀ TRUYỀN THÔNG

LÊ THÁI HÒA

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN
TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ

LUẬN VĂN THẠC SĨ KHOA HỌC

Thái Nguyên - Năm 2015


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
THÔNG TIN VÀ TRUYỀN THÔNG

LÊ THÁI HÒA

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN
TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. ĐỖ ĐỨC ĐÔNG

Thái Nguyên - Năm 2015

và cũng là người đã cung cấp cho em bộ dữ liệu để em thử nghiệm trong
bài luận văn này.
Cuối cùng, em xin chân thành cảm ơn sự quan tâm giúp đỡ của gia
đình, bạn bè và tập thể lớp Cao học K12I đã cổ vũ động viên em hoàn
thành tốt luận văn của mình.

Thái nguyên, ngày 23 tháng 7 năm 2015
Học viên Lê Thái Hòa


iii

MỤC LỤC
LỜI CAM ĐOAN ....................................................................................... i
LỜI CẢM ƠN ............................................................................................ ii
MỤC LỤC ................................................................................................ iii
Danh mục các ký hiệu và chữ viết tắt ......................................................... v
Danh mục các bảng .................................................................................. vii
Danh mục các hình .................................................................................. viii
MỞ ĐẦU ................................................................................................... 1
Chương 1. BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT
ĐỒ THỊ ...................................................................................................... 3
1.1. Bài toán tối ưu tổ hợp tổng quát ....................................................... 3
1.2. Bài toán tìm tập thống trị nhỏ nhất của một đồ thị (MWDSP) .......... 5
1.3. Các cách tiếp cận hiện nay giải quyết bài toán tìm tập thống trị nhỏ
nhất của đồ thị ......................................................................................... 5
1.3.1. Thuật toán tham lam tìm tập phủ đỉnh nhỏ nhất. ......................... 5
1.3.2. Thuật toán tham lam 1 (Greedy1) ............................................... 6
1.3.2. Thuật toán tham lam 2 (Greedy2) ............................................... 9
1.4. Một số ứng dụng trong thực tế về bài toán MWDSP ...................... 10

3.4. Kết luận chương ............................................................................. 48
KẾT LUẬN .............................................................................................. 49
TÀI LIỆU THAM KHẢO ........................................................................ 51


v

Danh mục các ký hiệu và chữ viết tắt
Kí hiệu và
chữ viết tắt

Ý nghĩa
Cận trên của vết mùi
Cận giữa của vết mùi
Vết mùi được khởi tạo ban đầu
Vết mùi trên cạnh
Vết mùi trên đỉnh



Thông tin heuristic trên cạnh



Thông tin heuristic trên đỉnh
Số vòng lặp trong thuật toán ACO
Số kiến sử dụng trong thuật toán ACO
Tham số bay hơi

3-LAS


MMAS

Max-Min Ant System (Hệ kiến Max Min)

MWDSP

Bài toán tìm tập thống trị nhỏ nhất của đồ thị

SMMAS

Smoothed Max-Min Ant System (Hệ kiến Max Min
trơn)

TSP

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


vii

Danh mục các bảng
Trang
Bảng 2.1: Thuật toán ACO theo thứ tự thời gian xuất hiện……….. 26
Bảng 3.1: Kết quả thực nghiệm trên bộ dữ liệu 1 với kích thước
nhỏ…………………………………………………………………. 44
Bảng 3.2: Kết quả thực nghiệm trên bộ dữ liệu 2 với kích thước
nhỏ…………………………………………………………………. 45
Bảng 3.3: Kết quả thực nghiệm trên bộ dữ liệu 1 với kích thước
lớn…………………………………………………………………. 46

15

Hình 2.3: Thí nghiệm bổ xung……………………………………...

16

Hình 2.4: Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm
)………………………………………………………...

20

Hình 2.5: Thuật toán ACO…………………………………………

21

( ,…,

Hình 2.6: Thuật toán ACO giải bài toán TSP có sử dụng tìm kiếm
cục bộ………………………………………………………………

25

Hình 3.1: Thuật toán cập nhật mùi SMMAS cho bài toán MWDSP

42


1

MỞ ĐẦU

cạnh khác nhau, các chức năng phân phối trọng số trên các đỉnh khác nhau
để thấy được hiệu quả của thuật toán đề xuất so với một số thuật toán đang
được sử dụng.


3

Chương 1. BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA
MỘT ĐỒ THỊ

Trong các bài toán thực tế cũng như trong lý thuyết, ta thường phải
tìm các giá trị cho các biến rời rạc để cực trị hàm mục tiêu nào đó. Các bài
toán này thường dễ phát biểu nhưng lại khó giải do chúng thuộc loại tối ưu
tổ hợp (TƯTH) NP - khó. Chương này giới thiệu các bài toán tối ưu tổ hợp
dưới dạng tổng quát, bài toán tìm tập thống trị nhỏ nhất và các cách tiếp
cận hiện nay.
1.1. Bài toán tối ưu tổ hợp tổng quát
Trong đời sống thực tế ta thường phải giải quyết nhiều bài toán
TƯTH quan trọng. Chẳng hạn như: tìm đường đi ngắn nhất nối hai điểm
trên một đồ thị đã cho, lập kế hoạch phân phối nguồn hàng tới nơi tiêu thụ
với chi phí cực tiểu, lập thời khóa biểu cho giáo viên và học sinh thuận lợi
nhất, định tuyến cho các gói dữ liệu trong Internet, lập lịch hợp lý cho các
hệ thống sản xuất, đối sánh các chuỗi gen trong sinh học phân tử v.v…
Mỗi bài toán TƯTH ứng với một bộ ba ( S , f , W) trong đó:
- S là tập hữu hạn trạng thái (lời giải tiềm năng hay phương án);
- f là hàm mục tiêu xác định trên ;
- W là tập các ràng buộc.
Mỗi phương án s  S thỏa mãn các ràng buộc W gọi là phương án trả
lời (hay lời giải). Mục đích của ta là tìm phương án chấp nhận được s* tối
ưu hóa toàn cục hàm mục tiêu , tức là một phương án s* tốt nhất. Chẳng

∈

∀ . Khi đó, mỗi phương án

định nhờ ít nhất một vectơ trong
2) Tồn tại tập con
rỗng với mọi
nào đó của
3) Từ

có độ dài không quá

của

được xác

từ

lên

( ) không

sao cho

có thể xây dựng được từ tập con

nhờ thủ tục mở rộng tuần tự dưới đây.

ta mở rộng tuần tự thành



iii) Áp dụng thủ tục mở rộng từ các phần tử
được mọi phần tử của

∈

> là mở rộng được và chưa thuộc

ràng buộc W, xác định tập con (
thì

=

.

và ánh xạ

∈ , trong đó tập

trong

:

∈

cho phép ta xây dựng

.

Như vậy, mỗi bài toán TƯTH được xem là một bài toán cực trị hàm

và
trong tập

là các vectơ
,

là tập

- chiều, trong đó thành phần

còn

nhận giá trị

là tập các vectơ thỏa mãn các ràng buộc W.

1.2. Bài toán tìm tập thống trị nhỏ nhất của một đồ thị (MWDSP)
= { , } trong đó

Cho một đồ thị vô hướng
cạnh của đồ thị. Với mỗi đỉnh
Một tập thống trị của
\

∈

là tập đỉnh,

có gắn một trọng số


- Tập các đỉnh đã được chọn vào làm kết quả là các đỉnh tô màu đen
( ).
- Tập các đỉnh không thuộc
gọi là các đỉnh tô màu xám ( ).

nhưng kề với ít nhất một đỉnh thuộc


6

- Các đỉnh còn lại là các đỉnh chưa được phủ gọi là đỉnh tô màu trắng
( ).
Trong tài liệu [4] người ta đưa ra ý tưởng như sau: Tại mỗi lần lặp
ta kết nạp thêm một đỉnh mới thuộc

hoặc

Việc ưu tiên chọn đỉnh nào đó kết nạp vào
(

vào

cho đến khi

= .

được xác định bởi giá trị của

là những đỉnh trắng kề với ).
Thuật toán được mô ta như sau:

cạnh màu đen sẽ được tô thành màu xám.
Như vậy sau khi ta kết nạp được
đổi thành

( ,

đỉnh vào

thì đồ thị được biến

). Khi đó trọng số của cạnh của đồ thị

được biểu

diễn như sau:
(, )

=

(

( , ))

(1.1)


7

Lưu ý



dựa trên hai tiêu chí:

+ Số lượng đỉnh màu trắng kề với nó càng nhiều càng tốt.
+ Trọng số của đỉnh đó càng nhỏ càng tốt.
Phép cộng 1 vào tử số để đảm bảo được việc so sánh giữa các đỉnh
không còn kết nối nữa, tức là những đỉnh cô lập (khi đó ta sẽ chọn đỉnh nào
có trọng số nhỏ hơn).
Theo công thức (1.3) ta thấy rằng khi đồ thị

chỉ gồm các đỉnh cô

lập thì việc lựa chọn đỉnh nào chỉ phụ thuộc vào trọng số của nó chứ không
phân biệt đỉnh đó đã được phủ hay chưa. Tức là có thể chọn thêm vào kết
quả đỉnh đã được tô màu xám mà không kề với bất kỳ đỉnh màu trắng nào.

A

1

C

B

5

Một ví dụ về đồ thị làm cho Greedy1 sai kết quả.

6


làm kết quả là đỉnh B, sau đó mới chọn đỉnh C. Kết quả cuối cùng bằng
W[A] + W[B] + W[C] = 1 + 5 + 6 = 12. (kết quả này sai so với kết quả
thực tế).
Ta có thể cải tiến thuật toán này bằng cách thêm vào đồ thị ban đầu
những cạnh khuyên ( , ) với 1 ≤ ≤ . Khi đó nếu một đỉnh màu xám
nằm cô lập (đã được phủ bởi đỉnh khác) thì giá trị

của nó sẽ bằng

không, trong khi một đỉnh màu trắng nằm cô lập thì giá trị

của nó lại

bằng 1. Vì vậy ta không cần cộng thêm 1 vào tử số, đồng thời tránh được
sai sót như trong ví dụ trên (cải tiến này được minh họa trong chương 3
bằng thuật toán Greedy1_new). Khi đó công thức (1.3) sẽ được biến đổi

γ =

như sau:
[]

()

(1.4)

()

0;
1 to


( ) (

∑( , )∈
( )

()

( , ))

(1.5)

Cũng tương tự như thuật toán trước, tại công thức (1.5) giả sử đồ thị
chỉ gồm các đỉnh thuộc W và R (màu trắng và màu xám) nằm cô lập.
Lúc đó

( ) = 0 với mọi , làm cho 

= 0 như vậy sẽ không có tiêu

chí để chọn lựa đỉnh nào là đỉnh tiếp theo kết nạp vào kết quả. Trên thực tế
ta thấy việc chọn những đỉnh màu xám không có ý nghĩa gì mà chỉ làm xấu
đi kết quả. Vì vậy, để thuật toán tốt hơn ta vẫn phải thêm vào đồ thị ban
đầu những cạnh ( , ) với 1 ≤ ≤ . Do đó ta có thể sửa công thức (1.5)
thành công thức sau:


=

( ) ∑( , )∈

do

If kề và là đỉnh mầu trắng then
{
[]
[]

[ ] + 1;
[ ]+

[ ];

}
 =

[ ] [ ]
[ ]

;

Hình 1.4: Thuật toán tính  [ ] trong Greedy2_new.
1.4. Một số ứng dụng trong thực tế về bài toán MWDSP
Đa số các bài toán về đồ thị đều được áp dụng rộng rãi trong thực tế,
bài toán MWDSP cũng không ngoại lệ, có thể đưa ra một số ứng dụng cụ
thể như sau:
Ứng dụng 1: Ứng dụng trong việc chọn địa điểm để xây dựng cột phát
sóng điện thoại. Giả sử một công ty viễn thông muốn phát sóng điện thoại
di động cho tất cả

ngôi làng, do địa hình phức tạp nên khi xây dựng cột

1.5. Kết luận chương
Các bài toán TƯTH ( , , W ) nhằm tìm cực trị hàm

trên tập hữu

hạn trạng thái , thỏa mãn ràng buộc W , có vai trò quan trọng trong nghiên
cứu lý thuyết và ứng dụng. Đa số các bài toán trong chúng thuộc loại NPkhó, khi đó với các bài toán cỡ lớn thì không giải đúng được. Đã có nhiều
phương pháp để giải quyết được đề xuất, trong đó các phương pháp giải
gần đúng với các kỹ thuật bổ trợ như tìm kiếm cục bộ, memetic đang được
sử dụng rộng rãi.
Bài toán tìm tập thống trị nhỏ nhất của đồ thị là một bài toán NP–khó
với không gian bài toán là 2 (với

là số đỉnh của đồ thị). Bài toán có

nhiều ý nghĩa về mặt khoa học cũng như ứng dụng trong thực tế.
Có nhiều ý tưởng tham lam để giải quyết bài toán tìm tập thống trị
nhỏ nhất của đồ thị tuy nhiên các chiến lược tham lam này cho kết quả còn
sai lệnh nhiều so với kết quả thực tế của bài toán. Việc nghiên cứu cách


12

giải bài toán trên để đạt kết quả tốt hơn là một lĩnh vực được nhiều nhà
khoa học trong nước và thế giới quan tâm.


13

Chương 2. PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN

kiến tìm được đường đi ngắn nhất từ tổ đến nguồn thức ăn và sau đó quay
trở tổ của mình.
Thí nghiệm trên cây cầu đôi
Có rất nhiều nghiên cứu để tìm hiểu hành vi của loài kiến đã được
tiến hành, một trong những thí nghiệm nổi tiếng nhất là thí nghiệm của
Deneubourg và các cộng sự của ông năm 1989, thí nghiệm này là cơ sở lý
thuyết đầu tiên và cũng tạo ra ý tưởng cho thuật toán ACO mà Dorigo đưa
ra sau này.
Họ đã thực nghiệm với tỉ lệ độ dài đường r =
nhau của chiếc cầu đôi, trong đó

giữa hai nhánh khác

là độ dài của nhánh dài còn

là độ dài

của nhánh ngắn.
Trong thực nghiệm thứ nhất, chiếc cầu đôi có hai nhánh bằng nhau (r
= 1, hình 2.1.a). Ban đầu, kiến lựa chọn đường đi một cách tự do từ tổ đến
nguồn thức ăn, cả hai nhánh đều có kiến đi, nhưng sau một thời gian các
con kiến này tập trung đi theo cùng một nhánh. Kết quả có thể được giải
thích như sau: ban đầu không có vết mùi nào trên cả hai nhánh, do đó kiến
lựa chọn nhánh bất kỳ với xác suất như nhau. Một cách ngẫu nhiên, sẽ có
một nhánh có số lượng kiến lựa chọn nhiều hơn nhánh kia. Do kiến để lại
vết mùi trong quá trình di chuyển, nhánh có nhiều kiến lựa chọn sẽ có nồng
độ mùi lớn hơn nồng độ mùi của nhánh còn lại. Nồng độ mùi trên cạnh lớn
hơn sẽ ngày càng lớn hơn vì ngày càng có nhiều kiến lựa chọn. Cuối cùng,
hầu như tất cả các kiến sẽ tập trung trên cùng một nhánh. Thực nghiệm này
cho thấy là sự tương tác cục bộ giữa các con kiến với thông tin gián tiếp là