ch1 算法概述¶

1. 概述¶

【算法】是一个有限的、明确的、有效的，从输入到输出的进程。

【目标】根据给定毕业生与医院间的偏好顺序，给出一个自强化的分配方案。

不稳定对：若 \(x\) 相比于自己分配的医院更偏好 \(y\)，且 \(y\) 相比于自己的某一个分配的毕业生更偏好 \(x\)，则称 \(x-y\) 是一个不稳定对。
稳定分配：不存在不稳定对的分配。

【婚姻匹配问题】对于给定的 \(n\) 个男人和 \(n\) 个女人，找到一个合适的匹配。每个人对所有的异性都给出了自己的偏好。

完美匹配：每个人都有配偶。
稳定性：希望任意未配对的男女，都没有改变配偶的动机。
不稳定对：在匹配 \(M\) 中，男人 \(m\) 和女人 \(w\) 未被配在一起，但 \(m\) 相比于当前的配偶更喜欢 \(w\)，且 \(w\) 相比于当前的配偶更喜欢 \(m\)，则称 \(m-w\) 是不稳定对。也就是说他们更有意愿在一起。
稳定匹配：不含有不稳定对的完美匹配。

追求-拒绝算法

【发现一】男人追求女人的顺序，总是在自己的偏好列表上从高到低的。

【发现二】一旦女人有了配偶，她就不会再回到单身状态。

【证明时间复杂度】算法会在至多 \(n^2\) 次迭代后终止。

【证明完美匹配】算法结束时，所有的男女都找到了自己的配偶。

反证法：假设有一个男人 \(Z\) 在算法终止时仍然没有找到配偶，由于男女人数一致，那么必定存在一个女人 \(A\) 在算法终止时也没有找到配偶，由发现二可知，\(A\) 从未被追求过。但由算法可知，\(Z\) 追求过每一个女人，导出矛盾。

【证明稳定匹配】算法返回的匹配中，不存在不稳定对。

反证法：假设 \(A-Z\) 是一个不稳定对，即他们都喜欢对方更胜于算法中给出的匹配 \(S^*\) 中的配偶，
- 若 \(Z\) 从未追求过 \(A\)，由发现一可知，\(Z\) 对 \(S^*\) 中的配偶的偏好更胜于 \(A\)，与假设不一致，因此 \(A-Z\) 是稳定的。
- 若 \(Z\) 追求过 \(A\)，则 \(A\) 拒绝了 \(Z\)（立刻或之后），即 \(A\) 对 \(S^*\) 中的配偶的偏好更胜于 \(Z\)，与假设不一致，因此 \(A-Z\) 是稳定的。

【理解 GS 算法】

【证明 GS 算法的结果总是男性最优（女性最差）分配】因为男性最优分配是唯一的，因此 GS 算法的结果也是唯一的。男性最优分配也是一个稳定匹配。

反证法：假设某个男人没有能够与最喜欢的有效伴侣在一起，则由男人从高到低的追求可得，有男人被有效伴侣拒绝。不妨称第一位被有效伴侣拒绝的男人为 \(Y\)，拒绝他的女人为 \(A\)，记 \(A-Y\) 配对的稳定匹配为 \(S\)。当 \(Y\) 被拒绝时，\(A\) 一定与一位她更喜欢的男人配对，记为 \(Z\)，记 \(S\) 中 \(Z\) 的配偶为 \(B\)。因为 \(Y\) 是第一个被有效伴侣拒绝的男人，故此时 \(Z\) 必定没有被有效伴侣拒绝过，因此 \(Z\) 相比于 \(B\) 一定更喜欢 \(A\)。但 \(A\) 相比于 \(Y\) 更喜欢 \(Z\)，故 \(A-Z\) 为 \(S\) 中的一个不稳定对，导出矛盾。