ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐINH VĂN VIỆT

MỘT THUẬT TOÁN HIỆU QUẢ CHO TẬP ĐỈNH THỐNG TRỊ CÓ
TRỌNG SỐ NHỎ NHẤT

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

HÀ NỘI – 2021


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐINH VĂN VIỆT

MỘT THUẬT TOÁN HIỆU QUẢ CHO TẬP ĐỈNH THỐNG TRỊ CĨ
TRỌNG SỐ NHỎ NHẤT

Ngành:

Khoa học máy tính

Chun ngành:

Khoa học máy tính

Mã số:

8480101.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn
PGS.TS HOÀNG XUÂN HUẤN

HÀ NỘI - 2021


Lời Cảm Ơn
Đầu tiên, tôi xin gửi lời cảm ơn đến PGS. TS. Hồng Xn Huấn, giảng
viên tại bộ mơn khoa học máy tính thuộc khoa cơng nghệ thơng tin. Trong khi
làm luận văn, thầy đã hướng dẫn tôi rất tận tình chu đáo. Khơng chỉ giới thiệu
những kiến thức hữu ích, thầy cịn truyền cảm hứng đến tơi về những ứng dụng
tự nhiên lý thú. Tôi ngày càng trưởng thành hơn khơng chỉ về nhiều kiến thức
hơn, mà cịn cả về nhận thức về đời sống thực tại. Tôi vơ cùng kính phục và cám
ơn thầy.
Tiếp theo, tơi vơ cùng cảm ơn bố mẹ đã luôn ở bên cạnh hỗ trợ tôi, giúp
tôi trong hầu hết các vấn đề gặp phải trong cuộc sống. Tôi xin cảm ơn gia đình
tơi, nơi tơi được sinh ra và lớn lên, nơi có rất nhiều kỷ niệm đẹp ảnh hưởng sâu
sắc đến những tư duy của tôi trong luận văn này. Nhờ tình thương vơ bờ bến của
họ, tơi đã khơng phải chịu quá nhiều áp lực của cuộc sống mưu sinh đầy vất vả,
có thêm nhiều thời gian dành cho luận văn này. Đây là động lực chính giúp tơi
hồn thành xong luận văn này.
Cuối cùng, tôi cảm ơn bạn bè và đồng nghiệp đã tạo điều kiện giúp tôi,
cùng tôi đi tiếp trên những chặng đường đầy thách thức không chỉ trong cơng
việc mà cịn các vấn đề ngồi cuộc sống. Tơi xin gửi lời cảm ơn đến tồn bộ tập
thể trường đại học Công Nghệ, trực thuộc đại học quốc gia Hà Nội. Ở đây, tôi đã
được sống trong môi trường năng động, trẻ trung, tràn trề cơ hội và thách thức.
Cảm ơn tất cả đã mở ra cánh cửa tương lai tươi sáng cho chính tơi!

Tác giả

Đinh Văn Việt

3


Lời Cam Đoan
Tơi xin cam đoan đây là cơng trình nghiên cứu của tơi dưới sự giám sát
của PGS.TS Hồng Xuân Huấn. Các phần đóng góp trong luận văn này chưa
được nộp cho một trình độ hoặc bằng cấp tại đây hoặc bất cứ các tổ chức nghiên
cứu giáo dục đại học. Các đóng góp và kết quả được trình bày trong luận văn
này hoàn toàn được kiểm nghiệm rõ ràng bằng các thực nghiệm dựa trên nhiều
bộ dữ liệu được chấp thuận và sử dụng bởi cộng đồng khoa học. Các phần có sự
đóng góp của người khác vào luận văn này đều được xin phép và có được sự
đồng ý chấp thuận của họ. Các phần kiến thức liên quan được sử dụng trong
luận văn này đều được tham chiếu rõ ràng từ các nguồn tham khảo được công
đồng khoa học công nhận và được liệt kê đầy đủ tại mục liệt kê tham khảo.
Tác giả

Đinh Văn Việt

4


Danh sách ký hiệu và viết tắt

NP

Nondeterministic polynomial Problem


P

Polynomial Problem

MDS

Minimum dominating set

MCDS

Minimum Connected Dominating Set

MIDS

Minimum Independent Dominating Set

MkDS

Minimum k-dominating Set

MWDS

Minimum Weighted Dominating Set

GA

Genetic Algorithm

ACO


Ant Colony Optimization

PSO

Particle Swarm Optimization

MA

Memetic Algorithm

LS

Local Search

LNS

Large Neighborhood Search

IP

Integer Programming

MMAS

Max-Min Ant System

GRASP

Greedy Randomized Adaptive Search Procedure


5


HGA

Hybrid Genetic Algorithm

ACO-LS

Hybrid ACO and local search

ACO-PPLS

Hybrid ACO and local search with intialization

HMA

Hybrid Memetic Algorithm

BPSO

Binary Particle Swarm Optimization

R-BPIG

Randomized population-based iterated greedy
algorithm

hyb-RPBIG


Hybrid Randomized population-based iterated
greedy algorithm

CC2FS

Two-level configuration checking and frequency
based scoring function

HTS-DS

Hybrid tabu search matheuristic

HLNS

Hybrid large neighborhood search

6


