ĐẠI HỌC HUẾ
VIỆN ĐÀO TẠO MỞ VÀ CÔNG NGHỆ THÔNG TIN

TIỂU LUẬN HỌC PHẦN
PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC

ĐỀ TÀI
NGHIÊN CỨU TÌM KIẾM HEURISTIC CHO
CÁC BIẾN THỂ CỦA BÀI TỐN HÔN NHÂN ỔN ĐỊNH

Chuyên ngành đào tạo: Khoa học máy tính
Mã số sinh viên: 7052900505
Họ tên học viên: ThS. Nguyễn Thị Uyên
Cơ quan công tác: Viện Kỹ thuật và Công nghệ,
Trường Đại học Vinh
Người hướng dẫn khoa học:
PGS.TS. Nguyễn Đức Vũ
Đại học Huế

Huế, 08/2023


Mục lục

1

Tính cấp thiết của đề tài . . . . . . . . . . . . . . . . .

1

1.1

Mơ tả bài tốn . . . . . . . . . . . . . . . . . .

1

1.2

Lý do chọn đề tài . . . . . . . . . . . . . . . . .

5

1.3

Ý nghĩa của đề tài . . . . . . . . . . . . . . . .

8

2

Mục tiêu đề tài . . . . . . . . . . . . . . . . . . . . . .

8

3

Nhiệm vụ nghiên cứu . . . . . . . . . . . . . . . . . . .

9

4


Ý nghĩa khoa học và thực tiễn . . . . . . . . . . . . . .

9

5

Đối tượng và phạm vi nghiên cứu . . . . . . . . . . . .

10

5.1

Đối tượng nghiên cứu . . . . . . . . . . . . . . .

10

5.2

Phạm vi của đề tài . . . . . . . . . . . . . . . .

10

6

Phương pháp nghiên cứu . . . . . . . . . . . . . . . . .

10

7


Bố cục của luận án . . . . . . . . . . . . . . . . . . . .

11

8

Các nghiên cứu liên quan

. . . . . . . . . . . . . . . .

11

9

Tiến độ thực hiện đề tài . . . . . . . . . . . . . . . . .

14

10

Dự kiến kết quả đạt được . . . . . . . . . . . . . . . .

16

11

Người hướng dẫn . . . . . . . . . . . . . . . . . . . . .

16


2


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

1
1.1

Tính cấp thiết của đề tài
Mơ tả bài tốn

Bài tốn hôn nhân ổn định (Stable Marriage Problem, SMP) là một
bài toán ghép cặp nổi tiếng được giới thiệu lần đầu tiên bởi Gale và
Shapley [12]. Bài toán SMP gồm một tập n người nam và một tập n
người nữ, trong đó mỗi người xếp hạng “thích” những người khác giới
theo một thứ tự ưu tiên từ 1 đến n trong một danh sách xếp hạng.
Mục đích của bài tốn là tìm một phép ghép giữa những người nam và
người nữ sao cho thỏa mãn tính ổn định (stable) theo một tiêu chuẩn
nào đó.
Một ví dụ về bài tốn SMP gồm 8 nam và 8 nữ với xếp hạng
“thích” của mỗi người được cho như bảng 1 [40]. Trong đó M0 là phép
ghép ổn định tối ưu cho tập nam, M10 là phép ổn định tối ưu cho tập
nữ, M3 là phép ghép ổn định tối ưu bình đẳng theo giới tính và M6
là phép ghép ổn định tối ưu tương đương theo giới tính. Đây là một
Bảng 1: Danh sách xếp hạng ưu tiên của 8 nam và 8 nữ
Man
m1
m2
m3

m4
m5
m6
m7
m8

Preference list Woman Preference list
43152687
w1
47381526
28453716
w2
53421867
58142367
w3
28643751
64325817
w4
56834712
65481723
w5
18523647
74256813
w6
86251743
85637214
w7
52836471
47135826
w8

45716283

bài toán ghép cặp của một số lượng tương đương giữa nam và nữ để
thỏa mãn một điều kiện ổn định tối ưu nào đó. Bài tốn hơn nhân ổn
định kích thước n gồm một tập n người đàn ông và một tập n người
phụ nữ trong đó mỗi người xếp hạng thứ tự "thích" những người khác
1


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

giới theo một thứ tự ưu tiên từ 1 đến n trong một danh sách mà được
gọi là danh sách xếp hạng thứ tự thích. Một phép ghép (matching)
M là một tập n cặp (nam, nữ) trong đó mỗi người đàn ông chỉ được
ghép với một người phụ nữ duy nhất và ngược lại. Nếu một nam m
và một nữ w là một cặp trong phép ghép M thì m và w được gọi là
"bạn ghép" hay cặp ghép trong M và được ký hiệu là m = M (w) và
w = M (m). Một nam m và một nữ w tạo thành một cặp ghép khối
(blocking pair) trong M nếu m "thích" w hơn M (m) (tức là thứ tự
ưu tiên của w bé hơn M (m) trong danh sách thích của m) và w thích
m hơn M (w). Một phép ghép M mà không chứa mọi cặp ghép khối
thì M được gọi là phép ghép ổn định, ngược lại M được gọi là không
ổn định. Ký hiệu pm (w) là thứ tự của nữ w trong danh sách xếp hạng
thích của nam m và pw (m) là thứ tự của nam m trong danh sách xếp
hạng thích của nữ w. Cho một phép ghép ổn định M , giá của tập nam
trong phép ghép M , ký hiệu là sm(M ), và giá của tập nữ trong phép
ghép M , ký hiệu là sw(M ), được định nghĩa như sau:
sm(M ) =

X


pm (w),

(1)

