稳定婚姻匹配问题
什么是稳定婚姻匹配问题
稳定婚姻问题（Stable Marriage Problem）是一个经典的算法问题，最早由 David Gale 和 Lloyd Shapley 在 1962 年提出。问题描述如下：
给定 N 个男性和 N 个女性，每个人都对所有异性有一个偏好排序列表。需要找到一种稳定的匹配方案，使得不存在这样的情况：男性 A 和女性 B 没有配对，但他们都更喜欢对方而不是各自当前的伴侣。如果存在这样的一对，就称之为"不稳定对"（blocking pair），整个匹配就是不稳定的。
Gale-Shapley 算法
Gale-Shapley 算法（又称延迟接受算法）的核心思想非常简单：
- 每一轮中，所有未匹配的男性向他们最喜欢的且还没被拒绝过的女性求婚；
- 每位女性在所有求婚者（包括当前伴侣）中选择她最喜欢的一个，暂时接受，拒绝其余的；
- 被拒绝的男性在下一轮继续向下一个偏好对象求婚；
- 重复以上过程，直到所有人都配对成功。
这个算法保证一定能找到一个稳定匹配，而且男方主动求婚的版本对男方是最优的。
Python 实现
# _*_ coding: utf-8 _*_
def stable_marriage(men_prefs, women_prefs):
"""
Gale-Shapley 稳定婚姻匹配算法
:param men_prefs: 男性偏好字典, 如 {'m1': ['w1', 'w2', 'w3'], ...}
:param women_prefs: 女性偏好字典, 如 {'w1': ['m1', 'm2', 'm3'], ...}
:return: 匹配结果字典, 如 {'m1': 'w1', 'm2': 'w2', ...}
"""
# 记录每个男性下一个要求婚的女性索引
men_next = {m: 0 for m in men_prefs}
# 当前未匹配的男性集合
free_men = list(men_prefs.keys())
# 当前匹配结果：女性 -> 男性
engaged = {}
# 预处理：将女性的偏好列表转换为排名字典，方便O(1)比较
women_rank = {}
for w, prefs in women_prefs.items():
women_rank[w] = {m: rank for rank, m in enumerate(prefs)}
# 主循环：只要还有未匹配的男性就继续
while free_men:
# 取出一个未匹配的男性
man = free_men[0]
# 获取他当前最想求婚的女性
woman = men_prefs[man][men_next[man]]
# 更新求婚索引
men_next[man] += 1
if woman not in engaged:
# 女性当前未配对，直接接受
engaged[woman] = man
free_men.pop(0)
else:
# 女性已经有伴侣，比较排名
current_man = engaged[woman]
if women_rank[woman][man] < women_rank[woman][current_man]:
# 新求婚者排名更高（数值更小），替换当前伴侣
engaged[woman] = man
free_men.pop(0)
free_men.append(current_man)
# 否则拒绝新求婚者，他继续留在未匹配列表中
# 返回男性视角的匹配结果
return {m: w for w, m in engaged.items()}
# 使用示例
if __name__ == '__main__':
# 3个男性和3个女性的偏好列表
men_prefs = {
'm1': ['w1', 'w2', 'w3'],
'm2': ['w2', 'w1', 'w3'],
'm3': ['w1', 'w3', 'w2'],
}
women_prefs = {
'w1': ['m2', 'm1', 'm3'],
'w2': ['m1', 'm3', 'm2'],
'w3': ['m3', 'm2', 'm1'],
}
result = stable_marriage(men_prefs, women_prefs)
for man, woman in sorted(result.items()):
print('{} <-> {}'.format(man, woman))
# 输出:
# m1 <-> w1
# m2 <-> w2
# m3 <-> w3
时间复杂度分析
- 最坏情况下，每个男性可能需要向所有 N 个女性求婚，共有 N 个男性，所以总的求婚次数最多为 N x N = N^2 次；
- 每次求婚操作中，女性比较排名是 O(1)（因为预处理了排名字典）；
- 因此整体时间复杂度为 O(N^2)，空间复杂度也是 O(N^2)（存储偏好列表和排名字典）。