Tóm Tắt Nội Dung
Bài tốn tập đỉnh thống trị có trọng số nhỏ nhất (MWDS) là một trong
những bài toán NP-Hard kinh điển được nhiều nhà nghiên cứu quan tâm và đã
được ứng dụng vào trong thực tiễn. Nhiều ứng dụng được tạo ra để đáp ứng sự
phát triển của các mạng lưới từ sự phát triển của xã hội. Các ứng dụng này chủ
yếu liên quan đến việc thiết kế và tận dụng các tài nguyên lợi ích thu được từ
các mạng lưới này. Hầu hết, các ứng dụng đều có liên quan đến bài tốn tập đỉnh
thống trị. Tuy đã có rất nhiều thuật tốn được đề xuất, nhưng các thuật toán vẫn
chưa đủ hiệu quả để giải quyết bài toán trên. Luận văn này đề xuất thuật tốn kết
hợp tìm kiếm với số lượng hàng xóm lớn (HLNS) để giải quyết bài toán đạt chất

lượng kết quả tốt trong lượng thời gian xác định trên một số bộ dữ liệu chuẩn.
Thực nghiệm đã chỉ ra rằng thuật tốn hiệu quả hơn các thuật tốn đã có trên các
bộ dữ liệu thực tế BHOSLIB và DIMACS. Cuối cùng, luận văn giới thiệu về
ứng dụng moderator-selector để chọn người điều hành cho một nhóm hoặc một
tổ chức trên một mạng lưới cho trước.

7


Mục lục
Lời Cảm Ơn ........................................................................................................... 3
Lời Cam Đoan ....................................................................................................... 4
Danh sách ký hiệu và viết tắt ................................................................................ 5
Tóm Tắt Nội Dung ................................................................................................ 7
Mục lục .................................................................................................................. 8
Danh sách thuật toán ........................................................................................... 10
Danh sách hình vẽ ............................................................................................... 11
Danh sách bảng ................................................................................................... 12
Mở Đầu................................................................................................................ 13
Chương 1. Giới Thiệu Bài Toán Tập Đỉnh Thống Trị Có Trọng Số Nhỏ Nhất . 20
1.1 Bài tốn tập đỉnh thống trị có trọng số cực tiểu và các bài toán liên
quan
21
1.2 Các nghiên cứu liên quan .............................................................. 25
1.3 Các ứng dụng liên quan đến bài toán tập đỉnh thống trị ............... 31
1.4 Một số định lý quan trọng ............................................................. 34
1.4.1 Đinh lý Cook-levin .................................................................. 34
1.4.2 Định lý khơng có bữa trưa miễn phí........................................ 35
Chương 2. Thuật tốn kết hợp tìm kiếm với số lượng hàng xóm lớn................. 36
2.1 Thuật toán HLNS .......................................................................... 36

2.2 Thuật toán khởi tạo cho tập đỉnh thống trị .................................... 37
2.3 Các thuật toán xóa các đỉnh trong tập đỉnh thống trị .................... 38
2.4 Các thuật toán sửa tập đỉnh ........................................................... 38
2.5 Các thuật tốn xóa bỏ đỉnh dư thừa trong tập đỉnh thống trị ........ 39
Chương 3. Thực nghiệm ..................................................................................... 41
2.1 Giới thiệu thực nghiệm ................................................................. 41
2.2 Kết quả thực nghiệm ..................................................................... 42
2.2.1 Thực nghiệm trên TH1 ............................................................ 42
2.2.2 Thực nghiệm trên TH2 ............................................................ 44

8


Chương 4. Ứng dụng chọn người điều hành cho nhóm moderator-selector ...... 46
4.1 Giới thiệu ứng dụng chọn người điều hành cho nhóm moderatorselector
46
4.2 Cách sử dụng ứng dụng................................................................. 48
Kết Luận Và Thảo Luận ...................................................................................... 52
Tài liệu tham khảo ............................................................................................... 53

9


Danh sách thuật tốn
Thuật Tốn 1: Tìm kiếm với số lượng hàng xóm lớn - LNS .................... 18
Thuật Tốn 2: Thủ tục tham lam thích nghi ngẫu nhiên GRASP ............ 19
Thuật Toán 3: Thuật toán HLNS .............................................................. 37
Thuật Toán 4: Thuật toán khởi tạo tập đỉnh ............................................. 38
Thuật Toán 5: Thuật tốn xóa đỉnh DEL .................................................. 38
Thuật Tốn 6: Thuật toán thêm đỉnh REPAIR ......................................... 39

Thuật Toán 7: Thuật toán DEL-REDUNDANT ...................................... 40

10


Danh sách hình vẽ
Hình 1: Đồ thị chuyển đổi giữa bài tốn SC và bài tốn MDS

24

Hình 2: Đồ thị chuyển đổi từ bài toán tập MDS sang bài toán SC

24

Hình 3: Ứng dụng moderators-selector

48

Hình 4: Mở một tệp đầu vào dưới định dạng json

49

Hình 5: Hiển thị tên người dùng và giá trị của họ

49

Hình 6: Hiển thị mối liên hệ giữa các người dùng

50


Hình 7: Hiển thị những người điều hành được chọn

50

Hình 8: Thiết lập chương trình

51

11


Danh sách bảng
Bảng 1: Tham số cấu hình cho HLNS ...................................................... 41
Bảng 2: Kết quả thực nghiệm trên TH1 .................................................... 43
Bảng 3: Kết quả thực nghiệm trên TH2 .................................................... 44

12


