排序算法之：基于“稳定婚姻问题”（Stable Marriage Problem）的Gale-Shapley算法在稳定匹配排序中的应用
字数 2478 2025-12-22 21:56:37

排序算法之：基于“稳定婚姻问题”（Stable Marriage Problem）的Gale-Shapley算法在稳定匹配排序中的应用

题目描述
我们考虑一个特殊的“排序”问题：将两组元素（例如，求职者与公司、学生与学校、男士与女士）按照他们的偏好列表进行稳定匹配，使得不存在“不稳定对”。这不是对单一数组的排序，而是根据双向偏好进行“配对排序”，确保结果的稳定性。经典的Gale-Shapley算法能解决此问题，并保证匹配的稳定性。请详细讲解该算法的步骤、正确性证明，并分析其时间复杂度和应用场景。

解题过程

1. 问题形式化定义
假设有两组数量相等的元素集合：

  • 男士集合 \(M = \{m_1, m_2, ..., m_n\}\)
  • 女士集合 \(W = \{w_1, w_2, ..., w_n\}\)
    每个男士对全部女士有一个严格的偏好排序列表（从最喜欢到最不喜欢），同样每位女士对全部男士也有严格的偏好列表。目标是找到一个完美匹配（一对一配对），使得不存在“不稳定对”。

不稳定对的定义：在匹配S中，如果存在一对\((m, w)\)，其中\(m\)与\(w\)当前没有配对，但\(m\)比起当前配偶更偏爱\(w\)，且\(w\)比起当前配偶更偏爱\(m\)，则\((m, w)\)称为不稳定对。

稳定匹配：匹配中不存在任何不稳定对。