pw (m).

(2)

(m,w)∈M

sw(M ) =

X
(m,w)∈M

Định nghĩa 1 (tối ưu cho tập nam): Một phép ghép M được
gọi là phép ghép ổn định tối ưu cho tập nam (man-optimal stable
matching) nếu M có giá trị sm(M ) là bé nhất trong tất cả các phép
ghép ổn định.
Định nghĩa 2 (tối ưu cho tập nữ): Một phép ghép M được
gọi là phép ghép ổn định tối ưu cho tập nữ (woman-optimal stable
matching) nếu M có giá trị sw(M ) là bé nhất trong tất cả các phép
ghép ổn định.
Cho bài tốn hơn nhân ổn định kích thước n, Gale and Shapley
2


Đề cương dự tuyển trình độ tiến sỹ - năm 2019


đã đề nghị một thuật toán, gọi là thuật toán Gale-Shapley [?], để tìm
một nghiệm tối ưu cho tập nam trong thời gian O(n2 ). Về cơ bản,
thuật toán là một dãy các đề nghị từ mỗi nam tới những người nữ
để tìm phép ghép tối ưu cho tập nam giới. Nếu vai trò của nam giới
được thay đổi cho nữ giới, tức là đề nghị từ mỗi nữ tới các nam, thì
nghiệm của thuật tốn Gale-Shapley là nghiệm tối ưu theo tập nữ.
Chú ý rằng, trong phép tối ưu theo tập nam giới thì mỗi nam chọn
được một người phụ nữ mà mình thích nhất nhưng mỗi nữ sẽ có người
nam mà mình ít thích nhất. Tương tự, trong phép tối ưu theo tập nữ
giới thì mỗi nữ chọn được một người nam mà mình thích nhất nhưng
mỗi nam sẽ có người phụ nữ mà mình ít thích nhất. Với bài tốn hơn
nhân ổn định kích thước n, có thể có nhiều phép ghép ổn định khác
với phép ghép ổn định tối ưu theo tập nam và phép ghép ổn định tối
ưu theo tập nữ. Hơn nữa, có thể nói rằng phép ghép ổn định tối ưu
theo tập nam và phép ghép ổn định tối ưu theo tập nữ là những phép
ghép “ích kỷ” cho tập nam và tập nữ, tức là những người đề xuất ln
có được bạn ghép mà mình thích nhất cịn người được ghép ln nhận
được bạn ghép tồi nhất trong danh sách ưu tiên của họ. Do đó cần tìm
các phép ghép ổn định tối ưu khác mà cân bằng cho cả tập nam và
tập nữ. Cho một phép ghép ổn định M , giá của phép ghép bình đẳng
theo giới tính (egalitarian cost) của M , ký hiệu là c(M ), và giá của
ghép tương đương theo giới tính (sex-equality cost) của M , ký hiệu là
d(M ), được định nghĩa như sau:
c(M ) = sm(M ) + sw(M ),

(3)

d(M ) = |sm(M ) − sw(M )|.

(4)


Định nghĩa 3 (tối ưu bình đẳng theo giới tính): Một phép
ghép M được gọi là phép ghép ổn định tối ưu bình đẳng theo giới tính
(egalitarian cost) nếu M có giá trị c(M ) là bé nhất trong tất cả các
3


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

phép ghép ổn định.
Định nghĩa 4 (tối ưu tương đương theo giới tính): Một phép
ghép M được gọi là phép ghép ổn định tối ưu tương đương theo giới
tính (sex-equality cost) nếu M có giá trị d(M ) là bé nhất trong tất cả
các phép ghép ổn định.
Bài tốn hơn nhân ổn định có các ràng buộc chặt, đó là yêu cầu
số nam và số nữ phải bằng nhau và mỗi người phải xếp thứ tự ưu tiên
của tất cả những người khác giới theo một thứ tự ưu tiên nghiêm ngặt
do đó bài tốn này khơng được ứng dụng nhiều trong thực tế. Từ đó,
các biến thể của bài toán SMP đã được đề xuất.
Một biến thể của SMP được gọi là bài tốn hơn nhân ổn định
với thứ tự ưu tiên ngang bằng (SMT - Stable Marriage Problem with
Ties), nghĩa là một người có thể xếp hạng mức độ ưu tiên kết hôn với
hai hay nhiều người khác giới bằng nhau. Một biến thể khác của SMP
là bài tốn hơn nhân ổn định với danh sách ưu tiên không đầy đủ
(SMI - Stable Marriage Problem with Incomplete lists), nghĩa là một
người có thể khơng xếp hạng một người khác giới bằng cách khơng
đưa người đó vào danh sách ưu tiên. Kết hợp hai biến thể trên, ta
có dạng tổng qt hơn là bài tốn hơn nhân ổn định với thứ tự ưu
tiên ngang nhau và danh sách ưu tiên không đầy đủ (SMTI - Stable
Marriage Problem with Ties and Incomplete lists).

Các biến thể của SMP xuất hiện phổ biến trong nhiều ứng dụng
trong thực tế như sắp xếp sinh viên thực tập [36], phân công đề tài [1,
3], xếp phòng ở [19, 11], cũng như nhiều ứng dụng trong kinh tế và các
lĩnh vực khác. Năm 2012, Shapley và Roth đã được trao giải thưởng
Nobel kinh tế với các kết quả đạt được trong đó vận dụng mơ hình
xuất phát từ bài tốn này.

4


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

Bảng 2: SMT với danh sách xếp hạng ưu tiên của 8 nam và 8 nữ
Man
m1
m2
m3
m4
m5
m6
m7
m8

