算法不想学(一): 随缘匹配

本文主要是介绍算法不想学(一): 随缘匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

文章内容取自http://www.cs.cmu.edu/~arielpro/15896s16/slides/896s16-16.pdf并有所修改, 如有侵权等问题, 请提示删除(手动感谢). 这次主要是开个系列分享分享有趣的算法.

稳定匹配(The Stable Matching Problem)

不稳定对(Unstable pair)

如果:

男生x相比现有配对更喜欢女生y
女生y相比现有配对更喜欢男生x

这就是一个不稳定对, 很好理解吧.
那么稳定匹配就是不存在不稳定对的匹配.
举个小栗子, 现在给出联谊上3男3女的喜欢表, 提什么男男/女女的, 一对多的, 麻烦关闭页面(手动无奈).

男生\喜欢	1st	2nd	3rd
X	A	B	C
Y	B	A	C
Z	A	B	C

女生\喜欢	1st	2nd	3rd
A	Y	X	Z
B	X	Y	Z
C	X	Y	Z

这里我们尝试给出一个解, 看是不是稳定匹配. X-C, Y-B, Z-A. 很明显, X, A, B是可能出事情的. 如果X-A, 就出事了, 因为A比起现在匹配的Z更喜欢X; 同理, X-B也出事了, B可是最喜欢X的. 那么GG, 红线崩了.

男生\喜欢	1st	2nd	3rd
X	A	B	C
Y	B	A	C
Z	A	B	C

女生\喜欢	1st	2nd	3rd
A	Y	X	Z
B	X	Y	Z
C	X	Y	Z

X-A, Y-B, Z-C如何呢? 发现是稳定的, 因为A, B都最不喜欢Z.

男生\喜欢	1st	2nd	3rd
X	A	B	C
Y	B	A	C
Z	A	B	C

女生\喜欢	1st	2nd	3rd
A	Y	X	Z
B	X	Y	Z
C	X	Y	Z

但是不是每次都这么好运能找到稳定匹配的, 所以需要算法帮助解决问题.

Propose-And-Reject Algorithm

Propose-And-Reject Algorithm(Gale-Shapley 1962)可以解决问题. 贴一下伪代码, 这个算法原本是解决求婚问题的, 但是当成联谊看比较合适, 哪有人日常换未婚夫的(手动滑稽).

Initialize each person to be free.
while (some man is free and hasn't proposed to every woman) {Choose such a man mw = 1st woman on m's list to whom m has not yet proposedif (w is free)assign m and w to be engagedelse if (w prefers m to her fiancé m')assign m and w to be engaged, and m' to be freeelsew rejects m
}