C++实现稳定婚姻问题：Gale-Shapley算法详解与工程实践-开发者社区

1. 项目概述与问题引入

“婚姻匹配问题”听起来像是个社会学话题，但它其实是计算机科学和运筹学中一个非常经典的组合优化问题，更广为人知的名字是“稳定婚姻问题”。我第一次接触这个问题是在学习算法设计课程时，当时觉得它简直是理论联系实际的完美典范——用严谨的数学和算法，去模拟并解决一个充满人性化色彩的社会匹配难题。后来在工作中，无论是设计任务调度系统、实习生与导师的双向选择，还是广告投放中的用户与广告位匹配，其底层逻辑都能看到这个问题的影子。

简单来说，稳定婚姻问题要解决的是：有两组数量相等的个体，比如男性和女性，每人都对另一组的所有成员有一个明确的偏好排序。我们的目标是找到一种一一对应的匹配方式，使得不存在这样一对“不幸福”的男女：他们彼此喜欢对方的程度，都超过了自己当前被匹配到的伴侣。这种“不幸福”的对儿，在算法里被称为“不稳定对”。如果一种匹配不存在任何不稳定对，那么它就是“稳定匹配”。这个问题的奇妙之处在于，对于任意给定的偏好列表，稳定匹配总是存在的，并且可以通过一个优雅且高效的算法——Gale-Shapley算法（也被称为“延迟接受算法”）来找到。

今天，我们就用C++来亲手实现并深入解析这个算法。选择C++，不仅因为其性能足以处理大规模匹配场景（比如上万甚至百万级的匹配），更因为通过实现这个过程，我们能深刻理解贪心算法的策略、数据结构的选用、以及如何将抽象的数学证明转化为可靠的代码逻辑。无论你是正在准备算法面试，还是对组合优化问题感兴趣，亦或是想找一个有趣的练手项目来巩固C++和数据结构，这篇文章都将带你从零开始，完成一个工业级强度的稳定婚姻问题求解器。

2. 核心算法原理：Gale-Shapley算法深度拆解

在动手写代码之前，我们必须吃透Gale-Shapley算法的核心思想。这个算法之所以经典，在于其简洁、高效且具有深刻的数学保证。它的过程可以类比为一个“求婚”仪式。

2.1 算法流程与“求婚”隐喻

假设我们有n位男士和n位女士。算法维护两个核心状态：每位男士的“求婚进度”（下一个准备求婚的女士在其偏好列表中的位置），以及每位女士的“当前订婚对象”。算法流程如下：

初始化：所有男士设为“自由”状态，所有女士设为“未订婚”状态。每位男士的求婚指针指向其偏好列表中的第一位女士。
循环（存在自由男士时）： a. 任选一位自由男士m。 b. 他向自己偏好列表中，排在当前指针位置（即他尚未求过婚的、最喜欢的）的那位女士w求婚。 c. 考察女士w的当前状态： - 如果w未订婚，则她接受求婚，m和w订婚。m变为“已订婚”状态。 - 如果w已订婚，假设当前未婚夫是m'。w会比较m和m'在她偏好列表中的位置。 - 如果w更喜欢m（即m在她的列表中排在m'之前），她会解除与m'的婚约，改为与m订婚。m变为“已订婚”，m'恢复“自由”状态。 - 如果w更喜欢m'，则她拒绝m的求婚。m保持“自由”状态。 d. 无论求婚成功与否，这位男士m的求婚指针都会向后移动一位（指向下一位偏好女士），以备下次循环可能再次求婚。
终止：当没有自由男士时，算法结束。所有订婚关系即构成最终的稳定匹配。

注意：这个描述是“男士主动版”。算法完全对称，也存在“女士主动版”，但通常的经典描述和实现都以男士为主动方。

2.2 算法正确性证明要点

为什么这个看似简单的过程一定能找到稳定匹配？我们可以从几个关键性质来理解：

