Tóm tắt Luận án Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất

BỘ GIÁO DỤC VÀ ĐÀO TẠO 
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI 
PHAN TẤN QUỐC 
CÁC THUẬT TOÁN GẦN ĐÚNG GIẢI BÀI TOÁN 
CÂY KHUNG VỚI CHI PHÍ ĐỊNH TUYẾN NHỎ NHẤT 
Chuyên ngành: Khoa học máy tính 
Mã số: 62480101 
TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH 
Hà Nội –2015 
Công trình được hoàn thành tại: 
Trường Đại học Bách khoa Hà Nội 
Người hướng dẫn khoa học: 
PGS.TS. Nguyễn Đức Nghĩa 
Phản biện 1: PGS.TS. Nguyễn Xuân Hoài 
Phản biện 2: TS. Nguyễn Đức Dũng 
Phản biện 3: TS. Hoàng Tuấn Hảo 
Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ 
cấp Trường họp tại Trường Đại học Bách khoa Hà Nội 
Vào hồi .. giờ, ngày .. tháng .. năm  
Có thể tìm hiểu luận án tại: 
1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 
2. Thư viện Quốc gia Việt Nam 
1 
MỞ ĐẦU 
Tối ưu hóa mạng liên quan đến nhiều lĩnh vực như toán ứng dụng, 
khoa học máy tính, vận trù học, kỹ thuật, mạng truyền thông, 
Nhiều bài toán thực tế trong lĩnh vực mạng truyền thông, chẳng hạn 
như các bài toán Optimal Communication Spanning Trees, Steiner 
Minimal Trees, Bounded Diameter Minimum Spanning Trees - 
BDMST, Minimum Routing Cost Spanning Trees thuộc lớp bài toán 
NP-khó hoặc NP-đầy đủ. 
Minimum Routing Cost Spanning Trees-MRCST là một bài toán tối 
ưu đồ thị nổi tiếng và có nhiều ứng dụng quan trọng trong lĩnh vực 
mạng truyền thông và trong tin sinh học. Bài toán này lần đầu tiên 
được giới thiệu bởi T. C. Hu vào năm 1974 qua công trình 
“Optimum communication spanning trees”. 
Mô hình toán học của bài toán MRCST có thể phát biểu như sau: 
Cho G là một đồ thị vô hướng liên thông có chi phí định tuyến 
không âm trên cạnh. Giả sử T là một cây khung của G. Chi phí định 
tuyến cho mỗi cặp đỉnh trên T được định nghĩa là tổng các chi phí 
định tuyến trên các cạnh của đường đi đơn nối chúng trên T và chi 
phí định tuyến của T được định nghĩa là tổng của tất cả các chi phí 
định tuyến giữa mọi cặp đỉnh của T. Bài toán MRCST đặt ra là tìm 
một cây khung có chi phí định tuyến nhỏ nhất trong số tất cả các 
cây khung của G. Bài toán MRCST đã được chứng minh thuộc lớp 
bài toán NP-khó. 
Việc đề xuất thuật toán dạng metaheuristic giải bài toán MRCST có 
ý nghĩa quan trọng, một mặt, nhằm giải quyết những bài toán ứng 
dụng thực tiễn vừa nêu; mặt khác, còn là cơ sở để giải quyết những 
bài toán cây khung tối ưu dạng NP-khó khác trên đồ thị. 
Bài toán MRCST đã thu hút được sự quan tâm nghiên cứu của nhiều 
nhà khoa học trong hơn bốn mươi năm qua. Hiện nay đã có hàng 
loạt thuật toán giải bài toán MRCST được đề xuất theo các hướng: 
tìm lời giải đúng, tìm lời giải gần đúng cận tỉ lệ, heuristic, 
metaheuristic. 
Mục đích của luận án là phát triển một số thuật toán gần đúng dạng 
metaheuristic giải bài toán MRCST cho chất lượng lời giải tốt hơn 
so với các thuật toán có cùng cỡ thời gian tính hoặc đòi hỏi thời 
gian tính ít hơn khi so sánh với các thuật toán có chất lượng lời giải 
2 
tương đương hoặc đưa ra lời giải tốt nhất mới cho một số bộ dữ liệu 
thực nghiệm chuẩn. 
Các kết quả nghiên cứu của luận án đã được công bố ở 4 bài báo tạp 
chí và 2 bài báo hội nghị chuyên ngành. 
Luận án được trình bày trong 5 chương. 
Luận án đã phân tích được ưu nhược điểm của từng thuật toán đối 
với từng loại dữ liệu thực nghiệm cụ thể và qua đó định hướng 
phạm vi áp dụng cho từng thuật toán đề xuất. 
Phụ lục của luận án ghi nhận kết quả thực nghiệm của các công 
trình nghiên cứu liên quan cho đến thời điểm hiện tại. 
Chương 1. TỔNG QUAN 
Chương này giới thiệu tổng quan về bài toán MRCST, các ứng dụng 
của bài toán MRCST, khảo sát các thuật toán giải bài toán MRCST, 
các tiêu chí đánh giá chất lượng một thuật toán giải gần đúng và hệ 
thống dữ liệu thực nghiệm chuẩn được sử dụng cho bài toán 
MRCST. 
1.1.BÀI TOÁN MRCST 
1.1.1.Một số định nghĩa 
Cho G = (V(G), E(G)) là một đồ thị vô hướng, liên thông, có trọng 
số không âm trên cạnh; trong đó V(G) là tập gồm n đỉnh, E(G) là 
tập gồm m cạnh, w(e) là trọng số của cạnh e, e E(G). 
Định nghĩa 1.1 (Chi phí định tuyến giữa một cặp đỉnh). Cho T = 
(V(T), E(T)) là một cây khung của G, trọng số trên cạnh e được hiểu 
là chi phí định tuyến của cạnh e, ta gọi chi phí định tuyến (routing 
cost) của một cặp đỉnh (u,v) trên T, ký hiệu là dT(u,v), là tổng chi 
phí định tuyến của các cạnh trên đường đi đơn (duy nhất) nối đỉnh u 
với đỉnh v trên cây T. 
Định nghĩa 1.2 (Chi phí định tuyến của một cây khung). Cho T = 
(V(T), E(T)) là một cây khung của G, chi phí định tuyến của T, ký 
hiệu là C(T), là tổng chi phí định tuyến giữa mọi cặp đỉnh thuộc cây 
T, tức là: 
, ( )
( ) ( , ).T
u v V T
C T d u v
 
 (1-1) 
