Chap1 算法导论与稳定匹配

1、学习目标

算法设计的第一步不是写代码，而是把现实问题压缩成清楚的数学对象：输入是什么，输出是什么，什么叫合法，什么叫更好。本章用稳定匹配作为第一个完整案例，练习从问题建模到算法证明。

一个算法问题通常写成：

1
2
3

输入：满足某些条件的数据对象
输出：满足某些性质的解
目标：如果有多个解，如何衡量好坏

比如排序：

1
2
3

输入：n 个可比较元素
输出：按非降序排列的序列
目标：正确排序，并尽可能高效

稳定匹配：

1
2
3

输入：两组人数相等的对象，每个人给出对另一组的偏好排序
输出：一组一对一匹配
目标：不存在会破坏当前匹配的阻塞对

设有 n 个学生和 n 个学校，双方都给出对另一方的完整偏好列表。

基本概念：

阻塞对是稳定匹配的核心。它表示当前结果里有一对双方都有动力私下换掉现有搭档，因此这个结果“不稳定”。

以学生向学校提出申请为例：

while 存在未匹配且还没申请完的学生:
    学生 s 向自己列表中尚未申请过的最喜欢学校 c 申请
    if c 当前没有匹配:
        c 暂时接受 s
    else:
        比较 s 和当前学生 s'
        c 保留更喜欢的那个，拒绝另一个

这个算法有两个很重要的动态：

每个学生最多向每个学校申请一次，总申请次数最多 n^2。每次循环至少发生一次新的申请，所以算法一定会终止。

1	申请次数 <= n * n

这类证明很常见：找到一个单调变化且有上界的量。这里的量就是“已经发出的申请数量”。

算法结束后，不会有人没被匹配。

证明思路：

所以算法结束时得到完美匹配。

假设算法结果存在阻塞对 (s, c)，即：

因为 s 按偏好从高到低申请，既然他更喜欢 c，他一定在当前学校之前向 c 申请过。

当时有两种情况：

因此最终 c 不可能更喜欢 s 胜过当前学生，矛盾。算法结果稳定。

实现时通常预处理：

1	rank[c][s] = 学校 c 对学生 s 的排名

这样比较两个学生谁更受学校喜欢就是 O(1)。

稳定匹配这个例子给出的训练价值：