Preference list Woman Preference list
[4 3] 1 5 2 6 8 7
w1
4 [7 3] 8 1 5 2 6
2 [8 4] 5 3 7 1 6
w2
5 3 [4 2] 1 8 6 7

5 8 1 [4 2] 3 6 7
w3
2 8 [6 4] 3 7 5 1
6 [4 3 2] 5 8 1 7
w4
5 6 [8 3] 4 7 1 2
6 [5 4] 8 1 7 2 3
w5
1 8 5 2 3 [6 4 7]
7 4 [2 5 6] 8 1 3
w6
8 [6 2] 5 1 7 4 3
8 [5 6 3] 7 2 1 4
w7
[5 2] 8 3 6 4 7 1
4 7 [1 3 5] 8 2 6
w8
4 [5 7] 1 6 2 8 3

Bảng 3: SMI với danh sách xếp hạng ưu tiên của 8 nam và 8 nữ
Man
m1
m2
m3
m4
m5
m6
m7
m8


1.2

Preference list Woman Preference list
452687
w1
47381526
284516
w2
53421867
5814267
w3
2864351
645817
w4
56834712
6581723
w5
18523647
7426813
w6
8651743
8563214
w7
5236471
4713826
w8
4516283

Lý do chọn đề tài


Cho tới nay nhiều thuật toán đã được đề xuất giải bài toán SMP
cũng như các biến thể của nó (xem phần tổng quan vấn đề nghiên
cứu). Với các thuật tốn tìm phép ghép tối ưu bình đẳng theo giới tính
(egalitarian cost) và tối ưu tương đương theo giới tính (sex-equality
cost), hầu như mới chỉ có bài tốn SMP được quan tâm. Trong khi đó,
các biến thể SMT, SMI hay SMTI thường xuất hiện nhiều trong các
ứng dụng thực tế. Mặt khác, các thuật toán đã đề xuất thường khơng
hiệu quả về thời gian tính tốn. Điều này một phần là do chúng các
5


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

thuật tốn chưa áp dụng các tính chất của cấu trúc của tập ghép cặp
ổn định để làm giảm các chi phí tính tốn. Do đó, nghiên cứu một cách
có hệ thống bài toán SMP và các biến thể của nó để tìm ra các phương
pháp hiệu quả nhằm giải quyết các biến thể của bài tốn SMP với kích
thước lớn là một lý do quan trọng để tôi chọn đề tài này. Gần đây, bài
toán SMP đã nhận được nhiều sự quan tâm của các nhà nghiên cứu
trong các lĩnh vực Trí tuệ nhân tạo và Tính tốn tối ưu. Năm 2012,
Shapley và Roth đã được trao giải thưởng Nobel kinh tế vì các thành
tựu đạt được dựa trên các mơ hình xuất phát từ bài tốn SMP trong
lĩnh vực quản lý thị trường chứng khốn tại Mỹ. Ngồi ra, bài tốn
SMP có nhiều ứng dụng trong thực tế như: (i) bài toán phân bổ sinh
viên ngành y tới thực tập tại các bệnh viện [30]; (ii) bài toán phân
công giảng viên hướng dẫn sinh viên thực hiện các đề tài [1]; (iii); (iv)
bài toán phân bổ nhà ở cho cư dân [6, 11]; (v) bài toán tối ưu hóa
các yêu cầu dịch vụ của người dùng Internet tới các nhà mạng viễn
thông [5]. Gale và Shapley đã đề xuất một thuật tốn Gale-Shapley
(GS) [12] để tìm ra các cặp ghép ổn định tối ưu từ một phía theo nam

(man-optimal ) hoặc theo nữ (woman-optimal ). Tuy nhiên do những
ràng buộc nghiêm ngặt trong danh sách xếp hạng, tức là yêu cầu số
nam và số nữ phải bằng nhau và mỗi người phải xếp hạng tất cả các
thành viên khác giới theo một thứ tự ưu tiên nhất định, vì vậy bài tốn
SMP thường ít gặp trong các ứng dụng thực tế. Do đó, một số biến
thể của bài toán SMP đã được đề xuất gần đây như: (i) bài tốn hơn
nhân ổn định với thứ tự ưu tiên ngang bằng (Stable Marriage problem
with Ties, SMT), tức là một người có thể xếp hạng nhiều người khác
giới với thứ tự ưu tiên bằng nhau; (ii) bài tốn hơn nhân ổn định với
danh sách không đầy đủ (Stable Marriage problem with incomplete,
SMI), tức là một người có thể xếp hạng một số người khác giới trong
danh sách xếp hạng; và (iii) bài tốn hơn nhân ổn định với thứ tự ưu
tiên ngang bằng và không đầy đủ (Stable Marriage Problem with Ties

6


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

and Incomplete lists, SMTI), là sự kết hợp của biến thể SMT và SMI.
Trong bài toán SMT và SMTI, với sự xuất hiện thứ tự ngang hàng
trong danh sách xếp hạng, Irving và cộng sự [22] đã chỉ ra ba điều
kiện của phép ghép ổn định gồm: ổn định yếu (weakly stable), ổn định
mạnh (strongly stable) và siêu ổn định (super-stable). Các tác giả đã
chứng minh rằng một phép ghép ổn định yếu luôn tồn tại, trong khi
phép ghép ổn định mạnh và siêu ổn định có thể khơng tồn tại với mọi
thể hiện của các bài toán SMT và SMTI. Luận án tập trung nghiên
cứu bài tốn tìm một phép ghép ổn định yếu sao cho có nhiều nhất số
cặp nam và nữ được ghép, gọi là bài toán MAXSMTI. Để đơn giản,
luận án gọi một phép ghép ổn định yếu là phép ghép ổn định. Manlove

