什么是备胎算法?_备胎怎么解释

什么是备胎算法?_备胎怎么解释什么是备胎算法?

大家好,又见面了,我是你们的朋友全栈君。

假设有三男(分别是 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://juejin.im/post/5ce1fa666fb9a07ecd3d2d2f

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/106815.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux安装JDK

    Linux安装JDKLinux安装JDK

  • java calendar计算时间差_Java Calendar 计算时间差

    java calendar计算时间差_Java Calendar 计算时间差publicstaticvoidmain(String[]args){Calendarc=Calendar.getInstance();inty=2016;//年intM=1;//月intd=1;//日intH=0;//时intm=0;//分ints=0;//秒c.set(Calendar.YEAR,y);c.set(Calendar.MONTH,M-1);c.set(…

  • 编程题:分苹果_同学分苹果的小学题

    编程题:分苹果_同学分苹果的小学题题目描述n只奶牛坐在一排,每个奶牛拥有ai 个苹果,现在你要在它们之间转移苹果,使得最后所有奶牛拥有的苹果数都相同,每一次,你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上,问最少需要移动多少次可以平分苹果,如果方案不存在输出-1。输入描述:每个输入包含一个测试用例。每个测试用例的第一行包含一个整数n(1<=n<=100),接下来的一行包含n个整数ai(1&l…

    2022年10月12日
  • 服务器 IIS服务器防盗链具体设置方法

    服务器 IIS服务器防盗链具体设置方法IIS主机的Rewrite伪静态组件下载与配置之前已经讲过,如果你的apache服务器,请看<Apache服务器设置防盗链的方法>,今天主要说下IIS服务器防盗链的设置方法。isapi_rewrite利用正则表达式进行替换规则的表示。进行正则表达式的编写的时候,可以利用isapi_rewrite提供的正则表达式测试工具(默认安装提供),进行调试。做好了匹配表达式和格式化表达式,我们可…

  • apache功能配置

    apache功能配置

  • java生成时间戳类型_Java获取当前时间戳的方法有哪些

    java生成时间戳类型_Java获取当前时间戳的方法有哪些Java获取当前时间戳的方法有哪些时间:2017-08-22来源:华清远见JAVA学院时间戳就是一种类型,只是精度很高,比datetime要精确的多,通常用来防止数据出现脏读现象。那么Java中如何获得时间戳,Java获得当前时间戳的方法有哪些呢?Java获取当前时间戳的三种方法//方法一System.currentTimeMillis();//方法二Calendar.getInst…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号