Feb 2
问题概述:有n个女生和n个男生,每位女生按照她的偏爱程度将男生排序,同时每位男生也按照自己的偏爱程度将女生排序,然后将这n个女生和n个男生配成完备婚姻。
如果存在两位女生A和B,两位男生a和b,使得A和a结婚,B和b结婚,但是A更偏爱b而不是a,b更偏爱A而不是B,则这 个婚姻就是不稳定的。反之,这个婚姻就是稳定的。
可以通过证明,得到每一个n女n男的社团,都存在稳定婚姻的结论。但是这种情况只在异性的社团中存在。也就是说在同性的社团里面,稳定婚姻的存在性将不再被保证。下面是一种简单的稳定婚姻的算法。
Gale-Shapley 算法:
while存在男人m是自由的且还没对每个女人都求过婚 选择这个男人m 令w是m的优先表中还没求过婚的最高排名的女人 if w 是自由的 (m,w)变成约会状态 else w当前与m1约会 if w更偏爱m1而不爱m m保持自由 else w更偏爱m而不爱m1 (m,w)变成约会状态 m1变成自由 endif endif endwhile
一道关于稳定婚姻问题的题目:ZJU 1576 Marriage is Stable。