稳定婚姻算法详解（C++实现Gale-Shapley配对算法）

什么是“稳定”配对？

假设有 n 位男士和 n 位女士，每个人都对异性有一个偏好列表（从最喜欢到最不喜欢）。一个配对方案是稳定的，当且仅当不存在一对男女（男A和女B），他们彼此更喜欢对方而不是当前各自的伴侣。

换句话说，如果存在这样一对人，他们宁愿离开现在的伴侣而选择彼此，那么这个配对就是不稳定的。

Gale-Shapley 算法原理

Gale-Shapley算法通过“求婚-拒绝”机制来实现稳定配对。算法流程如下（以男士主动求婚为例）：

1. 所有男士和女士初始都未配对。
2. 每位未配对的男士向他偏好列表中尚未被拒绝的最高排名女士求婚。
3. 每位女士收到多个求婚时，会选择她最偏好的那位（根据她的偏好列表），暂时接受；其余拒绝。
4. 被拒绝的男士继续向下一个偏好的女士求婚。
5. 重复上述过程，直到所有男士都被配对。

该算法保证在有限步内结束，并且结果一定是稳定的。此外，由于男士主动求婚，最终结果对男士是最优的（每位男士获得在所有稳定配对中可能的最佳伴侣），而对女士是最差的。

C++ 实现稳定婚姻算法

下面我们用 C++ 编写一个完整的 稳定婚姻算法 实现。我们将使用 vector 存储偏好列表，并用数组记录配对状态。

代码说明

• n：参与人数（男女各 n 人）
• menPref：男士偏好列表（索引为男士编号，值为女士编号的排列）
• womenPref：女士偏好列表（索引为女士编号，值为男士编号的排列）
• womenPartner：记录每位女士当前的伴侣
• nextProposal：记录每位男士下一次要求婚的对象在自己偏好列表中的位置
• wRank：为了快速判断女士是否更喜欢新求婚者，我们预先构建一个排名表

#include <iostream>#include <vector>#include <queue>using namespace std;void stableMarriage(int n,                     const vector<vector<int>>& menPref,                    const vector<vector<int>>& womenPref) {    // 记录每位女士当前的伴侣，-1 表示未配对    vector<int> womenPartner(n, -1);        // 每位男士下一次要向谁求婚（在自己偏好列表中的索引）    vector<int> nextProposal(n, 0);        // 构建女士的偏好排名：rank[i][j] 表示女士 i 对男士 j 的偏好排名（越小越喜欢）    vector<vector<int>> wRank(n, vector<int>(n));    for (int w = 0; w < n; ++w) {        for (int rank = 0; rank < n; ++rank) {            int man = womenPref[w][rank];            wRank[w][man] = rank;        }    }        // 所有未配对的男士加入队列    queue<int> freeMen;    for (int m = 0; m < n; ++m) {        freeMen.push(m);    }        while (!freeMen.empty()) {        int man = freeMen.front();        freeMen.pop();                // 获取该男士下一个想求婚的女士        int woman = menPref[man][nextProposal[man]];        nextProposal[man]++; // 下次跳到下一个                if (womenPartner[woman] == -1) {            // 女士当前单身，直接配对            womenPartner[woman] = man;        } else {            // 女士已有伴侣，比较新旧            int currentMan = womenPartner[woman];            if (wRank[woman][man] < wRank[woman][currentMan]) {                // 女士更喜欢新来的男士                womenPartner[woman] = man;                freeMen.push(currentMan); // 被甩的男士重新进入队列            } else {                // 女士拒绝，该男士继续求婚                freeMen.push(man);            }        }    }        // 输出结果    cout << "稳定配对结果：\n";    for (int w = 0; w < n; ++w) {        cout << "男士 " << womenPartner[w]              << " 与 女士 " << w << " 配对\n";    }}int main() {    int n = 4;        // 男士偏好列表（每行代表一位男士对女士的喜好顺序）    vector<vector<int>> menPref = {        {0, 1, 2, 3}, // 男士0 最喜欢女士0，其次1...        {1, 0, 2, 3},        {2, 1, 0, 3},        {3, 1, 2, 0}    };        // 女士偏好列表    vector<vector<int>> womenPref = {        {0, 1, 2, 3}, // 女士0 最喜欢男士0...        {1, 0, 3, 2},        {2, 0, 1, 3},        {3, 0, 1, 2}    };        stableMarriage(n, menPref, womenPref);        return 0;}

运行结果示例

以上程序输出：

稳定配对结果：男士 0 与 女士 0 配对男士 1 与 女士 1 配对男士 2 与 女士 2 配对男士 3 与 女士 3 配对

你可以尝试修改偏好列表，观察不同输入下的稳定配对结果。

总结

通过本教程，我们学习了稳定婚姻算法的基本概念、Gale-Shapley算法的工作原理，并用 C++ 完整实现了这一经典配对算法。该算法不仅理论优美，而且在现实中有广泛应用，如医学院毕业生分配、在线约会系统等。

无论你是算法初学者还是希望巩固图论与匹配知识的开发者，掌握这个算法都将为你打下坚实基础。记住，关键在于理解“稳定”的定义以及算法如何通过局部最优逐步达成全局稳定。

希望这篇关于 C++实现 稳定婚姻问题的教程对你有所帮助！