算法课 -- 1.1 稳定匹配问题

稳定匹配 问题描述

考虑n个男人的集合M与n个女人的集合W
$M = \{m_1, m_2, ..., m_n\} \\ W = \{ w_1, w_2, ..., w_n\}$M={m1​,m2​,...,mn​}W={w1​,w2​,...,wn​}
M x W(笛卡尔积)表示所有可能的形如(m, w)的有序对的集合
匹配S：是来自M x W的有序对的集合(M x W的子集), 并且具有下述性质：每个M的成员和每个W的成员至多出现在S的一个有序对中
完美匹配S‘：每个M的成员和每个W的成员恰好出现在S’的一个对中

偏爱
优先表
不稳定因素

稳定匹配S： 1. S是完美匹配 2. S中不含有不稳定因素

稳定匹配问题

1. 对每组优先表是否存在一个稳定匹配
2. 给定一组优先表， 如果存在稳定匹配， 能否有效得将其构建出来

Gale-Shapley(G-S)算法

算法分析

命题1.1 w从接受对她的第一次求婚开始始终保持约会状态，且她约会的一系列伴侣，(按照她的优先表)变得越来越好

命题1.2 m求过婚的一系列女子(按照他的优先表)变得越来越差

定理1.3 G-S算法在至多n^2次While循环的迭代后终止