×

Cài đặt thuật toán Gale-Shapley Deferred Acceptance trong lập trình

Avatar of admin
admin 0 Views

Thuật toán Gale-Shapley Deferred Acceptance, hay còn gọi là thuật toán kết đôi bền vững, là một công cụ mạnh mẽ trong toán học và khoa học máy tính để giải quyết vấn đề phân bổ ghép đôi một cách bền vững. Thuật toán này thường được áp dụng trong các hệ thống như kết đôi y khoa, các chương trình tuyển sinh đại học, và các vấn đề ghép đôi tương tự khác.

Nguyên tắc Hoạt động của Thuật toán

Thuật toán Gale-Shapley gồm hai tập hợp đỉnh ( A ) và ( B ), với mỗi thành viên trong tập hợp đều có một danh sách ưu tiên đối với các thành viên của tập hợp đối diện. Thuật toán sẽ hoạt động theo các bước như sau:

  1. Khởi tạo: Mỗi thành viên trong tập hợp ( A ) đều chưa có kết đôi.
  2. Tiến trình đề xuất: Mỗi thành viên chưa có kết đôi trong tập hợp ( A ) sẽ đề xuất cho thành viên mà họ ưu tiên cao nhất trong tập hợp ( B ) mà chưa từng bị từ chối.
  3. Xét duyệt đề xuất:
    • Nếu thành viên của tập hợp ( B ) chưa bị ghép đôi, họ sẽ chấp nhận lời đề nghị.
    • Nếu đã bị ghép đôi, họ sẽ so sánh thành viên hiện tại với đề xuất mới. Nếu thích hơn, họ sẽ chấp nhận đề xuất mới và loại bỏ thành viên cũ.
  4. Lặp lại: Quá trình này lặp lại cho đến khi không còn thành viên nào trong tập hợp ( A ) chưa có kết đôi và không bị từ chối hết các lựa chọn.

Cài đặt Thuật toán Gale-Shapley bằng Python

Dưới đây là một ví dụ đơn giản về cách cài đặt thuật toán Gale-Shapley trong Python:

def gale_shapley(men_preferences, women_preferences):
    # Initiate necessary variables
    n = len(men_preferences)
    unmatched_men = list(men_preferences.keys())
    proposals = {man: [] for man in men_preferences}
    current_engagements = {woman: None for woman in women_preferences}
    
    while unmatched_men:
        man = unmatched_men.pop(0)
        man_pref_list = men_preferences[man]
        
        for woman in man_pref_list:
            if woman not in proposals[man]:
                proposals[man].append(woman)
                
                if current_engagements[woman] is None:
                    current_engagements[woman] = man
                    break
                else:
                    current_man = current_engagements[woman]
                    woman_pref_list = women_preferences[woman]
                    
                    if woman_pref_list.index(man) < woman_pref_list.index(current_man):
                        current_engagements[woman] = man
                        unmatched_men.append(current_man)
                        break
        
    return current_engagements

if __name__ == "__main__":
    men_preferences = {
        "A": ["W1", "W2", "W3"],
        "B": ["W2", "W1", "W3"],
        "C": ["W1", "W3", "W2"]
    }
    
    women_preferences = {
        "W1": ["A", "B", "C"],
        "W2": ["B", "A", "C"],
        "W3": ["C", "A", "B"]
    }

    result = gale_shapley(men_preferences, women_preferences)
    print(result)

Phân tích và Ứng dụng

  • Độ phức tạp: 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 thành viên trong một tập hợp (tập hợp ( A ) hoặc ( B )).
  • Tính Bền Vững: Kết quả của thuật toán đảm bảo rằng không có hai thành viên nào muốn đổi đối tác với nhau để cả hai đều hài lòng hơn. Điều này ngăn chặn tình trạng "chiếm đoạt" đối tác từ cách đôi khác.
  • Ứng dụng thực tế: Như đã đề cập, thuật toán này rất hữu ích trong các vấn đề như phân bổ y khoa (National Resident Matching Program), các hệ thống hẹn hò, và thị trường lao động.

Kết Luận

Việc hiểu và cài đặt thành công thuật toán Gale-Shapley không chỉ cung cấp một giải pháp hiệu quả cho các bài toán ghép đôi mà còn mở ra nhiều khả năng ứng dụng trong đa dạng lĩnh vực. Việc áp dụng đúng cách sẽ giúp giải quyết nhiều vấn đề phân bổ nguồn lực một cách tối ưu và công bằng.

Comments

Bài viết liên quan