有限步内终止：每位男士最多向n位女士求婚，因此总求婚次数不超过n²。算法必然在有限步内结束。
匹配完整性：算法结束时，所有男士都订婚了（因为自由男士会持续求婚，而女士一旦订婚就不会再变回“未订婚”，只会更换对象）。由于人数相等，这也意味着所有女士都订婚了，形成了一个完美匹配。
稳定性：这是核心。采用反证法：假设算法产生的匹配中存在一个不稳定对(m, w)，即m比起自己的妻子mWife更喜欢w，同时w比起自己的丈夫wHusband也更喜欢m。那么，在算法执行过程中，m必然在向mWife求婚之前，先向w求过婚（因为他按偏好顺序求婚）。当m向w求婚时，w要么当时是自由的（那么她会接受m，后续不可能再与更不喜欢的wHusband订婚），要么当时已与wHusband或其他人订婚。如果已订婚，她会在m和当时未婚夫之间选择更偏好者。既然她最终嫁给了wHusband而不是m，说明在求婚发生时，她更偏好当时的未婚夫（可能是wHusband或其他人）。但根据传递性，她最终选择的wHusband至少不比当时的未婚夫差，因此她不可能在最终状态反而更喜欢m。这就产生了矛盾，证明了不稳定对不可能存在。

这个证明过程体现了算法设计的精妙：通过让主动方按偏好顺序“尝试”，让被动方始终保留可得到的最佳选择，自然消除了不稳定的可能性。

2.3 算法复杂度分析

时间复杂度：最坏情况下，每位男士都会向所有女士求婚一次。每次求婚操作（查找女士偏好、比较排名）我们可以在O(1)时间内完成（通过精心设计的数据结构，下文会详述）。因此，总时间复杂度为O(n²)。这对于实际应用（如数千人的匹配）是完全可以接受的。
空间复杂度：主要用来存储所有男士和女士的偏好列表，以及一些辅助数据结构，空间复杂度为O(n²)（存储所有偏好）或优化后可达O(n²)（存储排名索引）。

3. 数据结构设计与C++实现要点

理解了算法思想，接下来就是如何用C++高效地实现它。数据结构的选择直接决定了代码的简洁性和运行效率。

3.1 输入表示：偏好列表的存储

最直观的输入可能是两个二维向量：vector<vector<int>> menPref和vector<vector<int>> womenPref。menPref[i]是第i位男士的偏好列表，按喜好程度降序存储女士编号。但这样存在一个问题：当女士w需要比较男士m和当前未婚夫m’时，她需要在自己的偏好列表womenPref[w]中线性查找m和m’的位置以比较优先级，这是一个O(n)操作，会使总复杂度升至O(n³)。

