Gale-Shapley算法

稳定匹配

给定 n 个医院序列 H 和 n 个学生序列 S。每个医院会对所有学生按照其偏好进行排序。 每个学生同样也会对所有医院按照其偏好进行排序。每个医院 h ∈ H 与学生 s ∈ S 一一配对。如果所有医院与学生都进行了配对，就称其达到完全匹配。配对中的不稳定配对 h ↔ s 即为：
– h 当前配对的对象为 s′，而 h 的偏好是 s > s′。
– s 当前配对的对象为 h′，而 s 的偏好是 h > h′。
显然，只有在信息交互的过程才会发现不稳定配对。稳定匹配就是没有不稳定配对的完全匹配。

Gale-Shapley算法

该算法主要解决了事物之间匹配的问题，利用该算法能够求出最佳匹配也就是稳定匹配。现通过一例子来说明。设有一组男生w和一组女生m需要寻找对象，且每个男生和女生都有自己的偏好，且他们各自的偏好如下：

根据Gale-Shapley算法，我们首先遍历男生w，按照男生的需求的优先级先与女生匹配，若男生先要所选的女生已经被匹配了，那么需要观察女生的喜好，对比已经匹配的男生和想要匹配的男生，选择优者，被淘汰者则按照自己的顺序继续寻找女生匹配。该过程在该例子中可以表现为一下具体执行：
按照优先级首先与 匹配，现有配对：

按照优先级与 匹配，但 已有配对，择优选择 ， 重新配对选择 ，现有配对：

按照优先级选择 ，但 已有配对，择优选择 ， 重新配对选择 ，现有配对：

按照算法最后的稳定匹配为

Gale-Shapley算法最多需要执行步，因为算法需要遍历每一个男生，而每一个男生最坏情况需要匹配每一个女生。