稳定匹配（Stable Matching）
rqoi031
·
·
算法·理论
问题描述
给出一个带边权的完全二分图，设其中左侧点集为 S，右侧点集为 T，点 x(x\in S) 和点 y(y\in T) 间的边权为 w(x,y)。
根据以上条件，我们需要求出一组稳定匹配。
注意：
-
为了方便我们假设边权互不相同。
-
可能存在 w(a,b)\neq w(b,a)。
基本定义
匹配
一个匹配 M 指一个包含若干有序数对 (x,y) 的集合，其中 x\in S，y\in T，并且每个 x\in S 和每个 y\in T 最多只在一个数对中出现。
完美匹配
若 |M|=|S|=|T|，则称匹配 M 是一个完美匹配。
不稳定因素
对于一个完美匹配 M，若存在两个数对 (x,y),(a,b)\in M，且 w(x,a)>w(x,y)\land w(a,x)>w(a,b)，则称数对 (x,a) 是匹配 M 的一个不稳定因素。
稳定匹配
我们称一个匹配 M 是一个稳定匹配，当且仅当 M 是一个完美匹配，且 M 没有不稳定因素。
正当匹配
若存在稳定匹配 M，使得 (x,y)\in M，那么称 (x,y) 为一个正当匹配。
Gale-Shapley 算法
算法过程
首先，若 |S|\neq |T|，一定没有稳定匹配。
否则执行以下操作：
- 若对于所有 S 中的点，已经有了匹配的节点，即已经求出了稳定匹配，算法结束；否则：
- 选择任意一个没有匹配的节点 x\in S，
- 在 x 没有尝试匹配过的节点 y\in T 中选择 w(x,y) 最大的 y，
- 尝试匹配 x 和 y，
- 若 y 没有匹配，则将 (x,y) 加入 M；
- 否则，若 y 匹配了节点 z\in S，若 w(y,x)>w(y,z)，将 (y,z) 从 M 中移除，并将 (x,y) 加入 M；
- 否则，尝试失败。
- 找到了一个稳定匹配 M。
易证，该算法时间复杂度为 O(|S|^2)。
算法性质
完美性
该算法求出的匹配 M 是完美匹配。
证明
假设 x\in S 没有匹配，所以一定存在 y\in T 没有匹配。
根据算法，若尝试过匹配 y 和任意节点，那么 y 一定在匹配中，所以一定没有尝试匹配过 y。
又因为 x 没有匹配，根据算法，x 尝试过和所有 T 中的点匹配。
所以矛盾，命题得证。
稳定性
该算法求出的匹配 M 不存在不稳定因素。
证明
假设匹配 M 不包含 (x,y)(x\in S,y\in T)。
没有尝试过匹配 x 和 y，设 x 匹配了 z\in T。
因为 x 先尝试匹配边权更大的点，所以 w(x,z)>w(x,y)，即 (x,y) 不是不稳定因素。
尝试过匹配 x 和 y，设 y 匹配了 z\in S。
因为只有 w(y,z)>w(y,x) 才会将 (z,y) 移出 M，即 (x,y) 不是不稳定因素。
综上，M 不存在不稳定因素。
左侧点最优匹配
对于任意左侧点 x\in S，该算法求出的匹配 (x,y)(y\in T)，满足对于任意 z\in T，若 (x,z) 是正当匹配，那么 w(x,y)\geq w(x,z)。
证明
略。
右侧点最劣匹配
对于任意右侧点 y\in T，该算法求出的匹配 (x,y)(x\in S)，满足对于任意 z\in S，若 (z,y) 是正当匹配，那么 w(y,x)\leq w(y,z)。
证明
略。
例题
CF1147F Zigzag Game
参考资料
- 经典算法问题——稳定匹配（Stable Matching）