Nghiên Cứu Về Bài Toán Hôn Nhân Ổn Định và Các Thuật Toán Giải Quyết

Chuyên khảo phân tích Uftai ve tai day29718, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo., phục vụ nghiên cứu và ứng dụng thực tiễn

• Trường học: Trường Đại Học
• Chuyên ngành: Toán Học
• Đề tài: Nghiên Cứu Bài Toán Hôn Nhân Ổn Định và Thuật Toán Giải Quyết
• Loại tài liệu: Luận Án

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN HÔN NHÂN ỔN ĐỊNH
• 1.1. Bài toán hôn nhân ổn định
• 1.2. Các nghiên cứu liên quan
• 1.3. Các biến thể của bài toán hôn nhân ổn định
• 1.3.1. Bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng
• 1.3.2. Bài toán hôn nhân ổn định với danh sách không đầy đủ
• 1.3.3. Bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng và không đầy đủ
• 1.4. Các nghiên cứu liên quan
• 1.5. Một số bài toán mở rộng của bài toán SMTI
• 1.5.1. Bài toán Hospitals/Residents with Ties
• 1.5.2. Bài toán Student-Project Allocation
• 1.6. Các nghiên cứu liên quan
• 1.7. Vấn đề tồn tại
• 1.8. Định hướng nghiên cứu
• 1.9. Phương pháp thực nghiệm và đánh giá
• 1.9.1. Bộ dữ liệu
• 1.9.2. Tiêu chí đánh giá
• 1.9.3. Ngôn ngữ và cấu hình cài đặt
• 1.10. Kết luận chương 1
• 2. CHƯƠNG 2: ĐỀ XUẤT THUẬT TOÁN GIẢI BÀI TOÁN MAX-SMTI
• 2.1. Đề xuất thuật toán Max-Conflicts based heuristic search
• 2.2. Mô tả thuật toán
• 2.3. Các kết quả thực nghiệm
• 2.4. Đề xuất thuật toán Heuristic Repair
• 2.5. Mô tả thuật toán
• 2.6. Các kết quả thực nghiệm
• 2.7. Kết luận Chương 2
• 3. CHƯƠNG 3: ĐỀ XUẤT THUẬT TOÁN GIẢI BÀI TOÁN MAX-HRT
• 3.1. Đề xuất thuật toán Min-Conflicts
• 3.2. Mô tả thuật toán
• 3.3. Các kết quả thực nghiệm
• 3.4. Đề xuất thuật toán Heuristic Search
• 3.5. Mô tả thuật toán
• 3.6. Các kết quả thực nghiệm
• 3.7. Kết luận Chương 3
• 4. CHƯƠNG 4: ĐỀ XUẤT THUẬT TOÁN GIẢI BÀI TOÁN MAX-SPA
• 4.1. Đề xuất thuật toán SPA-P-heuristic giải bài toán MAX-SPA-P
• 4.2. Mô tả thuật toán
• 4.3. Các kết quả thực nghiệm
• 4.4. Đề xuất thuật toán HAG giải quyết bài toán MAX-SPA-ST
• 4.5. Mô tả thuật toán
• 4.6. Các kết quả thực nghiệm
• 4.7. Kết luận Chương 4
• MỞ ĐẦU
• KẾT LUẬN
• PHỤ LỤC
• A.1. Thuật toán Gale-Shapley
• A.2. Thuật toán tạo danh sách xếp hạng
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Bài Toán Hôn Nhân Ổn Định Giới Thiệu Chi Tiết

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 kinh điển, được giới thiệu lần đầu bởi Gale và Shapley vào năm 1962. Bài toán này bao gồm hai tập hợp: một tập hợp gồm n người nam và một tập hợp gồm n người nữ. Mỗi cá nhân trong một tập hợp đều có một danh sách ưu tiên, xếp hạng tất cả các thành viên của tập hợp kia theo mức độ ưa thích. Mục tiêu của bài toán là tìm ra một phép ghép cặp giữa nam và nữ sao cho không tồn tại bất kỳ cặp nào mà cả hai người đều thích nhau hơn so với người bạn đời hiện tại của họ. Nếu không có cặp nào như vậy, phép ghép cặp được coi là ổn định. Bài toán SMP đã thu hút sự quan tâm lớn từ cộng đồng nghiên cứu do tính ứng dụng rộng rãi của nó trong thực tế, ví dụ như các chương trình phân bổ dân cư và tối ưu hóa dịch vụ.

