Python实现Gale-Shapley算法出现不稳定匹配问题求助

问题回顾 #

为个人项目需求，我在Python中实现了Gale-Shapley算法，代码如下：

def gale_shapley(men_prefs, women_prefs):
    free_men = list(men_prefs.keys())
    relationships = {}
    while free_men:
        print(free_men, relationships)
        man = free_men.pop(0)
        prefs = men_prefs[man]
        for woman in prefs:
            current_women_prefs = women_prefs[woman]
            spouse = relationships.get(woman)  # relationships[women] but none if none found
            if not spouse:
                # If woman isn't in a relationship, get her into one !
                relationships[woman] = man
                break

            elif current_women_prefs.index(spouse) > current_women_prefs.index(man):
                # if the man is prefered to the current spouse of the woman, we divorce and remarry
                relationships[woman] = man
                free_men.append(spouse)
                break

    return relationships

我认为该实现会产生不稳定匹配，以下是一个失败案例：

print(gale_shapley({'A': ['4', '1', '3', '2'], 
                    'B': ['1', '3', '4', '2'],
                    'C': ['2', '1', '3', '4'],
                    'D': ['1', '3', '4', '2']},
                   {'1': ['B', 'A', 'D', 'C'],
                    '2': ['A', 'C', 'D', 'B'],
                    '3': ['B', 'D', 'C', 'A'],
                    '4': ['D', 'C', 'B', 'A']}))

# 输出结果: {'4': 'A', '1': 'B', '2': 'C', '3': 'D'}
# 我认为D与3、B与1存在交换意愿，属于不稳定匹配

问题分析 #

你对不稳定匹配的理解存在偏差：不稳定对的核心是一对男女双方都更偏好对方，胜过自己当前的配偶，单方面的偏好不构成不稳定对。

针对你的案例逐一验证：

• B的偏好列表中，1是第一选择，当前配偶就是1，因此B完全没有更换伴侣的意愿；
• 3的偏好里B是第一选择，但B的偏好中1的优先级高于3，B不会放弃当前配偶1去选择3；
• 其他配对中，不存在任何一对男女，彼此都更偏好对方胜过当前配偶。

因此，你的代码输出的结果是合法的稳定匹配，符合Gale-Shapley算法（男性主动求婚模式）的预期——这是一个男性最优、女性最劣的稳定匹配。

代码潜在优化点 #

你的代码逻辑本身是正确的，但为了可读性和效率，可以做如下优化：

def gale_shapley(men_prefs, women_prefs):
    free_men = list(men_prefs.keys())
    relationships = {}
    # 预处理女性偏好为排名字典，避免重复调用index提升效率
    women_rankings = {w: {man: idx for idx, man in enumerate(prefs)} for w, prefs in women_prefs.items()}
    
    while free_men:
        man = free_men.pop(0)
        prefs = men_prefs[man]
        for woman in prefs:
            spouse = relationships.get(woman)
            if not spouse:
                relationships[woman] = man
                break
            # 用预处理的排名字典替代index，更高效
            elif women_rankings[woman][man] < women_rankings[woman][spouse]:
                relationships[woman] = man
                free_men.append(spouse)
                break
            # 女性拒绝当前男性，继续向下一位求婚
            else:
                continue
    return relationships

优化点说明：

1. 预处理女性偏好为排名字典，将每次index()的O(n)时间复杂度降为O(1)，提升算法整体效率；
2. 显式添加else分支处理拒绝场景，代码逻辑更清晰可读。

内容的提问来源于stack exchange，提问作者Nolann Boyere