原野图书室（＾_－）ｄｂ（－＿＾）♪

高英杰的魔法帽:

稳定婚姻问题（运筹学）：

有n男n女，假设每人都按他对（异性）对象的喜好程度能够排序。现安排男女结婚，使得下列情形为真: 在n男n女中的任意两对夫妇(M, W)和(m, w)，都不存在M男对w女喜好度大于现任妻子W女，并且w女对M男喜好度也大于现任丈夫m男的情况。那么这样的n对男女的婚姻状况我们称之为稳定的。否则为不稳定。

1962年，两个研究运筹的数学家David Gale和Lloyd Shapley研究出了一种算法，被命名为Gale-Shapley算法。当然那个时候计算机并不尖端且不普及，在运筹学中算法是很重要的。该算法体现了匈牙利算法的一些基本思想。这个算法的大致思路是，规定所有男人可以表白，女人则不能，在n轮表白中，每一轮的单身男人都向自己内心排序最高的女人表白（不管其是否已婚），而女人们则在求爱者中选择内心排序最高者。

该算法大致如下：

建立模型的第一步是提出假设。

假设1.假设世界上的人数为2n，其中一半是男人，另一半是女人。

假设2.每一个人都对n个异性有一个婚姻选择上的排序，即喜爱程度有绝对大小。

假设3.稳定的婚姻指对于任意一个人A，他（她）的伴侣B是B和所有剩余异性所构成的集合中，排序最高的人，B同理。如此，A与B的组合便成为稳定的婚姻。

假设4.男人都是主动的，会主动去表白；女人则都不主动表白。表白时被表白方选择其内心排序最高的人结婚。（当某个女人只有一个男人对其表白时，则立即选择该男人）

现在我们来建立模型，假设n个男人构成的集合为A(a1,a2,...,an)，n个女人构成的集合为B(b1,b2,...,bn)。每个男人内心对n个女人的排序集合为Ai(i=1,2,...,n)，每个女人内心对n个男人的排序集合为Bi(i=1,2,...,n)。

然后来进行第一轮表白：所有男人对其排序最高的女人（即Ai的第一个元素,i=1,2,...,n）表白。被表白的所有女人均选择表白的人当中内心排序最高的男人结婚。到此，第一轮结束。第一轮的结果，对所有结婚的男人来说是最优的，但对某些结婚的女人来说并不是。这样的婚姻是不稳定的。

再来进行第二轮表白：所有剩下的单身男人仍对其排序最高的女人表白。被表白的单身女人均选择表白的男人当中内心排序最高的男人结婚，被表白的已婚女人则选择表白的男人和自己的丈夫所组成的集合中排序最高的男人结婚。到此，第二轮结束。

现在如此循环往复。最后是一定能得到一个稳定解的。

Gale和Shapley最后得到的结果是，所有男人都娶到了他能取到的所有女人中最好的，所有女人都嫁给了她能嫁给的所有男人中最差的。究其关键原因，是因为Gale和Shapley在阐述此问题时引入了表白这一概念，有表白这样的主动能力的男人就能取得好的结果。这个结果的现实意义也是不言而喻的——幸福需要自己去勇敢争取。

所以说爱他就让他主动去追人，这种思路有什么问题吗！？