💡 Thuật toán Gale-Shapley, còn được gọi là thuật toán ghép cặp ổn định hoặc Stable Matching Algorithm, là một thuật toán nổi tiếng được phát triển bởi hai nhà toán học David Gale và Lloyd Shapley vào năm 1962. Thuật toán này được dùng để giải quyết bài toán “ghép cặp ổn định” (Stable Marriage Problem) – một bài toán trong đó có hai nhóm đối tượng cần được ghép cặp sao cho không có bất kỳ cặp nào muốn rời khỏi mối ghép cặp hiện tại để đến với một đối tượng khác. Thuật toán này đã giành giải Nobel kinh tế năm 2012.
Thuật toán trên đã từng có khá nhiều người viết về nó, và thậm chí viết rất hay! Vì thế note này của mình chỉ chú trọng viết lại sao cho thật ngắn gọn về phần thuật toán và 1 mini demo để các bạn dễ hiểu nhất có thể. Các bạn muốn tìm hiểu sâu hơn thì có thể đọc các blog này thêm:
Thuật toán
Có bạn nam và bạn nữ quen biết nhau, mỗi bạn có một danh sách yêu thích của mình đối với bạn khác giới còn lại. Tìm cách ghép cặp các bạn này đôi một khác giới với nhau.
Khởi Tạo: Từng người trong nhóm các bạn trai sẽ chọn ra cô gái để mình ngỏ lời theo tiêu chí:
Cô gái đó chưa từng từ chối anh ta trước đó
Cô gái đó là cô gái anh ta thích nhất trong số các cô gái còn lại (chưa từ chối)
Lời Đề Nghị Và Chấp Nhận Tạm Thời: Cô gái khi nhận được ngỏ lời từ một chàng trai sẽ xem xét để chấp nhận tạm thời hay từ chối theo các tiêu chí:
Chấp nhận tạm thời nếu chưa có ai ngỏ lời
Hoặc nếu chàng trai đang ngỏ lời là chàng trai cô ấy thích hơn so với chàng trai cô ấy đang chấp nhận, cô ấy sẽ chấp nhận lời ngỏ này và từ chối chàng trai hiện tại
Ngoài ra, cô ấy từ chối
Tiếp Tục Lặp & Kết thúc:
Những chàng trai bị từ chối sẽ tiếp tục ngỏ lời với cô gái tiếp theo trong danh sách ưu tiên của mình.
Quy trình này tiếp tục lặp lại cho đến khi không còn chàng trai nào chưa có cặp hoặc không còn cô gái nào từ chối lời ngỏ lời.
Cài đặt
Cấu trúc dữ liệu: Hai nhóm người, một nhóm nam và một nhóm nữ. Mỗi cá nhân có tên, giới tính, partner hiện tại và danh sách yêu thích riêng của mình.
class Person {
constructor(name, gender, preferences = null, x = 0, y = 0){
this.name = name;
this.preferences = preferences;
this.partner = null;
this.gender = gender;
// dành cho phần vẽ
this.x = x;
this.y = y;
}
}
Xử lý chính:
Mỗi cá nhân có 3 hành động chính, được xử lý trong 3 functions:
propose(): tìm ra một đối tượng yêu thích nhất để ngỏ lời
accept(propose): trả về TRUE nếu nhận lời ngỏ propose, hoặc FALSE nếu ngược lại
reject(): từ chối partner hiện tại
Mỗi round, lần lượt kiểm tra từng cá nhân nam, nếu anh ta chưa có partner thì tìm kiếm partner để propose
proposeOnce() {
for (let i = 0; i < this.males.length; i++) {
let male = this.males[i];
if (male.partner == null) {
const female = male.propose();
const isAccepted = female.accept(male);
if (isAccepted) {
// update new partner
male.partner = female;
// rejects the current partner
female.reject();
// update the new partner
female.partner = male;
}
}
}
}
Repeat cho đến khi tất cả các cá nhân nam đều có partner:
// execute the proposing until all are engaged
let allEngaged = false;
while (!allEngaged) {
this.proposeOnce();
allEngaged = this.males.every(m => m.partner != null);
}