1.1. Định Nghĩa Bài Toán SMP và Tính Ổn Định

Một thể hiện I của bài toán SMP với kích thước n bao 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ữ. Mỗi người có một danh sách xếp hạng ưu tiên những người khác giới. Một phép ghép M là một tập M = {(mi, wj) ∈ M × W}, trong đó mỗi mi ∈ M chỉ được ghép duy nhất với một wj ∈ W và ngược lại. Tính ổn định của phép ghép được xác định bởi việc không tồn tại cặp chặn (blocking pair). Một cặp (mi, wj) là một cặp chặn nếu cả mi và wj đều thích nhau hơn so với bạn ghép hiện tại của họ trong phép ghép M. Nếu không có cặp chặn nào tồn tại, phép ghép M được coi là ổn định.

1.2. Ứng Dụng Thực Tế Của Bài Toán Hôn Nhân Ổn Định

Bài toán hôn nhân ổn định có nhiều ứng dụng thực tế quan trọng. Một trong những ứng dụng nổi bật nhất là trong các chương trình phân bổ dân cư tại Mỹ (National Resident Matching Program - NRMP). Ngoài ra, bài toán còn được áp dụng trong việc phát triển thị trường lao động cho sinh viên và nhân viên y tế, chương trình đăng ký nhà ở tại Scotland, dịch vụ phân bố dân cư tại Canada, và tối ưu hóa dịch vụ của người dùng Internet. Những ứng dụng này cho thấy tầm quan trọng và tính thực tiễn của việc nghiên cứu và giải quyết bài toán SMP.

II. Các Nghiên Cứu Liên Quan Đến Thuật Toán Gale Shapley

Năm 1962, Gale và Shapley đã đề xuất một thuật toán nổi tiếng gọi là thuật toán Gale-Shapley (GS) để 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). Thuật toán này đảm bảo tìm được một phép ghép ổn định trong thời gian đa thức. 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 toá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.

2.1. Thuật Toán Gale Shapley Ưu Điểm và Hạn Chế

Thuật toán Gale-Shapley (GS) là một thuật toán kinh điển để giải bài toán hôn nhân ổn định. Ưu điểm chính của thuật toán là đảm bảo tìm được một phép ghép ổn định trong thời gian đa thức. Tuy nhiên, thuật toán có một số hạn chế. Thứ nhất, nó yêu cầu số lượng nam và nữ phải bằng nhau. Thứ hai, 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. Những ràng buộc này khiến cho bài toán SMP ít gặp trong các ứng dụng thực tế.

2.2. Các Biến Thể Của Bài Toán Hôn Nhân Ổn Định

Để khắc phục những hạn chế của bài toán SMP gốc, một số biến thể đã được đề xuất. Các biến thể này bao gồm: (i) bài toán hôn nhân ổn định với thứ tự ưu tiên ngang bằng (Stable Marriage problem with Ties, SMT), (ii) bài toán hôn nhân ổn định với danh sách không đầy đủ (Stable Marriage problem with incomplete, SMI), và (iii) bài toá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 and Incomplete lists, SMTI). Các biến thể này mở rộng phạm vi ứng dụng của bài toán SMP và cho phép mô hình hóa các tình huống thực tế phức tạp hơn.

2.3. Độ Phức Tạp Thuật Toán Gale Shapley và Các Cải Tiến

Thuật toán Gale-Shapley có độ phức tạp thời gian là O(n^2), với n là số lượng người tham gia. Mặc dù thuật toán này hiệu quả, nhưng các nhà nghiên cứu vẫn tiếp tục tìm kiếm các cải tiến để giảm độ phức tạp hoặc tối ưu hóa hiệu suất trong các trường hợp cụ thể. Các cải tiến này có thể bao gồm việc sử dụng các cấu trúc dữ liệu hiệu quả hơn hoặc áp dụng các kỹ thuật heuristic để giảm số lượng phép so sánh cần thiết.

III. Bài Toán SMTI Ổn Định Yếu Mạnh và Siêu Ổn Định

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ự đã 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 toá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 MAX-SMTI.

3.1. Các Điều Kiện Ổn Định Trong Bài Toán SMTI

