2009年4月16日星期四

The Stable Marriage Problem

稳定婚姻问题

这是从社会生活中过分简化、抽象出来的一个组合数学问题。参考:
http://www.cs.columbia.edu/~evs/intro/stable/writeup.html
http://zh.wikipedia.org/wiki/稳定婚姻问题

严格描述如下:
定义:
  • 考虑n个男人,用大写字母表示(X,Y,Z...)、n个女人,用小写字母表示(x,y,z...)
  • 每个人有一个异性的偏好列表,例如X(x>y>z...)表示X喜欢x胜过喜欢y,喜欢y胜过喜欢z...(静态严格全序,即不存在相等或不可比较的情况,可传递,且不随时间改变)
  • 一个婚姻表示为一个序对,例如Xx表示X与x结婚
  • 一个婚姻组合为所有男人到所有女人的一一对应,表示为n个婚姻,恰好没有人单身
  • 称一对男女(X, y)是不满的,若存在Y、x使得Xx、Yy、X(y>x)、y(X>Y)成立,也就是说,X和x结婚,Y和y结婚,但是X和y喜欢彼此胜过喜欢他们现有的配偶,所以X和y不满于现在的婚姻,存在重新组合的不稳定因素
  • 称一个婚姻组合是稳定的,若其中不包含不满的男女对
  • 一个稳定婚姻问题是指:给定n男n女和他们的偏好列表,问是否存在一个稳定的婚姻组合
定理:
  • 任何一个稳定婚姻问题的实例,都是"是"实例。进一步地,存在一个多项式时间算法,求出稳定婚姻问题的解。
算法(被称作求婚算法):
初始时所有男人和女人设为单身
每一步
任选一个当前单身的男人X
X向其列表中尚未标记为"拒绝"的、最喜欢的女人x求婚(其存在性在命题0中证明)
如果x单身,则Xx结婚,X从单身男人集合中移除
否则(存在Y,使得已经有Yx)如果x(X>Y),则Xx,Y放回单身男人集合并从Y的列表中标记x为"拒绝"
否则X留在单身男人集合中并从X的列表中标记x为"拒绝"
直到单身男人集合为空集(可终止性在命题1中证明)

命题0:上述算法每一步的男人X,都能找到可以求婚的x
证明:反证法,假设不然,也就是说这时候X的列表中所有女人都已经拒绝X了。注意到按照算法的构造,只有结过婚的女人才能拒绝男人,而且结过婚的女人只能改嫁不能返回单身,因此这时候所有女人都非单身,从而所有男人都已经结婚了,这与X还单身矛盾。假设不成立,原命题得证。

命题1:上述算法至多n+n^2步终止
证明:每一步要么有一个女人第一次结婚,要么有一个男人被拒绝,注意到n个男人的列表总长度为n^n,因此算法至多n+n^2步终止

命题2:算法的正确性:上述算法终止时,得到一个稳定的婚姻组合
证明:反证法,假设不然,算法终止时存在(X,y)不满,即Xx、Yy、X(y>x)、y(X>Y)
由于X(y>x),因此X向y求婚,发生在X向x求婚之前,而最终Xx,说明存在一个时刻,y拒绝或抛弃了X
若当时y拒绝了X,说明y的配偶Z在y心中比X好,即y(Z>X),而最终Yy,说明要么Y就是Z,要么y(Y>Z),从而都有y(Y>X),与假设y(X>Y)矛盾
若当时y抛弃了X,说明那时候有一个Z向y求婚,而且y(Z>X),而最终Yy,说明要么Y就是Z,要么y(Y>Z),从而都有y(Y>X),与假设y(X>Y)矛盾
得证。

应用:
这个算法北应用到大学联合招生、

2 条评论:

xlvector 说...

这不是二分图匹配问题嘛

王元涛 说...

确实是一个二分图匹配的问题,不过问题的提法很特别。不是最大化匹配的个数,而是判定是否存在“稳定的”匹配。