稳定婚姻问题详解 | Baeldung中文网

1. 问题概述

稳定婚姻问题（Stable Marriage Problem）的核心目标是：在两组各有 n 个成员（通常称为“男性”和“女性”）之间，建立一个稳定的配对关系。

每位男性对所有女性有一个偏好排序；
每位女性对所有男性也有一个偏好排序；
不存在“不稳定对”（blocking pair）——即不存在一对男女，他们彼此都更偏好对方而不是当前的配对对象。

稳定匹配的意义在于：一旦形成匹配，没有人能通过私下换配获得更好的结果。

2. 问题定义

我们定义：

男性集合为 Y = {m1, m2, ..., mn}
女性集合为 X = {w1, w2, ..., wn}
每位男性和女性都对异性有明确的偏好排序（无并列）

稳定匹配定义：
如果不存在这样的配对 (m, w)，使得：

m 更喜欢 w 而不是当前的配对对象；
w 也更喜欢 m 而不是当前的配对对象；

则称当前匹配是稳定的。

3. 示例说明

假设我们有以下三男三女：

男性偏好表

男性	第一选择	第二选择	第三选择
John	Bethany	Anna	Rose
Smith	Bethany	Rose	Anna
Tony	Rose	Bethany	Anna

女性偏好表

女性	第一选择	第二选择	第三选择
Anna	Smith	Tony	John
Bethany	Tony	John	Smith
Rose	Smith	Tony	John

3.1 婚姻配对与不稳定性

假设当前匹配为：

M = {(John, Anna), (Smith, Bethany), (Tony, Rose)}

John 更喜欢 Bethany；
Bethany 更喜欢 John；
所以 (John, Bethany) 是一个 blocking pair；
当前匹配 不稳定。

4. Gale-Shapley 算法

解决稳定婚姻问题的经典算法是 Gale-Shapley 算法，由 David Gale 和 Lloyd Shapley 提出。

算法步骤（伪代码）

algorithm StableMarriageAlgorithm(Y, X, n, preferenceLists):
    Free_Men <- Y
    Free_Women <- X
    M <- empty set

    while Free_Men is not empty:
        m <- select a free man
        w <- highest-preference woman on m's list he hasn't proposed to

        if w is free:
            M <- M + (m, w)
            remove m and w from Free_Men and Free_Women
        else:
            m_current <- current match of w
            if w prefers m over m_current:
                M <- M - (m_current, w) + (m, w)
                add m_current to Free_Men
                remove m from Free_Men

    return M

算法特点

男性主动提出，女性被动接受或拒绝；
每个男性只能向每个女性提出一次；
女性保留当前最偏好的男性；
最终匹配一定是稳定的。

5. 示例运行过程

我们以之前的三男三女为例逐步运行算法。

初始状态

所有男女都未匹配：

Free Men: John, Smith, Tony
Free Women: Anna, Bethany, Rose

迭代过程

John 提出 Bethany → Bethany 接受
M = {(John, Bethany)}
Smith 提出 Bethany → Bethany 拒绝 Smith（更喜欢 John）
Smith 提出 Rose → Rose 接受
M = {(John, Bethany), (Smith, Rose)}
Tony 提出 Rose → Rose 拒绝 Tony（更喜欢 Smith）
Tony 提出 Bethany → Bethany 接受 Tony（更喜欢他）
M = {(Tony, Bethany), (Smith, Rose)}
John 提出 Anna → Anna 接受
M = {(Tony, Bethany), (Smith, Rose), (John, Anna)}

最终匹配

M = {(Tony, Bethany), (Smith, Rose), (John, Anna)}

✅ 无 blocking pair，匹配稳定。

6. 理论分析

6.1 算法终止性

每个男性最多提出 n 次；
共 n 个男性 → 最多 n² 次提出；
每次提出后，男性不再重复；
所以算法一定在 O(n²) 步内终止。

6.2 稳定性证明（反证法）

假设最终匹配不稳定，存在一对 (m, w)，他们彼此更偏好对方。

由于 m 会从最偏好到最不偏好依次提出；
如果 m 最终没和 w 匹配，说明 w 拒绝了他；
拒绝说明 w 当前匹配的男性更受她青睐；
所以 (m, w) 不可能同时更偏好彼此 → 矛盾；
所以最终匹配一定是稳定的。

7. 时间与空间复杂度

项目	复杂度	说明
时间复杂度	`O(n²)`	每人最多提出 `n` 次，共 `n` 人
空间复杂度	`O(n²)`	保存偏好列表

⚠️ 注意：假设女性能在 O(1) 时间内比较两个男性。

8. 实际应用场景

医疗住院医生分配

医院和医生分别提交偏好；
使用 Gale-Shapley 算法进行匹配；
保证匹配稳定，医生不会跳槽，医院不会反悔。

高校招生匹配

学生填报志愿；
学校根据成绩和偏好录取；
可防止学生“策略性填报”；
印度、美国等国家采用此机制。

9. 总结

稳定婚姻问题是一个经典的组合优化问题；
Gale-Shapley 算法能以 O(n²) 时间找到稳定匹配；
该算法保证匹配稳定、无 blocking pair；
应用广泛，如医生分配、高校录取等；
✅ 适合有经验的开发者理解与实现。

Persistence

REST

Security