Trong bài toán SMTI, sự xuất hiện của thứ tự ngang hàng trong danh sách xếp hạng dẫn đến ba điều kiện ổn định khác nhau: ổn định yếu, ổn định mạnh và siêu ổn định. Một phép ghép được coi là ổn định yếu nếu không tồn tại cặp chặn nào mà cả hai người đều thích nhau hơn so với bạn ghép hiện tại. Một phép ghép được coi là ổn định mạnh nếu không tồn tại cặp chặn nào mà một trong hai người thích nhau hơn và người kia không tệ hơn so với bạn ghép hiện tại. Một phép ghép được coi là siêu ổn định nếu không tồn tại cặp chặn nào mà cả hai người đều không tệ hơn so với bạn ghép hiện tại.

3.2. Bài Toán MAX SMTI Mục Tiêu và Độ Phức Tạp

Bài toán MAX-SMTI tập trung vào việc 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. Manlove và cộng sự đã chứng minh rằng bài toán MAX-SMTI là NP-khó. Điều này có nghĩa là không có thuật toán nào có thể giải quyết bài toán này trong thời gian đa thức, trừ khi P = NP. Do đó, việc nghiên cứu các thuật toán hiệu quả để giải quyết vấn đề này là một thách thức lớn cho các nhà nghiên cứu.

IV. Ứng Dụng Của Bài Toán Hôn Nhân Ổn Định Mở Rộng

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 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 (Hospitals/Residents with Ties problem, (HRT)); (ii) bài toá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); và (iii) bài toán phân bổ nhà ở cho dân cư (Stable Roommates problem, SR). Mục tiêu của bài toán MAX-HRT 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 toán MAX-SPA, 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.

4.1. Bài Toán HRT Phân Bổ Sinh Viên Y Khoa Thực Tập

Bài toán Hospitals/Residents with Ties (HRT) là một ứng dụng quan trọng của bài toán SMTI. Trong bài toán này, mục tiêu là phân bổ sinh viên ngành y tới thực tập tại các bệnh viện sao cho có nhiều nhất số sinh viên được phân bổ và phép ghép là ổn định. Bài toán MAX-HRT là một biến thể của bài toán HRT nhằm 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.

4.2. Bài Toán SPA Phân Công Đề Tài Cho Sinh Viên

Bài toán Student-Project Allocation (SPA) là một ứng dụng khác của bài toán SMTI. Trong bài toán này, mục tiêu là phân công giảng viên hướng dẫn sinh viên thực hiện đề tài sao cho có nhiều nhất số sinh viên nhận được đề tài và phép ghép là ổn định. Bài toán MAX-SPA là một biến thể của bài toán SPA nhằm 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.

4.3. Ứng Dụng Trong Kinh Tế và Các Lĩnh Vực Khác

Ngoài các ứng dụng trong y tế và giáo dục, bài toán hôn nhân ổn định và các biến thể của nó còn có nhiều ứng dụng trong kinh tế và các lĩnh vực khác. Ví dụ, bài toán có thể được sử dụng để phân bổ nhà ở cho dân cư, 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, và thiết kế các hệ thống đề xuất trong thương mại điện tử. Những ứng dụng này cho thấy tính linh hoạt và tầm quan trọng của bài toán SMP trong việc giải quyết các vấn đề thực tế.

V. Các Thuật Toán Heuristic Giải Bài Toán SMTI Lớ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 và SPA. Các hướng tiếp cận chủ yếu là thuật toán xấp xỉ, lập trình nguyên, lập trình thích nghi, tìm kiếm cục bộ, tìm kiếm bầy đàn và một số phương pháp khác. Bài toán SMTI và các biển thể mở rộng của nó là các bài toán NP-khó. 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 toá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.

5.1. Thuật Toán Tìm Kiếm Ổn Định Tổng Quan Các Phương Pháp

Các thuật toán giải bài toán SMTI và các biến thể của nó có thể được chia thành nhiều loại khác nhau, bao gồm thuật toán xấp xỉ, lập trình nguyên, lập trình thích nghi, tìm kiếm cục bộ, tìm kiếm bầy đàn và các phương pháp heuristic. Mỗi loại thuật toán có những ưu điểm và nhược điểm riêng, và hiệu quả của chúng phụ thuộc vào đặc điểm cụ thể của bài toán.

5.2. Ưu Điểm Của Thuật Toán Heuristic Trong Bài Toán SMTI

