稳定婚姻问题

昨天的算法课就以稳定婚姻问题(stable marriage problem, SMP)作为切入,来介绍什么是算法,以及怎样分析和设计算法。这个算法足够简单,但从算法的正确性到实现细节上,可以讨论的地方很多,下面我就来梳理一下相关的知识。

先来介绍一下什么是稳定婚姻问题:$n$个男生和$n$个女生,每一个人都按照喜好程度对所有的异性排了名,将男生和女生完全匹配,使得没有两个异性喜欢彼此超过自己当前的伴侣。当不存在这样的匹配时,就认为这个匹配时稳定的。

算法

1962年David Gale和Lloyd Shapley证明了,对于相等数量的男生和女生,SMP问题总是有使得所有婚姻都稳定的解,而且还提出了一个算法。

Gale–Shapley算法由若干次迭代组成:

  • 在第一次迭代,每一个未订婚的男生向他最喜欢的女生求婚,然后每个女生向她最喜欢的追求者说“maybe”,向其他的追求者说“no”,她暂时与她目前为止最喜欢的追求者订婚,追求者同样也是暂时与她订婚。
  • 在随后每次的迭代中,每一个未订婚的男生向他尚未求过婚的最喜欢的女生求婚(不管这个女生是否已经订婚了),然后对于每个女生,如果她相比于现在暂时的伴侣更喜欢这个男生,就对这个男生说“maybe”(这种情况下她就会拒绝她当前暂时的伴侣,这个伴侣变成未订婚的状态)。订婚的临时性质保留了已经订婚的女性“升级伴侣”的权利(并且在此过程中“甩掉”那时的伴侣)。
  • 不断重复这个过程直到每个人都订婚了。

这个算法的时间复杂度时$O(n^2)$,其中$n$是男生和女生的数量。

这个算法保证了:

每一个人都会匹配

最后不会出现一个男生和一个女生都没有订婚的情况,因为他一定在某个时间点向她过求婚(因为必要的话男生可能会向每一个女生求婚),而且只要被求过婚,她就一定会在那之后保持订婚的状态。

婚姻时稳定的

设A和B都订婚了,但伴侣不是彼此。在算法完成之后,不可能出现A和B更喜欢彼此甚于自己当前的伴侣。因为如果B更喜欢A的话,他就一定会在向当前这个伴侣求婚之前向A求过婚。如果A接受了他的求婚,但最后却没有嫁给他,必定是因为她碰到了一个更喜欢的而甩了B,因此A不可能喜欢B甚于自己当前的伴侣;如果A拒绝了他的求婚,一定是因为她已经与一个更喜欢的人订婚了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function stableMatching {
Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to {
w = first woman on m’s list to whom m has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
m' becomes free
(m, w) become engaged
else
(m', w) remain engaged
}
}

稳定婚姻问题在许多真实的场景中都有应用,一个重要的大规模应用是将用户分配给大型分布式互联网服务中的服务器。数十亿用户访问互联网上的网页,视频和其他服务,要求每个用户都与全球提供该服务的数十万台服务器中的一台相匹配。用户更喜欢足够接近的服务器,因为请求的服务可以提供更快的响应时间,从而导致每个用户对服务器进行(部分)优先排序。每个服务器都倾向于以较低的成本为用户服务,从而导致每个服务器对用户进行(部分)优先排序。分发大部分全球内容和服务的内容分发网络(Content delivery network, CDN)每十秒钟解决一次用户和服务器之间的这一庞大而复杂的稳定婚姻问题,使得数十亿用户能够与其各自的服务器相匹配,这些服务器可提供所请求的网页,视频或其他服务。

如果您觉得这篇文章对您有帮助,请随意打赏。