Joyce' Blog
0%

算法复习笔记（一）

发表于

稳定匹配（邀请-拒绝算法 [Gale-Shapley 1962] ）

一个匹配S是稳定的，如果匹配S是完美的且不存在相对于S的不稳定因素。

算法

初始，每个人都是自由的。一个自由的男人m选择他的优先表上排名高的女人w,发起邀请，那么(m,w)进入中间状态： 约会 。

如果又有另一个男人m’发起邀请，那么女人w决定,选择m,还是m’. 如果m优先， 那么约会状态不变。否则(m’,w)变成约会状态，m变成自由状态。

循环往复；当没有人处于自由状态，那么所有的约会被定为后的结果， 返回终的完美匹配

1
2
3
4
5
6
7
8
9
Initialize each person to be free. 
while(some man is free and hasn't proposed to every woman) { 		Choose such a man m 
    w = 1st woman on m's list to whom m has not yet proposed 
    if (w is free) 
          assign m and w to be engaged 
    else if (w prefers m to m') 
             assign m and w to be engaged, and m' to be free 		else 
             w rejects m 
}

至多n^2次While循环的迭代后终止。G-S算法的每次执行都得到男士对应的最佳有效伴侣集合。每个女士与她最差的有效伴侣配对。

trick：女士对自己的优先表做反向变换； 
1
2
for i = 1 to n 
	inverse[pref[i]] = i

五类典型问题

Interval scheduling: n log n greedy algorithm.

Weighted interval scheduling: n log n dynamic programming algorithm.

Bipartite matching: nkmax-flow based algorithm.

Independent set: NP-complete.

Competitive facility location: PSPACEcomplete.

算法分析

亚线性时间(O(logn))-线性时间O(n)-O(nlogn)阶时间-平方时间-立方时间-O(n^k)时间-指数时间(Exponential time)-n!时间

我对不起葡萄