稳定婚姻问题(Stable Marriage Problem)

张文泰 posted @ 2010年2月02日 05:18 in Art of Science with tags 稳定婚姻问题 , 4250 阅读

问题概述：有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。