Mở Đầu
Một lượng lớn các liên kết tồn tại trong thế giới hiện nay đã kết nối hầu
hết mọi thứ lại với nhau, và phát triển dần về số lượng tạo ra một số lượng
khổng lồ các mạng lưới.
Các mạng lưới được tạo ra từ các tổ chức xã hội được hình thành ở trong
hầu hết các nơi mà con người đang sinh sống. Với một xã hội hiện đại như ngày
nay, trẻ con đến trường tham vào các tổ chức trong trường học. Người lớn đi
làm và tham gia vào rất nhiều tổ chức và mạng lưới trong xã hội như: hệ thống
tổ chức lao động, hệ thống bảo hiểm xã hội, … Người già thường ít tham gia
vào các tổ chức hơn, hầu hết trong số đó là các tổ chức về hưu trí và hội những
người bạn già. Các tổ chức này thường được hình thành một cách tự nhiên từ

các nhu cầu cần thiết của cuộc sống, hình thành các mạng lưới với đầy đủ kích
cỡ khác nhau.
Các mạng lưới được tạo thành từ dựa trên các hệ thống khổng lồ như
mạng điện, mạng INTERNET, và mạng viễn thông. Các mạng lưới này được
phát triển mạnh mẽ trong thời kỳ kỷ nguyên của kỹ thuật số và trí tuệ nhân tạo.
Hiện nay, các mạng điện cung cấp đủ điện cho hàng tỷ người dùng ở khắp nơi
trên thế giới với kết cấu rất linh hoạt và phong phú phụ thuộc vào địa hình. Tiếp
theo, các mạng xã hội nổi tiếng như Twitter, Wechat, QQ, Facebook, với số
lượng người dùng từ vài trăm triệu đến tỷ người dùng. Trên các mạng này, mọi
người được sử dụng rất nhiều tiện ích như nhắn tin, trị chuyện trực tiếp, chơi trị
chơi cùng nhau. Cuối cùng, các mạng viễn thơng hiện nay được phủ song hầu
như toàn bộ các nơi tập trung đông đảo con người sinh sống, cho phép hàng
triệu người dùng giao tiếp với nhau trong một khoảng rộng lớn một cách linh
hoạt khơng bị gị bó như các mạng lưới cố định.
Các mạng cảm biến được hình thành để thu thập các thông tin cần thiết
phục vụ cho các ứng dụng thực tiễn. Các mạng lưới cảm biến được sử dụng rất
nhiều trong thực tế và trong cuộc sống vạn vật kết nối như ngày nay. Đầu tiên,
các ứng dụng về nhà ở thông minh cần đến hàng trăm cảm biến để thu thập các
thông tin về mơi trường, sức khỏe, các tiện ích giải trí, và các cơng cụ hỗ trợ.
Bên cạnh đó, các ứng dụng về phương tiện đi lại như ô tô, máy bay, tàu vũ trụ
cần rất nhiều các cảm biến với đầy đủ các loại kể cả tối tân nhất hiện nay. Thêm
vào nữa, các ứng dụng bảo vệ môi trường cũng cần rất nhiều các cảm biến đến
có thể theo dõi chính xác tình hình mơi trường hiện nay, giúp các nhà điều hành

13


và người có trách nhiệm, cũng như tồn bộ dân cư ứng phó kịp thời với các điều
kiện mơi trường thay đổi thất thường phức tạp như ngày nay. Cuối cùng, các
ứng dụng liên quan đến hàng không vũ trụ đang được quan tâm nhất với các

thiết bị chủ yếu gồm các tổ hợp, mạng lưới phức tạp giúp con người khám phá
và chinh phục vũ trụ.
Hầu hết các mạng lưới được hình thành với những khởi đầu khơng q
phức tạp phục vụ cho những đối tượng mục tiêu bình thường. Sau đó, cùng với
sự phát triển của đời sống và nhu cầu thực tế, các mạng này phát triển với số
lượng và kích thước như khổng lồ và đa dạng và thành phần. Chẳng hạn như,
mạng xã hội Facebok với khởi đầu chỉ khoảng vài chục ngàn người dùng, trong
đó chủ yếu là các sinh viên đại học. Các tiện ích bạn đầu chủ yếu là nhắn tin và
chia sẽ ảnh cá nhân qua mạng. Khoảng chục năm về sau, mạng xã hội này đã
phát triển lên đến vài trăm triệu người dùng với rất nhiều tiện ích và có tới cả
trăm ngàn gian hàng trên mạng xã hội nay. Cho đến bây giờ, hầu hết những
người dùng INTERNET hiện đại đều biết đến mạng xã hội Facebook với hơn tỷ
người dùng ở khắp mọi người trên thế giới với đủ các thành phần từ người dân
bình thường, doanh nhân cho đến các người nổi tiếng.
Phân tích các mạng lưới sẽ giúp con người khai thác hiệu quả chúng. Việc
tìm hiểu về một mạng lưới sẽ giúp con người hiểu rõ hơn các tính chất của một
mạng lưới, các thành phần liên quan và sự phát triển của mạng lưới đó. Từ đó,
họ sẽ đưa ra các quyết định vào mạng lưới đó để thu được hiệu quả lớn nhất cho
chính họ. Chẳng hạn, việc triển khai INTERNET trên một phạm vi địa lý cần
tìm hiểu về sự phân bố dân cư, tính chất địa lý của vùng miền, yếu tố sử dụng
của người dụng để có thể quyết định đặt các thiết bị ở các vị trí hợp lý giúp giảm
thiểu cơng sức chi phí, thời gian triển khai mạng cũng như làm giảm chi phí bảo
trì mạng này.
Phân tích và khai thác các mạng lưới hiệu quả luôn tạo ra các giá trị to lớn
cho người sử dụng, đặc biệt trong kỷ nguyên của vạn vật kết nối (IOT). Một
trong những yếu tố được quan tâm là tập các nốt ảnh hưởng đến toàn bộ mạng
lưới, và bài toán được quan tâm gần đây là bài toán tìm tập đỉnh thống trị có
trọng số nhỏ nhất.
Phân tích mạng lưới để khai thác và phát triển mạng lưới, giúp các hệ
thống nên mạnh mẽ, hoạt động tốt hơn, nhiều tính năng hơn, giúp người dùng và

