Thuật toán Stable Marriage Problem là một bài toán kinh điển trong lý thuyết đồ thị và trí tuệ nhân tạo, được sử dụng để giải quyết vấn đề ghép cặp sao cho không có hai người nào muốn rời bỏ cặp hiện tại của mình để tạo một cặp mới với người khác. Đây là một vấn đề thú vị và có rất nhiều ứng dụng thực tiễn, từ việc ghép cặp học sinh với các trường đại học đến việc phân phối các công việc theo sở thích cá nhân. Trong bài viết này, chúng ta sẽ tìm hiểu cách cài đặt thuật toán này trong lập trình.
Bối cảnh và Mô tả
Stable Marriage Problem đề cập đến việc có một số lượng bằng nhau các chàng trai và cô gái (n chàng trai và n cô gái). Mỗi người có danh sách ưu tiên của chính mình cho những người khác giới mà họ muốn kết duyên. Nhiệm vụ của thuật toán là sắp xếp các cặp sao cho không ai muốn "bỏ" đối tác hiện tại của mình để kết hợp với người khác mà họ ưa thích hơn.
Thuật toán Gale-Shapley
Gale-Shapley là một thuật toán nổi tiếng được thiết kế để giải quyết vấn đề này. Thuật toán này đảm bảo rằng kết quả sẽ là một bộ ghép cặp ổn định.
Các bước chính của thuật toán:
- Khởi tạo: Mỗi chàng trai và cô gái đều được đánh dấu là độc thân.
- Đề xuất và xem xét:
- Mỗi chàng trai độc thân sẽ đề xuất người đàu tiên trong danh sách ưu tiên của mình mà anh chưa từng đề xuất.
- Mỗi cô gái nhận được đề xuất sẽ chọn giữa việc chấp nhận lời cầu hôn hoặc giữ lại đối tác hiện tại của mình dựa trên thứ tự ưu tiên của cô.
- Đánh dấu ghép đôi:
- Nếu cô gái chấp nhận đề xuất, cô và anh chàng sẽ tạm thời được ghép đôi, và anh chàng không còn là độc thân.
- Nếu cô gái từ chối đề xuất, anh chàng sẽ tiếp tục đề xuất người tiếp theo trong danh sách của mình.
- Lặp lại các bước trên cho đến khi tất cả mọi người đều đã được ghép cặp.
Cài đặt trong Python
Dưới đây là cách cài đặt chi tiết thuật toán này bằng ngôn ngữ lập trình Python:
def stable_marriage(n, men_preferences, women_preferences):
# Đánh dấu các cô gái là độc thân
women_partner = [-1] * n
# Các chàng trai đang độc thân
free_men = list(range(n))
# Danh sách đề xuất của các chàng trai cho từng cô gái
mens_next_proposal = [0] * n
# Đối tượng python để nhanh chóng kiểm tra thứ tự ưu tiên của nữ với từng nam
women_priority = []
for w_prefs in women_preferences:
priority = {man: rank for rank, man in enumerate(w_prefs)}
women_priority.append(priority)
while free_men:
man = free_men.pop(0)
man_prefs = men_preferences[man]
woman = man_prefs[mens_next_proposal[man]]
mens_next_proposal[man] += 1
current_partner = women_partner[woman]
# Nếu cô gái hiện tại độc thân
if current_partner == -1:
women_partner[woman] = man
else:
if women_priority[woman][man] < women_priority[woman][current_partner]:
women_partner[woman] = man
free_men.append(current_partner)
else:
free_men.append(man)
return [(women_partner[i], i) for i in range(n)]
# Dữ liệu thử nghiệm
n = 3
men_preferences = [
[0, 1, 2],
[1, 2, 0],
[2, 0, 1]
]
women_preferences = [
[1, 0, 2],
[2, 1, 0],
[0, 2, 1]
]
result = stable_marriage(n, men_preferences, women_preferences)
print("Kết quả ghép đôi ổn định là:", result)
Phân tích kết quả
Kết quả trả về từ hàm stable_marriage là một danh sách các cặp sao cho mỗi cặp là một bộ gồm (chàng trai, cô gái).
Ứng dụng thực tế
Thuật toán này không chỉ áp dụng cho việc ghép đôi nam nữ mà còn có thể ứng dụng trong nhiều lĩnh vực khác như:
- Ghép cặp sinh viên và trường đại học: Giúp tối ưu sự lựa chọn của sinh viên và chỉ tiêu của các trường đại học.
- Ghép cặp nhà đầu tư và dự án khởi nghiệp: Giúp nhà đầu tư tìm kiếm những dự án phù hợp với tiêu chí của họ và ngược lại.
- Phân bố tài nguyên và công việc: Giúp phân chia công việc hoặc tài nguyên sao cho không có sự không hài lòng lớn giữa các bên.
Việc hiểu và cài đặt thuật toán Stable Marriage Problem mang lại rất nhiều lợi ích và giúp dễ dàng giải quyết các bài toán phức tạp trong thực tế.
Comments