Gale Shapley匹配算法第三次迭代陷入循环问题排查求助

问题描述 #

运行以下Gale-Shapley匹配算法代码时，前两次迭代正常，但第三次迭代系统陷入循环无法结束。

原始代码 #

导入库 #

import networkx as nx
import matplotlib.pyplot as plt

偏好列表示例（3男3女） #

men_prefs = {
    'm1': ['w2', 'w1', 'w3'],
    'm2': ['w1', 'w2', 'w3'],
    'm3': ['w1', 'w3', 'w2']
}
women_prefs = {
    'w1': ['m3', 'm1', 'm2'],
    'w2': ['m2', 'm1', 'm3'],
    'w3': ['m1', 'm3', 'm2']
}

创建二分图 #

B = nx.Graph()
B.add_nodes_from(men_prefs.keys(), bipartite=0)
B.add_nodes_from(women_prefs.keys(), bipartite=1)
for man, prefs in men_prefs.items():
    for woman in prefs:
        B.add_edge(man, woman)

运行Gale-Shapley算法（存在死循环问题） #

free_men = set(men_prefs.keys())
engaged = {}
while free_men:
    man = free_men.pop()
    woman = men_prefs[man][0]
    if woman in engaged:
        current_man = engaged[woman]
        if women_prefs[woman].index(man) < women_prefs[woman].index(current_man):
            engaged[woman] = man
            free_men.add(current_man)
        else:
            free_men.add(man)
    else:
        engaged[woman] = man

绘制匹配图 #

pos = nx.bipartite_layout(B, men_prefs.keys())
plt.figure(figsize=(6, 4))
nx.draw_networkx_nodes(B, pos, node_color=['lightblue'])
nx.draw_networkx_edges(B, pos, edgelist=engaged.items(), edge_color='red', width=2)
nx.draw_networkx_labels(B, pos, font_size=12, font_family='sans-serif')
plt.axis('off')
plt.show()

问题定位 #

死循环的核心原因是：没有记录男性已向哪些女性求过婚。每次男性回到自由状态后，都会重新向自己偏好列表的第一个女性求婚，而非下一个未求婚的女性。例如：

• m1首次向w2求婚并订婚
• 之后m2向w2求婚，由于w2更喜欢m2，m1被踢回自由男集合
• m1再次弹出后，又会重复向w2求婚，陷入“求婚-被拒-回到自由-再求婚”的无限循环

修复方案 #

为每个男性维护一个当前求婚索引，记录他已经求到偏好列表的第几个女性。每次被拒绝后，索引递增，下次向下一个偏好的女性求婚，避免重复求婚。

修正后的Gale-Shapley算法代码 #

free_men = set(men_prefs.keys())
engaged = {}
# 记录每个男性当前的求婚位置索引，初始为0（第一个偏好）
current_proposal_idx = {man: 0 for man in men_prefs}

while free_men:
    man = free_men.pop()
    # 获取当前男性还未求婚的下一个女性
    if current_proposal_idx[man] < len(men_prefs[man]):
        woman = men_prefs[man][current_proposal_idx[man]]
        current_proposal_idx[man] += 1  # 无论结果如何，该女性已被求婚过，索引后移
        if woman in engaged:
            current_man = engaged[woman]
            # 比较当前男性和已订婚男性在女性偏好中的排名
            if women_prefs[woman].index(man) < women_prefs[woman].index(current_man):
                # 女性选择新男性，原男性回到自由集合
                engaged[woman] = man
                free_men.add(current_man)
            else:
                # 女性拒绝新男性，新男性回到自由集合
                free_men.add(man)
        else:
            # 女性未订婚，直接订婚
            engaged[woman] = man

验证结果 #

修正后的代码会正常完成匹配，最终的稳定匹配结果为：

• w1: m3
• w2: m2
• w3: m1

绘制的匹配图也会正确显示这三组红色匹配边，无循环问题。

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