nhà quản lý mạng có thêm nhiều lợi ích. Các mạng lưới phân tích bao gồm:
mạng xã hội, mạng di động, mạng cảm biến, mạng lưới tổ chức xã hội. Việc
14


khai thác từ các mạng này chủ yếu khai thác tăng kích thước hệ thống, kích
thích người dùng tham gia vào hệ thống, kích thích người dùng sử dụng dịch vụ
trên mạng, kéo dài tuổi thọ của mạng, giảm thiểu chi phí vận hành và bảo trì, và
quản lý hệ thống.
Phân tích mạng xã hội và các tổ chức xã hội liên quan đến các bài toán
quản lý mạng xã hội, nguồn thông tin lan truyền trên mạng xã hội, bài toán về
quảng cáo trên mạng xã hội. Việc phân tích mạng xã hội, giúp cho nhà phát
hành sử dụng thông tin từ mạng xã hội hiệu quả để triển khai các dịch vụ và
giảm thiểu chi phí vận hành hệ thống. Người dùng sử dụng các dịch vụ như
quảng cáo trên mạng xã hội, tìm kiếm bạn bè, tạo dựng hình ảnh trên mạng xã
hội, mạng lại lợi ích lớn hơn cho họ. Các tổ chức xã hội tốt hơn khi chọn lựa
được các nhà quản lý hiệu quả phù hợp và tối ưu. Ví dụ: người dùng mạng xã
hội Youtube thường hay xem những quảng cáo bao cao su DUREX ở trên trong
các nhóm youtuber nổi tiếng, và thường chia sẻ nó với những người bạn của họ
thơng qua các mạng xã hội khác như Facebook, Zalo.
Bài toán tìm tập đỉnh thống trị có trọng số nhỏ nhất trên mạng lưới được
áp dụng để khai thác các yếu tố về việc tìm ra tập các thành phần có khả năng
chi phối tồn bộ các thành phần cịn lại trong mạng. Đó là được áp dụng cho đồ
thị vơ hướng để tìm ra một tập đỉnh chính có tổng trọng số nhỏ nhất sao cho các
đỉnh không thuộc đã chọn kề với tập đỉnh đã chọn.
Việc tìm ra tập đỉnh này giúp việc phân tích thiết kế trên mạng hiệu quả
hơn, do thông thường các tác động lên đồ thị sẽ ảnh hưởng chủ yếu bởi tập đỉnh
chính. Tại mỗi thành viên trong tập đỉnh chính, người dùng có thể tập trung
dùng chúng để quản lý chi phối, hoặc xử lý các tác vụ nặng. Điều này giúp giảm
thiểu các cơng việc phải làm trên tồn bộ hệ thống vì chỉ cần tập trung vào một

tập đỉnh chính là một bộ phận của mạng. Có rất nhiều nghiên cứu ứng dụng về
tập đỉnh trị đã được công bố về các ứng dụng liên quan đến mạng xã hội, mạng
di động, và mạng cảm biến, … Tuy rằng, các nghiên cứu về tập đỉnh thống trị có
trọng số nhỏ nhất rất lâu nhưng hồn tồn có giá trị trong kỷ nguyên của kết nối
vạn vật với một lượng dữ liệu khổng lồ được lưu chuyển và xử lý.
Trong gần 20 năm gần đây, đã có rất nhiều nghiên cứu cho bài toán này.
Do bài toán được chứng minh thuộc lớp bài toán NP-hard nên cho đến thời điểm
nay vẫn chưa có một thuật tốn hiệu quả để xử lý bài tốn với kết quả chính xác
trong thời gian đa thức. Các thuật tốn chính xác hiện nay có độ phức tạp tính
tốn theo hàm mũ, nên chỉ mang tính lý thuyết mà chưa thể áp dụng trong thực
15


tế. Các nghiên cứu này gồm các thuật tốn chính xác cho tập đỉnh thống trị của
Fomin, Van Rooij dựa trên thuật toán nhánh và rút gọn [8][23]. Các thuật toán
khả dụng hiện nay cho bài toán này là các thuật toán metaheuristic với các
phương pháp kinh điển gồm tối ưu đàn kiến, giải thuật di truyền, tối ưu bầy đàn,
các thuật tốn memetic, các thuật tốn tìm kiếm địa phương, và thuật tốn
matheuristic.
Các thuật tốn matheuristic có ưu điểm là đưa ra lời giải đủ tốt trong một
thời gian hợp lý so với các thuật toán tham lam hoặc các thuật tốn ngẫu nhiên.
Các cơng trình nghiên cứu bao gồm: áp dụng thuật toán tối ưu đàn kiến để tìm
tập đỉnh thống trị [17] [19], áp dụng thuật tốn di truyền để tìm các tập thống trị
[17], áp dụng thuật tốn bầy đàn để tìm tập đỉnh thống trị [13], áp dụng các thuật
tốn memetic để tìm tập đỉnh thống trị [14], áp dụng thuật tốn tìm kiếm địa
phương với kỹ thuật cấu hình kiểm thử dựa trên các hàm điểm tần suất [26], các
nghiên cứu lên quan đến matheuristic như kết hợp các thuật toán tham lam với
quy hoạch nguyên và việc kết hợp tìm kiếm tabu với quy hoạch ngun [1] [2].
Các thuật tốn bầy đàn thì dựa vào số lượng cá thể và phương pháp phát
triển quần thể nên thường chạy khá chậm hoặc là chúng bị tăng một lượng chi

