GIỚI THIỆU VỀ BÀI TOÁN HÔN NHÂN BỀN VỮNG
Tuyển sinh đại học và vấn đề hôn nhân bền vững
1.1.1 Giới thiệu vấn đề tuyển sinh đại học
Vấn đề chúng ta quan tâm liên quan đến tình huống tiêu biểu như sau:
Một trường đại học có hạn ngạch q cho số ứng cử viên n tham gia xét tuyển, và mỗi ứng cử viên chỉ có thể chấp nhận một đề nghị nhập học Văn phòng tuyển sinh phải định tính đánh giá và quyết định những ứng cử viên đủ tiêu chuẩn Tuy nhiên, việc xác định số lượng và danh sách ứng cử viên có khả năng chấp nhận là một thách thức do sự không chắc chắn trong việc ứng cử viên sẽ đăng ký trường nào, vị trí của họ tại trường và khả năng được các trường khác chấp nhận Kết quả của những yếu tố không chắc chắn này ảnh hưởng đến khả năng đạt được kết quả và chất lượng như mong đợi của các trường đại học.
Thủ tục tuyển sinh thường gây khó khăn cho cả ứng viên lẫn các trường đại học Ứng viên phải liệt kê các trường dự tuyển theo thứ tự ưu tiên, điều này có thể ảnh hưởng đến cơ hội được chấp nhận Nếu một ứng viên xếp một trường đại học ở vị trí thứ 3, khả năng được nhận vào trường đó có thể bị giảm đi.
Việc lập một "danh sách chờ" cho các ứng cử viên không được chấp nhận nhưng vẫn có cơ hội vào học sau này là rất cần thiết Điều này cho phép các thí sinh được thông báo về tình trạng của mình và giữ hy vọng nếu có chỗ trống Mỗi ứng cử viên có thể được chấp nhận vào một trường đại học và đồng thời được đưa vào danh sách chờ của những trường mà họ ưu tiên hơn.
Chúng tôi tin rằng những khó khăn trong quy trình nộp đơn vào đại học có thể được giải quyết Bài viết này sẽ trình bày một quy trình nộp đơn hợp lý cho cả hai nhóm, nhằm loại bỏ mọi bất ổn và đảm bảo rằng mỗi trường đại học nhận đủ số lượng ứng viên theo hạn ngạch đã được xác định.
Danh sách ứng cử viên sẽ được phân bổ cho m trường đại học, với q i là chỉ tiêu của trường đại học thứ i Mỗi ứng cử viên sẽ sắp xếp danh sách các trường theo thứ tự ưu tiên giảm dần, loại bỏ những trường mà họ không chọn trong bất kỳ trường hợp nào Để đơn giản, chúng ta giả định rằng không có bất kỳ ràng buộc nào trong quá trình này.
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 7 nhấn mạnh rằng, khi một ứng cử viên không quan tâm đến hai hay nhiều trường đại học, họ vẫn cần phải sắp xếp danh sách các trường theo thứ tự ưu tiên Mỗi trường đại học sẽ căn cứ vào thứ tự này để xếp hạng các ứng cử viên mong muốn vào trường của mình.
Các ý tưởng quan trọng trong bài viết này khẳng định rằng mọi phép gán đều có quyết định cuối cùng, nhấn mạnh rằng các tình huống được mô tả trong các định nghĩa sau đây không nên xảy ra Theo định nghĩa 1.1, một phép gán cho các ứng cử viên vào các trường đại học được coi là không ổn định nếu có hai ứng cử viên α và β được gán cho trường A và B, trong khi β lại thích A hơn B và A cũng thích β hơn α.
Ứng cử viên β nên chọn trường A vì A có khả năng chấp nhận β mà không ảnh hưởng đến chỉ tiêu tuyển sinh Cả hai trường A và B đều đang xem xét khả năng thay đổi của mình Do đó, sự gán kết ban đầu không ổn định, cho thấy rằng việc hợp tác giữa các trường đại học và ứng cử viên không dễ dàng, nhưng có thể mang lại lợi ích cho cả hai bên.
Yêu cầu đầu tiên trong việc chuyển nhượng là không được thể hiện sự không ổn định, điều này dẫn đến câu hỏi liệu có thể luôn tìm thấy một phân công phù hợp hay không Phần tiếp theo sẽ cung cấp câu trả lời khẳng định cho câu hỏi này, mặc dù bằng chứng không quá khó khăn, nhưng kết quả có thể không hoàn toàn rõ ràng, như một số ví dụ sẽ chỉ ra.
Trong bối cảnh có nhiều giải pháp ổn định, việc xác định phép gán tối ưu là cần thiết Theo định nghĩa 1.2, một phép gán được coi là tối ưu nếu không có phép gán ổn định nào khác tốt hơn cho tất cả các ứng cử viên Điều này nhấn mạnh tầm quan trọng của việc áp dụng các nguyên lý triết học để đạt được một công thức chính xác cho phép gán ổn định.
Việc công nhận sự tồn tại của các phép gán ổn định vẫn còn xa vời so với những phép gán tối ưu Tuy nhiên, nếu một phép gán tối ưu tồn tại, nó sẽ là duy nhất Do đó, trong trường hợp có hai phép gán, nếu một phép gán tốt hơn phép gán còn lại, thì phép gán đó chính là phép gán tối ưu.
Phép gán ổn định và bài toán hôn nhân bền vững
Trong việc tìm hiểu về các phép gán ổn định, một trường hợp đặc biệt được xem xét khi số lượng ứng cử viên và trường đại học là như nhau, cùng với các chỉ tiêu thống nhất Mặc dù tình huống này không phản ánh thực tế trong tuyển sinh đại học, nhưng nó mở ra một câu chuyện thú vị với khởi đầu dễ dàng.
Trong một cộng đồng gồm n người đàn ông và n người phụ nữ, mỗi cá nhân đưa ra danh sách xếp hạng những người khác giới theo ưu tiên cho đối tác hôn nhân Vấn đề cần giải quyết là cách ghép đôi để đảm bảo các cuộc hôn nhân bền vững, tức là không có cặp nào mà người chồng lại thích người vợ của cặp khác hơn vợ mình, và ngược lại, người vợ cũng không thích người chồng của cặp khác hơn chồng mình.
Câu hỏi đặt ra là liệu có thể tìm ra một sự ổn định trong mọi danh sách hay không Để làm rõ điều này, chúng ta sẽ xem xét một ví dụ cụ thể dưới đây.
Ví dụ 1.1: Cho ma trận sắp xếp thự tự ưu tiên trong Hình 1.1 của 3 người đàn ông α, β và γ và 3 người phụ nữa A, B, và C
Hình 1.1 Ma trận sắp xếp thứ tự ưu tiên của 3 người đàn ông và 3 người phụ nữ
Trong ma trận xếp hạng, chỉ số đầu tiên thể hiện thứ hạng của người phụ nữ do nam giới đánh giá, trong khi chỉ số thứ hai phản ánh thứ hạng của nam giới do nữ giới xác định Cụ thể, α được chọn ở vị trí đầu tiên, A đứng thứ hai và B ở vị trí thứ ba; ngược lại, A lựa chọn β đứng đầu, tiếp theo là γ và α ở vị trí thứ ba.
Có 6 trường hợp có thể xảy ra, trong đó có 3 trường hợp ổn định Một trong số đó là trường hợp khi người đàn ông lựa chọn đầu tiên Lúc này, α kết hôn với A, β kết hôn với B, và γ kết hôn với C Khi đó cho dù những người phụ nữ đưa ra lựa chọn cuối cùng, sự ghép cặp này vẫn ổn định Một trường hợp khác là người phụ nữ đưa ra sự lựa chọn đầu tiên, lúc này các cặp được ghép đôi sẽ là α với C, β với A, và γ với B Trường hợp thứ 3 là sự lựa chọn thứ 2 của cả những người đàn ông và phụ nữ và ta có α kết hôn với B, β kết hôn với C, và γ kết hôn với A Người đọc có thể nhận ra rằng những trường hợp còn lại là không ổn định
Ví dụ 1.2: Cho ma trận sắp xếp như Hình 1.2
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 9
Hình 1.2 Ma trận sắp xếp thứ tự ưu tiên của 4 người đàn ông và 4 người phụ nữ
Trong ma trận, chỉ có một trường hợp ổn định được xác định trên đường tròn Điều này cho thấy rằng trong tình huống này, không có sự lựa chọn nào của cả nam và nữ có thể đạt được sự ổn định.
Vấn đề tìm bạn cùng phòng tương tự như vấn đề hôn nhân, với việc một số chàng trai tạo thành các cặp bạn cùng phòng Sự ổn định của các cặp này được xác định khi không có hai chàng trai nào muốn ở cùng nhau nhưng lại không sống chung Ví dụ, nếu các chàng trai α, β, γ và δ có sở thích chọn nhau theo thứ tự α chọn β, β chọn γ, γ chọn α, và tất cả đều chọn δ cuối cùng, thì sẽ có sự không ổn định trong việc ghép cặp Điều này có thể dẫn đến việc bất kỳ ai ở cùng δ đều muốn chuyển ra ngoài Định lý 1.1 khẳng định rằng luôn tồn tại một cuộc hôn nhân ổn định.
Chúng ta sẽ chứng minh sự tồn tại của một cuộc hôn nhân ổn định thông qua việc lặp lại thủ tục, cụ thể là thuật toán Gale - Shapley, mà sẽ được thảo luận chi tiết trong chương tiếp theo Theo Định lý 1.2, mọi ứng cử viên đều có ít nhất một cặp được xác định bởi một phép gán từ các thủ tục hoãn chấp nhận khi họ ở dưới bất kỳ một phép gán ổn định khác.
Một trường được coi là "có thể" cho ứng cử viên β nếu có một phép gán ổn định được gửi tới anh ta Để chứng minh điều này, giả sử rằng đến một thời điểm nhất định trong quá trình, không có ứng cử viên nào được chuyển từ các trường đại học phù hợp với β.
Trường đại học A, sau khi xem xét các ứng dụng, đã từ chối đơn của ứng viên α vì không đủ tiêu chuẩn so với các ứng viên β1, βq Điều này cho thấy rằng α không thể được chấp nhận, vì mỗi βi đều ưu tiên chọn đại học A hơn bất kỳ trường nào khác, ngoại trừ những trường đã từ chối họ trước đó.
Xem xét một giả thuyết rằng α được gửi đến trường đại học A, trong khi những người khác được gửi đến các trường đại học khác có thể phù hợp hơn với họ Ít nhất một trong những β i sẽ phải chọn một trường đại học kém mong muốn hơn A Tuy nhiên, sự sắp xếp này không ổn định, vì β i và A có thể thay đổi lựa chọn để tối ưu hóa lợi ích của cả hai.
Trong chương này, chúng ta đã khám phá tình huống điển hình trong tuyển sinh đại học và nội dung của bài toán hôn nhân bền vững Ở chương tiếp theo, tôi sẽ giới thiệu về Thuật toán Gale – Shapley và đề xuất một sự mở rộng cho thuật toán này.
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 11
TÌM HIỂU THUẬT TOÁN GALE – SHAPLEY VÀ ĐỀ XUẤT MỘT MỞ RỘNG CỦA NÓ
Thuật toán Gale – Shapley
Trong một nhóm gồm 2n người, bao gồm n người đàn ông và n người phụ nữ, mỗi người đàn ông sẽ bày tỏ cảm nghĩ của mình về n người phụ nữ bằng cách xếp hạng từ người mà anh ta thích nhất đến người ít thích nhất Tương tự, các phụ nữ cũng sẽ đưa ra ý kiến về những người đàn ông theo cách tương tự.
Vấn đề đặt ra là làm thế nào để ghép đôi những người với nhau một cách bền vững, tránh tình trạng người chồng của cặp này lại thích người vợ của cặp kia, và ngược lại Trong các lĩnh vực kinh tế và xã hội, sự tương tác giữa cá nhân và tổ chức không chỉ đơn thuần là gặp gỡ hay ký hợp đồng, mà còn liên quan đến những giao dịch phức tạp mang tính "ghép đôi có tính toán".
Vậy ta có yêu cầu bài toán:
Input: Danh sách những người đàn ông, những người phụ nữ, và danh sách yêu thích theo thứ tự ưu tiên của họ
Output: Những cặp đôi ổn định
2.1.2 Thuật toán Để chứng minh các định lý đưa ra ở chương 1, Shapley và Gale đưa ra một thuật toán mà sau này trở nên nổi tiếng với tên gọi “Thuật toán Gale – Shapley”[1] Trước khi thực hiện thuật toán, mỗi người đàn ông và mỗi người phụ nữ sẽ đưa ra danh sách thứ tự ưu tiên 1, 2… n
Trước khi tiến hành ghép cặp, sở thích của mỗi người cần phải được xác định rõ ràng và không được thay đổi trong quá trình thực hiện thuật toán Nếu không tuân thủ quy tắc này, kết quả sẽ không ổn định Thuật toán sẽ được thực hiện theo các bước cụ thể để đảm bảo tính chính xác và hiệu quả.
Mỗi người đàn ông gửi lời yêu cầu tới người phụ nữ mà anh ta ưu tiên nhất trong danh sách của mình
Mỗi người phụ nữ sẽ loại tất cả ngoại trừ người mà cô ấy nói là có thể tạm thời chấp nhận ở thời điểm hiện tại
Những người đàn ông không được chọn sẽ tiếp tục đưa ra lựa chọn với người phụ nữ ưu tiên tiếp theo Người phụ nữ sẽ đồng ý với yêu cầu của người đàn ông nếu:
- Cô ấy chưa được ghép cặp với người nào
- Cô ấy thích anh này hơn người mà cô ấy được ghép trước đó
Ngược lại, cô ấy sẽ loại anh này
Tiếp tục cho đến khi tất cả phụ nữ được cầu hôn, thuật toán sẽ kết thúc với sự ghép đôi ổn định giữa nam và nữ Chúng ta có thể tóm tắt thuật toán như sau:
2 Khởi tạo m ∈ M và w ∈ W còn độc thân
3 while ∃ người đàn ông độc thân m vẫn còn có người phụ nữ w để gửi lời đề nghị
5 w là người phụ nữ m thích nhất mà vẫn chưa gửi lời đề nghị
8 else một cặp (m', w) đã đính hôn
13 (m', w) vẫn đang là một cặp
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 13 Để hiểu rõ hơn về thuật toán Gale - Shapley, chúng ta sẽ xem xét một ví dụ như sau
Ví dụ 2.1: Cho 4 người đàn ông (α, β, γ, δ) và 4 người phụ nữ (A, B, C, D) và danh sách yêu thích của họ được cho bởi 1 ma trận như Hình 1.2 ở chương 1
Chúng tôi đã tái cấu trúc danh sách ưu tiên của từng bên thành bảng, sắp xếp theo thứ tự giảm dần từ trái qua phải Các giá trị được gán cho những người đàn ông α, β, δ, γ lần lượt là m1, m2, m3, m4, và cho những người phụ nữ A, B, C, D là w1, w2, w3, w4 Cụ thể, Bảng 2.1(a) thể hiện thứ tự ưu tiên của những người đàn ông đối với những người phụ nữ, trong khi Bảng 2.1(b) phản ánh thứ tự ưu tiên của những người phụ nữ đối với những người đàn ông.
Bảng 2.1 Danh sách ưu tiên của người đàn ông (a) và của người phụ nữ (b)
Theo thuật toán Gale - Shapley, ta thực hiện như sau:
- m1 gửi lời đề nghị đến w1 Do w1 chưa có ai gửi lời đề nghị nên cô ấy sẽ chấp nhận m1, ta có cặp (m1, w1)
- m2 gửi lời đề nghị đến w1 Lúc này, w1 đang hứa hôn với m1, so sánh mức độ ưu tiên thì w1 ưu tiên m1 hơn m2 nên m2 bị từ chối, ta có cặp (m2, w1)
- m3 gửi lời đề nghị đến w2 Do w2 chưa có ai gửi lời đề nghị nên cô ấy sẽ chấp nhận m3, ta có cặp (m3, w2)
- m4 gửi lời đề nghị đến w4 Do w4 chưa có ai gửi lời đề nghị nên cô ấy sẽ chấp nhận m4, có cặp (m4, w4)
M2 bị từ chối và tiếp tục gửi lời đề nghị tới W4, người phụ nữ ưu tiên tiếp theo Lúc này, W4 đang hứa hôn với M4 nhưng vì cô thích M2 hơn nên đã từ chối M4 để chấp nhận lời đề nghị từ M2 Kết quả là cặp (M2, W4) hình thành Các cặp khác bao gồm M1 với W1, W2, W3, W4; M2 với W1, W4, W3, W2; M3 với W2, W1, W3, W4; và M4 với W4, W2, W3, W1.
M4 đã bị từ chối, nhưng sẽ tiếp tục gửi lời đề nghị đến W2, người phụ nữ ưu tiên tiếp theo Hiện tại, W2 đang hứa hôn với M3, nhưng vì cô ấy thích M4 hơn nên sẽ từ chối M3 để chấp nhận lời đề nghị từ M4 Kết quả là cặp đôi (M4, W2) hình thành.
M3 bị từ chối và sẽ gửi lời đề nghị tới người phụ nữ ưu tiên tiếp theo, W1, người đang hứa hôn với M1 Tuy nhiên, W1 lại thích M3 hơn, nên cô quyết định từ chối M1 để chấp nhận lời đề nghị từ M3, dẫn đến cặp đôi (M3, W1).
M1 đã bị từ chối và sẽ chuyển sang gửi lời đề nghị tới người phụ nữ ưu tiên tiếp theo là W2 Tuy nhiên, W2 hiện đang hứa hôn với M4 và vì cô ấy thích M4 hơn M1, nên W2 quyết định giữ nguyên mối quan hệ với M4 và từ chối M1.
M1 bị loại và quyết định gửi lời đề nghị tới người phụ nữ ưu tiên tiếp theo là W3 Khi đó, W3 chưa nhận được lời đề nghị nào khác, nên cô đã chấp nhận hứa hôn với M1 Kết quả là cặp đôi (M1, W3) được hình thành.
Sau khi thuật toán hoàn tất, chúng ta đã xác định được các cặp ghép đôi ổn định: (m1, w3), (m2, w4), (m3, w1) và (m4, w2), tương tự như kết quả hiển thị trong vòng tròn của ma trận trong Hình 1.2.
Giả sử có một người đàn ông m và một người phụ nữ w thích nhau hơn vợ hoặc chồng hiện tại của mình nhưng không thể đến với nhau Theo thuật toán Gale - Shapley, m sẽ gửi lời đề nghị tới w, và vì w cũng thích m, cô sẽ từ chối người hứa hôn trước đó để chấp nhận m Tuy nhiên, nếu m lại kết hôn với vợ hiện tại, điều này chỉ xảy ra khi w thích một người khác hơn và từ chối m, điều này mâu thuẫn với giả định ban đầu của chúng ta.
Vậy theo thuật toán Gale - Shapley, chúng ta sẽ luôn tìm được kết quả ổn định, như vậy Định lý 1.1 trong Chương 1 đã được chứng minh
Kiểm tra tính ổn định cho ví dụ trên
Xét cặp (m1, w3) và (m2, w4): Chúng ta thấy rằng m1 không thích w4 hơn w3, w3 không thích m2 hơn m1 và ngược lại, m2 cũng không thích w3 hơn w4, w4 cũng không thích m1 hơn m2
Xét cặp (m1, w3) và (m3, w1): Chúng ta thấy rằng m1 không thích w1 hơn w3, w3 không thích m3 hơn m1 và ngược lại, m3 cũng không thích w3 hơn w1, w1 cũng không thích m1 hơn m3
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 15
Xét cặp (m1, w3) và (m4, w2): Chúng ta thấy rằng m1 không thích w2 hơn w3, w3 không thích m4 hơn m1 và ngược lại, m4 cũng không thích w3 hơn w2, w2 cũng không thích m1 hơn m4
Xét cặp (m2, w4) và (m3, w1): Chúng ta thấy rằng m2 không thích w1 hơn w4, w4 không thích m3 hơn m2 và ngược lại, m3 cũng không thích w4 hơn w1, w1 cũng không thích m2 hơn m3
Xét cặp (m2, w4) và (m4, w2): Chúng ta thấy rằng m2 không thích w2 hơn w4, w4 không thích m4 hơn m2 và ngược lại, m4 cũng không thích w4 hơn w2, w2 cũng không thích m2 hơn m4
Xét cặp (m3, w1) và (m4, w2): Chúng ta thấy rằng m3 không thích w2 hơn w1, w1 không thích m4 hơn m3 và ngược lại, m4 cũng không thích w1 hơn w2, w2 cũng không thích m3 hơn m4
Không có cặp nào mà người vợ (chồng) của cặp này lại thích chồng (vợ) của cặp khác hơn là chồng (vợ) của chính mình Điều này cho thấy thuật toán sẽ kết thúc sau một số bước hữu hạn và cung cấp một lời giải ổn định, đáp ứng yêu cầu của bài toán.
Bài toán hôn nhân bền vững với số lượng người đàn ông và phụ nữ khác
Khi số lượng đàn ông và phụ nữ không bằng nhau, thuật toán vẫn có thể tìm ra các cặp đôi ổn định Tuy nhiên, nếu số lượng đàn ông nhiều hơn, sẽ có một số đàn ông không được kết hôn, và ngược lại, nếu số lượng phụ nữ nhiều hơn, sẽ có một số phụ nữ không được kết hôn Dưới đây, chúng ta sẽ xem xét một số ví dụ cho trường hợp này.
Trong ví dụ 2.2, có 4 người đàn ông (m1, m2, m3, m4) và 3 người phụ nữ (w1, w2, w3) với danh sách ưu tiên được trình bày trong Bảng 2.2 Bảng 2.3 (a) thể hiện thứ tự ưu tiên của các người đàn ông đối với phụ nữ, trong khi Bảng 2.3 (b) cho thấy thứ tự ưu tiên của các người phụ nữ đối với đàn ông, với thứ tự ưu tiên giảm dần từ trái sang phải.
Bảng 2.2 Danh sách ưu tiên của người đàn ông (a) và của người phụ nữ (b)
Theo thuật toán Gale - Shapley, ta thực hiện như sau:
- m1 gửi lời đề nghị đến w2 Do w2 đang độc thân nên nhận lời m1, ta có cặp (m1, w2)
- m2 gửi lời đề nghị đến w3 Do w3 đang độc thân nên nhận lời m2, ta có cặp (m2, w3)
M3 đã gửi lời đề nghị đến W3, trong khi W3 đang hứa hôn với M2 Tuy nhiên, W3 đã ưu tiên M3 hơn M2 và quyết định từ chối M2 để chấp nhận lời đề nghị từ M3, tạo nên một cặp ghép mới (M3, W3).
- m4 gửi lời đề nghị đến w1 Do w1 chưa có ai đến cầu hôn nên w1 sẽ nhận lời m4, ta có cặp (m4, w1)
M2 bị từ chối và quyết định tìm kiếm người phụ nữ tiếp theo, gửi lời đề nghị tới W2 Tuy nhiên, W2 đang hứa hôn với M1 và ưu tiên M1 hơn, dẫn đến việc M2 lại tiếp tục bị từ chối.
M2 tiếp tục tìm đến người cuối cùng trong danh sách là W1, người đang hứa hôn với M4 So với M4, M2 có mức độ ưu tiên thấp hơn trong lòng W1, vì vậy W1 quyết định giữ mối quan hệ với M4 và từ chối M2.
Sau khi thuật toán kết thúc Ta có 3 cặp được ghép đôi ổn định như sau: (m1, w2), (m3, w3), (m4, w1) Và m2 là người không được kết hôn
Trong ví dụ 2.3, có 5 người đàn ông (m1, m2, m3, m4) và 3 người phụ nữ (w1, w2, w3) với danh sách ưu tiên như sau: Bảng 2.3 (a) thể hiện sự ưu tiên của các người đàn ông đối với các người phụ nữ, trong khi Bảng 2.3 (b) phản ánh sự ưu tiên của các người phụ nữ đối với các người đàn ông Cụ thể, m1 ưu tiên w2, w1, w3; m2 ưu tiên w3, w2, w1; m3 ưu tiên w3, w1, w2; và m4 ưu tiên w1, w3, w2 Về phía phụ nữ, w1 ưu tiên m1, m3, m4, m2; w2 ưu tiên m3, m4, m1, m2; và w3 ưu tiên m4, m1, m3, m2.
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 17
Bảng 2.3 Danh sách ưu tiên của người đàn ông (a) và của người phụ nữ (b)
Dựa vào số lượng 3 người phụ nữ và quy tắc mỗi người chỉ được ghép cặp với 1 người, có thể dự đoán rằng sẽ có 2 người đàn ông bị loại Tiếp theo, chúng ta sẽ phân tích các cặp ghép và xác định những người sẽ bị loại.
- m1 gửi lời đề nghị đến w2 Do w2 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời m1, ta có cặp (m1, w2)
- m2 gửi lời đề nghị đến w3 Do w3 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời m2, ta có cặp (m2, w3)
- m3 gửi lời đề nghị đến w3 Lúc này, w3 ưu tiên m3 hơn m2 nên w3 từ chối m2 để nhận lời đề nghị từ m3, ta có cặp ghép mới (m3, w3)
- m4 gửi lời đề nghị đến w1 Do w1 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời m4, ta có cặp (m4, w1)
M5 đã gửi lời đề nghị đến W2, người đang hứa hôn với M1 Tuy nhiên, W2 lại ưu tiên M5 hơn M1, dẫn đến việc cô từ chối M1 Kết quả là một cặp ghép mới hình thành giữa M5 và W2.
Tiếp theo, hai người đàn ông bị loại là m1 và m2 sẽ tiếp tục gửi lời đề nghị đến những người phụ nữ ưu tiên tiếp theo của mình
M1 sẽ gửi lời đề nghị đến W1, trong khi W1 đang hứa hôn với M4 Tuy nhiên, W1 lại ưu tiên M1 hơn M4 trong danh sách của mình, dẫn đến việc M4 bị từ chối Kết quả là chúng ta có một cặp ghép mới: M1 và W1.
- m2 sẽ gửi lời đề nghị đến w1 Lúc này, w2 vẫn ưu tiên m5 hơn m2 m2 vẫn là người bị từ chối m1 w2 w1 w3 m2 w3 w2 w1 m3 w3 w1 w2 m4 w1 w3 w2 m5 w2 w3 w1 w1 m1 m3 m4 m2 m5 w2 m5 m4 m3 m1 m2 w3 m4 m1 m3 m5 m2
Sau vòng lặp vừa qua, m2 và m4 đã bị loại, buộc họ phải gửi lời đề nghị đến những người phụ nữ ưu tiên tiếp theo trong danh sách của mình.
M2 gửi lời đề nghị kết hôn đến W1, nhưng W1 vẫn ưu tiên M1 hơn, dẫn đến việc M2 tiếp tục bị từ chối Từ đó, có thể thấy rằng M2 không được ghép cặp thành công sau thuật toán này, vì tất cả những người mà anh ta đề nghị đều từ chối và không chấp nhận anh.
- m4 sẽ gửi lời đề nghị đến w3 Lúc này, w3 ưu tiên m4 hơn m3 => m3 bị từ chối
M3 là người bị loại và quyết định gửi lời đề nghị đến w1, nhưng w1 lại ưu tiên m1, dẫn đến việc m3 bị từ chối một lần nữa Sau đó, m3 tìm đến w2, người cuối cùng trong danh sách của mình, nhưng w2 đang hứa hôn với m5 và ưu tiên m5 nhất Vì vậy, m3 chấp nhận bị từ chối.
Vậy sau khi thuật toán kết thúc, ta tìm được các cặp như sau:
(m1, w1); (m4, w3); (m5, w2) Còn m2 và m3 là những người bị loại
Tương tự như hai ví dụ trên, chúng ta xét tiếp một ví dụ cho trường hợp số lượng người phụ nữ nhiều hơn số lượng người đàn ông
Ví dụ 2.4: Cho 3 người đàn ông (m1, m2, m3) và 4 người phụ nữ (w1, w2, w3, w4) với danh sách sự ưu tiên của mỗi người được cho như sau
Bảng 2.4 Danh sách ưu tiên của người đàn ông (a) và của người phụ nữ (b)
Theo các bước của thuật toán, ta tiến hành ghép cặp như sau
- m1 gửi lời đề nghị đến w2 Do w2 chưa có ai đề nghị trước đó nên cô ấy nhận lời m1, ta có cặp (m1, w2)
- m2 gửi lời đề nghị đến w3 Do w3 chưa có ai đề nghị trước đó nên cô ấy nhận lời m2, ta có cặp (m2, w3) w1 m1 m3 m2 w2 m3 m1 m2 w3 m1 m3 m2 w4 m1 m3 m2 m1 w2 w1 w3 w4 m2 w3 w2 w4 w1 m3 w3 w4 w1 w2
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 19
M3 đã gửi lời đề nghị đến W3, trong khi W3 đang hứa hôn với M2 Tuy nhiên, W3 ưu tiên M3 hơn M2 và quyết định từ chối M2 để chấp nhận lời đề nghị từ M3, tạo nên một cặp ghép mới là M3 và W3.
M2 bị từ chối và quyết định tìm đến W2, người mà M2 đã ưu tiên tiếp theo Tuy nhiên, W2 đang hứa hôn với M1 và lại đặt M1 lên trên M2, dẫn đến việc M2 tiếp tục bị từ chối.
- m2 sẽ gửi lời đề nghị tiếp theo cho w4 theo danh sách ưu tiên Lúc này, w4 chưa có ai gửi lời đề nghị nên sẽ chấp nhận m2, ta có cặp (m2, w4)
Như vậy, lúc này ta có các cặp (m1, w2), (m3, w3), (m2, w4) và w1 là người phụ nữ chưa được kết hôn.
Một mở rộng của thuật toán Gale - Shapley
Trong bài toán hôn nhân bền vững, chúng ta chỉ xem xét trường hợp đơn giản là mỗi người đàn ông kết hôn với một người phụ nữ Tuy nhiên, trong thực tế, khi áp dụng cho bài toán tuyển sinh hay phân công sinh viên thực tập, số lượng sinh viên và các trường khác nhau, mỗi trường có chỉ tiêu nhận sinh viên nhất định Do đó, nội dung của thuật toán hiện tại không phản ánh đầy đủ các vấn đề này, vì vậy việc mở rộng thuật toán là rất cần thiết.
Bài toán hôn nhân đã trở nên phức tạp hơn, không còn đơn thuần là một vợ một chồng nữa Trong trường hợp này, mỗi người phụ nữ có thể có nhiều hơn một chồng, dẫn đến việc chỉ tiêu của họ được tăng lên Để minh họa cho sự mở rộng này, chúng ta sẽ xem xét một ví dụ cụ thể.
Trong ví dụ 2.5, có tổng cộng 4 người đàn ông và 2 người phụ nữ, với chỉ tiêu của mỗi người phụ nữ là q = 2, tức là bằng nhau Danh sách ưu tiên của họ được trình bày trong Bảng 2.5.
Bảng 2.5 Danh sách ưu tiên của người đàn ông (a) và của người phụ nữ (b)
Theo như thuật toán, ta cũng cho 4 người đàn ông gửi lời đề nghị đến 2 người phụ nữ theo thứ tự trong danh sách ưu tiên của họ
- m1 gửi lời đề nghị đến w2 Do w2 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời m1, ta có cặp (m1, w2)
- m2 gửi lời đề nghị đến w1 Do w1 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời m2, ta có cặp (m2, w1)
- m3 gửi lời đề nghị đến w1.Vì chỉ tiêu q=2 nên w1 vẫn có thể nhận lời m3, ta có cặp
M4 đã gửi lời đề nghị đến W1, trong khi W1 đang hứa hôn với M3 và M2 Khi so sánh mức độ ưu tiên giữa M4, M3 và M2, W1 nhận thấy M2 không phải là sự lựa chọn hàng đầu của mình Do đó, cô quyết định từ chối M2 để chấp nhận lời đề nghị từ M4.
Sau khi m2 bị loại, anh ta sẽ gửi lời đề nghị đến người phụ nữ tiếp theo trong danh sách, là w2, và được chấp nhận vì w2 còn có thể chấp nhận thêm một người Kết quả là ta có cặp (m2, w2) Cuối cùng, ta thu được các bộ: {(m1, w2), (m2, w2)}, {(m3, w1), (m4, w1)}.
Trong ví dụ 2.6, có tổng cộng 5 người đàn ông và 2 người phụ nữ, với chỉ tiêu của mỗi người phụ nữ là bằng nhau và q = 2 Danh sách ưu tiên của họ được trình bày trong Bảng 2.6a và Bảng 2.6b.
Bảng 2.6 Danh sách ưu tiên của người đàn ông (a) và của người phụ nữ (b)
(a) (b) Đầu tiên, chúng ta cũng để mỗi người đàn ông gửi lời đề nghị đến cô gái mà anh ta yêu thích nhất trong danh sách
- m1 gửi lời đề nghị đến w2 Do w2 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời m1, ta có cặp (m1, w2) m1 w2 w1 m2 w1 w2 m3 w1 w2 m4 w1 w2 m5 w2 w1 w1 m1 m5 m4 m2 m3 w2 m3 m4 m5 m2 m1
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 21
- m2 gửi lời đề nghị đến w1 Do w2 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời m1, ta có cặp (m2, w1)
- m3 gửi lời đề nghị đến w1 Do w1 có chỉ tiêu q=2, nên vẫn có thể chấp nhận hứa hôn với m3, ta có cặp (m3, w1)
M4 đã gửi lời đề nghị đến W1 Khi so sánh mức độ ưu tiên của W1 với M2, M3 và M4, M3 là người có mức độ ưu tiên thấp nhất Do đó, W1 quyết định loại M3 để chấp nhận lời đề nghị từ M4, tạo thành cặp (M4, W1).
M5 đã gửi lời đề nghị đến W2, và do W2 có chỉ tiêu Q=2, nên W2 có thể chấp nhận hứa hôn với M5 Kết quả sau vòng thứ nhất là các cặp: (M1, W2), (M2, W1), (M4, W1) và (M5, W2), trong khi M3 bị loại.
M3 sẽ gửi lời đề nghị đến w2, người phụ nữ ưu tiên tiếp theo, trong khi w2 đang hứa hôn với m1 và m5 So sánh mức độ ưu tiên của w2 đối với m1, m3 và m5 cho thấy m1 là lựa chọn kém ưu tiên nhất Do đó, w2 sẽ từ chối m1 để chấp nhận lời đề nghị từ m3, tạo thành cặp (m3, w2).
Vậy sau vòng thứ 2 ta có các bộ sau: {(m2, w1), (m4, w1)}, {(m5, w2), (m3, w2)} và m1 là người bị loại
- m1 là người bị loại nên anh ta lại gửi tới người phụ nữ ưu tiên tiếp theo của mình là w1
Trong tình huống này, w1 đang hứa hôn với m2 và m4, nhưng khi so sánh mức độ ưu tiên giữa m1, m2 và m4, rõ ràng m2 là người có ưu tiên thấp nhất Do đó, w1 quyết định từ chối m2 và chấp nhận lời cầu hôn từ m1, tạo thành cặp đôi (m1, w1).
Sau vòng thứ 3, các cặp kết quả là {(m1, w1), (m4, w1)}, {(m5, w2), (m3, w2)}, và m2 bị loại M2 gửi lời đề nghị đến w2, người phụ nữ ưu tiên tiếp theo, nhưng w2 đang hứa hôn với m3 và m5 So sánh mức độ ưu tiên của w2 đối với m2, m3 và m5, m2 vẫn là lựa chọn kém ưu tiên nhất, do đó w2 quyết định giữ lại m3 và m5, từ chối m2.
Sau khi bị từ chối nhiều lần, m2 đã chấp nhận rằng mình không thể kết hôn, vì anh đã đề nghị với tất cả các phụ nữ trong danh sách mà mình đã chuẩn bị, nhưng đều nhận được câu trả lời từ chối.
Vậy kết quả cuối cùng, ta tìm được các bộ ghép với nhau là: {(m1, w1), (m4, w1)}; {(m3, w2), (m5, w2)} và m2 là người không được kết hôn
Ví dụ 2.7: Ta xét ví dụ tương tự như Ví dụ 2.6 nhưng chỉ tiêu của mỗi người phụ nữ tăng lên 1 đơn vị, nghĩa là chỉ tiêu q=3
Ban đầu, m1 gửi lời đề nghị đến w2 Do w2 chưa có ai gửi lời đề nghị nên cô ấy sẽ chấp nhận lờ đề nghị của m1, ta có cặp (m1, w2)
- m2 gửi lời đề nghị đến w1 Do w1 chưa có ai gửi lời đề nghị nên cô ấy sẽ chấp nhận lời đề nghị của m2, ta có cặp (m2, w1)
- m3 gửi lời đề nghị đến w1, ta có cặp (m3, w1) vì w1 vẫn đang còn chỉ tiêu
- m4 gửi lời đề nghị đến w1, ta có cặp (m4, w1) vì w1 vẫn đang còn chỉ tiêu
- m5 gửi lời đề nghị đến w2, ta có cặp (m5, w2) vì w2 vẫn đang còn chỉ tiêu
Vậy sau vòng đầu tiên tất cả những người đàn ông đều được kết hôn với những người phụ nữ, ta có các bộ sau: { (m1, w2), (m5, w2) }; { (m2 ,w1), (m3, w1), (m4, w1) }
Trong một tình huống cụ thể, có hai người phụ nữ với chỉ tiêu kết hôn là q=3 Nếu chỉ có 5 người đàn ông, sẽ có một người phụ nữ không đạt được số lượng chồng theo chỉ tiêu đã đề ra Trong trường hợp này, w2 là người không đủ số chồng như mong muốn.
Trong ví dụ 2.8, có tổng cộng 7 người đàn ông và 3 người phụ nữ, với chỉ tiêu của mỗi người phụ nữ là bằng nhau và q = 2 Danh sách ưu tiên của từng người được trình bày trong Bảng 2.7.
Bảng 2.7 Danh sách ưu tiên của người đàn ông (a) và của người phụ nữ (b)
Theo thuật toán Gale – Shapley mở rộng, ta thực hiện như sau:
- m1 gửi lời đề nghị đến w1 Do w1 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời đề nghị từ m1, ta có cặp (m1, w1)
- m2 gửi lời đề nghị đến w2 Do w2 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời đề nghị từ m2, ta có cặp (m2, w2) m1 w1 w2 w3 m2 w2 w1 w3 m3 w1 w3 w2 m4 w3 w2 w1 m5 w2 w3 w1 m6 w3 w1 w2 m7 w1 w3 w2 w1 m1 m2 m3 m4 m5 m6 m7 w2 m2 m4 m6 m1 m3 m7 m5 w3 m5 m3 m7 m2 m1 m4 m6
Nguyễn Thị Lam - Lớp 52K2 - Khoa CNTT 23
- m3 gửi lời đề nghị đến w1, ta có cặp (m3, w1) vì w1 vẫn đang còn chỉ tiêu
- m4 gửi lời đề nghị đến w3 Do w3 chưa có ai gửi lời đề nghị nên cô ấy sẽ nhận lời đề nghị từ m4, ta có cặp (m4, w3)
- m5 gửi lời đề nghị đến w2, ta có cặp (m5, w2) vì w2 vẫn đang còn chỉ tiêu
- m6 gửi lời đề nghị đến w3, ta có cặp (m6, w3) vì w3 vẫn đang còn chỉ tiêu
M7 đã gửi lời đề nghị đến W1, trong khi W1 đang hứa hôn với M1 và M3 So sánh mức độ ưu tiên giữa M1, M3 và M7, M7 là người có mức độ ưu tiên thấp nhất Do đó, M7 đã bị từ chối.
Thuật toán Gale – Shapley mở rộng
Thuật toán này được phát triển từ thuật toán Gale - Shapley đã đề cập trong Phần 2.1, với sự bổ sung về dữ liệu đầu vào bao gồm không chỉ số lượng nam và nữ mà còn cả chỉ tiêu về số lượng chồng mà mỗi phụ nữ có thể kết hôn Trước khi thực hiện thuật toán, cả nam và nữ sẽ lập danh sách thứ tự ưu tiên từ 1 đến n.
Mỗi người đàn ông gửi lời đề nghị tới người phụ nữ mà anh ta ưu tiên nhất trong danh sách của mình
Mỗi người phụ nữ sẽ loại tất cả ngoại trừ người mà cô ấy nói là có thể tạm thời chấp nhận ở thời điểm hiện tại
Những người đàn ông không được chọn vẫn tiếp tục gửi lời mời đến người phụ nữ ưu tiên tiếp theo Người phụ nữ sẽ đồng ý với lời mời của người đàn ông nếu:
- Cô ấy chưa lấy đủ chỉ tiêu
- Cô ấy thích anh này hơn những người nằm trong danh sách hứa hôn hiện tại của Ngược lại, cô ấy sẽ loại anh này
Quá trình tiếp tục cho đến khi tất cả các người đàn ông đều đã kết hôn hoặc bị từ chối bởi tất cả phụ nữ trong danh sách của họ Khi thuật toán hoàn thành, chúng ta sẽ có một sự ghép đôi ổn định giữa các người đàn ông và phụ nữ.
Thực thi thuật toán
Các thuật toán được trình bày trong Phần 2.1 và Phần 2.5 đã được triển khai bằng ngôn ngữ Java trong môi trường NetBeans, và thực hiện trên laptop ASUS với bộ vi xử lý Intel Core i5 - 4210U, có tốc độ tối đa lên đến 2.7GHz.
Trong lớp Men, phương thức để người đàn ông gửi lời đề nghị theo thứ tự ưu tiên được định nghĩa là: public boolean propose().
{ for(int i=0;i