稳定婚姻问题详解（C语言实现延迟接受算法）

什么是“稳定”？

假设我们有 n 位男士和 n 位女士。每位男士对所有女士有一个偏好排序，每位女士也对所有男士有偏好排序。一个配对方案是稳定的，当且仅当不存在一对男女（m, w），他们不是彼此的当前伴侣，但都更喜欢对方胜过当前伴侣。这样的配对称为“不稳定对”，而我们的目标就是避免这种情况。

算法核心思想

Gale-Shapley 算法采用“求婚-拒绝”机制：

• 所有男士初始时都是自由的。
• 每位自由的男士向他尚未求婚且最偏好的女士求婚。
• 每位女士收到多个求婚时，会选择她最偏好的那位（根据她的偏好列表），暂时接受；其余拒绝。
• 被拒绝的男士继续向下一个偏好的女士求婚。
• 重复此过程，直到所有男士都配对成功。

该算法保证在有限步内结束，并且结果是男士最优、女士最劣的稳定匹配（即每位男士在所有可能的稳定匹配中获得最好的可能伴侣）。

C语言实现步骤

下面我们用 C语言实现这个算法。我们将使用以下数据结构：

• menPref：男士偏好矩阵（menPref[i][j] 表示第 i 位男士第 j 喜欢的女士）
• womenPref：女士偏好矩阵（womenPref[i][j] 表示第 i 位女士第 j 喜欢的男士）
• womenRank：为加速查找，将女士偏好转换为排名（womenRank[w][m] 表示女士 w 对男士 m 的偏好排名，越小越喜欢）
• nextProposal：记录每位男士下一次要向谁求婚（索引）
• currentPartner：记录每位女士当前的临时伴侣
• freeMen：用队列管理当前自由的男士

完整代码实现

#include <stdio.h>#include <stdlib.h>#define MAX 100int main() {    int n;    printf("请输入人数 n: ");    scanf("%d", &n);    int menPref[MAX][MAX];    int womenPref[MAX][MAX];    int womenRank[MAX][MAX];    int nextProposal[MAX] = {0};    int currentPartner[MAX];    int freeMen[MAX];    int freeCount = n;    // 输入男士偏好    printf("\n输入 %d 位男士的偏好（每行 n 个数字，表示女士编号 0~%d）:\n", n, n - 1);    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            scanf("%d", &menPref[i][j]);        }    }    // 输入女士偏好    printf("\n输入 %d 位女士的偏好（每行 n 个数字，表示男士编号 0~%d）:\n", n, n - 1);    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            scanf("%d", &womenPref[i][j]);        }    }    // 构建女士的排名表：womenRank[w][m] = 男士 m 在女士 w 心中的排名（0 最喜欢）    for (int w = 0; w < n; w++) {        for (int rank = 0; rank < n; rank++) {            int man = womenPref[w][rank];            womenRank[w][man] = rank;        }    }    // 初始化所有女士无伴侣，用 -1 表示    for (int i = 0; i < n; i++) {        currentPartner[i] = -1;        freeMen[i] = i; // 所有男士初始自由    }    // 主循环：只要还有自由男士    while (freeCount > 0) {        int man = freeMen[freeCount - 1]; // 取出一个自由男士        freeCount--;        // 他向下一个未求婚的女士求婚        int woman = menPref[man][nextProposal[man]];        nextProposal[man]++;        if (currentPartner[woman] == -1) {            // 女士当前单身，接受求婚            currentPartner[woman] = man;        } else {            int currentMan = currentPartner[woman];            // 比较当前伴侣和新追求者            if (womenRank[woman][man] < womenRank[woman][currentMan]) {                // 女士更喜欢新追求者                currentPartner[woman] = man;                // 原伴侣变回自由                freeMen[freeCount] = currentMan;                freeCount++;            } else {                // 女士拒绝，男士继续自由                freeMen[freeCount] = man;                freeCount++;            }        }    }    // 输出结果    printf("\n稳定婚姻配对结果:\n");    for (int w = 0; w < n; w++) {        printf("男士 %d 与 女士 %d 配对\n", currentPartner[w], w);    }    return 0;}

运行示例

假设 n = 3，输入如下：

男士偏好：
0: 0 1 2
1: 1 0 2
2: 0 1 2

女士偏好：
0: 1 0 2
1: 0 1 2
2: 0 1 2

程序将输出稳定配对，例如：
男士 1 与 女士 0 配对
男士 0 与 女士 1 配对
男士 2 与 女士 2 配对

为什么这个算法重要？

稳定婚姻算法不仅是理论上的优美解法，更是现实世界配对算法的基础。例如美国的“国家住院医师匹配计划”（NRMP）就基于此算法改进而来。理解它有助于掌握算法设计中的贪心策略、稳定性概念以及实际应用价值。

总结

通过本教程，你已经学会了：

• 什么是稳定婚姻问题及其“稳定”定义
• Gale-Shapley 延迟接受算法的核心逻辑
• 如何用 C语言实现该算法
• 算法的实际应用场景

无论你是算法初学者还是准备面试的程序员，掌握稳定婚姻算法、C语言实现、延迟接受算法和配对算法这四个关键词所代表的知识，都将为你打下坚实基础。