稳定匹配的两种方式
-
完美匹配
集合M={m1,m2……mn}和集合W={w1,w2……wn},令M×W={(mi,wj)|mi∈M,wi∈W}
同时，S∈M×W,S是M×W的一个有序对的集合，且M的任意一个成员和W的任意一个成员都仅仅只会在S中一个对里。
-
稳定匹配
集合M={m1,m2……mn}和集合W={w1,w2……wn},∀mi∈M,mi对于W有一个偏好排序。同时，∀wj∈W,wj对于M也有一个偏好排序。
如果存在一种完美匹配，使得:(以下两者符合其一即可）
∀(mi,wj)∈S,对于mi来说，wj>(∀wk∈W - wj)
或者：
∀(mi,wj)∈S,对于wj来说，mi>(∀mk∈M - mi)
也就是说，无论对于mi还是wj来说，只要其中的一个得到了最偏好的那一个即可。
G-S算法的伪代码
∀mi∈M,∀wi∈W,mi和wi都是自由的。
While ∃mj∈M,且mj是自由的,∃wk∈W,mj还未向wk求过婚:
选择这样的一个男人mj
令wk是mj的优先表中还未求过婚的排名最高的女人
If wk是自由的 then
(mj,wk)变成约会状态
Else wk当前与mt约会:
If wk更加偏爱mt而不爱mj Then
mj 保持自由
Else wk更加偏爱mj而不爱mt
(mj,wk)变成约会状态
mt 变为自由状态
Endif
Endif
EndWhile
G-S算法的特点
w选择的约会对象会越来越好。
m选择的约会对象会越来越差。
当w处于约会状态下，遇到一个更好的求婚对象时，她会选择抛弃原有的约会对象，从而选择更好的。因此，w的约会对象会越来越好，m的约会对象会越来越差。
G-S算法在至多n2次While循环后终止。
如果m是自由的，那么至少存在未被他求婚的女人。
循环结束时返回的集合S是一个完美匹配。(反证法）
G-S算法执行结束返回的集合S是一个稳定匹配。
证明：（反证法）
G-S算法的每次执行都得到同一个集合S。(即结果不变）
在稳定匹配中S中，每个女人与她最差的有效伴侣配对。
