Thuật toán Gale-Shapley
Thuật toán Gale-Shapley giải quyết bài toán hôn nhân ổn định: làm thế nào để ghép đôi hai nhóm (ví dụ: bác sĩ nội trú với bệnh viện, học sinh với trường học) sao cho không có cặp đôi nào ưa thích nhau hơn đối tác được chỉ định của họ. Được giới thiệu bởi David Gale và Lloyd Shapley vào năm 1962, thuật toán đảm bảo một sự ghép đôi ổn định trong thời gian đa thức thông qua quy trình chấp nhận hoãn lại, trong đó một bên đề xuất tuần tự và bên kia phản hồi, sửa đổi các lựa chọn khi có các lựa chọn tốt hơn xuất hiện.
Đọc toàn bộ phương pháp
Đăng nhập bằng tài khoản miễn phí để đọc phần này.
Bản đồ phương pháp
Lân cận của các phương pháp liên quan — chọn một nút để khám phá.
Nguồn tài liệu
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. DOI: 10.1080/00029890.1962.11989827 ↗
- Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628. DOI: 10.1287/moor.7.4.617 ↗
Cách trích dẫn trang này
ScholarGate. (2026, June 3). Gale-Shapley Stable Marriage Algorithm. ScholarGate. https://scholargate.app/vi/game-theory/gale-shapley-algorithm
Phương pháp nào?
Đặt phương pháp này bên cạnh những phương pháp gần gũi nhất với nó và đọc chúng song song — thư viện bày sách lên bàn; lựa chọn là của bạn.
- Cân bằng Nash BayesLý thuyết trò chơi↔ so sánh
- Mô hình Người ủy thác - Người đại diệnLý thuyết trò chơi↔ so sánh
- Chu trình Giao dịch Tối ưuLý thuyết trò chơi↔ so sánh
- Cơ chế VCGLý thuyết trò chơi↔ so sánh
Được tham chiếu bởi
Phát hiện lỗi trên trang này? Báo cáo hoặc đề xuất chỉnh sửa →