专栏首页大数据文摘算法证明:女生遇到心动的男人一定要追!

算法证明:女生遇到心动的男人一定要追!

本文来自知乎网友尼克余

链接:http://www.zhihu.com/question/27355234

我来讲恋爱中的博弈,不,我来讲恋爱中的算法,不,我来讲算法!!

有个著名的问题,叫做 stable matching。早年是一个可爱的俄罗斯老头在图论课上教我的,印象非常深刻,拿出来娱乐下大家。因为这个算法应用太广泛了,这个算法的两位发明人 David Gale 和 Lloyd Shapley,在 2012 年因为这个算法获得诺贝尔经济学奖。

先说结论:女生遇到心动的男人一定要追!我马上就要来证明。

前方高能预警!!!含大量数学图论及计算机编程算法知识,萌妹子请直接退散。

假设,有一个平行世界,我们姑且叫这个世界,平行世界 999 号,这个世界有 n 个男人,还有 n 个女人,然后每一个男人,都有一个对喜欢的女人的排序,比如男 A,有一个排序(女 A,女 B,一直到女 N),每一个女人都有一个喜欢的男人的排序,比如女 A,有一个排序(男 A,男 B,一直到男 N)。每个男的都会试图去追求自己的排序里头排的最高的女性,每个女的都会接受自己排序里头最高的男性的追求。

再假设这个平行世界 999 号,有以下追求方法(算法):

1. 这个世界上只有男人能够追求女人,女人收到一个男人的追求,可以选择说“你做我男友吧”,或者“你滚犊子”。当女人说“你做我男友吧”的时候,这个男人和女人进入了男女朋友模式,当女人说,“你滚犊子”的时候,这个男人回复单身。

2. 每个男人只能在单身的时候追求女人,而每个女人最多只能有一个男朋友

3. 每个男人都会追求自己名单上排位最高的女人,当被拒之后,会追求排位次高的女人,被拒之后再追第三高的女人,以此类推。每个女人,如果没有男朋友,收到追求,会立刻说,“你做我男友吧”,如果有男朋友,会将现有男朋友与追求者比较,选择其中排位更高的,甩掉排位更低的。

4. 每个男人都会锲而不舍的一直把整个排序追求完,直到脱离单身状态为止。

5. 当每个男的和女的都有一个女、男朋友的时候,会所有人一起结婚。

怎样,是不是和现实很像?让我喝口水继续写!

我的结论是,这个世界里头,一定会有这么一个组合,使得,这 n 个男的,和 n 个女的,会形成一个稳定的一一对应的婚姻关系。也就是说,这 N 个男人和女人,都合理的选择了自己名单上最高的排位的那个对象。

我说的有点乱,因为我学的是用英语学的,而我的翻译实在是不咋地,我先来简化问题:

一、假设这个世界上只有 1 个男人,1 个女人:

那不用想了,排什么排,去滚床单,裸奔,过没羞没躁的生活去吧。

二、假设这个世界上有 2 个男人(男 A,男 B),2 个女人(女 A,女 B):

这就开始复杂了,

如果,男 A 和男 B 的排序都是(女 A,女 B),女 A 和女 B 的排序都是(男 A,男 B)。

那么很简单,男 A 和男 B 一起去追女 A,男 B 迅速杯具,男 A 和女 A 在一起,男 B 和女 B 在一起,故事完结。

如果,男 A 和男 B 的排序都是(女 A,女 B),女 A 和女 B 的排序都是(男 B,男 A)。

那么也很简单,男 A 和男 B 一起去追女 A,男 A 迅速杯具,男 B 和女 A 在一起,男 A 和女 B 在一起,股市完结。

如果,男 A 的排序是 (女 A,女 B),男 B 的排序是(女 B,女 A),女 A 的排序是(男 B,男 A),女 B 的排序是(男 A,男 B)呢,那怎么办?

那么现在,男 A 会去追求女 A,女 A 会说,“你做我男友吧”,男 B 会去追求女 B,女 B 会说“你做我男友吧”。

于是大家结婚了。

所以现在的组合是,男 A 和女 A,男 B 和女 B。

但是!!!但是!!!

你们发现了问题没有???

每个男的都追求到了自己最喜欢的女士,每个女士却只赢得了自己最不喜欢的男士!!!!

这就是这个算法的一个弊端,就是追求者,有占优的可能性。

如果反过来,平行世界 999 里,只允许女人追求男人,会出现下面情况:

女 A 去追求男 B,男 B 会说,“你做我女友吧”,女 B 去追求男 A,男 A 会说“你做我女友吧”。

于是大家都结婚了。

现在的组合是男 A 和女 B,男 B 和女 A。这同样是一个稳定的匹配。

但是!!!但是!!!现在每个女士都追求到了自己最喜欢的男士,每个男士却只赢得了自己最不喜欢的女士!!!

三、推广到 N 男 N 女,也是一样的推论。

简单的说,就是因为这是一个单向筛选,每个男的都会确保会向自己的排序中最高的女性表白。然而男性被“滚犊子”的唯二可能性,是因为这个女性有一个她心目中排序更高的男朋友,或者当了一段时间男朋友,但一个排序更高的男人向她表白。(当然现实中大家也懂,你就是没戏的了,而且是你本来就没戏)

因此,确保了男性一定能追求到自己喜欢的名单里头,排位最高的女性。

也就是说,在这个追求关系里头,主动的那一方更能够找到自己更喜欢的异性,而被动那一方,却没有这样的优势。

所以结论就是,妹子们,遇到喜欢的男人,一定要主动!

via:程序员的那些事(微信ID: iProgrammer)

本文分享自微信公众号 - 大数据文摘(BigDataDigest)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2015-01-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 视觉直观感受 7 种常用排序算法

    大数据文摘
  • 信吗?美联社已经用机器人写作了!

    大数据文摘
  • 个体化医疗的现状、发展与趋势深度详解

    大数据文摘
  • 加入在线服务--在线多人共享屏幕

    Screego 是一个共享屏幕的应用.使用golang进行开发,在readme中作者吐槽了微软等公司的延迟问题,然后就开源了这个项目.?

    caoayu
  • Android真机安装sqlite3的方法

    Android版本: 4.4.2 PS C:\Users\jiang> adb shell shell@hwH60:/ $ su - root # 此时输入s...

    用户1221057
  • 提高性能:用RequireJS优化Wijmo Web页面

    上周Wijmo 2014 V2版本刚刚发布(下载地址),  有网友下载后发现仅仅使用了40个Widgets的一小部分,还需要加载全部的jquery.wijmo-...

    葡萄城控件
  • Flutter中的文本输入框组件TextField

    1. maxLines 最大输入行。默认为单行输入框,配置此参数后则为多行输入框;

    越陌度阡
  • 拒绝千篇一律 我有我的个性

    “ 地图服务快速发展的今天,千篇一律的地图样式已经无法满足开发者的需求了。各行各业的开发者都有自己特有的、针对不同行业特性的地图样式诉求,比如做共享单车的希望...

    腾讯位置服务
  • 学界 | 北邮夺冠CVPR 2018 DeepGlobe比赛,他们是这样做卫星图像识别的

    在刚刚结束的CVPR2018: DeepGlobe Road Extraction Challenge(全球卫星图像道路提取)比赛中,北京邮电大学信息与通信工程...

    大数据文摘
  • Java并发之死锁实例

    项目地址:https://github.com/windwant/threadtest

    WindWant

扫码关注云+社区

领取腾讯云代金券