2. Gale-Shapley算法步骤
算法也称为“延迟接受算法”（Deferred Acceptance），分为男士主动版（男士求婚）和女士主动版，这里以男士主动为例：

  • 初始化：所有男士和女士都标记为“自由”（未配对）。
  • 循环：当存在自由男士且该男士还有未求过婚的女士时，执行以下步骤：
    1. 任选一位自由男士 \(m\)。
    2. \(m\) 向他尚未求过婚的女士中，按偏好列表顺序选择最喜欢的女士 \(w\)。
    3. 如果 \(w\) 是自由的，则 \(m\) 和 \(w\) 暂时配对（订婚）。
    4. 如果 \(w\) 已与某男士 \(m'\) 配对，则 \(w\) 比较 \(m\) 和 \(m'\) 在她的偏好列表中的位置：
      • 如果 \(w\) 更偏爱 \(m\) 超过 \(m'\)，则 \(w\) 与 \(m'\) 解除配对（\(m'\) 变回自由），并与 \(m\) 配对。
      • 如果 \(w\) 更偏爱 \(m'\)，则 \(m\) 的求婚被拒绝，保持自由。
  • 终止：当所有男士都不自由（即所有男士都有配对）时结束，此时女士也必然全部配对。

3. 逐步示例
假设有两位男士 \(m_1, m_2\) 和两位女士 \(w_1, w_2\)，偏好如下：
男士偏好列表：
\(m_1: w_1 > w_2\)
\(m_2: w_1 > w_2\)
女士偏好列表：
\(w_1: m_2 > m_1\)
\(w_2: m_1 > m_2\)

算法执行过程：

  • 初始：全部自由。
  • 选 \(m_1\)，向 \(w_1\) 求婚，\(w_1\) 自由 → 配对 \((m_1, w_1)\)。
  • 选 \(m_2\)，向 \(w_1\) 求婚，\(w_1\) 已与 \(m_1\) 配对，但 \(w_1\) 更偏爱 \(m_2\) → \(w_1\) 与 \(m_1\) 分手，与 \(m_2\) 配对，\(m_1\) 变自由。
  • 选 \(m_1\)（自由），向下一偏好 \(w_2\) 求婚，\(w_2\) 自由 → 配对 \((m_1, w_2)\)。
  • 所有男士已配对，结束。
    最终匹配：\(\{(m_2, w_1), (m_1, w_2)\}\)，可验证无不稳定对。

4. 正确性证明要点

  • 终止性：每个男士最多向 \(n\) 位女士求婚，总求婚次数不超过 \(n^2\)，算法必然终止。
  • 完美匹配：结束时若有自由男士，他必向所有女士求过婚，但每次求婚若女士已配对，要么维持原配对要么换人，始终保证女士有配对，因此不存在自由男士与自由女士同时存在，结果必然完美匹配。
  • 稳定性（反证法）：假设存在不稳定对 \((m, w)\)，其中 \(m\) 与 \(w'\) 配对，\(w\) 与 \(m'\) 配对，且 \(m\) 更偏爱 \(w\) 超过 \(w'\)，\(w\) 更偏爱 \(m\) 超过 \(m'\)。那么在算法中，\(m\) 在向 \(w'\) 求婚前必先向 \(w\) 求过婚（因他按偏好顺序）。当 \(m\) 向 \(w\) 求婚时：
    • 若 \(w\) 当时自由，会接受 \(m\)，之后 \(w\) 只会换到更偏爱的男士，不可能最终与比 \(m\) 差的 \(m'\) 配对，矛盾。
    • 若 \(w\) 当时与某男士配对，那她当时选择的男士至少和她当前配偶 \(m'\) 一样好（因后续只会换到更偏爱的），而 \(m'\) 不如 \(m\) 被偏爱，矛盾。
      因此不稳定对不存在，匹配是稳定的。

5. 算法特性与复杂度

  • 时间复杂度：每个男士最多求婚 \(n\) 次，每次求婚需 O(1) 时间（用数组记录偏好排名），总 O(\(n^2\))。
  • 男士最优/女士最劣：男士主动版本得到的稳定匹配是“男士最优”（每个男士得到的配偶是所有稳定匹配中他可能得到的最偏爱的女士），同时也是“女士最劣”（每位女士得到的配偶是所有稳定匹配中她可能得到的最不偏爱的男士）。
  • 唯一性：稳定匹配可能不唯一，但男士主动版总得到同一匹配（男士最优解）。

6. 应用场景

  • 大学招生（学生与学校匹配）。
  • 医院实习分配（National Resident Matching Program）。
  • 网络中的资源分配与任务调度。
  • 任何涉及双向偏好排序的配对问题，可视为一种广义的“排序”任务。

总结：Gale-Shapley 算法通过简单的求婚-拒绝机制，高效解决了稳定匹配问题，其思想可用于多种资源分配场景，是排序与匹配理论中的经典算法。

排序算法之：基于“稳定婚姻问题”（Stable Marriage Problem）的Gale-Shapley算法在稳定匹配排序中的应用 题目描述 我们考虑一个特殊的“排序”问题：将两组元素（例如，求职者与公司、学生与学校、男士与女士）按照他们的偏好列表进行稳定匹配，使得不存在“不稳定对”。这不是对单一数组的排序，而是根据双向偏好进行“配对排序”，确保结果的稳定性。经典的Gale-Shapley算法能解决此问题，并保证匹配的稳定性。请详细讲解该算法的步骤、正确性证明，并分析其时间复杂度和应用场景。 解题过程 1. 问题形式化定义 假设有两组数量相等的元素集合： 男士集合 \( M = \{m_ 1, m_ 2, ..., m_ n\} \) 女士集合 \( W = \{w_ 1, w_ 2, ..., w_ n\} \) 每个男士对全部女士有一个严格的偏好排序列表（从最喜欢到最不喜欢），同样每位女士对全部男士也有严格的偏好列表。目标是找到一个完美匹配（一对一配对），使得不存在“不稳定对”。 不稳定对的定义 ：在匹配S中，如果存在一对\((m, w)\)，其中\(m\)与\(w\)当前没有配对，但\(m\)比起当前配偶更偏爱\(w\)，且\(w\)比起当前配偶更偏爱\(m\)，则\((m, w)\)称为不稳定对。 稳定匹配：匹配中不存在任何不稳定对。 2. Gale-Shapley算法步骤 算法也称为“延迟接受算法”（Deferred Acceptance），分为男士主动版（男士求婚）和女士主动版，这里以男士主动为例： 初始化 ：所有男士和女士都标记为“自由”（未配对）。 循环 ：当存在自由男士且该男士还有未求过婚的女士时，执行以下步骤： 任选一位自由男士 \(m\)。 \(m\) 向他尚未求过婚的女士中，按偏好列表顺序选择最喜欢的女士 \(w\)。 如果 \(w\) 是自由的，则 \(m\) 和 \(w\) 暂时配对（订婚）。 如果 \(w\) 已与某男士 \(m'\) 配对，则 \(w\) 比较 \(m\) 和 \(m'\) 在她的偏好列表中的位置： 如果 \(w\) 更偏爱 \(m\) 超过 \(m'\)，则 \(w\) 与 \(m'\) 解除配对（\(m'\) 变回自由），并与 \(m\) 配对。 如果 \(w\) 更偏爱 \(m'\)，则 \(m\) 的求婚被拒绝，保持自由。 终止 ：当所有男士都不自由（即所有男士都有配对）时结束，此时女士也必然全部配对。 3. 逐步示例 假设有两位男士 \(m_ 1, m_ 2\) 和两位女士 \(w_ 1, w_ 2\)，偏好如下： 男士偏好列表： \(m_ 1: w_ 1 > w_ 2\) \(m_ 2: w_ 1 > w_ 2\) 女士偏好列表： \(w_ 1: m_ 2 > m_ 1\) \(w_ 2: m_ 1 > m_ 2\) 算法执行过程： 初始：全部自由。 选 \(m_ 1\)，向 \(w_ 1\) 求婚，\(w_ 1\) 自由 → 配对 \((m_ 1, w_ 1)\)。 选 \(m_ 2\)，向 \(w_ 1\) 求婚，\(w_ 1\) 已与 \(m_ 1\) 配对，但 \(w_ 1\) 更偏爱 \(m_ 2\) → \(w_ 1\) 与 \(m_ 1\) 分手，与 \(m_ 2\) 配对，\(m_ 1\) 变自由。 选 \(m_ 1\)（自由），向下一偏好 \(w_ 2\) 求婚，\(w_ 2\) 自由 → 配对 \((m_ 1, w_ 2)\)。 所有男士已配对，结束。 最终匹配：\(\{(m_ 2, w_ 1), (m_ 1, w_ 2)\}\)，可验证无不稳定对。 4. 正确性证明要点 终止性 ：每个男士最多向 \(n\) 位女士求婚，总求婚次数不超过 \(n^2\)，算法必然终止。 完美匹配 ：结束时若有自由男士，他必向所有女士求过婚，但每次求婚若女士已配对，要么维持原配对要么换人，始终保证女士有配对，因此不存在自由男士与自由女士同时存在，结果必然完美匹配。 稳定性 （反证法）：假设存在不稳定对 \((m, w)\)，其中 \(m\) 与 \(w'\) 配对，\(w\) 与 \(m'\) 配对，且 \(m\) 更偏爱 \(w\) 超过 \(w'\)，\(w\) 更偏爱 \(m\) 超过 \(m'\)。那么在算法中，\(m\) 在向 \(w'\) 求婚前必先向 \(w\) 求过婚（因他按偏好顺序）。当 \(m\) 向 \(w\) 求婚时： 若 \(w\) 当时自由，会接受 \(m\)，之后 \(w\) 只会换到更偏爱的男士，不可能最终与比 \(m\) 差的 \(m'\) 配对，矛盾。 若 \(w\) 当时与某男士配对，那她当时选择的男士至少和她当前配偶 \(m'\) 一样好（因后续只会换到更偏爱的），而 \(m'\) 不如 \(m\) 被偏爱，矛盾。 因此不稳定对不存在，匹配是稳定的。 5. 算法特性与复杂度 时间复杂度 ：每个男士最多求婚 \(n\) 次，每次求婚需 O(1) 时间（用数组记录偏好排名），总 O(\(n^2\))。 男士最优/女士最劣 ：男士主动版本得到的稳定匹配是“男士最优”（每个男士得到的配偶是所有稳定匹配中他可能得到的最偏爱的女士），同时也是“女士最劣”（每位女士得到的配偶是所有稳定匹配中她可能得到的最不偏爱的男士）。 唯一性 ：稳定匹配可能不唯一，但男士主动版总得到同一匹配（男士最优解）。 6. 应用场景 大学招生（学生与学校匹配）。 医院实习分配（National Resident Matching Program）。 网络中的资源分配与任务调度。 任何涉及双向偏好排序的配对问题，可视为一种广义的“排序”任务。 总结 ：Gale-Shapley 算法通过简单的求婚-拒绝机制，高效解决了稳定匹配问题，其思想可用于多种资源分配场景，是排序与匹配理论中的经典算法。