稳定匹配

稳定匹配的两种方式

• 完美匹配

集合M={m₁,m₂……m_n}和集合W={w₁,w₂……w_n},令M×W={(m_i,w_j)|m_i∈M,w_i∈W}
同时，S∈M×W,S是M×W的一个有序对的集合，且M的任意一个成员和W的任意一个成员都仅仅只会在S中一个对里。

• 稳定匹配

集合M={m₁,m₂……m_n}和集合W={w₁,w₂……w_n},∀m_i∈M,m_i对于W有一个偏好排序。同时，∀w_j∈W,w_j对于M也有一个偏好排序。
如果存在一种完美匹配，使得:(以下两者符合其一即可）
∀(m_i,w_j)∈S,对于m_i来说，w_j>(∀w_k∈W - w_j)
或者：
∀(m_i,w_j)∈S,对于w_j来说，m_i>(∀m_k∈M - m_i)
也就是说，无论对于m_i还是w_j来说，只要其中的一个得到了最偏好的那一个即可。

G-S算法的伪代码

∀m_i∈M,∀w_i∈W,m_i和w_i都是自由的。
While ∃m_j∈M,且m_j是自由的,∃w_k∈W,m_j还未向w_k求过婚:
选择这样的一个男人m_j
令w_k是m_j的优先表中还未求过婚的排名最高的女人
If w_k是自由的 then
(m_j,w_k)变成约会状态
Else w_k当前与m_t约会:
If w_k更加偏爱m_t而不爱m_j Then
m_j 保持自由
Else w_k更加偏爱m_j而不爱m_t
(m_j,w_k)变成约会状态
m_t 变为自由状态
Endif
Endif
EndWhile

G-S算法的特点

w选择的约会对象会越来越好。
m选择的约会对象会越来越差。

当w处于约会状态下，遇到一个更好的求婚对象时，她会选择抛弃原有的约会对象，从而选择更好的。因此，w的约会对象会越来越好，m的约会对象会越来越差。

G-S算法在至多n²次While循环后终止。

如果m是自由的，那么至少存在未被他求婚的女人。

循环结束时返回的集合S是一个完美匹配。(反证法）

G-S算法执行结束返回的集合S是一个稳定匹配。
证明：（反证法）

G-S算法的每次执行都得到同一个集合S。(即结果不变）

在稳定匹配中S中，每个女人与她最差的有效伴侣配对。