phí về thời gian do kết hợp với cả các thuật tốn tìm kiếm địa phương để cải
thiện kết quả. Các thuật toán matheuristic là sự kết hợp với các thuật toán
metaheuristic với quy hoạch nguyên. Trong các phương pháp matheuristic được
đề xuất hiện này thì có hai chiến lược được đề ra là có gắng khởi tạo lời giải tốt
và sử dụng quy hoạch nguyên để tiếp tục tìm kiếm lời giải hoặc hạn chế khơng
gian tìm kiếm để đưa ra bài tốn rút gọn sau đó dùng quy hoạch nguyên để giải
quyết.
Điều kiện kết thúc của các thuật toán trên thường dựa trên số lần lặp hoặc
giới hạn thời gian chạy và các tham số này được người dùng đưa ra do quá trình
thực nghiệm. Các kết quả thực nghiệm đưa ra đã cho thấy hiện nay các thuật
tốn tìm kiếm địa phương hoặc các thuật toán tabu kết hợp quy hoạch nguyên là
tốt nhất trong số tất cả các thuật toán đã được áp dụng để tìm tập đỉnh thống trị.
Ngồi ra, các thuật tốn tìm kiếm địa phương cịn được áp dụng cho các tập dữ
liệu lớn [12] [2].
Các thuật tốn tìm kiếm địa phương hoạt động khá tốt tuy nhiên còn rất
nhiều điểm hạn chế về chất lượng như kết quả thực nghiệm trên bộ dữ liệu
BHOSLIB và bộ dữ liệu DIMACS trong thực nghiệm. Các nghiên cứu việc áp
dụng các phương pháp khác thì có chất lượng lời giải hạn chế hoặc thời gian
16


gian chạy khá chậm. Các hạn chế này có thể được khắc phục bởi thuật tốn tìm
kiếm với số lượng hàng xóm lớn (LNS). Bên cạnh đó, để hạn chế bớt các đỉnh
kém chất lượng, thuật toán GRASP được sử dụng để làm giải quyết vấn đề này.
Tìm kiếm với số lượng hàng xóm lớn là thuật tốn sử dụng số lượng lớn
các ứng viên trong một vùng rộng lớn hơn các thuật tốn tìm kiếm địa phương
đã biết trước đó. Thuật tốn được đề xuất lần đầu tiên bởi L.Shaw, và đã được
áp dụng hiệu quả để giải quyết bài tốn định tuyến giao thơng [20]. Ý tưởng của
thuật tốn là lựa chon các ứng viên có khoảng cách lớn trong khơng gian tìm
kiếm so với ứng viên hiện tại (thuật toán (1)).

Thuật toán LNS sử dụng hai phép tốn là DEL (phép xóa) và REPAIR
(phép sửa) để tìm kiếm lời giải có chất lượng tốt, trong đó để tạo ra ứng viên
mới S+ sẽ được tạo ra từ lời giải hiện tại S. Nếu S+ được chấp nhận bởi
ACCEPT(S, S+), thuật toán sẽ tiếp tục tiến hành xét duyệt tại ứng viên S+. Phép
tốn DEL sẽ xóa đi một phần trong lời giải S để tạo S−. Do việc loại bỏ một
phần lời giải nên S− thường vi phạm các điều kiện đặt ra. Do vậy, để tạo ra ứng
viên mới chấp nhận được phép toán REPAIR sẽ thêm vào một số thành viên vào
S− để tạo ứng viên S+. Do hai phép toán DEL và REPAIR bớt và thêm một phần
của lời giải S nên S+ và S có sự sai khác khá lớn. Số lượng ứng viên mới có thể
được tạo ra từ S là nhiều hơn rất nhiều so với các thuật tốn tìm kiếm địa
phương trước đây.
Các phép toán DEL và REPAIR rất đa dạng và phong phú phụ thuộc vào
từng loại bài toán khác nhau và do người dùng lựa chọn. Các thuật toán này kết
hợp với nhau để tạo nên một thuật tốn hiệu quả. Ví dụ, việc lựa chọn phần tử
để loại bỏ trong một lời giải S có thể tuân theo phân bố chuẩn, hoặc phân bố
đều. Việc kết hợp sử dụng các phép toán này sẽ làm tăng độ hiệu quả của thuật
tốn và phương pháp thích nghi tìm kiếm với số lượng hàng xóm lớn được đề
xuất. Phương pháp này dựa vào việc gán trọng số cho mỗi thuật toán và cập
nhập các trọng số này sau mỗi lần thực thi một phép tốn nào đó [16].
procedure Tìm kiếm với số lượng hàng xóm lớn – LNS;
Begin
Khởi tạo lời giải S;
S∗←S
while ( chưa chạy hết thời gian tìm kiếm ) do
S− ← DELETE(S); // hàm DELETE xóa một số thành phần
trong lời giải S
17


S+ ← REPAIR(S−); // hàm REPAIR thêm một số đỉnh cho đến

khi hợp lệ
if ACCEPT(S, S+) then // lời giải S+ có được chấp nhận để xét
tiếp khơng
S← S+;
end-if
if (S+ tối ưu hơn S∗ ) then
S∗ = S+
end-if
end-while
Đưa ra lời giải S;
End;
Thuật Tốn 1: Tìm kiếm với số lượng hàng xóm lớn - LNS

