算法: Perfect Matching

问题描述

这个问题也叫做 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) 为一对
• 程序结束