Thuật toán heuristic có một số ưu điểm quan trọng trong việc giải bài toán SMTI. Thứ nhất, chúng có thể tìm ra các nghiệm chấp nhận được trong thời gian ngắn hơn so với các thuật toán chính xác. Thứ hai, chúng có thể được áp dụng cho các bài toán có kích thước lớn mà các thuật toán chính xác không thể xử lý được. Thứ ba, chúng 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.

5.3. Cải Tiến Thuật Toán Hướng Nghiên Cứu Mới

Các nhà nghiên cứu tiếp tục tìm kiếm các cải tiến cho các thuật toán giải bài toán SMTI. Các hướng nghiên cứu mới bao gồm việc phát triển các thuật toán heuristic hiệu quả hơn, kết hợp các thuật toán khác nhau để tận dụng ưu điểm của từng thuật toán, và áp dụng các kỹ thuật học máy để tự động điều chỉnh các tham số của thuật toán.

VI. Đề Xuất Thuật Toán Tối Ưu Cho Bài Toán MAX SMTI

Luận án này tập trung nghiên cứu các thuật toá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 toán MAX-SMTI và các mở rộng của bài toán gồm MAX-HRT và MAX-SPA. 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 toá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 MAX-SPA.

6.1. Mục Tiêu Nghiên Cứu MAX SMTI MAX HRT MAX SPA

Mục tiêu chính của luận án là đề xuất các thuật toán heuristic hiệu quả để giải quyết ba bài toán: MAX-SMTI, MAX-HRT và MAX-SPA. Các thuật toán này nhằm tìm một phép ghép ổn định yếu với kích thước tối đa cho mỗi bài toán.

6.2. Phân Tích Thuật Toán Tiêu Chí Đánh Giá

Để đánh giá hiệu quả của các thuật toán đề xuất, luận án sử dụng các tiêu chí sau: (i) chất lượng nghiệm (tức là kích thước của phép ghép ổn định tìm được), (ii) thời gian thực hiện, và (iii) độ phức tạp tính toán. Các thuật toán được so sánh với các thuật toán đã được công bố trước đó để đánh giá tính ưu việt của chúng.

6.3. Ứng Dụng Thuật Toán Hoãn Chấp Nhận và Các Phương Pháp Khác

Luận án có thể sử dụng hoặc so sánh với thuật toán hoãn chấp nhận (deferred acceptance algorithm) như một phần của quá trình nghiên cứu và đánh giá. Ngoài ra, các phương pháp khác như lập trình nguyên, tìm kiếm cục bộ và tìm kiếm bầy đàn cũng có thể được sử dụng để so sánh và đánh giá hiệu quả của các thuật toán heuristic đề xuất.

Trích đoạn nội dung tài liệu

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ơ sở lý thuyết 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 n người nam và n người nữ, trong đó mỗi người xếp hạng tất các mọi người khác giới từ 1 đến n theo thứ tự ưu tiên. Mục tiêu bài toán là tìm một phép ghép giữa nam và nữ sao cho thỏa mãn không tồn tại hai người khác giới thích nhau hơn bạn ghép hiện tại của họ. Nếu không tồn tại những người như vậy thì phép ghép đó được xem là ”ổn định”. 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) [28]; chương trình đăng ký nhà ở tại Scotland (Scottish Pre-registration house officer Allocations) [29]; dịch vụ phân bố dân cư tại Canada (Resident Matching Service-CARMS) [30]; 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 [31].

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}, 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ự [32], 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ự [41], 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ự [42], 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ự [33], 2005 Thuật toán di truyền (GA) Phép ghép ổn định hai phía Vien và cộng sự [23], 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ự [43], 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ự [35], 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ự [36], 2005 Thuật toán ZigZag Phép ghép cân bằng theo giới tính Iwama và cộng sự [37], 2010 Thuật toán xấp xỉ Phép ghép ổn định hai phía Everaere và cộng sự [38], 2013 Thuật toán Swing Phép ghép tương đương theo giới tính Giannakopoulos và cộng sự [39], 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ự [44], 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, 32], phương pháp tìm kiếm heuristic [33, 23, 10, 34, 35], và một số phương pháp nghiên cứu khác [36, 37, 38, 39, 40] 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) [45], 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) [46].

Một số thuật toán xấp xỉ đã được đề xuất để giải quyết bài toán SMT.