Thủ tục GRASP được sử dụng lần đầu tiên để giải quyết bài toán tập phủ
[7]. Đây là sự kết hợp khéo léo giữa các thuật toán tham lam, danh sách hạn chế
và sự lựa chọn ngẫu nhiên được trình bày trong thuật tốn (2). Các hàm đánh giá
ở trong thủ tục đều là các hàm tham lam, và các ngưỡng để tuyển chọn ứng viên
đều do người dùng tự thiết lập. Việc chọn tham số tối ưu thường là do người
dùng sử dụng thực nghiệm. Thuật tốn này có ưu điểm là dễ cài đặt, độ phức tạp
thấp và cho chất lượng lời giải vừa phải. Thuật tốn đã áp dụng để giải quyết bài
tốn tìm tập đỉnh thống trị trong thuật toán memetic được đề xuất bởi Gen Ling
[14].
Procedure

Thuật toán GRASP

Input

X = {x1, x2, …, xn}


Begin
S ← {};
while (S chưa là lời giải hợp lệ) do
pi←{fval{xi} | xi∉S}; // fval là hàm đánh giá giá trị của xi
pmax ←maxp (p);
RCL ← {xi | pi≤ 𝛼 ∗ 𝑝𝑚𝑎𝑥}; // danh sách hạn chế RCL
xp ← lựa chọn ngẫu nhiên với phân bố đều từ danh sách RCL;
S ← S ∪ xp ;

18


end-while;
Đưa ra lời giải S;
End;
Thuật Toán 2: Thủ tục tham lam thích nghi ngẫu nhiên GRASP

Thuật tốn tạo danh sách RCL dựa trên mức ngưỡng tỉ lệ 𝛼 với giá trị
đánh giá lớn nhất trên tập các ứng viên X. Giá trị 𝛼 nếu càng lớn thì kích thước
của RCL càng lớn và ngược lại càng bé. Nếu RCL chỉ có 1 phần tử, thuật tốn
GRASP sẽ trở thành thuật tốn tham lam. Thơng thường, giá trị 𝛼 được chọn
vừa đủ để giới hạn kích thước của RCL và chọn những ứng viên tiềm năng đê
tạo ra các lời giải có chất lượng tốt hơn. Bên cạnh đó, ứng viên được thêm vào
sẽ được chọn ngẫu nhiên trong danh sách RCL, nên thuật tốn có thể cho ra lời
giải khác nhau trên cùng một đầu vào. Số lượng các lời giải có thể tạo ra từ thuật
tốn này phụ thuộc vào giá trị 𝛼.
Từ đây, tôi đề xuất áp dụng thuật tốn kết hợp tìm kiếm với số lượng hàng
xóm lớn với GRASP cho bài tốn tìm tập đỉnh thống trị có trọng số cực tiểu.
Việc kết hợp này được hình thành dựa vào việc áp dụng các chiến thuật xóa đỉnh
khác nhau, và áp dụng GRASP cho phần khởi tạo và thuật toán chỉnh sửa đỉnh

để tạo thành các tập đỉnh thống trị có chất lượng tốt. Trong đó, các phần đóng
góp gồm:
1. Đề xuất thuật tốn tìm kiếm với số lượng hàng xóm lớn,
2. Chứng minh độ hiệu quả của thuật toán so với các thuật toán khác
bằng thực nghiệm,
3. Áp dụng cho ứng dụng chọn người điều hành nhóm moderatorsselector.
Luận văn được tổ chức thành 4 chương ngoại trừ phần kết luận. Chương 1
giới thiệu vấn đề, các nghiên cứu, ứng dụng liên quan, và một số định lý quan
trọng trong lý thuyết về độ phức tạp tính tốn. Chương 2 trình bày về thuật tốn
kết hợp tìm kiếm với số lượng hàng xóm lớn HLNS cho bài tốn tìm tập đỉnh
thống trị có trọng số cực tiểu, thuật toán cho lời giải khá tốt. Chương 3 đưa ra
kết quả thực nghiệm của thuật toán trên 2 bộ dữ liệu BHOSLIB và DIMACS với
các phân tích so sánh nhận xét đánh giá so với cá thuật toán đã có. Chương 4
trình bày về áp dụng thuật tốn tìm tập đỉnh thống trị vào trong ứng dụng chọn
người điều hành trong nhóm trên mạng xã hội.

19


Chương 1. Giới Thiệu Bài Toán Tập Đỉnh Thống Trị Có Trọng Số
Nhỏ Nhất
Chương này chủ yếu giới thiệu về bài toán tập đỉnh thống trị và những
nghiên cứu về nó, gồm có:
1. Trình bày về bài tốn liên quan đến tập đỉnh thống trị MDS, MCDS,
MIDS, MkDS, MWDS,
2. Trình bày về các nghiên cứu về phương pháp giải cứu bài tốn MWDS,
3. Trình bày các ứng dụng liên quan đến tập đỉnh thống trị,
4. Trình bày một số định lý quan trọng trong lý thuyết về độ phức tạp tính
tốn:
a) Định lý Cook-Levin,

b) Định lý về khơng có bữa trưa miễn phí (no free-lunch theorem).

20


