The Stable Marriage Problem(稳定婚姻问题)(转自人人网)

稳定婚姻问题The Stable Marriage Problem最早是由两个美国数学家David Gale&Lloyd Shapley于1962年在American Mathematical Monthly上提出的,这个问题和图论有关(求完全二分图的稳定完备匹配,这是一个NP问题)。对于以前没有接触过这个问题的人,这个理论最出人意外的结论是:传统的求爱、结婚过程是male-optimal(男生主动)的,也就是说,男性能够得到尽可能好的心上人,女性却不然。这里我们就不科普了,直接上问题:

引用

给定若干个男生和同样多的女生,他们每个人都对所有的异性有一个心理的偏好次序(无并列)。具...

© lanceleeneu | Powered by LOFTER