摘要：今天是特殊节日，你化身为丘比特，来设计一个算法分配对象。延迟接受算法盖尔沙普利算法，也被称为延迟接受算法，简称算法。结尾语最后回到标题，对于爱情问题，上面的盖尔沙普利算法告诉我们一点主动追求比被动等待更有希望获得幸福。
假设有三男（分别是 A ，B ，C ）和三女（分别是 x，y ，z ），他（她）们对异性的心仪程度如对话框所示。
比如对于男 A 来说，心仪对象排名为 x 排第一，y 排第二，z 排第三。
今天是特殊节日，你化身为丘比特，来设计一个算法分配对象。
立即接受算法
下面以男生主动追求对象为例来讲解 立即接受算法。
一开始男生们都去追求自己 最 心仪的女生，而女生们面对追求者们立刻做出决定确定对象（如果有多个追求者则选择他们之前心仪程度更高的那个，只有一个的话那就只能选他）。
然后，被拒绝的男生们马上再去追求第二心仪的女生，以此类推，直到配对完毕，如动图所示。
这样做法有一个很严重的问题：当你被你的 No.1拒绝后，再去追求你的 No.2 的时候，你心中的 No.2 可能已经在第一轮中选择了其他人，比如男生 B 在第一轮去表白女生 x，表白失败后想去追求 y，但女生 y 已经和 C 在一起了，悲剧的是 y 眼中的真命天子正是一开始没来表白的男生 B。
最终的匹配情况如下图所示。
虽然现在匹配结束出结果了，每个男生和女生都有对象，但是会出现以下情况。
对于男生 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 放入了考察范围。
第二轮，每个男生再向心中的 No.2 示爱。并且从第二轮开始，每位女生们只保留自己到现在为止所收获的最心仪的男生（但是不用答应他，只hold在心里），而拒绝其他所有人。
而被拒绝的男生（也就是现在尚没有女生 hold 你的男生）则继续在下一轮中向心中排名的下一个女生表白。
以此类推，一轮轮继续下去，直到所有想示爱的男生都示完为止。
最后，每个女生手里都有 hold 的对象。
使用 延迟接受算法 后，最终 A - x ，B - y ，C - z 在一起，并且在这 6 人中，你不可能找到一男一女符合以下条件：他（她）们都更愿意抛弃已有的对象而与彼此在一起。
使用 延迟接受算法 匹配后的结果是一种稳定的状态结果。
结尾语最后回到标题，对于爱情问题，上面的盖尔-沙普利算法告诉我们一点：
主动追求比被动等待更有希望获得幸福。
所以，如果你无法让表白成为你胜利的号角，那倒在进攻的冲锋号上也未尝不可。
如果你觉得该文章不错，不妨：
1、点赞，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
2、关注我，让我们成为长期关系
3、关注公众号「五分钟学算法」，里面已有 100 多篇算法类原创文章，欢迎各位的关注，第一时间阅读我的文章。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/6749.html
摘要：本文会介绍位图处理，矢量图和图像处理，重点是，并且最后会附上一个小应用。以上列举部分，更多备胎在此矢量图处理讲完位图再说矢量图。矢量图在绘制图标商业动画元素上应用非常广范。 计算机图像处理是一门很成熟的技术，任何一门可操作系统接口的语言都能很轻易的实现各种处理操作。但是前端限于浏览器环境和接口限制，处理起来会有诸多不便，这里所说的前端图像处理，是真的指不借助任何后端服务纯前端实现的图像...
摘要：小丽总是会在朋友圈发布自己的各种生活状态。总结我们从观察者模式特点入手，通过一个案例，一步一步完善了观察着的写法，特点组后介绍了总已有的实现关注我，这里只有干货同系列文章从未这么明白的设计模式一单例模式 showImg(https://segmentfault.com/img/remote/1460000018874501); 本文原创地址，我的博客：https://jsbintask...
摘要：引言今天我们来聊聊，随着互联网发展，这两年前后端分离的开发模式兴起，也从以住的幕后走上了台面，让更多的人而得知，以前传统的开发方式大多局限在后端人员接触较多一些。 showImg(https://segmentfault.com/img/bVbi8JE?w=1008&h=298); 引言 今天我们来聊聊Mock，随着互联网发展，这两年前后端分离的开发模式兴起，Mock也从以住的幕...
阅读 1678·2021-11-25 09:43
阅读 2023·2021-11-19 09:40
阅读 3076·2021-11-18 13:12
阅读 1584·2021-09-29 09:35
阅读 480·2021-08-24 10:00
阅读 2291·2019-08-30 15:55
阅读 1568·2019-08-30 12:56
阅读 1673·2019-08-28 17:59