và cộng sự [7] đã chứng minh rằng bài tốn MAXSMTI là NP-khó,
do đó việc nghiên cứu các thuật tốn tốn hiệu quả để giải quyết vấn
đề này là một thách thức cho các nhà nghiên cứu. Gần đây, bài toán
SMTI được cộng đồng nghiên cứu quan tâm nhiều bởi những ứng dụng
của nó trong thực tế như: (i) bài tốn phân bổ sinh viên ngành y tới
thực tập tại các bệnh viện (Hospitals/Residents with Ties problem,
(HRT)) [30]; (ii) bài tốn phân cơng giảng viên hướng dẫn sinh viên
thực hiện đề tài (Student-Project Allocation problem, SPA) [1, 24]; và
(iii) bài toán phân bổ nhà ở cho dân cư (Stable Roommates problem,
SR) [6, 11]. Mục tiêu của bài tốn MAXHRT là tìm một phép ghép ổn

định sao cho có nhiều nhất số sinh viên ngành y được phân bổ thực
tập tại các bệnh viện. Tương tự bài tốn MAXSPA, có nghĩa là tìm
một phép ghép ổn định sao cho có nhiều nhất số sinh viên nhận được
đề tài do các giảng viên hướng dẫn.
Trong những năm qua, nhiều thuật toán đã được đề xuất giải quyết
bài toán SMTI và các biến thể mở rộng như HRT [30] và SPA [1, 13,
24, 26, 33, 32, 4]. Các hướng tiếp cận chủ yếu là thuật toán xấp
xỉ [1, 2, 25, 18], lập trình nguyên [29, 27], lập trình thích nghi [32],
tìm kiếm cục bộ [13, 39, 37, 40], tìm kiếm bầy đàn [38] và một số

7


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

phương pháp khác [4, 41, 8]. Bài toán SMTI và các biển thể mở rộng
của nó là các bài tốn NP-khó [31, 23]. Mặc dù, đã có nhiều hướng
tiếp cận để giải các bài toán này, tuy nhiên, các phương pháp đã đề
xuất chưa đạt được kết quả mong muốn về chất lượng nghiệm và thời

gian thực hiện cho các bài tốn này với kích thước lớn. Hướng tiếp cận
theo heuristic là các phương pháp giải bài toán dựa trên kinh nghiệm
thông qua việc khám phá một phần không gian tìm kiếm nhằm đưa
ra một nghiệm chấp nhận được, do vậy hướng tiếp cận này sẽ tăng
tốc độ tìm kiếm nghiệm. Ngoài ra, các phương pháp heuristic thường
thể hiện khá tự nhiên với cách suy nghĩ và hành động của con người
dựa trên các kinh nghiệm về sự hiểu rõ bài toán đặt ra.
1.3

Ý nghĩa của đề tài
− Về khoa học: Đóng góp các thuật tốn để giải quyết các biến
thể SMP kích thước lớn, có độ phức tạp thuật toán thấp hơn
các thuật toán trước đây.
− Về thực tiễn: Nếu đề tài thành cơng có thể ứng dụng cho
nhiều bài tốn thực tế có kích thước lớn hơn.

2

Mục tiêu đề tài

Luận án này tập trung nghiên cứu các thuật tốn heuristic để tìm một
phép ghép ổn định yếu với kích thước tối đa cho bài tốn MAX-SMTI
và các mở rộng của bài toán gồm MAX-HRT [30] và MAX-SPA [1, 24].
Mục tiêu nghiên cứu của luận án tập vào ba nội dung chính: (i) Đề
xuất các thuật tốn heuristic để giải quyết bài toán MAX-SMTI; (ii)
Đề xuất các thuật toán heuristic để giải quyết bài toán MAX-HRT;
và (iii) Đề xuất các thuật toán heuristic để giải quyết bài toán MAXSPA. Với mục tiêu đã đặt ra, luận án đạt được các kết quả như sau:
− Đề xuất hai thuật toán giải quyết bài toán MAX-SMTI bao
8



Đề cương dự tuyển trình độ tiến sỹ - năm 2019

gồm thuật tốn MCS và thuật tốn HR. Các đóng góp này
được trình bày ở Chương 2 của luận án và cơng bố ở cơng trình
[A.1] và [A.2].
− Đề xuất hai thuật toán giải quyết bài toán MAX-HRT bao
gồm thuật tốn MCA và thuật tốn HS. Các đóng góp này
được trình bày ở Chương 3 của luận án và cơng bố ở cơng trình
[A.3] và [B.1] (đang gửi tạp chí).
− Đề xuất hai thuật giải quyết bài toán MAX-SPA bao gồm thuật
tốn SPAPheuristic và thuật tốn HAG. Các đóng góp này
được trình bày ở Chương 4 của luận án và cơng bố ở cơng trình
[A.4], [B.2] (đang gửi tạp chí) và [A.5].

3

Nhiệm vụ nghiên cứu
− Nghiên cứu tổng quan bài toán SMP và các biến thể của bài
toán SMP.
− Nghiên cứu các phương pháp đã đề xuất giải quyết bài toán
SMTI và các biến thể của bài toán SMTI.
− Nghiên cứu các thuật tốn tìm kiếm heuristic để giải quyết bài
toán SMTI và các biến thể của bài toán SMTI.
− Cài đặt, thử nghiệm, so sánh và đánh giá các thuật tốn đề
xuất với các thuật tốn khác đã cơng bố cho bài toán SMTI và
các biến thể của bài tốn SMTI với kích thước lớn.

4


