听师兄一句劝，早点去追学姐学妹！

短命女 2023-01-22 13:56 26阅读 0赞

听师兄一句劝，早点去追学姐学妹，为啥呢？

**看完这篇文章你就知道了**。

假设有三男（分别是 A ，B ，C ）和三女（分别是 x，y ，z ），他（她）们对异性的心仪程度如对话框所示。

比如对于男 A 来说，心仪对象排名为 x 排第一，y 排第二，z 排第三。

今天是特殊节日，你化身为丘比特，来设计一个算法分配对象。

![1908612749ea30b70f81b06bb2855301.png][]

### 立即接受算法 ###

下面以男生主动追求对象为例来讲解 **立即接受算法**。

一开始男生们都去追求自己 **最** 心仪的女生，而女生们面对追求者们立刻做出决定确定对象（如果有多个追求者则选择他们之前心仪程度更高的那个，只有一个的话那就只能选他）。

然后，被拒绝的男生们马上再去追求第二心仪的女生，以此类推，直到配对完毕，如动图所示。

![d4a6801f68e1d727a825dbc1402bc1be.gif][]

这样做法有一个很严重的问题：当你被你的 No.1拒绝后，再去追求你的 No.2 的时候，你心中的 No.2 可能已经在第一轮中选择了其他人，比如男生 B 在第一轮去表白女生 x，表白失败后想去追求 y，但女生 y 已经和 C 在一起了，悲剧的是 y 眼中的真命天子正是一开始没来表白的男生 B。

最终的匹配情况如下图所示。

![2662777a9cbe703409f8bd4e3207a956.png][]

虽然现在匹配结束出结果了，每个男生和女生都有对象，但是会出现以下情况。

对于男生 B 来说，虽然他和女生 z 在一起，但其实他更期望和 y 在一起（注意 A 与 x 都是双方的挚爱，拆不开的）。

同时，对于女生 y 来说，虽然她和男生 C 在一起，但其实她更期望和 B 在一起。

即男生 B 和女生 y 都更愿意离开自己的现任对象而彼此在一起。

所以，使用**立即接受算法**匹配后的结果是一种不稳定的状态结果。

### 延迟接受算法 ###

“盖尔-沙普利算法”（the Gale-Shapley algorithm），也被称为“延迟接受算法”（deferred-acceptance algorithm），简称“GS算法”。

目前该算法在 **高中择校系统、肾脏移植** 等实际应用上起到了巨大的作用，你甚至可以在 2012 年诺贝尔经济学奖中看到它的身影。

这个算法一个核心之处在于，合意的要约不会立即被接受，而只是被“抓住”（hold on to），也就是“延迟接受”。

还是以男生主动追求对象为例来讲解 **延迟接受算法**。

首先每个男生在第一轮中向自己最心仪的女生表白，但是各位女生不用立即做决定，而是先 **hold** 住。

#### 第一轮 ####

第一轮，男生 A 和男生 B 都跟女生 x 表白，女生 x 按捺激动的心情，矜持没有表态直接选男生 A，只是把男生 A 放入考察范围

男生 C 跟女生 y 表白，女生 y 略显失望，但把男生 C 放入了考察范围。

![e3c0e328955ee2a38a1f8234602ecb64.png][]

#### 第二轮 ####

第二轮，每个男生再向心中的 No.2 示爱。并且从第二轮开始，每位女生们只保留自己到现在为止所收获的最心仪的男生（但是不用答应他，只hold在心里），而拒绝其他所有人。

而被拒绝的男生（也就是现在尚没有女生 hold 你的男生）则继续在下一轮中向心中排名的下一个女生表白。

以此类推，一轮轮继续下去，直到所有想示爱的男生都示完为止。

最后，每个女生手里都有 hold 的对象。

![d01065e7add5fedb85492be7a6429ca2.png][]

![0bcda7c39e4cec2bd4e478307ac25ad4.png][]

使用 **延迟接受算法** 后，最终 A - x ，B - y ，C - z 在一起，并且在这 6 人中，你**不可能**找到一男一女符合以下条件：他（她）们都更愿意抛弃已有的对象而与彼此在一起。

使用 **延迟接受算法** 匹配后的结果是一种**稳定**的状态结果。

### 结尾语 ###

对于爱情问题，上面的盖尔-沙普利算法告诉我们一点：

**主动追求比被动等待更有希望获得幸福**。

所以，如果你无法让表白成为你胜利的号角，那倒在进攻的冲锋号上也未尝不可。

好了，以上就是本文的全部内容了，如果觉得有收获，记得点赞、再看、留言、转发，我们下期再见。

另外，算法的学习也是必经之路，这里给大家推荐一个大佬的刷题笔记。

> 链接: https://pan.baidu.com/s/1-NtihTGBHLKkBiXCKWaClQ  
> 密码: e0ff

把这份笔记突击学习一下，很多算法考察，基本都稳了，就算你现在不学算法，那么这份笔记也值得你收藏，万一有人问你 Leetcode 某道题解，或者有大神在讨论题解，咱打开这份笔记，不管三七二十一，直接把最优解扔给他，然后退出群聊。

[1908612749ea30b70f81b06bb2855301.png]: /images/20221020/7dde15561e0c41fb9419317a9daebfcc.png
[d4a6801f68e1d727a825dbc1402bc1be.gif]: /images/20221020/52d25f1def0f4856b7ab891fcf226425.png
[2662777a9cbe703409f8bd4e3207a956.png]: /images/20221020/e9df2572a12c4e3797cfcdeccff27cf2.png
[e3c0e328955ee2a38a1f8234602ecb64.png]: /images/20221020/08258a453a854ac7a0268f6aa736469b.png
[d01065e7add5fedb85492be7a6429ca2.png]: /images/20221020/4449a964e5504f00bae782d7798ab486.png
[0bcda7c39e4cec2bd4e478307ac25ad4.png]: /images/20221020/57297e970c8f45c4ac402b6b0041f543.png