稳定婚姻问题算法关键代码分析

稳定婚姻问题是图匹配理论中的一个经典问题，它模拟了人们在婚姻市场上的匹配过程。其中关键的算法是“吉尔莫尔-斯坦利”（Gale-Shapley）算法，也称为“男子追求女子”的算法。以下是核心代码分析：

# 假设我们有两个列表，男生列表men和女生列表women，分别表示单身男性和女性
men = ['A', 'B', 'C'] # 男人列表
women = ['X', 'Y', 'Z'] # 女人列表

class Man:
    def __init__(self, name):
        self.name = name
        self.pref_women = {}  # 喜欢的女人列表，按顺序排列

# 吉尔莫尔-斯坦利算法
def gale_shapley(men, women):
    for man in men:
        man.pref_women = sorted(women, key=lambda w: -man.rank[w])  # 设置偏好顺序
        woman = Woman(man.name)
        while woman not in man.pref_women:
            current_partner = woman.current_partner
            if current_partner is None or man.rank[current_partner] < man.rank[woman]:
                man.propose(woman)  # 提议
            woman.accept_or_ignore(man)  # 女方接受或无视
    return marry_result(men, women)

# 结果存储函数
def marry_result(men, women):
    married_pairs = []
    for man in men:
        woman = man.woman
        if woman is not None:
            married_pairs.append((man.name, woman.name))
    return married_pairs

# 男人求婚和女人选择操作
class Woman:
    def __init__(self, name):
        self.name = name
        self.current_partner = None

    def accept_or_ignore(self, man):
        if self.current_partner is None or man.rank[self.name] > man.rank[self.current_partner]:
            self.current_partner = man.name
            man.accept(self)

# 初始化男人的排名，这里假设是最喜欢的女人的排名
for man in men:
    man.rank = {w: i for i, w in enumerate(men, start=1)}

gale_shapley_result = gale_shapley(men, women)
print("稳定配对结果：", gale_shapley_result)