Thuật toán Gale-Shapley, hay còn gọi là thuật toán ghép đôi ổn định, là một phương pháp phổ biến được sử dụng để giải quyết các vấn đề liên quan đến việc ghép đôi giữa hai tập hợp mối liên hệ với nhau. Thuật toán này được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau như tuyển dụng, ghép đôi trong hôn nhân, và phân công sinh viên với các chương trình học.
1. Nguyên lý hoạt động của thuật toán
Thuật toán này được xây dựng dựa trên nguyên lý của việc ghép đôi sao cho không có bất kỳ hai đối tượng nào trong hai tập hợp có thể "tái ghép đôi" với nhau để tạo ra một ghép đôi ổn định hơn. Nói cách khác, thuật toán nhắm đến việc tạo ra một trạng thái trong đó không có bất kỳ cặp đối tượng nào có thể cùng nhau cải thiện vị thế của họ.
2. Cài đặt thuật toán
Dưới đây là hướng dẫn cài đặt thuật toán Gale-Shapley trong lập trình.
2.1 Chuẩn bị dữ liệu
Trước tiên, ta cần có dữ liệu đầu vào bao gồm danh sách thứ tự ưu tiên của các đối tượng trong mỗi tập hợp. Giả sử chúng ta có hai tập hợp, A và B, và mỗi đối tượng trong tập hợp A có danh sách ưu tiên của các đối tượng trong tập hợp B, và ngược lại.
men_preferences = {
'A': ['X', 'Y', 'Z'],
'B': ['Y', 'X', 'Z'],
'C': ['X', 'Z', 'Y']
}
women_preferences = {
'X': ['B', 'A', 'C'],
'Y': ['A', 'B', 'C'],
'Z': ['A', 'B', 'C']
}
2.2 Thuật toán chính
Tiếp theo, chúng ta sẽ xây dựng thuật toán chính để thực hiện việc ghép đôi ổn định dựa trên dữ liệu đầu vào.
def stable_matching(men_preferences, women_preferences):
free_men = list(men_preferences.keys())
women_partners = {woman: None for woman in women_preferences}
men_proposals = {man: [] for man in men_preferences}
while free_men:
man = free_men[0]
man_pref_list = men_preferences[man]
for woman in man_pref_list:
if woman not in men_proposals[man]:
men_proposals[man].append(woman)
current_partner = women_partners[woman]
if current_partner is None:
women_partners[woman] = man
free_men.remove(man)
break
else:
woman_pref_list = women_preferences[woman]
if woman_pref_list.index(man) < woman_pref_list.index(current_partner):
women_partners[woman] = man
free_men.remove(man)
free_men.append(current_partner)
break
return women_partners
# Áp dụng thuật toán
result = stable_matching(men_preferences, women_preferences)
print(result)
2.3 Giải thích kết quả
Kết quả của hàm stable_matching là một từ điển thể hiện các cặp ghép đôi ổn định giữa hai tập hợp.
3. Ứng dụng thực tiễn
Thuật toán Gale-Shapley đã được áp dụng trong nhiều hệ thống thực tiễn:
- Hệ thống tuyển dụng: Ghép đôi giữa các ứng viên và công ty sao cho cả hai bên đều cảm thấy hài lòng nhất có thể với đối tác của mình.
- Phân công sinh viên: Chia sinh viên vào các khóa học, nhóm nghiên cứu hoặc chương trình đào tạo hợp lý nhất có thể.
- Ghép đôi trong hôn nhân: Thực hiện ghép đôi giữa nam và nữ trong các hẹn hò hoặc kết hôn, đảm bảo không có ai muốn thay đổi đối tác hơn cặp hiện tại.
Kết luận
Thuật toán ghép đôi ổn định mang lại nhiều lợi ích trong việc giải quyết các bài toán ghép đôi phức tạp, đảm bảo sự công bằng và ổn định trong các mối tương quan đôi bên. Việc cài đặt thuật toán này trong lập trình cũng không quá phức tạp và có thể triển khai trong nhiều ngôn ngữ lập trình khác nhau.
Comments