Ý nghĩa khoa học và thực tiễn
− Về khoa học: Luận án đề xuất các thuật tốn tìm kiếm heuristic mới để giải quyết bài tốn SMTI các biến thể của bài tốn
SMTI. Đóng góp của các thuật toán để giải quyết các bài toán
là hiệu quả hơn về chất lượng nghiệm và thời gian thực hiện so
với các thuật toán trước đây.
9


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

− Về thực tiễn: Các thuật tốn đề xuất có thể áp dụng để giải
quyết các bài toán tối ưu thỏa mãn ràng buộc, thuộc lớp bài
tốn NP-khó cho nhiều ứng dụng thực tế có kích thước lớn
trong các lĩnh vực y tế, giáo dục, kinh tế và xã hội.

5
5.1

Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu
− Nghiên cứu tổng quan bài toán MAX-SMTI và các biến thể.
− Nghiên cứu các thuật tốn tìm kiếm heuristic cho bài tốn
MAX-SMTI.
− Nghiên cứu các thuật tốn tìm kiếm heuristic cho bài toán
MAX-HRT và MAX-SPA.

5.2

Phạm vi của đề tài
− Nghiên cứu đề xuất các thuật tốn tìm kiếm heuristic cho bài

tốn SMTI và các biến thể của bài toán SMTI.
− Nghiên cứu phương pháp tiến hành thực nghiệm, so sánh và
đánh giá thuật toán đề xuất so với các hướng tiếp cận khác.

6

Phương pháp nghiên cứu
− Nghiên cứu lý thuyết: Nghiên cứu các tài liệu về bài tốn hơn
nhân ổn định và các biến thể đã công bố ở trong và ngồi nước.
Phân tích ưu điểm và các tồn tại của các thuật tốn đã đề xuất.
Trên cơ sở đó, đề xuất các thuật tốn tìm kiếm heuristic để giải
quyết bài tốn với kích thước lớn.
− Nghiên cứu thực nghiệm: Nghiên cứu các các phương pháp xử lý
số liệu thực nghiệm; cài đặt các thuật toán đề xuất và nghiên

10


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

cứu các phương pháp đánh giá hiệu quả của các thuật tốn
được thực hiện bằng ngơn ngữ lập trình MATLAB.

7

Bố cục của luận án
− Mở đầu: Trình bày tổng quan về bài toán nghiên cứu, lý do
chọn đề tài, đối tượng, mục tiêu và nội dung nghiên cứu của
luận án.
− Chương 1 : Trình bày cơ sở lý thuyết và tổng quan tình hình

nghiên cứu của bài tốn SMP và các biến thể.
− Chương 2 : Trình bày các thuật tốn đề xuất giải bài tốn
MAX-SMTI.
− Chương 3 : Trình bày các thuật toán đề xuất giải bài toán
MAX-HRT.
− Chương 4 : Trình bày các thuật tốn đề xuất giải bài tốn
MAX-SPA.
− Kết luận: Trình bày những kết quả đã đạt được và hướng
phát triển trong tương lai.

8

Lịch sử nghiên cứu liên quan
Cho một bài tốn SMP kích thước n, Gusfield [16] đề xuất một

thuật toán để sinh ra tất cả các phép ghép ổn định với độ phức tạp
thời gian O(n2 + n|S|), trong đó |S| là số các phép ghép ổn định của
SMP. Irving và cộng sự [21] khai thác cấu trúc mạng lưới (lattice) của
tập phép ghép ổn định và sử dụng lý thuyết đồ thị để tìm phép ghép
tối ưu bình đẳng với độ phức tạp thời gian là O(n4 ). Vì các thuật tốn
trên là nhưng thuật tốn vét cạn, chúng tìm ra được nghiệm chính xác
theo một tiêu chuẩn tối ưu nào đó. Tuy nhiên vì số lượng phép ghép
ổn định của bài tốn SMP tăng theo hàm mũ [20], các thuật toán
trên là khơng hiệu quả để tìm nghiệm khi bài tốn SMP có kích thước
11


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

lớn. Everaere và cộng sự [10] đề xuất một thoán tốn Swing để tìm

một phép ghép ổn định tối ưu tương đương. Ở vịng lặp lẻ của thuật
tốn, nam giới đóng vai trị là người đề nghị và nữ giới đóng vai trị
là người đáp ứng và vai trị của nam và nữ được hốn đổi ở vịng lặp
chẳn. Thuật tốn Swing có độ phức tạp thời gian là O(n3 ) và chỉ tìm
được một phép ghép ổn định thay vì một phép ghép ổn định tối ưu
tương đương. Giannakopoulos và cộng sự [15] đề xuất một thuât toán
ESMA [15] để tìm một phép ghép ổn định M mà có giá trị c(M ) lớn
nhưng d(M ) bé. Về cơ bản, ý tưởng của thuật toán ESMA tương tự
như ý tưởng của thuật toán Swing, tức là nam và nữ là những người đề
nghị và người đáp ứng trong các vịng lặp của thuật tốn. Tuy nhiên,
trong ESMA người đề nghị là nam khi dấu của hàm sin(k 2 ) là dương
và người đề nghị là nữ khi dấu của hàm là âm, trong đó k là biến đếm
vịng lặp trong thuật tốn. Thuật tốn ESMA có độ phức tạp thời
gian là O(n2 ) và chỉ tìm được một phép ghép ổn định M với c(M ) lớn
và d(M ) bé nhưng M không phải là phép ghép ổn định tối ưu bình
đẳng và cũng khơng phải là phép ghép ổn định tối ưu tương đương.
SMT là một biến thể đầu tiên của bài toán SMP, với thứ tự ưu tiên
ngang bằng nhau. Manlove và cộng sự đã nghiên cứu thuật toán xấp
xỉ với độ dài bằng 2 cho bài tốn SMT [7]. Với sự mở rộng này thì
việc tìm được phép ghép ổn định là tương đối phức tạp. Tuy nhiên,
trong nghiên cứu này, các tác giả đã đề xuất được hai giải thuật xấp
xỉ để giải quyết bài toán ghép cặp ổn định SMT với danh sách ưu tiên
ghép cặp có nhiều nhất 1 phép ghép có độ ưu tiên bằng nhau và có
độ dài bằng 2. Halldorsson và cộng sự [17] đề xuất một thuật toán với
độ phức tạp đa thức để tìm nghiệm xấp xỉ tối ưu bình đẳng và tối ưu
tương đương cho bài tốn SMT dựa trên lý thuyết đồ thị. Gần đây,
D´aniel Marx và cộng sự đã nghiên cứu các thuật tốn tìm kiếm cục
bộ và thuật toán xấp xỉ FPT [9] với độ phức tạp NP để tìm ra nghiệm
tối ưu bình đẳng. Ngoài ra, Trang và các cộng sự đã đề xuất phương


