问题描述
这个问题也叫做 Perfect Marriage 问题，是用来相亲时候怎么配对男女都好，比如非诚勿扰里的每个男嘉宾会对女嘉宾排一个自己喜欢的顺序，当然女嘉宾也会对男嘉宾排一个序，作为节点组当然会实现 “两情相悦” 是对好啦。可是总会有不如意的情况。
比如现在有男女双方的喜好排序表，有两个男: m1, m2, 两个女: w1, w2
| 男人 | 最喜欢的女人 | 要将就的女人 |
|---|---|---|
| m1 | w1 | w2 |
| m2 | w1 | w2 |
| 女人 | 最喜欢的男人 | 要将就的男人 |
|---|---|---|
| w1 | m1 | m2 |
| w2 | m1 | m2 |
用二分图可以画成这样
如果现在我们匹配他们为 m1 - w2, m2 - w1，肯定是不好的，也称为 Unstable Matching，因为 m1 - w1 才是情投意合的 (双向的)。所以 m1-w1, m2-w2 才更好一点，这种称为 Stable Matching。
Shapley Algorithm
使用这个算法可以很容易帮我们找到 Stable Matching。算法如下
先初始化男人和女人都是可以没有匹配好的
while (还有男人 m 没有匹配) {
w = 当前男人 m 最喜欢的女人
if(w 还没有匹配
(m, w) 先匹配成一对
else if 存在 (m', w)
if w 更喜欢 m，而不太喜欢 m'
(m, w) 会组成一对
m' 重置为 “未匹配”
else
(m', w) 还是一对组合
}
以上面为例子
- 首先我们先看 m2，发现他更喜欢 w1，所以先搞个组合 (m2, w1)
- 再看 m1，发现他更喜欢 w1。而且现在存在组合 (m2, w1)，可是 w1 更喜欢 m1，所以
- 将 (m2, w1) 拆散，组合成 (m1, w1)
- 现在 m2 重置为 “未匹配”
- 因为 m2 是未匹配的，所以再看他下一个更喜欢的是谁，是 w2，所以组合他们 (m2, w2) 为一对
- 程序结束