优化策略：我们引入“反向索引”或“排名矩阵”。除了存储偏好列表，我们额外用一个二维数组vector<vector<int>> womenRank来存储排名。其中womenRank[w][m]表示在女士w的心中，男士m的排名（数值越小，排名越靠前，越喜欢）。这样，当女士需要比较两个男士时，只需要O(1)时间查询womenRank[w][m]和womenRank[w][m']并比较数值即可。

3.2 核心状态维护

我们需要跟踪以下动态状态：

wife[m]和husband[w]：记录当前的匹配结果。wife[m]表示男士m的妻子编号（-1表示自由），husband[w]类似。
nextProposal[m]：记录男士m下一次要求婚的对象在其menPref[m]列表中的索引。初始为0。
自由男士列表：我们需要高效地选取一位自由男士。使用一个队列queue<int> freeMen是最自然的选择。初始时将所有男士入队。

3.3 C++类设计

我们将设计一个StableMarriage类，封装数据和方法，使接口清晰，易于复用。

#include <iostream> #include <vector> #include <queue> using namespace std; class StableMarriage { private: int n; // 男女人数（假定相等） vector<vector<int>> menPref; // 男士偏好列表 menPref[man][rank] = woman vector<vector<int>> womenPref; // 女士偏好列表 womenPref[woman][rank] = man vector<vector<int>> womenRank; // 女士排名矩阵 womenRank[woman][man] = rank // 算法执行过程中的状态 vector<int> wifeOfMan; // wifeOfMan[man] = woman 或 -1 vector<int> husbandOfWoman; // husbandOfWoman[woman] = man 或 -1 vector<int> nextProposalIdx; // nextProposalIdx[man]，指向menPref中下一个要求婚的女士索引 queue<int> freeMen; // 当前自由的男士队列 public: // 构造函数：初始化偏好列表，并构建 womenRank StableMarriage(const vector<vector<int>>& mp, const vector<vector<int>>& wp); // 核心算法：Gale-Shapley，返回匹配结果（wifeOfMan） vector<int> solve(); // 工具函数：检查给定的匹配是否是稳定的 bool isStable(const vector<int>& match) const; private: // 初始化 womenRank 矩阵 void buildWomenRankMatrix(); };

3.4 关键实现细节与陷阱

构建排名矩阵buildWomenRankMatrix：这是实现高效比较的关键。不能简单地用find函数在womenPref[w]中查找，那仍是O(n)。我们需要利用数组索引直接映射。

void StableMarriage::buildWomenRankMatrix() { womenRank.resize(n, vector<int>(n)); for (int w = 0; w < n; ++w) { // 女士w的偏好列表中，第rank位是男士m // 那么女士w给男士m的排名就是rank for (int rank = 0; rank < n; ++rank) { int m = womenPref[w][rank]; womenRank[w][m] = rank; // 排名数值越小越喜欢 } } }

注意：这里假设男士和女士的编号都是从0到n-1的整数。如果输入是字符串或其他标识符，需要先建立到整型ID的映射。

核心算法solve的实现：

vector<int> StableMarriage::solve() { // 初始化状态 wifeOfMan.assign(n, -1); husbandOfWoman.assign(n, -1); nextProposalIdx.assign(n, 0); // 初始化自由男士队列 for (int m = 0; m < n; ++m) freeMen.push(m); while (!freeMen.empty()) { int m = freeMen.front(); // 取一位自由男士 freeMen.pop(); // 如果这位男士已经向所有女士求过婚了，理论上在Gale-Shapley中不会发生， // 因为总有女士会接受他。但为了代码健壮性，可以检查。 if (nextProposalIdx[m] >= n) { // 这种情况意味着输入可能有误，或者算法逻辑有问题。 // 在实际稳定婚姻问题中，不会出现所有女士都拒绝一位男士的情况。 continue; } // 这位男士的下一个求婚对象 int w = menPref[m][nextProposalIdx[m]]; nextProposalIdx[m]++; // 无论成败，指针后移 if (husbandOfWoman[w] == -1) { // 情况1：女士w自由，直接订婚 wifeOfMan[m] = w; husbandOfWoman[w] = m; } else { // 情况2：女士w已订婚，现任是m2 int m2 = husbandOfWoman[w]; // 比较女士w对m和m2的偏好 if (womenRank[w][m] < womenRank[w][m2]) { // w更喜欢m，甩掉m2，与m订婚 wifeOfMan[m] = w; husbandOfWoman[w] = m; // m2恢复自由 wifeOfMan[m2] = -1; freeMen.push(m2); } else { // w更喜欢现任m2，拒绝m // m保持自由，需要放回队列吗？不，他会在本轮循环外，因为未被处理而“消失”。 // 实际上，我们需要让m继续留在自由男士中，尝试下一位女士。 // 所以，我们需要把m重新加回队列。 freeMen.push(m); } } } return wifeOfMan; }

这里有一个极易出错的细节：当男士求婚被拒绝后，他应该被重新放回自由男士队列，以便下次循环继续尝试向其他女士求婚。很多初学者实现的版本会遗漏这一步，导致算法提前终止或结果错误。

4. 完整代码实现与测试

让我们将上述设计整合成一个完整的、可编译运行的程序，并添加详细的注释和测试用例。

4.1 完整C++代码

#include <iostream> #include <vector> #include <queue> #include <cassert> using namespace std; class StableMarriage { private: int n; // 人数 vector<vector<int>> menPref; vector<vector<int>> womenPref; vector<vector<int>> womenRank; // womenRank[woman][man] = preference rank (0 is most preferred) // 构建反向索引，实现O(1)的比较 void buildWomenRankMatrix() { womenRank.resize(n, vector<int>(n)); for (int w = 0; w < n; ++w) { for (int rank = 0; rank < n; ++rank) { int m = womenPref[w][rank]; womenRank[w][m] = rank; } } } public: // 构造函数：接收偏好列表，并构建排名矩阵 StableMarriage(const vector<vector<int>>& mp, const vector<vector<int>>& wp) : menPref(mp), womenPref(wp) { assert(mp.size() == wp.size()); n = mp.size(); // 可选：这里可以添加输入有效性检查，例如每个列表是否包含0到n-1的所有数字 buildWomenRankMatrix(); } // 执行Gale-Shapley算法（男士主动版） vector<int> solve() { // wifeOfMan[man] = woman he is engaged to, -1 if free // husbandOfWoman[woman] = man she is engaged to, -1 if free vector<int> wifeOfMan(n, -1), husbandOfWoman(n, -1); // nextProposalIdx[man] = index of next woman in his preference list to propose to vector<int> nextProposalIdx(n, 0); queue<int> freeMen; // 所有男士初始都是自由的 for (int m = 0; m < n; ++m) freeMen.push(m); while (!freeMen.empty()) { int m = freeMen.front(); freeMen.pop(); // 防止越界（理论上不应发生） if (nextProposalIdx[m] >= n) continue; // 这位男士向他偏好列表中下一个未求过婚的女士求婚 int w = menPref[m][nextProposalIdx[m]]; nextProposalIdx[m]++; if (husbandOfWoman[w] == -1) { // Case 1: 女士w是自由的，接受求婚 wifeOfMan[m] = w; husbandOfWoman[w] = m; } else { // Case 2: 女士w已与m2订婚 int m2 = husbandOfWoman[w]; // 比较w对m和m2的偏好 if (womenRank[w][m] < womenRank[w][m2]) { // w更喜欢m，所以解除与m2的婚约，与m订婚 wifeOfMan[m] = w; husbandOfWoman[w] = m; // m2变为自由 wifeOfMan[m2] = -1; freeMen.push(m2); } else { // w更喜欢现任m2，拒绝m // m求婚失败，放回队列继续尝试下一位女士 freeMen.push(m); } } } return wifeOfMan; } // 验证匹配的稳定性 bool isStable(const vector<int>& match) const { // match[man] = woman // 首先，检查是否是一个完美匹配（每个人都有一个伴侣） vector<int> reverseMatch(n, -1); for (int m = 0; m < n; ++m) { int w = match[m]; if (w < 0 || w >= n) return false; // 无效匹配 if (reverseMatch[w] != -1) return false; // 一位女士匹配了多位男士 reverseMatch[w] = m; } // 检查所有可能的男女对(m, w)，看是否存在不稳定对 for (int m = 0; m < n; ++m) { int mWife = match[m]; for (int w = 0; w < n; ++w) { int wHusband = reverseMatch[w]; // 如果m比起自己的妻子更喜欢w bool mPrefersW = false; for (int prefWoman : menPref[m]) { if (prefWoman == w) { mPrefersW = true; break; } if (prefWoman == mWife) break; // 先遇到妻子，说明更喜欢妻子 } // 如果w比起自己的丈夫更喜欢m bool wPrefersM = false; for (int prefMan : womenPref[w]) { if (prefMan == m) { wPrefersM = true; break; } if (prefMan == wHusband) break; } // 如果双方都更偏好对方，则是不稳定对 if (mPrefersW && wPrefersM) { cout << "发现不稳定对: 男士" << m << " 和 女士" << w << endl; cout << " 男士" << m << " 的妻子是 女士" << mWife << endl; cout << " 女士" << w << " 的丈夫是 男士" << wHusband << endl; return false; } } } return true; } // 打印匹配结果 static void printMatch(const vector<int>& match) { cout << "稳定匹配结果 (男士 -> 女士):" << endl; for (int m = 0; m < match.size(); ++m) { cout << " 男士 " << m << " 匹配 女士 " << match[m] << endl; } } }; int main() { // 示例输入：3位男士，3位女士 // 偏好列表：每个列表按偏好降序排列。例如menPref[0] = {1, 0, 2} 表示男士0最喜欢女士1，其次是女士0，最后是女士2。 vector<vector<int>> menPref = { {1, 0, 2}, // 男士0的偏好 {2, 1, 0}, // 男士1的偏好 {0, 1, 2} // 男士2的偏好 }; vector<vector<int>> womenPref = { {2, 0, 1}, // 女士0的偏好 {0, 1, 2}, // 女士1的偏好 {1, 2, 0} // 女士2的偏好 }; StableMarriage sm(menPref, womenPref); vector<int> match = sm.solve(); cout << "=== Gale-Shapley 算法求解稳定婚姻问题 ===" << endl; StableMarriage::printMatch(match); if (sm.isStable(match)) { cout << "验证通过：该匹配是稳定的。" << endl; } else { cout << "验证失败：该匹配不稳定！" << endl; } // 另一个测试用例：经典对称案例 cout << "\n=== 测试用例2：对称偏好 ===" << endl; vector<vector<int>> menPref2 = { {0, 1, 2}, {0, 1, 2}, {0, 1, 2} }; vector<vector<int>> womenPref2 = { {0, 1, 2}, {0, 1, 2}, {0, 1, 2} }; StableMarriage sm2(menPref2, womenPref2); vector<int> match2 = sm2.solve(); StableMarriage::printMatch(match2); cout << "稳定性验证: " << (sm2.isStable(match2) ? "通过" : "失败") << endl; return 0; }

4.2 代码解析与运行结果

代码结构解析：

buildWomenRankMatrix: 在构造函数中调用，一次性构建女士排名矩阵，将后续每次比较的成本降至O(1)。
solve: 算法的核心循环。使用queue管理自由男士，确保“任选一位自由男士”的操作是O(1)。注意求婚被拒后重新入队的逻辑。
isStable: 一个朴素的稳定性验证函数，通过双重循环检查所有可能的男女对。时间复杂度O(n³)，仅用于小规模测试和调试。在生产环境中，对于大规模n，这个验证函数会成为瓶颈，但算法本身的正确性保证了结果稳定，通常不需要调用。
printMatch: 一个简单的输出工具函数。

运行结果分析：对于第一个测试用例，程序输出可能如下：

=== Gale-Shapley 算法求解稳定婚姻问题 === 稳定匹配结果 (男士 -> 女士): 男士 0 匹配 女士 1 男士 1 匹配 女士 2 男士 2 匹配 女士 0 验证通过：该匹配是稳定的。

你可以手动验证一下这个结果：检查是否存在一对男女，他们彼此更喜欢对方胜过自己的现任。例如，男士0匹配了女士1（他的第一选择）。女士1匹配了男士0（她的第二选择，她的第一选择是男士0？这里需要看女士1的偏好列表{0,1,2}，她最喜欢男士0，但男士0没有选她？等等，这里输出显示男士0匹配了女士1。让我们检查：女士1的丈夫是男士0，这正是她的第一选择，所以她非常满意。男士0也得到了他的第一选择（女士1）。因此这对是稳定的。继续检查其他组合，会发现没有不稳定对。

对于对称偏好测试用例，所有男士和女士的偏好顺序都一样。结果将是“男士i匹配女士i”，因为每位男士都首先向最喜欢的女士（女士0）求婚，但只有一位男士（排名最靠前的）能成功，其他人被拒后依次向下选择，最终形成一种“按主动方偏好排序”的匹配。这是Gale-Shapley算法的一个重要性质：它总是返回男士最优（man-optimal）或女士最劣（woman-pessimal）的稳定匹配。即，在所有可能的稳定匹配中，每个男士得到的伴侣，都是他可能得到的最好的那一位（在所有稳定匹配中比较）；反之，每位女士得到的是她可能得到的最差的那一位。

5. 算法变体、优化与常见问题

基础的Gale-Shapley算法已经实现，但在实际应用中，我们可能会遇到各种变体和需要优化的场景。

5.1 处理不等数量与不完全列表

经典问题假设男女数量相等且偏好列表完整。现实情况可能更复杂：

数量不等：比如求职者多于职位。我们可以引入“虚拟”个体来补齐数量，或者修改算法终止条件（当一方没有更多可接受的提案时停止）。更常见的做法是允许一方有人未匹配，并定义这些“单身”状态也是稳定的（因为没有他/她更喜欢的、且也喜欢他/她的可用对象）。
不完全偏好列表：个人可能只对部分对方成员有偏好，甚至拒绝与某些人匹配。这需要在数据结构中处理“不可接受”的情况。在算法中，当男士的求婚指针指向一个他认为不可接受的女士，或向一个认为他不可接受的女士求婚时，应直接跳过或拒绝。

实现上，可以用一个特殊值（如-1）或一个布尔矩阵acceptable来标记可接受关系。在求婚和比较环节，都需要先检查可接受性。

5.2 性能优化与大规模数据处理

当n非常大（例如10万）时，O(n²)的空间复杂度（存储所有偏好）可能成为瓶颈。

稀疏偏好：如果每个人只对少数对象有偏好，可以使用邻接表（如vector<list<int>>）存储偏好列表，并用unordered_map存储排名，节省空间。
流式处理/外部存储：如果偏好列表太大无法全部装入内存，需要设计外部排序和磁盘I/O友好的算法变体，这通常超出了经典Gale-Shapley的范畴，需要更复杂的分布式或近似算法。

对于时间复杂度O(n²)，在n=1e5时，循环次数是1e10，在普通机器上可能过慢。此时需要考虑：

并行化：算法的每次求婚在某种程度上是独立的。可以尝试让多位自由男士同时求婚，但需要处理对女士状态的并发访问锁，可能带来额外开销。
启发式或近似算法：对于超大规模问题，有时可以接受近似稳定解，以换取运行时间的大幅降低。

5.3 常见陷阱与调试技巧

下标错误：这是C++算法题中最常见的问题。务必清楚你的数据结构的维度（n）和索引范围（0到n-1）。在访问menPref[m][i]或womenRank[w][m]前，确保m,w,i在有效范围内。
忘记重新入队：如前所述，求婚被拒的男士必须放回freeMen队列，否则算法会漏掉部分男士，导致匹配不全。
排名矩阵构建错误：womenRank[w][m]存储的是女士w给男士m的排名（0最好）。确保在构建时，循环变量rankcorrectly corresponds to the position inwomenPref[w]。
输入验证：生产代码应增加对输入有效性的检查，例如检查每个偏好列表是否包含0到n-1的所有数字（或所有可接受对象的ID），是否有重复等。
验证函数的性能：自带的isStable函数是O(n³)，仅用于小规模测试。不要用它来验证大规模结果。
多解问题：稳定匹配可能不唯一。Gale-Shapley算法（男士主动版）只找到其中一种（男士最优解）。如果你的算法结果与参考解不同，不一定代表错误，只要你的匹配是稳定的即可。可以用isStable函数验证。