12


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

pháp tìm kiếm cục bộ để giải quyết bài tốn SMT nhằm tìm kiếm các
kết hợp ổn định bình đẳng và bình đẳng giới [37]. Thuật tốn dựa vào
phép ghép ổn định đối với nam giới thông qua một chuỗi các kết hợp
ổn định. Đồng thời, dựa vào một chuỗi các kết hợp ổn định để tìm
kiếm các kết hợp ổn định bình đẳng và bình đẳng giới. Đối với mỗi kết
hợp ổn định của chuỗi, một tập hợp lân cận được xây dựng bằng cách
sử dụng thao tác ghép cặp. Kết hợp ổn định lân cận tốt nhất được
chọn để tiếp tục tìm kiếm. Thực nghiệm cho thấy thuật toán tương
đối hiệu quả.
SMI là một biến thể khác của bài tốn SMP với danh sách ưu tiên
khơng đầy đủ. Patrick Prosser đã trình bày bài tốn bạn cùng phịng
ổn định (Stable Roommates-SR) [34]. Nghiên cứu đã sử dụng mã hóa
ràng buộc (Constraint Encoding-CE) với O(n2 ) ràng buộc nhị phân
(binary constraints) với thời gian thực hiện là O(n3 ). Mơ hình hóa của
bài tốn cùng phịng ổn định với danh sách khơng đầy đủ (SRI) cũng
tương tự mơ hình hóa các vấn đề hơn nhân ổn định (SM) với danh
sách khơng đầy đủ (SMI). Mơ hình bài tốn SRI cho các kết quả tốt
cho các trường hợp có n <= 1000 trong khoảng 2 giây. Kết quả thực
nghiệm cho thấy tuy độ phức tạp thuật toán là NP nhưng việc tìm
các tối ưu bình đẳng tương đối là đơn giản. Liu và cộng sự [35] đã
nghiên cứu biến thể SMI áp dụng cho bài toán kinh tế. Nghiên cứu
đã đề xuất và cải tiến thuật toán Gale and Shapley [?], đồng thời đưa
ra một số khái niệm và định nghĩa mới cho vấn đề SMI trong thực tế
nhằm để phân công công nhân trong công ty hợp lý hơn.
Kết hợp hai biến thể SMT và SMI ta được biến thể SMTI. Gent

và cộng sự đã trình bày thuật tốn hoàn chỉnh đầu tiên cho biến thể
SMTI [14]. Nghiên cứu này đã trình bày các giải pháp lập trình ràng
buộc để giải quyết vấn đề SMTI và tối ưu hóa các trường hợp ngẫu
nhiên của SMTI. Kết quả của phương pháp này đã tìm ra được các
cặp ghép ổn định và tối ưu với chi phí ít hơn khi thay đổi ngẫu nhiên

13


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

danh sách các tham số. Các trường hợp ngẫu nhiên cho thấy rõ sự
khác biệt đáng kể về kích thước giữa nhỏ nhất và lớn nhất của biến
thể SMTI. Halldorsson và cộng sự [17], đã trình bày một thuật tốn
ngẫu nhiên xấp xỉ với dự kiến đảm bảo hiệu suất cho các trường hợp
SMTI trong đó các mối quan hệ chỉ xảy ra ở một chiều, có nhiều nhất
là một ràng buộc (tie) cho mỗi danh sách và mỗi ràng buộc có độ dài
là 2. Nghiên cứu khác của Halldorsson và cộng sự [28], đã giới thiệu
một thuật toán xấp xỉ với đảm bảo hiệu suất là 2/(1 + 1/L2 ) cho các
trường hợp SMTI trong đó các mối quan hệ chỉ xảy ra ở một chiều và
mỗi ràng buộc có chiều dài tối đa L. Kết qủa thực nghiệm cho tỷ lệ
tương đối là 13/7 trong đó các mối quan hệ được cho phép ở cả hai
chiều và độ dài là 2. Trong khi đó, Gelain và cộng sự [13] đã đề xuất
phương pháp tìm kiếm cục bộ cho vấn đề SMTI. Nghiên cứu đã tìm
ra một phép ghép ổn định với kích thước tương đối là 100, tuy nhiên
nếu kích thước lớn hơn thuật tốn cịn chưa hiệu quả.

9

Tiến độ thực hiện đề tài

Bảng 4: Tiến độ thực hiện

TT Nội dung
1

Học

theo

chương
trình
tạo

Tiến độ thực hiện theo năm và quý

Sản

Năm 1

phẩm

I

Hồn

II

III

Năm 2

IV

I

II

III

Năm 3
IV

I

