稳定婚姻算法详解（Python实现Gale-Shapley算法解决婚配问题）

算法核心思想

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

1. 所有男士最初都是自由的；
2. 每位自由男士向他尚未求婚、且排名最高的女士求婚；
3. 每位女士如果收到多个求婚，会选择她最偏好的那位（根据她的偏好列表），暂时接受，拒绝其他人；
4. 被拒绝的男士变为自由状态，继续向下一个心仪对象求婚；
5. 重复直到所有男士都配对成功。

Python 实现稳定匹配

下面我们用 Python 编写一个完整的 稳定婚姻算法 实现。代码结构清晰，适合初学者理解。

def stable_marriage(men_prefs, women_prefs):    """    实现 Gale-Shapley 稳定婚姻算法    :param men_prefs: 男士偏好字典，如 {'m1': ['w1', 'w2', 'w3'], ...}    :param women_prefs: 女士偏好字典，如 {'w1': ['m2', 'm1', 'm3'], ...}    :return: 配对结果字典，如 {'m1': 'w2', 'm2': 'w1', ...}    """    from collections import deque    # 初始化：所有男士自由，使用队列管理求婚顺序    free_men = deque(men_prefs.keys())        # 记录每位男士当前求婚到第几位（索引）    man_proposal_index = {man: 0 for man in men_prefs}        # 女士当前的配对对象    wife_of = {}        # 为每位女士建立偏好排名映射（便于快速比较）    woman_rank = {}    for woman, prefs in women_prefs.items():        woman_rank[woman] = {man: idx for idx, man in enumerate(prefs)}        while free_men:        man = free_men.popleft()        # 获取该男士的偏好列表        his_prefs = men_prefs[man]                # 找到下一个未求婚的女士        if man_proposal_index[man] >= len(his_prefs):            continue  # 理论上不会发生，因为人数相等                    woman = his_prefs[man_proposal_index[man]]        man_proposal_index[man] += 1                if woman not in wife_of:            # 女士当前单身，直接配对            wife_of[woman] = man        else:            current_man = wife_of[woman]            # 比较当前配对和新追求者            if woman_rank[woman][man] < woman_rank[woman][current_man]:                # 女士更喜欢新追求者                wife_of[woman] = man                free_men.append(current_man)  # 被甩的男士重新进入自由队列            else:                # 女士拒绝，男士继续求婚                free_men.append(man)        # 构建最终结果：男士 -> 女士    husband_of = {man: woman for woman, man in wife_of.items()}    return husband_of# 示例数据men_preferences = {    'm1': ['w1', 'w2', 'w3'],    'm2': ['w2', 'w1', 'w3'],    'm3': ['w1', 'w2', 'w3']}women_preferences = {    'w1': ['m2', 'm1', 'm3'],    'w2': ['m1', 'm2', 'm3'],    'w3': ['m1', 'm2', 'm3']}result = stable_marriage(men_preferences, women_preferences)print("稳定匹配结果：", result)

运行结果解释

以上代码输出可能为：

稳定匹配结果： {'m1': 'w2', 'm2': 'w1', 'm3': 'w3'}

你可以验证：不存在一对男女（比如 m1 和 w1）同时更喜欢对方而非当前伴侣，因此这是一个稳定匹配。

应用场景

虽然名为“婚姻算法”，但 婚配问题编程 广泛应用于：

• 医学院学生与实习医院的分配（NRMP系统）；
• 学校招生与学生志愿匹配；
• 任务调度与资源分配。

总结

通过本教程，我们学习了 稳定婚姻算法 的原理，并用 Python实现稳定匹配。Gale-Shapley算法不仅理论优美，而且实用性强。无论你是算法初学者还是想解决实际配对问题，掌握这一经典算法都非常有价值。

希望这篇教程对你有帮助！如果你有任何问题，欢迎在评论区留言交流。