丘比特之箭与数学匹配的魔法：婚姻配对问题

创作时间:

作者:

@小白创作中心

丘比特之箭与数学匹配的魔法：婚姻配对问题

引用

来源

https://www.cnblogs.com/ofnoname/p/18729619

在数学的世界里，爱情也可以用算法来诠释。Gale-Shapley算法，这个诞生于1962年的经典算法，不仅解决了婚姻配对问题，更揭示了稳定匹配背后的数学之美。让我们一起探索这个将爱情与数学完美结合的奇妙理论。

男女稳定婚姻问题

霓虹闪烁的都市里，婚介所的王阿姨正对着满墙的会员资料发愁。985硕士张先生执着于温柔贤惠的文科女生，创业女强人李小姐却将幽默感列为择偶第一要素。看似简单的牵线搭桥，实则暗藏玄机——若强行配对"条件相当"但偏好错位的两人，很可能上演现实版《前任攻略》：小王和小芳虽在婚介所登记结婚，私下却与彼此的真爱暗度陈仓。

这正是数学家Gale和Shapley在1962年精准捕捉的婚姻配对问题：当(n)位男士与(n)位女士各自手握一份心动排序表，如何设计一个"拆不散"的终极配对方案？这里的"拆不散"不是月老的红线，而是一种精妙的数学稳态——稳定匹配。

定义：稳定婚姻问题

设男士集合(M = {m_1, m_2, ..., m_n})，女士集合(F = {f_1, f_2, ..., f_n})，每个人心中都有一杆秤：

每位男士(m_i)对女士的偏好可表示为全序关系(>_{m_i})
每位女士(f_j)对男士的偏好同理为(>_{f_j})

一个匹配μ 是将男士与女士一一对应的双射。匹配的方案有很多种，但这个匹配要成为稳定匹配，必须消灭所有"私奔因子"——即不存在((m, f))使得：

(m)比起其现任(μ(m))，更爱(f)（即(f >_{m} μ(m))）
同时(f)比起其现任(μ(f))，更爱(m)（即(m >_{f} μ(f))）

这样的危险组合((m, f))被称为阻塞对(blocking pair)，就像婚恋市场里的不定时炸弹。他们更喜欢彼此，却都委屈的和不太喜欢的现任在一起。而我们的任务，就是构建一个让所有炸弹自动失效的匹配方案。

Gale-Shapley算法：相亲会

此刻，数学家们已经挥舞着算法之杖悄然降临。用递玫瑰的智慧破解爱情密码。想象所有男女来到相亲会配对。Gale和Shapley设计的算法，作为主持人，指挥着这场求偶仪式：

初始化：每位男士和女士都处于自由状态，手中空空如也。
求婚阶段：每位自由男士(m)按照自己的偏好列表，向尚未拒绝过他的最高位女士(f)献上玫瑰。
抉择时刻：每位女士(f)收到若干玫瑰后，暂时保留最心仪的那一支（即偏好列表中排名最高的男士），其余男士惨遭拒绝。已经拥有配偶的女士会将当前配偶也加入和新的请求比较，选择最心爱的那一个。这意味着已配对的男性可能重新单身，他需要向偏好位下一位的女性继续求婚。
循环往复：被拒绝的男士们重获自由身，继续向下一位心仪女士发起攻势，直到所有女士都手握一支玫瑰。

用伪代码描述这场玫瑰盛宴：

初始化所有男士和女士为自由状态
while 存在自由男士 do
    选择一位自由男士m
    f = m的偏好列表中尚未被自己求婚的最高位女士
    if f处于自由状态 then
        m和f暂时配对
    else
        if f更偏爱m而非当前配对对象m' then
            解除f与m'的配对
            m和f暂时配对
            将m'设为自由状态
        else
            m继续保持自由状态
        end if
    end if
end while

正确性与复杂度

Gale-Shapley算法最令人惊叹之处，在于它总能找到一个稳定匹配。：

终止性：算法必然在有限步内结束。因为每位男士最多向(n)位女士求婚，且每次求婚至少有一位男士被拒绝或配对，总步数不超过(n^2)，时间复杂度为(O(n^2))
完美匹配：算法总是所有男士和女士都配对成功时才结束。若有男士(m)未配对，必有女士(f)也未配对，而(m)会继续向(f)求婚。
稳定性：假设存在阻塞对((m, f))，即非夫妻但(m)更爱(f)，(f)更爱(m)。根据算法，(m)必然曾向(f)求过婚，而(f)要么拒绝了(m)（与(f)更爱(m)矛盾），要么接受了(m)（与(m)未配对矛盾）。因此，阻塞对不存在。