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 输入表示偏好列表的存储最直观的输入可能是两个二维向量vectorvectorint menPref和vectorvectorint womenPref。menPref[i]是第i位男士的偏好列表按喜好程度降序存储女士编号。但这样存在一个问题当女士w需要比较男士m和当前未婚夫m’时她需要在自己的偏好列表womenPref[w]中线性查找m和m’的位置以比较优先级这是一个O(n)操作会使总复杂度升至O(n³)。优化策略我们引入“反向索引”或“排名矩阵”。除了存储偏好列表我们额外用一个二维数组vectorvectorint 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。自由男士列表我们需要高效地选取一位自由男士。使用一个队列queueint freeMen是最自然的选择。初始时将所有男士入队。3.3 C类设计我们将设计一个StableMarriage类封装数据和方法使接口清晰易于复用。#include iostream #include vector #include queue using namespace std; class StableMarriage { private: int n; // 男女人数假定相等 vectorvectorint menPref; // 男士偏好列表 menPref[man][rank] woman vectorvectorint womenPref; // 女士偏好列表 womenPref[woman][rank] man vectorvectorint womenRank; // 女士排名矩阵 womenRank[woman][man] rank // 算法执行过程中的状态 vectorint wifeOfMan; // wifeOfMan[man] woman 或 -1 vectorint husbandOfWoman; // husbandOfWoman[woman] man 或 -1 vectorint nextProposalIdx; // nextProposalIdx[man]指向menPref中下一个要求婚的女士索引 queueint freeMen; // 当前自由的男士队列 public: // 构造函数初始化偏好列表并构建 womenRank StableMarriage(const vectorvectorint mp, const vectorvectorint wp); // 核心算法Gale-Shapley返回匹配结果wifeOfMan vectorint solve(); // 工具函数检查给定的匹配是否是稳定的 bool isStable(const vectorint match) const; private: // 初始化 womenRank 矩阵 void buildWomenRankMatrix(); };3.4 关键实现细节与陷阱构建排名矩阵buildWomenRankMatrix 这是实现高效比较的关键。不能简单地用find函数在womenPref[w]中查找那仍是O(n)。我们需要利用数组索引直接映射。void StableMarriage::buildWomenRankMatrix() { womenRank.resize(n, vectorint(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的实现vectorint 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; // 人数 vectorvectorint menPref; vectorvectorint womenPref; vectorvectorint womenRank; // womenRank[woman][man] preference rank (0 is most preferred) // 构建反向索引实现O(1)的比较 void buildWomenRankMatrix() { womenRank.resize(n, vectorint(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 vectorvectorint mp, const vectorvectorint wp) : menPref(mp), womenPref(wp) { assert(mp.size() wp.size()); n mp.size(); // 可选这里可以添加输入有效性检查例如每个列表是否包含0到n-1的所有数字 buildWomenRankMatrix(); } // 执行Gale-Shapley算法男士主动版 vectorint solve() { // wifeOfMan[man] woman he is engaged to, -1 if free // husbandOfWoman[woman] man she is engaged to, -1 if free vectorint wifeOfMan(n, -1), husbandOfWoman(n, -1); // nextProposalIdx[man] index of next woman in his preference list to propose to vectorint nextProposalIdx(n, 0); queueint 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 vectorint match) const { // match[man] woman // 首先检查是否是一个完美匹配每个人都有一个伴侣 vectorint 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 vectorint 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。 vectorvectorint menPref { {1, 0, 2}, // 男士0的偏好 {2, 1, 0}, // 男士1的偏好 {0, 1, 2} // 男士2的偏好 }; vectorvectorint womenPref { {2, 0, 1}, // 女士0的偏好 {0, 1, 2}, // 女士1的偏好 {1, 2, 0} // 女士2的偏好 }; StableMarriage sm(menPref, womenPref); vectorint match sm.solve(); cout Gale-Shapley 算法求解稳定婚姻问题 endl; StableMarriage::printMatch(match); if (sm.isStable(match)) { cout 验证通过该匹配是稳定的。 endl; } else { cout 验证失败该匹配不稳定 endl; } // 另一个测试用例经典对称案例 cout \n 测试用例2对称偏好 endl; vectorvectorint menPref2 { {0, 1, 2}, {0, 1, 2}, {0, 1, 2} }; vectorvectorint womenPref2 { {0, 1, 2}, {0, 1, 2}, {0, 1, 2} }; StableMarriage sm2(menPref2, womenPref2); vectorint 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²)的空间复杂度存储所有偏好可能成为瓶颈。稀疏偏好如果每个人只对少数对象有偏好可以使用邻接表如vectorlistint存储偏好列表并用unordered_map存储排名节省空间。流式处理/外部存储如果偏好列表太大无法全部装入内存需要设计外部排序和磁盘I/O友好的算法变体这通常超出了经典Gale-Shapley的范畴需要更复杂的分布式或近似算法。对于时间复杂度O(n²)在n1e5时循环次数是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函数验证。5.4 扩展应用场景理解了稳定婚姻问题你就掌握了一类“双边匹配”问题的核心解法。它的变体应用极其广泛全国住院医生匹配计划这是最著名的现实应用。医学院毕业生学生和医院职位互相提交偏好列表通过一个改进的算法考虑医院可以有多个职位进行匹配。学校招生学生选择学校学校选择学生。任务分配将任务分配给工人双方各有偏好如工人对任务的擅长程度任务对工人技能的要求。无线网络中的资源分配用户设备与基站/信道的匹配。广告拍卖广告主与广告位的匹配。在这些应用中偏好可能不是严格的排序而是由分数、权重决定并且可能涉及容量一方可以匹配多个对方。这就需要修改算法但其核心思想——通过一系列“提议”和“有条件接受”来达到稳定状态——依然适用。实现这个算法的过程是一次对贪心策略、循环不变量、算法正确性证明以及高效数据结构设计的综合训练。它提醒我们许多现实世界的复杂问题背后往往隐藏着优美而高效的数学解。