Bài toán MRCST: Cho đồ thị G được định nghĩa như trên, bài toán 
đặt ra là trong số tất cả các cây khung của đồ thị G cần tìm một cây 
khung có chi phí định tuyến nhỏ nhất. 
3 
Bài toán này được đặt tên là bài toán cây khung với chi phí định 
tuyến nhỏ nhất (Minimum Routing Cost Spanning Tree-MRCST). 
Bài toán MRCST đã được chứng minh thuộc lớp bài toán NP-khó. 
Định nghĩa 1.3 (Tải định tuyến một cạnh của cây khung) Cho T = 
(V(T), E(T)) là một cây khung của đồ thị G. Nếu loại khỏi cây T 
một cạnh e thì T sẽ được tách ra thành hai cây con T1 và T2 với hai 
tập đỉnh tương ứng là V(T1) và V(T2). Ta gọi tải định tuyến của cạnh 
e, ký hiệu là l(T,e), là giá trị 2×V(T1) ×V(T2) . 
Từ định nghĩa, dễ thấy rằng tải định tuyến của cạnh e chính bằng số 
lượng đường đi trên cây T có chứa cạnh e. 
Định lý 1.1 sau cho ta cách tính chi phí định tuyến của cây khung 
thông qua tải định tuyến của các cạnh. 
Định lý 1.1. Cho T là một cây khung của G, ta có: 
 
)(
)(),()(
TEe
eweTlTC (1-2) 
và chi phí định tuyến của T có thể tính được trong thời gian O(n). 
1.1.2.Thuật toán tính chi phí định tuyến của cây khung 
Đây là thuật toán được đề cập trong tất cả công trình giải bài toán 
MRCST; ở đây chúng tôi trình bày thuật toán tính chi phí định tuyến 
của cây khung chi tiết hơn các công trình kể trên ở góc độ kỹ thuật. 
Algorithm 1.1. Thuật toán tính chi phí định tuyến của một cây 
khung 
RoutingCost(T) 
Đầu vào: Cây khung T được biểu diễn là cây có gốc tại v1 
Đầu ra: Chi phí định tuyến của cây khung T 
1. if (T = ) return + ; // Qui ước cây rỗng có chi phí + 
2. Thực hiện duyệt cây T theo chiều sâu (Depth First Search) bắt 
đầu từ đỉnh v1 ta thu được biểu diễn của T dưới dạng cây có gốc 
tại đỉnh v1. Gọi nu là số lượng đỉnh của cây con có gốc là u. Với 
mỗi đỉnh u của cây T, u v1, ký hiệu eu = (p(u), u); trong đó p(u) 
là cha của u trong cây T. 
3. C=0; 
4. for (mỗi đỉnh u V(T) {v1}) { 
5. l(eu) = 2 nu (n nu); 
6. C = C + l(eu) w(eu); 
7. } 
4 
8. return C; 
RoutingCost là thủ tục quan trọng được sử dụng trong tất cả các 
thuật toán giải bài toán MRCST. Các thuật toán giải bài toán 
MRCST thường xuyên thực hiện thao tác loại một cạnh của cây 
khung và sau đó thêm một cạnh khác sao cho kết quả thu được là 
một cây khung có chất lượng tốt hơn hoặc là thêm một cạnh vào 
cây khung và sau đó loại một cạnh trong chu trình vừa mới hình 
thành sao cho kết quả thu được là một cây khung có chất lượng tốt 
hơn; hai thao tác này mặc dù chỉ đem lại sự thay đổi nhỏ về mặt cấu 
trúc cây, nhưng để tính chi phí định tuyến của cây khung thu được 
sau mỗi thao tác trên vẫn đòi hỏi độ phức tạp O(n). 
1.1.3.Đánh giá chi phí định tuyến của cây khung 
Định lý 1.2. Giả sử T là một cây khung của đồ thị G. Khi đó với 
mọi cạnh e E(T) ta có: 
22( 1) ( , ) / 2.n l T e n (1-3) 
Từ định lý 1.1 và định lý 1.2 trên, chúng tôi đề xuất các hệ quả sau: 
Hệ quả 1.1. Chi phí định tuyến của cây khung T bất kỳ thỏa mãn 
bất đẳng thức sau: 
2 2
min max2( 1) ( ) ( 1) / 2,n w C T n n w (1-4) 
Trong 
đó min min{ ( ) : ( )}w w e e E G và max max{ ( ) : ( )}w w e e E G 
Hệ quả 1.2. Đối với đồ thị đầy đủ G với trọng số trên các cạnh đều 
là w0, ta có chi phí định tuyến của cây khung tối ưu là 
2(n−1)2w0 (1-5) 
1.2.ỨNG DỤNG 
Có thể tìm thấy các ứng dụng của bài toán MRCST trong các lĩnh 
vực mạng thiết kế mạng và tin sinh học. 
1.3.CÁC NGHIÊN CỨU LIÊN QUAN BÀI TOÁN MRCST 
Đối với bài toán thuộc lớp NP-khó như bài toán MRCST thì khó hy 
vọng tìm được một thuật toán vượt trội cả về chất lượng lời giải lẫn 
thời gian tính trên mọi bộ dữ liệu thực nghiệm. Do đó đã có nhiều 
thuật toán giải bài toán MRCST được đề xuất. Mỗi thuật toán giải 
bài toán MRCST, tại thời điểm công bố có một đóng góp nhất định, 
hoặc là cải thiện chất lượng lời giải, hoặc là cải thiện thời gian tính, 
5 
hoặc là đề xuất một cách tiếp cận mới cho chất lượng lời giải tương 
đương. 
Bảng 1.1. Danh sách các thuật toán giải bài toán MRCST hiện biết 
Thứ 
tự 
Tên gọi thuật toán Kiểu thuật toán 
Năm 
đề xuất 
1 Branch And Bound giải đúng 1979 
2 Branch And Bound + Column Generation giải đúng 2002 
3 Wong cận tỉ lệ 2 1980 
4 General Star cận tỉ lệ 4/3 1999 
5 Parallelized Approximation Algorithm cận tỉ lệ 4/3 2008 
6 PTAS cận tỉ lệ 1+ 1999 
7 Add heuristic 2005 
8 Campos heuristic 2008 
9 
ESCGA (thuật giải di truyền mã hóa 
cạnh) 
metaheuristic 
2005 
10 
BCGA (thuật giải di truyền mã hóa 
Prũfer) 
metaheuristic 
2005 
11 SHC (tìm kiếm leo đồi ngẫu nhiên) Metaheuristic 2005 
12 PBLS (tìm kiếm địa phương) metaheuristic 2008 
13 
PABC (thuật toán Artificial Bee 
Colony) 
Metaheuristic 
2011 
14 
ABC+LS (thuật toán Artificial Bee 
Colony + Local Search) 
metaheuristic 
2011 
15 Distributed Approximation Algorithm cận tỉ lệ 2 2014 
1.4.TIÊU CHÍ ĐÁNH GIÁ THUẬT TOÁN 
Chất lượng của một thuật toán gần đúng được đánh giá qua chất 
lượng lời giải và thời gian tính. 
Đối với lớp những thuật toán gần đúng cận tỷ lệ, có thể đánh giá 
đóng góp mới thông qua cận tỷ lệ của thuật toán. Tuy nhiên, đối với 
phần lớn các thuật toán gần đúng hiện nay, việc đánh giá tiên 
nghiệm chất lượng của lời giải mà chúng đưa ra là không thể thực 
hiện được. Trong tình huống này, các nhà khoa học chấp nhận giải 
pháp là đánh giá qua thực nghiệm. 
Để chứng tỏ thuật toán đề xuất của mình có những đóng góp mới để 
giải bài toán đặt ra, các nhà khoa học cần tiến hành thực nghiệm 
trên các bộ dữ liệu chuẩn để chỉ ra thuật toán của mình đề xuất so 
với những thuật toán hiện biết có những điểm tốt hơn hoặc ở tiêu 
chí thời gian, hoặc ở tiêu chí chất lượng lời giải, chẳng hạn: 
6 
 hoặc thuật toán đề xuất đòi hỏi thời gian ít hơn khi so với các 
thuật toán có cùng chất lượng lời giải tương đương, 
 hoặc thuật toán đề xuất cho lời giải với chất lượng tốt hơn so 
với các thuật toán có cùng cỡ thời gian tính, 
 hoặc thuật toán đề xuất đưa ra lời giải tốt nhất mới (new best 
solution) cho một số bộ dữ liệu trong bộ dữ liệu chuẩn, 
 hoặc tốt nhất, thuật toán đề xuất là tốt hơn mọi thuật toán hiện 
biết ở cả hai tiêu chí thời gian lẫn chất lượng lời giải đem 
lại, 
Trong lý thuyết phân tích độ phức tạp tính toán của thuật toán, các 
nhà khoa học đã đưa ra tiêu chí khách quan để đánh giá thời gian 
tính của thuật toán: đó là đánh giá thời gian tính của thuật toán giải 
bài toán bởi một hàm của kích thước dữ liệu đầu vào của bài toán, 
được ghi nhận dưới dạng ký pháp tiệm cận (asymptotic notation), 
trong đó ký hiệu O được sử dụng để ghi nhận đánh giá tiệm cận 
trên. Tuy nhiên, một nhược điểm của việc sử dụng ký hiệu tiệm cận 
chính là kết quả so sánh tốc độ tăng của các hàm chỉ đúng khi đối 
số “đủ lớn”. Vì thế khi đối số chưa đủ lớn thì kết quả so sánh có thể 
là không đúng. Chẳng hạn, một thuật toán có đánh giá thời gian tính 
là f(n) = 1000n2 O(n2) là nhanh hơn thuật toán có đánh giá g(n) = 
2n3 O(n3) khi n đủ lớn. Nhưng khi n<100, dễ thấy là đòi hỏi 
1000n2 (= 107, khi n=100) là lớn hơn đòi hỏi 2n3 (= 2*106, khi 
n=100) đến 5 lần. 
Mặt khác, người sử dụng rất cần thông tin chi tiết về thời gian mà 
thuật toán đòi hỏi để đưa ra lời giải có chất lượng đáp ứng yêu cầu 
đặt ra đối với những kích thước cụ thể tương ứng với kích thước bài 
toán ứng dụng mà họ cần lựa chọn thuật toán giải. Để đáp ứng yêu 
cầu này, bên cạnh việc đưa ra đánh giá thời gian tính lý thuyết của 
thuật toán trong ký pháp tiệm cận, các nhà khoa học khi phát triển 
thuật toán thường đưa ra thông tin về thời gian tính thực nghiệm 
của thuật toán. 
Khi so sánh thời gian tính của các thuật toán khác nhau dựa trên 
thực nghiệm, lại phát sinh một yêu cầu Khi so sánh các thuật toán 
cần chạy trên một hạ tầng thông tin; mà để đáp ứng yêu cầu này, 
khi tiến hành thực nghiệm các tác giả không những phải cài đặt 
thuật toán của mình mà còn phải cài đặt lại các thuật toán của các 
7 
tác giả khác trên cùng một ngôn ngữ lập trình và chạy trên cùng 
một cấu hình máy tính để giải cùng bộ dữ liệu chuẩn. Đây là một 
thách thức với cộng đồng những nhà khoa học trong lĩnh vực phát 
triển thuật toán. Do đó, ngay cuối những năm 1980, có một cách 
giải quyết vần đề này được cộng đồng các nhà khoa học sử dụng 
trong những tình huống như vậy: Đó là dựa vào thông tin đánh giá 
tốc độ xử lý của các máy tính được các chuyên gia máy tính đưa ra. 
Hiện nay, trong công trình Performance of Various Computers 
Using Standard Linear Equations Software của Jack J. Dongarra đã 
trình bày cách đánh giá hiệu quả của các hệ thống máy tính khác 
nhau bằng việc sử dụng các phần mềm tính toán giải hệ phương 
trình tuyến tính. Công trình này sử dụng đơn vị đo Mflop/s (Million 
Floating-point Operations Per Second – triệu phép tính dấu phảy 
động trên giây) để đánh giá hiệu suất của các máy tính. Kết quả của 
công trình nghiên cứu là bảng số liệu về tốc độ đo bởi Mflop/s cho 
mỗi một cấu hình máy tính. Sử dụng bảng thông tin này các tác giả 
không cần cài đặt lại thuật toán của người khác, mà để so sánh 
tương đối thời gian tính của các thuật toán có thể đưa ra các thông 
tin sau: Thời gian tính được công bố bởi chính tác giả thuật toán; 
thông tin về cấu hình máy tính thực hiện thuật toán; qui đổi thời 
gian tính dựa trên thông tin về tốc độ máy tính lấy từ công trình của 
Dongarra. 
1.5.HỆ THỐNG DỮ LIỆU THỰC NGHIỆM CHUẨN 
Trong các công trình nghiên cứu gần đây về bài toán MRCST, các 
tác giả thường sử dụng 35 bộ dữ liệu là các đồ thị đầy đủ: Trong đó 
21 bộ dữ liệu là các đồ thị đầy đủ Euclid được lấy từ website 
 và 14 bộ dữ liệu 
đồ thị đầy đủ ngẫu nhiên được đề xuất từ công trình của tác giả 
Bryant A. Julstrom (B. A. Julstrom là tác giả đầu tiên sử dụng 35 
bộ dữ liệu này). 
Trong nhiều giáo trình cấu trúc dữ liệu, lý thuyết đồ thị; khi bàn về 
các cách biểu diễn đồ thị trên máy tính, đều nhấn mạnh là hầu hết 
các đồ thị gặp trong thực tế ứng dụng là đồ thị thưa. Vì vậy, trong 
luận án, để phân tích hiệu quả của các thuật toán trên các đồ thị 
thưa, chúng tôi sử dụng thêm 14 bộ dữ liệu là các đồ thị thưa; trong 
đó có 7 bộ dữ liệu 500 đỉnh và 7 bộ dữ liệu 1000 đỉnh. Toàn bộ 14 
8 
bộ dữ liệu bổ sung này chúng tôi lấy lấy từ website 
Như vậy, luận án sử dụng tổng cộng 49 bộ dữ liệu, và chúng tôi gọi 
đây là hệ thống dữ liệu thực nghiệm chuẩn cho bài toán M ... ợc công bố trước đó như WONG, ADD, CAMPOS, SHC, PBLS, 
ESCGA, BCGA trên mọi bộ dữ liệu; Thuật toán TST cho lời giải 
chất lượng tương đương với thuật toán PBLS trên các đồ thị đầy đủ 
Euclid và với thời gian tính nhanh hơn. 
4.1.THUẬT TOÁN TST 
Mục này luận án trình bày thuật toán tìm kiếm Tabu cơ bản; trình 
bày các thủ tục tìm bước chuyển tốt nhất, cập nhật danh sách Tabu, 
các chiến lược đa dạng hóa của thuật toán TST. 
Với thuật toán TST, tính đa dạng được thể hiện qua việc khởi tạo cá 
thể ban đầu ngẫu nhiên và khi chiến lược tăng cường hóa một lời 
giải không còn được hiệu quả. Thuật toán TST sử dụng tính tăng 
cường mạnh mẻ qua chiến lược tìm kiếm lân cận. 
Độ phức tạp một lần lặp của thuật toán TST là O(mn). 
4.2.THỰC NGHIỆM VÀ ĐÁNH GIÁ 
19 
Chúng tôi tiến hành thực nghiệm thuật toán TST trên BDMRCST. 
Với mỗi loại đồ thị, chúng tôi so sánh chi phí định tuyến và thời 
gian tính thuật toán TST với các thuật toán SHC, PBLS, CAMPOS, 
HCSRI, ESCGA, GST, ABC+LS. 
Chất lượng lời giải 
Đánh giá chung, trên 49 bộ dữ liệu thì thuật toán TST cho chất 
lượng lời giải tốt hơn (tồi hơn) các thuật toán SHC (38.8%, 2.0%), 
PBLS (12.2%, 10.2%), CAMPOS (100.0%, 0.0%), HCSRI (16.3%, 
10.2%), ESCGA (88.6%, 0.0%), GST (14.3%, 2.0%), ABC+LS 
(6.1%, 18.4%). 
Thời gian tính 
TST có thời gian tính nhanh hơn các thuật toán PBLS, ESCGA ở 
mọi bộ dữ liệu đầy đủ của Julstrom. Thuật toán TST có thời gian 
tính nhanh hơn các thuật toán SHC, PBLS, GST, ABC+LS ở các đồ 
thị thưa. Với các đồ thị đầy đủ có kích thước lớn, thuật toán TST có 
thời gian tính nhanh hơn thuật toán ABC+LS. Thuật toán TST có 
thời gian tính chậm hơn thuật toán HCSRI ở mọi bộ dữ liệu thuộc 
BDMRCST. Ưu điểm nổi trội của TST là cho thời gian tính nhanh 
hơn các thuật toán đã công bố trước đó như SHC, PBLS, ABC+LS 
trên đồ thị thưa. Cụ thể, với các đồ thị thưa, thuật toán TST có thời 
gian tính chỉ bằng không quá 4.25% thời gian tính của thuật toán 
SHC, không quá 41.71% thời gian tính của thuật toán PBLS, không 
quá 0.30% thời gian tính của thuật toán ABC+LS. Thuật toán TST 
có thời gian tính chậm hơn rất nhiều so với thuật toán CAMPOS. 
4.3.KẾT LUẬN CHƯƠNG 4 
Chương này đề xuất mới thuật toán TST dựa trên thuật toán tìm 
kiếm Tabu để giải bài toán MRCST. Thuật toán TST cho lời giải với 
chất lượng tốt hơn các thuật toán WONG, ADD, CAMPOS, ESCGA, 
BCGA, GST, SHC, PBLS, HCSRI. Thuật toán TST cho lời giải với 
chất lượng tốt hơn hoặc tương đương với thuật toán ABC+LS trên 
tất cả các đồ thị thưa và đồ thị đầy đủ ngẫu nhiên, tuy nhiên TST 
cho lời giải với chất lượng tồi hơn thuật toán ABC+LS trên một số 
đồ thị đầy đủ Euclid. Thuật toán TST cho thời gian tính nhanh hơn 
thuật toán ABC+LS trên các đồ thị thưa và đồ thị đầy đủ có kích 
thước lớn, thuật toán TST cho thời gian tính nhanh hơn các thuật 
toán ESCGA, PBLS trên hệ thống dữ liệu thực nghiệm chuẩn. 
20 
Các kết quả chính của chương này được nghiên cứu sinh công bố 
tại tạp chí Công nghệ Thông tin và truyền thông [4], năm 2013. 
Chương 5. THUẬT TOÁN BẦY ONG 
Thuật toán TST có ưu điểm là có thời gian tính nhanh hơn các thuật 
toán SHC, PBLS, GST, PABC, ABC+LS trên các đồ thị thưa. TST 
cho chất lượng lời giải tốt hơn thuật toán GST nhưng TST vẫn tồi 
hơn các thuật toán PABC, ABC+LS trên một số bộ dữ liệu đồ thị đầy 
đủ Euclid. 
Chương này đề xuất một thuật toán mới có tên gọi là BST để giải bài 
toán MRCST. Thuật toán BST được phát triển dựa trên thuật toán 
bầy ong cơ bản; bản thân thuật toán bầy ong cơ bản là một công cụ 
hữu hiệu để giải quyết các bài toán bài toán tổ hợp NP-khó. Thuật 
toán BST đề xuất mới các chiến lược tăng cường hóa và đa dạng 
hóa; BST là vận dụng đầu tiên của thuật toán bầy ong cơ bản vào 
việc giải bài toán MRCST (sơ đồ thuật toán bầy ong cơ bản này khác 
với sơ đồ của thuật toán cơ bản mà thuật toán PABC phát triển). 
BST cho chất lượng lời giải tốt hơn các thuật toán đã được công bố 
cũng như các thuật toán mà luận án đề xuất như PABC, ABC+LS, 
ESCGA, BCGA, TST. 
5.1.THUẬT TOÁN BẦY ONG CƠ BẢN 
Mục này luận án trình bày thuật toán bầy ong cơ bản từ công trình 
“The bees algorithm - A novel tool for complex optimisation 
problems” của nhóm tác giả D.T. Pham, A. Ghanbarzadeh, E. Koc, 
S. Otri, S. Rahim, M. Zaidi (2006). 
5.2.THUẬT TOÁN BST 
Mục này luận án trình bày một áp dụng của thuật toán bầy ong cơ 
bản vào việc giải bài toán MRCST. 
Thuật toán BST sử dụng thuật toán cây đường đi ngắn nhất để tạo 
quần thể ban đầu: mỗi cá thể là một cây đường đi ngắn nhất có gốc 
xuất phát từ một đỉnh ngẫu nhiên nào đó của đồ thị. 
Quần thể P có N cá thể, sắp xếp các cá thể trong quần thể P theo 
chiều tăng dần theo chi phí định tuyến của các cá thể. Sau khi sắp 
xếp, ta phân bố các cá thể vào ba nhóm: Nhóm 1 gồm h cá thể tốt 
nhất, nhóm 2 gồm p-h cá thể tốt tiếp theo và nhóm 3 gồm N-p cá 
thể còn lại của quần thể. 
Luận án đã đề xuất cách thức phân nhóm các cá thể vào ba nhóm cá 
21 
thể để thực hiện việc tìm kiếm; đề xuất này là khác biệt so với cách 
thức phân nhóm các cá thể theo thuật toán bầy ong chuẩn. 
Luận án đã đề xuất hai chiến lược tìm cây khung lân cận; trong đó 
chiến lược thứ nhất là mới so với các cách tiếp cận đã được công bố 
ở các công trình liên quan giải bài toán MRCST và chiến lược thứ 
hai đã được đề cập đến trong thuật toán HCSIR ở chương 2 của luận 
án. 
Luận án đã đề xuất hai chiến lược đa dạng hóa để làm tăng tính đa 
dạng của lời giải: Chiến lược thứ nhất là chiến lược đa dạng đã 
được sử dụng trong thuật toán TST ở chương 4 của luận án. Chiến 
lược thứ hai là thực hiện đa dạng hóa bằng cách thay thế lời giải 
đang xét bằng một cây khung ngẫu nhiên dựa vào kỹ thuật bánh xe 
quay rulet. 
Sơ đồ của thuật toán BST 
Thuật toán BST trước hết là tạo quần thể ban đầu P, sau đó là lặp lại 
các thao tác: Sắp xếp các cá thể thuộc quần thể P và phân bố các cá 
thể vào các nhóm; mỗi cá thể thuộc nhóm 1 cho tìm kiếm lân cận k1 
lần, mỗi cá thể thuộc nhóm 2 cho tìm kiếm lân cận k2 lần, các cá thể 
thuộc các nhóm 1,2 đã được khai thác cạn thì được thay thế bằng 
một lời giải ngẫu nhiên (thực hiện đa dạng hóa lời giải). Trong mỗi 
bước lặp, quần thể P đã được cập nhật thông qua các thao tác tìm 
kiếm lân cận và tìm kiếm lân cận ngẫu nhiên. Khi thuật toán dừng, 
cá thể tốt nhất tìm được trong quá trình thực hiện thuật toán được 
công bố làm lời giải cần tìm. 
Độ phức tạp một lần lặp của thuật toán BST là O(Nn2 + Nlog N). 
5.3.THỰC NGHIỆM VÀ ĐÁNH GIÁ 
Trong chương này, luận án đã so sánh thuật toán BST với tất cả các 
thuật toán đã được khảo sát đến, qua đó có một cái nhin tổng thể về 
chất lượng của các thuật toán và cũng để thuận tiện khi cần so sánh 
các cặp thuật toán nào đó với nhau. 
Chất lượng lời giải 
Đánh giá chung, với 49 bộ dữ liệu trên, thuật toán BST cho chất 
lượng lời giải tốt hơn (tồi hơn) các thuật toán WONG (100.00%, 
0.0%), CAMPOS (100.0%, 0.0%), SHC (40.8%, 0.0%), PBLS 
(24.5%, 0.0%), HCSRI (24.5%, 0.0%), HCSIR (26.5%, 0.0%), TST 
(18.4%, 0.0%). 
22 
Đánh giá chung, với 49 bộ dữ liệu trên, thuật toán BST cho chất 
lượng lời giải tốt hơn (tồi hơn) các thuật toán ESCGA (88.6%, 
0.0%), BCGA (100.0%, 0.0%), GST (20.4%, 0.0%), PABC (17.1%, 
2.9%), ABC+LS (18.4%, 2.0%). 
BST tốt hơn ABC+LS ở 9 bộ dữ liệu, trong đó có 6 bộ dữ liệu nằm 
trong số 35 bộ dữ liệu đã được các công trình khác công bố chất 
lượng lời giải và 3 bộ dữ liệu nằm trong số 14 bộ dữ liệu mà luận 
án đã bổ sung. 
Thời gian tính 
Thuật toán BST có thời gian tính nhanh hơn các thuật toán SHC, 
PBLS, TST ở các bộ dữ liệu đầy đủ của Julstrom và có thời gian 
tính chậm hơn so với các thuật toán SHC, PBLS, TST trên các đồ thị 
thưa. Cụ thể, với các bộ dữ liệu đầy đủ của Julstrom, thuật toán BST 
có thời gian tính chỉ bằng không quá 52.37% thời gian tính của 
thuật toán SHC, không quá 45.30% thời gian tính của thuật toán 
PBLS, không quá 51.87% thời gian tính của thuật toán TST. Thuật 
toán BST có thời gian tính chậm hơn các thuật toán SHC, PBLS, 
TST trên các đồ thị thưa. 
Thuật toán BST có thời gian tính chậm hơn thuật toán HCSRI trên 
mọi bộ dữ liệu thuộc BDMRCST. 
Thuật toán BST có thời gian tính nhanh hơn các thuật toán ESCGA, 
BCGA, PABC, ABC+LS ở mọi bộ dữ liệu thuộc BDMRCST. Cụ thể, 
với các bộ dữ liệu đầy đủ của Julstrom, thuật toán BST có thời gian 
tính chỉ bằng không quá 22.27% thời gian tính của thuật toán 
ESCGA, không quá 58.56% thời gian tính của thuật toán BCGA, 
không quá 94.37% thời gian tính của thuật toán PABC, không quá 
93.15% thời gian tính của thuật toán ABC+LS. Với các bộ dữ liệu 
đồ thị thưa, thuật toán BST có thời gian tính chỉ bằng không quá 
12.73% thời gian tính của thuật toán ABC+LS. Thuật toán BST có 
thời gian tính nhanh hơn thuật toán GST trên đồ thị thưa, nhưng 
chậm hơn trên các đồ thị đầy đủ. 
5.4.KẾT LUẬN CHƯƠNG 5 
Thuật toán BST là công trình đầu tiên giải bài toán MRCST được 
phát triển dựa trên thuật toán bầy ong chuẩn, thuật toán BST đề xuất 
mới cách thức phân bố các cá thể vào các nhóm cá thể để thực hiện 
việc tìm kiếm, thuật toán BST đề xuất mới chiến lược tăng cường 
23 
hóa và đề xuất cách thức áp dụng chiến lược đa dạng hóa vào trong 
sơ đồ thuật toán BST. Kết quả thực nghiệm trên hệ thống dữ liệu 
thực nghiệm chuẩn cho thấy thuật toán BST cho chất lượng lời giải 
tốt nhất trong số các cách tiếp cận hiện biết. Thuật toán BST cũng 
cho thời gian tính nhanh nhất khi so sánh với các thuật toán 
metaheuristic có chất lượng lời giải tốt nhất đã khảo sát trên hầu hết 
hệ thống dữ liệu thực nghiệm chuẩn. 
Các kết quả chính của chương này được nghiên cứu sinh báo cáo 
trong hội nghị ICTFIT2012 tháng 4/2012 [3], sau đó được chỉnh 
sửa và công bố tại tạp chí Tin học và điều khiển học [5], năm 2013. 
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 
KẾT LUẬN 
Luận án đề xuất một số thuật toán mới dạng metaheurristic giải 
quyết bài toán MRCST. Đó là các thuật toán tìm kiếm leo đồi 
HCSRI, HCSIR, thuật toán di truyền GST, thuật toán tìm kiếm Tabu 
TST và thuật toán bầy ong BST. 
Đóng góp mới của luận án là sự tổng hợp các thuật toán trên với các 
kỹ thuật tìm kiếm lân cận trên cơ sở đặc tính của bài toán MRCST. 
Theo hiểu biết của tác giả luận án, luận án là công trình đầu tiên 
phát triển thuật toán dựa trên tìm kiếm Tabu và thuật toán bầy ong 
để giải bài toán MRCST ; trong các thuật toán TST, BST; luận án đã 
đề xuất một số chiến lược tăng cường hóa và đa dạng hóa mới. Các 
thuật toán HCSRI, HCSIR đề xuất cách thức tìm kiếm lân cận mới 
so với các thuật toán tìm kiếm địa phương đã công bố trước đó như 
SHC và PBLS; đề xuất này có hiệu quả rõ nét đối với các đồ thị thưa 
và đồ thị đầy đủ ngẫu nhiên. Thuật toán GST đề xuất các phép lai và 
phép đột biến mới, khác biệt so với các phép toán di truyền trong 
các thuật toán di truyền trước đó. 
Kết quả thực nghiệm trên hệ thống dữ liệu thực nghiệm chuẩn cho 
thấy rằng: Các đề xuất này cho chất lượng lời giải tốt hơn hoặc có 
thời gian tính nhanh hơn các thuật toán trong cùng lớp và phần lớn 
các thuật toán đã được công bố trước đó. Cụ thể, các thuật toán 
HCSRI, HCSIR cho chất lượng lời giải tốt hơn các thuật toán xấp xỉ, 
các thuật toán heuristic và các thuật toán di truyền đã công bố là 
WONG, GENERAL STAR, PTAS, ADD, CAMPOS, ESCGA, BCGA. 
Các thuật toán HCSRI, HCSIR có ưu điểm cho chất lượng lời giải 
tương đương các thuật toán metaheuristic tốt nhất trên loại đồ thị 
đầy đủ ngẫu nhiên và đồ thị thưa trong thời gian nhanh hơn hẳn; 
24 
đặc biệt khi làm việc với các đồ thị thưa có nhiều đỉnh. Thuật toán 
GST cho chất lượng lời giải tốt hơn các thuật toán di truyền đã công 
bố là ESCGA, BCGA. Thuật toán TST cho chất lượng lời giải tốt hơn 
các thuật toán tìm kiếm địa phương SHC, PBLS, các thuật toán 
heuristic và các thuật toán di truyền đã được công bố. Thuật toán 
BST cho chất lượng lời giải tốt hơn các thuật toán tốt nhất hiện biết 
là PABC, ABC+LS, cũng như tất cả các thuật toán heuristic, các 
thuật toán tìm kiếm địa phương, các thuật toán di truyền đã được 
công bố. 
Luận án đã xây dựng bảng tổng hợp so sánh chi phí định tuyến của 
từng cặp các thuật toán với nhau. 
Trên cơ sở những kết quả khảo sát thực nghiệm các thuật toán, luận 
án đề xuất hướng áp dụng từng thuật toán cụ thể vào các loại dữ 
liệu, cụ thể như sau: 
 Đối với loại đồ thị đầy đủ Euclid, thuật toán BST cho chất 
lượng lời giải tốt nhất. 
 Đối với loại đồ thị đầy đủ ngẫu nhiên, do các thuật toán 
SHC, PBLS, HCSRI, TABU, GST, PABC, ABC+LS, BST cho 
chất lượng lời giải tương đương, và thuật toán HCSRI khi đó 
có thời gian tính nhanh hơn các thuật toán còn lại. Do đó, 
trong trường hợp là đồ thị đầy đủ ngẫu nhiên nên chọn thuật 
toán HCSRI. 
 Đối với loại đồ thị thưa, các thuật toán PBLS, TST, GST, 
HCSRI, HCSIR, BST cho chất lượng lời giải tương đương, 
và thuật toán HCSRI khi đó có thời gian tính nhanh hơn hẳn 
các thuật toán còn lại. Do đó, trong trường hợp là đồ thị 
thưa, đặc biệt là với đồ thị thưa có nhiều đỉnh thì nên chọn 
thuật toán HCSRI. 
HƯỚNG PHÁT TRIỂN 
Tiếp tục phát triển các kỹ thuật tìm kiếm lân cận, các chiến lược 
tăng cường hóa lời giải, đa dạng hóa lời giải vào sơ đồ các thuật 
toán HCSRI, HCSIR, GST, TST, BST với mong muốn tiếp tục cải 
tiến chất lượng lời giải. Bên cạnh đó, thời gian tính các thuật toán 
BST, GST hiện tại dù nhanh hơn các thuật toán metaheuristic dạng 
quần thể đã được công bố nhưng vẫn chưa đáp ứng yêu cầu thực tế 
khi làm việc với các đồ thị có kích thước trên 10000 đỉnh. 
Dựa vào sơ đồ của các thuật toán đề xuất và các thuật toán của các 
tác giả khác, có thể xây dựng một khung thuật toán để giải quyết 
một số bài toán cây khung truyền thông tối ưu lớp NP-khó khác. 
25 
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ 
CỦA LUẬN ÁN 
[1]. Phan Tan Quoc (2012). A Heuristic approach for solving the 
minimum routing cost spanning tree problem. International 
Journal of Machine Learning and Computing (IJMLC), 
IACSIT, volume 2, pp.406-409. 
[2]. Phan Tan Quoc (2012). A Genetic approach for solving the 
minimum routing cost spanning tree problem. International 
Journal of Machine Learning and Computing (IJMLC), 
IACSIT, volume 2, pp.410-414. 
[3]. Phan Tấn Quốc, Nguyễn Đức Nghĩa (2012). Thuật toán bầy 
ong giải bài toán cây khung với chi phí định tuyến nhỏ nhất. 
ICTFIT, Tuyển tập công trình nghiên cứu Công nghệ thông tin 
& Truyền thông, Nhà xuất bản Khoa học Kỹ thuật, pp.73-81. 
[4]. Phan Tấn Quốc, Nguyễn Đức Nghĩa (2013). Thuật toán tìm 
kiếm Tabu giải bài toán cây khung với chi phí định tuyến nhỏ 
nhất. Tạp chí Công nghệ Thông tin và Truyền thông, pp.5-13. 
[5]. Phan Tấn Quốc, Nguyễn Đức Nghĩa (2013). Thuật toán bầy 
ong giải bài toán cây khung với chi phí định tuyến nhỏ nhất. 
Tạp chí Tin học và điều khiển học, T.29, S3, 2013, pp.265-276. 
[6]. Phan Tan Quoc, Nguyen Duc Nghia (2013). An Experimental 
Study of Minimum Routing Cost Spanning Tree Algorithms. 
IEEE, SoCPaR, 2013, pp.164-171.