1.1 Bài tốn tập đỉnh thống trị có trọng số cực tiểu và các bài toán liên quan
Trên một đồ thị vô hướng G = (V, E), một tập đỉnh S ⊆ V là tập đỉnh
thống trị, nếu bất kỳ đỉnh v ∈ V và v ∉ S, ∃ đỉnh u ∈ S là đỉnh kề với đỉnh v.
Trên một đồ thị vô hướng G bất kỳ luôn tồn tại ít nhất một tập đỉnh thống trị.
Các vấn đề liên quan đến tập đỉnh thống trị gồm:
1. Tìm tập đỉnh thống trị có số lượng nhỏ nhất - MDS (minimum
dominating set),
2. Tìm tập đỉnh thống trị liên thơng nhỏ nhất - MCDS (minimum
connected dominating set),
3. Tìm tập đỉnh thống trị độc lập nhỏ nhất - MIDS (minimum independent
dominating set),
4. Tìm tập đỉnh thống trị S với việc mỗi đỉnh v ∉ S, ∃ đỉnh u ∈ S, sao cho
tồn tại đường đi giữa hai đỉnh không quá k cạnh - MkDS (minimum kdominating set),
5. Tìm tập đỉnh thống trị có trọng số nhỏ nhất - MWDS (minimum
dominating set).
Với đồ thị vô hướng G = (V, E), ta gọi C là ma trận kề biểu diễn các cạnh
của đồ thị, trong đó: mỗi phần tử Cij = 1 biểu thị có cạnh kết nối giữa đỉnh i và
đỉnh j, Cij = 0 biểu thị khơng có cạnh kết nối giữa đỉnh i và đỉnh j. Vec tơ W là
vec tơ trọng số, trong đó w(i) là giá trị của thành phần thứ i của W, biểu diễn
trọng số của đỉnh i. Mỗi một tập đỉnh D ⊆ V được biểu diễn bởi một vec tơ nhị
phân x, trong đó x(i) là giá của thành phần thứ i và nhận giá trị 0 hoặc 1 biểu thị
đỉnh đó được chọn đỉnh thống trị hay không. Một tập đỉnh S ⊆ V với biểu diễn x
là tập đỉnh thống trị nếu thỏa mãn điều kiện (1.1)
∑𝑛𝑗=1 𝐶𝑖𝑗 × 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛


(1.1)

Từ đây, các bài toán MDS, MCDS, MIDS, MkDS, MWDS được mơ hình
hóa mơ hình hóa tốn học như sau:
1. bài tốn tìm tập đỉnh thống trị có kích thước nhỏ nhất (MDS) được
mơ hình hóa theo công thức (1.2)
𝑛

𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1

21


𝑛

𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛

(1.2)

𝑗=1

2. bài tốn tìm tập đỉnh thống trị liên thơng có kích thước nhỏ nhất
(MCDS) được mơ hình hóa theo cơng thước (1.3)
𝑛

𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1
𝑛


𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀= 1, 𝑛
𝑗=1

𝑛ế𝑢 𝑥𝑖 + 𝑥𝑗 = 2, 𝑡ℎì 𝐶𝑖𝑗 = 1

(1.3)

3. bài tốn tìm tập đỉnh thống trị độc lập có kích thức nhỏ nhất (MIDS)
được mơ hình hóa theo cơng thức (1.4)
𝑛

𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1
𝑛

𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛
𝑗=1

𝑛ế𝑢 𝑥𝑖 + 𝑥𝑗 = 2, 𝑡ℎì 𝐶𝑖𝑗 = 0

(1.4)

4. bài tốn tìm tập đỉnh thống trị có kích thước nhỏ nhất (MkDS) được
mơ hình hóa theo cơng thức (1.5)
𝑛

𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1

22



𝑛

𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛
𝑗=1

𝑛ế𝑢 𝑥𝑖 + 𝑥𝑗 = 2, 𝑐ó đườ𝑛𝑔 đ𝑖
𝑔𝑖ữ𝑎 𝑖 𝑣à 𝑗 𝑘ℎô𝑛𝑔 𝑞𝑢á 𝑘 đỉ𝑛ℎ

(1.5)

5. bài tốn tìm tập đỉnh thống trị có trọng số nhỏ nhất (MWDS) được
mơ hình hóa theo cơng thức (1.6)
𝑛

𝑚𝑖𝑛𝑥 ∑ 𝑤𝑖 𝑥𝑖
𝑖=1
𝑛

𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛

(1.6)

𝑗=1

Tất cả các bài toán trên đều được chứng minh là bài toán NP-Hard. Việc
chứng minh này dựa vào phép rút gọn xấp xỉ L-approximation giữa các bài toán
tập đỉnh thống trị và tập phủ [3][5]. Do bài toán tập phủ (set covering) là một
trong 21 bài toán được chứng minh thuộc lớp NP-Hard bởi R.Karp [9], nên các

bài toán liên quan đến tập đỉnh thống trị đều là NP-Hard.
Sau đây là phép rút gọn xấp xỉ L-reduction giữa bài toán tập đỉnh thống trị
nhỏ nhất và tập phủ nhỏ nhất. Từ bài toán tập phủ sang tập đỉnh thống trị: với
bài toán p = (S, U), trong đó: U = u1, ... , um là tập chứa toàn bộ các thành phần
cơ bản, S = S1, S2, ..., Sn là tập các tập đỉnh thỏa mãn S ⊆ U. Cho I là tập hợp các
chỉ mục của S, tại đây đồ thị G = (E, V) được xây dựng trong đó E = U ∪ I là tập
các đỉnh của G, V được biểu diễn bằng ma trận kề trong đó các đỉnh thuộc I tạo
thành một đồ thị đầy đủ, các đỉnh thuộc U là các đỉnh độc lập lẫn nhau (tức là:
CIi, Ij = 1, ∀Ii, Ij ∈ I , Cui, uj = 0, và CIi, uk = 1 ∀uk ∈ Si).
1. Nếu tồn tại một tập phủ P ∪ S, thì tồn tại tập đỉnh thống trị tương
ứng là tập con của I trên G. Ví dụ: bài tốn p = (S, U), trong đó: U =
u1, u2, u3, u4, u5, S = S1, S2, S3 với S1 = u1, u2, S2 = u1, u3, u4, S3 = u4,
u5. Đồ thị G = (V, E) được xây dựng gồm V = I1, I2, I3, u1, u2, u3, u4,