II

III

Năm 4
IV

I

II

x

thành
đào

chương


Tiến

trình

học

sĩ tại Học

năm

thứ

viên

nhất

năm

thứ nhất

14

III

IV


Đề cương dự tuyển trình độ tiến sỹ - năm 2019


2

Nghiên

Báo

cứu

chun đề

tổng

quan

về

bài

cáo

x

tổng quan

tốn

SMP

và


các

biến

thể của nó
3

Học

theo

chương
trình
tạo

Hồn

x

thành
đào

chương

Tiến

trình

học


sĩ tại Học

năm

thứ

viện

hai

năm

thứ hai
4

Nghiên
cứu

Báo
các

phương

cáo

x

chun đề
tổng quan


pháp đã đề
xuất

giải

quyết

các

bài tốn
5

Học

theo

chương
trình
tạo

Hồn

x

thành
đào

chương

Tiến


trình

học

sĩ tại Học

năm

thứ

viện

ba

năm

thứ ba

6

Nghiên

01 bài kỷ

cứu

yếu

phương


thảo quốc

pháp tìm

tế

kiếm

01 bài kỷ

heuristic

yếu

x

hội

x

hội

thảo quốc
tế

15


Đề cương dự tuyển trình độ tiến sỹ - năm 2019


01 bài kỷ
yếu

x

hội

thảo quốc
tế
01 bài báo

x

trong nước
01 bài báo

x

quốc tế chỉ
số Scopus
01 bài báo

x

quốc tế có
chỉ số ISI
7

Bảo


vệ

Tồn

luận

án

LA

văn

x

cấp cơ sở
8

Bảo

vệ

luận

án

cấp

nhà


Luận án

x

nước

10

Dự kiến kết quả đạt được
− 03 bài báo hội thảo quốc tế,
− 01 bài báo đăng trên tạp chí có chỉ số Scopus,

11

Người hướng dẫn
Người hướng dẫn 1

PGS.TS. Nguyễn Đức Vũ

Học viên thực hiện

ThS. Nguyễn Thị Uyên

16


Tài liệu tham khảo

[1] David J. Abraham, Robert W. Irving, and David F. Manlove. The studentproject allocation problem. In Proceedings of the 14th International Symposium,
pages 474–484, Kyoto, Japan, Dec. 2003.

[2] David J. Abraham, Robert W. Irving, and David F. Manlove. Two algorithms
for the student-project allocation problem. Journal of Discrete Algorithms,
5(1):73–90, 2007.
[3] David J. Abraham, Robert W. Irving, and David F. Manlove. Two algorithms
for the student-project allocation problem. Journal of Discrete Algorithms,
5(1):73–90, 2007.
[4] Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Parameterized algorithms for stable matching with ties and incomplete
lists. Theoretical Computer Science, 723(1):1–10, 2018.
[5] Kashyab J Ambarani, Shivansh Sharma, Shravan Komarabattini, My T Thai,
and Tu N Nguyen. Enforcing resource allocation and vnf embedding in ran
slicing. In 2021 IEEE Global Communications Conference, pages 1–6. IEEE,
2021.
[6] Katarína Cechlárová and Tamás Fleiner. On a generalization of the stable
roommates problem. ACM Transactions on Algorithms (TALG), 1(1):143–156,
2005.
[7] Kazuo Iwamay Shuichi Miyazaki David F. Manlove, Robert W. Irving and
Yasufumi Morita. Hard variants of stable marriage. Theoretical Computer
Science, 276(2):261–279, 2002.
[8] Maxence Delorme, Sergio García, Jacek Gondzio, Jorg Kalcsics, and David
Manlove. Mathematical models for stable matching problems with ties and
incomplete lists, 2019.

17


Đề cương dự tuyển trình độ tiến sỹ - năm 2019

[9] Ildikó Schlotter Dániel Marx. Parameterized complexity and local search approaches for the stable marriage problem with ties. Algorithmica, 58(1):170–
187, 2010.
[10] Patricia Everaere, Maxime Morge, and Gauthier Picard. Minimal concession

strategy for reaching fair, optimal and stable marriages. In Proceedings of the
2013 International Conference on Autonomous Agents and Multi-agent Systems
(AAMAS), pages 1319–1320, St. Paul, MN, USA, May 2013.
[11] Tamas Fleiner, Robert W. Irving, and David F. Manlove. Efficient algorithms
for generalized stable marriage and roommates problems. Theoretical Computer
Science, 381(1-3):162–176, 2007.
[12] D. Gale and L. S. Shapley. College admissions and the stability of marriage.
The American Mathematical Monthly, 9(1):9–15, 1962.
[13] Mirco Gelain, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and
Toby Walsh. Local search for stable marriage problems with ties and incomplete
lists. In Proceedings of PRICAI 2010: Trends in Artificial Intelligence, pages
64–75, Daegu, Korea, August 2010.
[14] Ian Philip Gent and Patrick Prosser. An empirical study of the stable marriage
problem with ties and incomplete lists. In Proceedings of the 15th European
Conference on Artificial Intelligence, pages 141–145, Lyon, France, July 2002.
[15] Ioannis Giannakopoulos, Panagiotis Karras, Dimitios Tsoumakos, Katerina
Doka, and Nectarios Koziris. An equitable solution to the stable marriage
problem. In 2015 IEEE 27th International Conference on Tools with Artificial
Intelligence (ICTAI), pages 989–996, Vietri sul Mare, Italy, Nov. 2015.
[16] Dan Gusfield. Three fast algorithms for four problems in stable marriage. SIAM
Journal on Computing, 16(1):111–128, 1987.
[17] Magnus M. Halldorsson, Robert W. Irving, Kazuo Iwama, David F. Manlove,
Shuichi Miyazaki, Yasufumi Morita, and Sandy Scott. Approximability results for stable marriage problems with ties. Theoretical Computer Science,
306(1):431 – 447, 2003.
[18] Magnus M. Halldórsson, Kazuo Iwama, and Shuichi Miyazaki. Improved approximation results for the stable marriage problem. ACM Transactions on
Algorithms, 3(3):1–18, 2007.

