Bài toán hôn nhân ổn định: Cho N nam và N nữ, mỗi người có danh sách ưu tiên đối phương. Tìm cách ghép cặp sao cho không tồn tại cặp (nam, nữ) mà cả hai đều thích nhau hơn bạn đời hiện tại. Giải pháp: thuật toán Gale-Shapley.
Thuật toán
Hàm WomenPrefersMenOverMen1(prefer, w, m, m1):
Duyệt danh sách ưu tiên của nữ w:
Nếu gặp m1 trước: trả về true (giữ cặp cũ).
Nếu gặp m trước: trả về false (chuyển sang m).
Hàm stableMarriage(prefer):
Khởi tạo wPartner[N] = -1, mFree[N] = false.
freeCount = N.
Khi còn nam tự do:
Chọn nam m tự do đầu tiên.
Duyệt nữ theo ưu tiên của m:
Nếu nữ w tự do: ghép cặp, cập nhật.
Ngược lại: nếu w thích m hơn m1 (chồng hiện tại), hủy cặp cũ, ghép với m.
In kết quả.
Ví dụ mã nguồn
#include <iostream>
#include <cstring>
using namespace std;
#define N 4
bool womanPrefersMan(int prefer[2*N][N], int w, int m, int m1) {
for (int i = 0; i < N; i++) {
if (prefer[w][i] == m1) return true;
if (prefer[w][i] == m) return false;
}
return false;
}
void stableMarriage(int prefer[2*N][N]) {
int wPartner[N];
bool mFree[N];
memset(wPartner, -1, sizeof(wPartner));
memset(mFree, false, sizeof(mFree));
int freeCount = N;
while (freeCount > 0) {
int m;
for (m = 0; m < N; m++) if (!mFree[m]) break;
for (int i = 0; i < N && !mFree[m]; i++) {
int w = prefer[m][i];
if (wPartner[w-N] == -1) {
wPartner[w-N] = m;
mFree[m] = true;
freeCount--;
} else {
int m1 = wPartner[w-N];
if (!womanPrefersMan(prefer, w, m, m1)) {
wPartner[w-N] = m;
mFree[m] = true;
mFree[m1] = false;
}
}
}
}
cout << "Nu\tNam\n";
for (int i = 0; i < N; i++)
cout << i+N << "\t" << wPartner[i] << endl;
}
int main() {
int prefer[2*N][N] = {
{7,5,6,4}, {5,4,7,6}, {4,5,7,6}, {4,5,7,6},
{0,1,3,2}, {0,1,3,2}, {0,1,3,2}, {0,1,3,2}
};
stableMarriage(prefer);
return 0;
}
Đầu ra
Nu Nam 4 3 5 1 6 2 7 0