23


u5. E = (I1, I2), (I2, I3), (I3, I1), (I1, u1), (I1, u2), (I2, u1), (I2, u3), (I2, u4),
(I3, u4), (I3, u5) (xem hình vẽ (1)). Tại đây, tồn tại duy nhất một tập
phủ P = S1, S2, S3, và trên đồ thị G ta có tập đỉnh thống trị tương ứng
là D = I1, I2, I3,
2. Từ bài toán tập đỉnh thống trị sang tập phủ: với đồ thị G = (V, E) (V
= v1, v2, ..., vn), ta xây dựng bài toán tập phủ với U = V, S = S1, S2 ,
... , Sn, với Si là tập hợp của vi với các đỉnh kề nó. Với mỗi tập phủ D
trên đồ thị G ta có tập phủ P trên đồ tập S tương ứng. Ví dụ: đồ thị
G = (V, E) (V = v1, v2, v3, v4, v5, E = (v1, v2), (v1, v3), (v2, v4), (v2, v5),
(v3, v4), (v3, v5)), ta có tập đỉnh thống trị D = (v2, v3) tương ứng với
tập phủ P = (S2, S3) (xem hình vẽ 2).

I

1

2

3

U
1

3

2

4

5

Hình 1: Đồ thị chuyển đổi giữa bài toán SC và bài toán MDS

G = (V, E)

1

2

3

S2

S3

4

5

Hình 2: Đồ thị chuyển đổi từ bài toán tập MDS sang bài toán SC

Các bài toán MDS, MCDS, MIDS, MkDS, MWDS là các bài toán thuộc
lớp bài toán NP-hard. Lời giải của một trong bài toán trên có thể được áp dụng

24


lại cho nhau với một số thay đổi nhất định. Chẳng hạn, lời giải của vấn đề MDS
có thể được áp dụng cho lời giải của MCDS với việc thêm rằng buộc liên thơng
vào trong thuật tốn. lời giải của bài tốn MWDS có thể áp dụng được trực tiếp
cho bài toán MDS với việc đặt trọng số mỗi đỉnh bằng 1. Do mối quan hệ mật
thiết giữa các bài tốn này, luận văn trình bày phương pháp để giải quyết cho
vấn đề MWDS là bài toán tổng quát nhất trong số các bài toán trên.
1.2 Các nghiên cứu liên quan
Bài toán tập đỉnh thống trị là một trong những bài tốn chưa có lời giải
chính xác trong thời gian đa thức trên những thiết bị phần cứng hiên nay. Do
độ phức tạp tính tốn hiện nay cho các bài toán dạng này là độ phức tạp theo
hàm mũ nên cộng đồng nghiên cứu ứng dụng thường ưu thích sử dụng các
phương pháp metaheuristic với độ tốt của lời giải tỷ lệ với thời gian thực thi
của thuật toán. Do vậy, trong khoảng thời gian vừa đủ, chất lượng của lời giải
thường sai khác so với lời giải chính xác một lượng chấp nhận được tùy vào
từng yêu cầu của các ứng dụng trong thực tế. Các phương pháp metaheuristic
chủ yếu dành cho lớp bài toán này thường là:
1. giải thuật di truyền (GA) [17],
2. phương pháp tối ưu đàn kiến (ACO) [17][19],

3. phương pháp tối ưu bầy đàn (PSO) [13],
4. phương pháp memetic (MA) [14],
5. tìm kiếm địa phương (LS) [1][26],
6. tìm kiếm với số lượng hàng xóm lớn (LNS)[14].
Các phương pháp trên là những phương pháp kinh điển để giải quyết lớp
bài toán NP-Hard được nghiên cứu và sử dụng trong gần 50 năm của ngành
khoa học máy tính. Các phương pháp trên đều mơ phỏng lại các hiện tượng tự
nhiên như thuật toán di truyền lấy cảm hướng từ việc giao phối giữa các cá thể
trong loài với nhau, phương pháp tối ưu đàn kiến lấy cảm hứng từ việc kiếm
mồi của đàn kiến, phương pháp tối ưu bầy đàn lấy cảm hứng từ việc kiếm mồi
của đàn chim trong tự nhiên. Các phương pháp này đều sử dụng lại kinh
nghiệm thu được từ lần khám phá trước để đưa ra lời giải tiếp theo.
Các kinh nghiệm này đến từ kinh nghiệm người dùng hoặc là các lời
giải từ các lần khám phá ngẫu nhiên trong không gian tìm kiếm. Ngồi ra, một
hướng nghiên cứu mới matheuristic gần đây kết hợp giữa phương pháp
metaheuristic với quy hoạch nguyên (IP) để đưa ra lời giải với chất lượng tốt
trong thời gian hợp lý cũng đã thu được một số thành tựu đáng kể.
25