CHƯƠNG 1. TỔNG QUAN VỀ BÀI TOÁN HÔN NHÂN ỔN ĐỊNH Chương này trình bày các khái niệm, các định nghĩa, các ví dụ và tổng quan tình hình nghiên cứu liên quan đến bài toán hôn nhân ổn định và các biến thể mở rộng của bài toán. Bài toán hôn nhân ổn định 1. Giới thiệu Bài toá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 bởi Gale and Shapley năm 1962 [1].
Bài toán bao gồm một tập nam và một tập nữ có số lượng bằng nhau và mục tiêu của bài toán là tìm một phép ghép giữa nam và nữ sao cho thỏa mãn một điều kiện tối ưu nào đó. Gần đây bài toán này được cộng đồng nghiên cứu rất quan tâm bởi những ứng dụng rộng lớn của nó trong thực tế như các chương trình phân bổ dân cư tại Mỹ (National Resident Matching Program-NRMP) [4]; ứng dụng phát triển của thị trường lao động cho sinh viên và nhân viên y tế (Evolution of the Labor Market for Medical Interns and Residents) [29]; chương trình đăng ký nhà ở tại Scotland (Scottish Pre-registration house officer Allocations) [30]; dịch vụ phân bố dân cư tại Canada (Resident Matching Service-CARMS) [31]; và một số ứng dụng về việc tối ưu hóa dịch vụ của người dùng Internet [32]. Một thể hiện I (instance) của bài toán SMP kích thước n gồm một tập M = {m1 , m2 , · · · , mn } người nam và một tập W ={w1 , w2 , · · · , wn } người nữ, trong đó mỗi người có một danh sách xếp hạng “thích” những người khác giới theo một thứ tự ưu tiên nghiêm ngặt. Một phép ghép M (matching) là một tập M = {(mi , wj ) ∈ M × W} gồm n cặp, trong đó mỗi mi ∈ M chỉ được ghép duy nhất với một wj ∈ W và ngược lại.
Ký hiệu rank(mi , wj ) là thứ hạng của wj ∈ W trong danh sách xếp 6 Bảng 1.1: Một thể hiện của bài toán SMP Danh sách xếp hạng của mi ∈ M Danh sách xếp hạng của wj ∈ W m1 : w 4 w 7 w 3 w 8 w 1 w 5 w 2 w 6 w1 : m1 m3 m5 m4 m2 m6 m8 m7 m2 : w5 w3 w4 w2 w1 w8 w6 w7 w2 : m8 m2 m4 m5 m3 m7 m1 m6 m3 : w3 w8 w2 w4 w6 w7 w5 w1 w3 : m5 m8 m1 m4 m2 m3 m6 m7 m4 : w5 w6 w8 w3 w4 w7 w1 w2 w4 : m2 m4 m3 m6 m5 m8 m1 m7 m5 : w1 w3 w5 w2 w8 w6 w4 w7 w5 : m6 m5 m4 m8 m1 m7 m2 m3 m6 : w8 w6 w2 w5 w1 w7 w4 w3 w6 : m7 m4 m2 m5 m6 m8 m1 m3 m7 : w2 w5 w8 w3 w6 w4 w7 w1 w7 : m3 m8 m6 m5 m7 m2 m1 m4 m8 : w5 w7 w4 w1 w6 w2 w8 w3 w8 : m4 m7 m1 m3 m5 m8 m2 m6 hạng của mi ∈ M và rank(wj , mi ) là thứ hạng của mi ∈ M trong danh sách xếp hạng của wj ∈ W. Nếu mi ∈ M thích wj ∈ W hơn wk ∈ W nghĩa là rank(mi , wj ) < rank(mi , wk ) và nếu wj ∈ W thích mi ∈ M hơn mt ∈ M nghĩa là rank(wj , mi ) < rank(wj , mt ). Một cặp (mi , wj ) ∈ M × W là một cặp chặn (blocking pair) cho một phép ghép M nếu thỏa mãn các điều kiện: 1. Một phép ghép M là ổn định (stable) nếu không tồn tại bất kỳ cặp chặn (mi , wj ) ∈ M × W cho M , ngược lại M được gọi là không ổn định.
Một thể hiện SMP gồm 8 người nam và 8 người nữ được chỉ ra trong Bảng 1. Phép ghép M = {(m1 , w3 ), (m2 , w1 ), (m3 , w2 ), (m4 , w8 ), (m5 , w7 ), (m6 , w4 ), (m7 , w5 ), (m8 , w6 )} là phép ghép không ổn định vì tồn tại các cặp chặn {(m2 , w2 ), (m2 , w4 ), (m4 , w5 ), (m4 , w6 ), (m5 , w1 ), (m5 , w2 ), (m5 , w3 ), (m5 , w5 ), (m5 , w6 ), (m6 , w5 ), (m6 , w6 ), (m6 , w7 ), (m8 , w5 ), (m8 , w7 )} cho M. Phép ghép M = {(m1 , w3 ), (m2 , w4 ), (m3 , w2 ), (m4 , w5 ), (m5 , w1 ), (m6 , w6 ), (m7 , w8 ), (m8 , w7 )} là phép ghép ổn định. Các nghiên cứu liên quan Phần này trình bày các hướng nghiên liên quan giải quyết bài toán SMP.
Năm 1962, bài toán SMP được Gale và Shapley [1] đề xuất và nghiên cứu. Họ đã trình bày một thuật toán nổi tiếng gọi là thuật toán Gale-Shapley (GS) để tìm một phép ghép tối ưu cho tập nam hoặc tập nữ trong thời gian O(n2 ). Tuy nhiên, phép ghép ổn định tối ưu cho tập nam và phép ghép ổn định tối ưu cho tập nữ là những phép ghép “ích kỷ”, tức là trong thuật toán GS những người đề xuất luôn có được bạn ghép mà mình thích nhất còn người được ghép luôn nhận được bạn ghép tồi nhất trong danh sách xếp hạng của họ. Vì vậy các nghiên cứu sau 7 Bảng 1.2: Các nghiên cứu liên quan giải quyết bài toán SMP Tác giả, năm xuất bản Thuật toán Mục tiêu Thuật toán xấp xỉ Gale và Shapley [1], 1962 Thuật toán Gale-Shapley Phép ghép tối ưu một phía KazuoIwama và cộng sự [33], 2010 Thuật toán xấp xỉ Phép ghép cân bằng giới tính Thuật toán heuristic Mô hình bài toán SMP Codognet và cộng sự [43], 2001 Thuật toán tìm kiếm cục bộ như bài toán thỏa mãn ràng buộc (CSP) Gent và cộng sự [44], 2002 Thuật toán sinh ngẫu nhiên Sinh ngẫu nhiên các thể hiện SMP Nakamura và cộng sự [34], 2005 Thuật toán di truyền (GA) Phép ghép ổn định hai phía Vien và cộng sự [24], 2007 Thuật toán tối ưu đàn kiến (ACS) Phép ghép ổn định hai phía Gelain và cộng sự [45], 2010 Thuật toán tìm kiếm cục bộ (SML) Phép ghép ổn định hai phía Việt và các cộng sự [36], 2019 Thuật toán Short list-BilS Phép ghép ổn định hai phía Hướng tiếp cận khác Zavidovique và cộng sự [37], 2005 Thuật toán ZigZag Phép ghép cân bằng theo giới tính Iwama và cộng sự [38], 2010 Thuật toán xấp xỉ Phép ghép ổn định hai phía Everaere và cộng sự [39], 2013 Thuật toán Swing Phép ghép tương đương theo giới tính Giannakopoulos và cộng sự [40], 2015 Thuật toán ESMA dựa trên Swing Phép ghép tương đương theo giới tính Tayu và cộng sự [46], 2017 Sử dụng cấu trúc Cây Phép ghép tối ưu từ hai phía này thường tập trung vào việc tìm các phép ghép tối ưu tối cân bằng cho cả tập nam và tập nữ.
Một số phương pháp nghiên cứu để giải quyết bài toán này đã được đề xuất như: phương pháp xấp xỉ [1, 33], phương pháp tìm kiếm heuristic [34, 24, 11, 35, 36], và một số phương pháp nghiên cứu khác [37, 38, 39, 40, 41, 42] như được trình bày trong trong Bảng 1. Mặc dù, có nhiều nghiên cứu đã được đề xuất để giải quyết bài toán SMP, tuy nhiên bài toán SMP ít được ứng dụng trong thực tế bởi các yêu cầu ràng buộc nghiêm ngặt của danh sách xếp hạng, tức là mỗi mi ∈ M phải xếp hạng tất cả wj ∈ W và ngược lại. Do đó, những năm gần đây một số biến thể mới của bài toán SMP đã được giới thiệu và ứng dụng nhiều trong thực tế. Vì vậy, luận án tập trung nghiên cứu và đề xuất các thuật toán theo hướng tiếp cận heuristic để giải quyết các biến thể của bài toán SMP và các ứng dụng mở rộng.
Các biến thể của bài toán hôn nhân ổn định 1. Bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng Một biến thể đầu tiên của bài toán SMP được gọi là bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng (Stable Marriage Problem with Ties, SMT) [47], nghĩa là một người có thể xếp hạng “thích” một số người khác giới với ưu tiên bằng nhau. Một thể hiện SMT gồm 8 người nam và 8 người nữ được minh họa trong Bảng 1.3, trong đó mỗi mi ∈ M có thể xếp hạng “thích” một số wj ∈ W cùng một thứ tự ưu tiên và ngược lại. Ví dụ: m1 : (w4 w3 ) w1 w5 w2 w6 w8 w7 , nghĩa là m1 xếp hạng w4 và w3 cùng một thứ tự ưu tiên trong danh xếp hạng của m1.
Từ đây về sau, luận án quy ước sử dụng ký hiệu “()” để mô tả thứ tự ưu tiên bằng nhau trong danh sách xếp hạng của mi ∈ M và wj ∈ W.3: Một thể hiện của bài toán SMT Danh sách xếp hạng của mi ∈ M Danh sách xếp hạng của wj ∈ W m1 : (w4 w3 ) w1 w5 w2 w6 w8 w7 w1 : m4 (m7 m3 ) m8 m1 m5 m2 m6 m2 : w2 (w8 w4 ) w5 w3 w7 w1 w6 w2 : m5 m3 (m4 m2 ) m1 m8 m6 m7 m3 : w5 w8 w1 (w4 w2 ) w3 w6 w7 w3 : m2 m8 (m6 m4 ) m3 m7 m5 m1 m4 : w6 (w4 w3 w2 ) w5 w8 w1 w7 w4 : m5 m6 (m8 m3 ) m4 m7 m1 m2 m5 : w6 (w5 w4 ) w8 w1 w7 w2 w3 w5 : m1 m8 m5 m2 m3 (m6 m4 m7 ) m6 : w7 w4 (w2 w5 w6 ) w8 w1 w3 w6 : m8 (m6 m2 ) m5 m1 m7 m4 m3 m7 : w8 (w5 w6 w3 ) w7 w2 w1 w4 w7 : (m5 m2 ) m8 m3 m6 m4 m7 m1 m8 : w4 w7 (w1 w3 w5 ) w8 w2 w6 w8 : m4 (m5 m7 ) m1 m6 m2 m8 m3 Trong bài toán SMT, các định nghĩa về phép ghép M tương tự như bài toán SMP đã được trình bày trong Phần 1. Tuy nhiên với bài toán SMT, một phép ghép M được xem xét với khả năng ổn định yếu (weakly stable), ổn định mạnh (strongly stable), và ổn định siêu mạnh (super-stable) [48]. Một số thuật toán xấp xỉ đã được đề xuất để giải quyết bài toán SMT. Một thuật toán T được gọi là một thuật toán r-xấp xỉ (r–approximation) cho một bài toán tối ưu nếu T luôn tìm ra một nghiệm T (x) thỏa mãn |T (x)| ≥ |opt(x)|/r cho tất cả các thể hiện x của bài toán, trong đó opt(x) là nghiệm tối ưu của thể hiện x.
Manlove và cộng sự [9] đã đề xuất hai thuật toán 2-xấp xỉ để tìm nghiệm gần đúng trong thời gian đa thức cho bài toán SMT.