18



Đề cương dự tuyển trình độ tiến sỹ - năm 2019

[19] Robert W. Irving. An efficient algorithm for the “stable roommates” problem.
Journal of Algorithms, 6(1):577–595, 1985.
[20] Robert W. Irving and Paul Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15(3):655–667, 1986.
[21] Robert W. Irving, Paul Leather, and Dan Gusfield. An efficient algorithm
for the "optimal" stable marriage. Journal of the Association for Computing
Machinery, 34(3):532–543, 1987.
[22] Robert W Irving and David F Manlove. The stable roommates problem with
ties. Journal of Algorithms, 43(1):85–105, 2002.
[23] Robert W. Irving and David F. Manlove. Finding large stable matchings.
Journal of Experimental Algorithmics, 14(2):1.2–1.2:30, 2009.
[24] Robert W Irving, David F Manlove, and Sandy Scott. Strong stability in the
hospitals/residents problem. In Annual Symposium on Theoretical Aspects of
Computer Science, pages 439–450. Springer, 2003.
[25] Kazuo Iwama, Shuichi Miyazaki, and Naoya Yamauchi. A 1.875: approximation
algorithm for the stable marriage problem. In Proceedings of the eighteenth
annual ACM-SIAM symposium on Discrete algorithms, pages 288–297, New
Orleans, Louisiana, Jan. 2007.
[26] Adam Kunysz. An algorithm for the maximum weight strongly stable matching problem. In 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123, pages 42:1–42:13. Schloss Dagstuhl-LeibnizZentrum fuer Informatik, 2018.
[27] Augustine Kwanashie and David F. Manlove. An integer programming approach to the hospitals/residents problem with ties. In Proceedings of the International Conference on Operations Research, pages 263–269, Erasmus University Rotterdam, Sep. 2013.
[28] Shuichi Miyazaki Magnus M. Halldorsson, Kazuo Iwama and Hiroki Yanagisawa. Improved approximation results for the stable marriage problem. ACM
Transactions on Algorithms (TALG), 3(3):30, 2007.
[29] David Manlove, Duncan Milne, and Sofiat Olaosebikan. An integer programming approach to the student-project allocation problem with preferences over
projects. In International Symposium on Combinatorial Optimization, pages
313–325. Springer, 2018.

19



Đề cương dự tuyển trình độ tiến sỹ - năm 2019

[30] David F. Manlove. The Hospitals/Residents Problem. In: Kao MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA, 2008.
[31] Kazuo IwamaShuichi MiyazakiYasufumi MoritaDavid Manlove. Stable marriage with incomplete lists and ties. In Proceedings of 26th International Colloquium on Automata, Languages, and Programming, pages 443–452, Prague,
Czech Republic, July 1999.
[32] Danny Munera, Daniel Diaz, Salvador Abreu, Francesca Rossi, Vijay Saraswat,
and Philippe Codognet. Solving hard stable matching problems via local search
and cooperative parallelization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 1212–1218, Austin, Texas, Jan. 2015.
[33] Sofiat Olaosebikan and David Manlove. Super-stability in the student-project
allocation problem with ties. Journal of Combinatorial Optimization, pages
1–37, 2020.
[34] Patrick Prosser. Stable roommates and constraint programming. In International Conference on AI and OR Techniques in Constriant Programming for
Combinatorial Optimization Problems, pages 15–28, Cork, Ireland, May. 2014.
[35] Andrew postlewaite Larry samuelson Qingmin liu, George j. mailath. Stable
matching with incomplete information. Econometrica, 82(2), 2014.
[36] Alvin E. Roth. The evolution of the labor market for medical interns and
residents: A case study in game theory. Journal of Pilitical Economy, 92(6):991–
1016, 1984.
[37] Le Hong Trang, Hoang Huu Viet, and TaeChoong Chung. Finding "optimal"
stable marriages with ties via local search. In Proceedings of the 2016 Eighth
International Conference on Knowledge and Systems Engineering (KSE2016),
pages 61–66, Hanoi, Vietnam, Oct. 2016.
[38] Ngo Anh Vien, Nguyen Hoang Viet, Hyun Kim, SeungGwan Lee, and TaeChoong Chung. Ant colony based algorithm for stable marriage problem. In
Advances and Innovations in Systems, Computing Sciences and Software Engineering, pages 457–461, 2007.
[39] Hoang Huu Viet, Le Hong Trang, Seung Gwan Lee, and Tae Choong Chung.
A bidirectional local search for the stable marriage problem. In Proceedings of
the 2016 International Conference on Advanced Computing and Applications
(ACOMP), pages 18–24, Can Tho City, Vietnam, Nov. 2016.

20



Đề cương dự tuyển trình độ tiến sỹ - năm 2019

[40] Hoang Huu Viet, Le Hong Trang, Seung Gwan Lee, and Tae Choong Chung.
An empirical local search for the stable marriage problem. In Proceedings of the
14th Pacific Rim International Conference on Artificial Intelligence - PRICAI
2016: Trends in Artificial Intelligence, pages 556–564, Phuket, Thailand, Aug.
2016.
[41] Rakesh V Vohra. Stable matchings and linear programming. Current Science,
pages 1051–1055, 2012.

21