0%

稳定婚姻问题

问题

有$n$个男生和$n$个女生,有$2n$个排列$p_1,p_2\cdots p_n,q_1,q_2\cdots q_n$,$p_i$代表第$i$个男生的喜好($p_{i,1}$表示他最喜欢的女生,$p_{i,2}$是他第二喜欢的,以此类推),$q_i$代表第$i$个女生的喜好。

稳定婚姻问题即,求一个男生和女生的完美匹配$M$,使得不存在$(x,y)\not\in M$,$x$对$y$的好感高于$x$现在的配偶且$y$对$x$的好感高于$y$现在的配偶。

Gale–Shapley算法

过程

迭代进行以下过程$n$次:

  • 对于每一个没有订婚的男生,让他向他目前还没有求爱过的女生中他最喜欢的那个求爱(不管那个女生是否已经订婚)。然后,每一个女生在这一轮向她求爱的男生以及她原来的配偶中,选择一个她最有好感的,作为她现在的配偶。可能会出现女生和原来配偶撕约的情况,但是被撕约了的男生将加入下一轮的求爱。

正确性

求出来的肯定是一个匹配,并且是完美匹配,因为只要一个女生被求过爱,之后就不可能单身了。

整个过程中,女生的配偶会越来越好,而男生的配偶会越来越差。所以当算法结束的时候,对于每个男生,比他现在的配偶更好的女生的配偶一定都比他好。

时间复杂度

迭代$n$次,每次复杂度$O(n)$,总时间复杂度$O(n^2)$。