数学

单身男女不用慌,死理性派让你们成功速配

速配怎么才能成功?速配有可能成功吗?怎么才能找到最适合自己的人?稳定婚姻法

万俟麻木 发表于  2011-04-19 02:14

一些朋友喜欢看江苏卫视的《非诚勿扰》,不过在里面,四五个男生对二十四个姑娘,磨磨唧唧一个多小时,还常常配对失败……死理性派表示:给我100 个男人100个女人,就可使其一一配对,还不会有人私奔。

听起来很扯吧?然而数学家们可是切切实实地研究过这个问题哦。这就是所谓的稳定匹配问题(Stable Marriage Problem,也叫稳定婚姻问题)。

先对意中人排个名

要进行速配,当然要考虑男女双方的意愿。不幸的是,要让每一个人都刚好能和自己最喜欢的人在一起基本上是不可能的(所以才有那么多三角恋多角恋啊),总不免有人最终得不到自己最爱的那个TA,这时候他就不得不考虑“第一喜欢”的人、“第六喜欢”的人……所以,每个人都必须将对面的100个异性按最喜欢到最不喜欢排个序,不妨称之为“偏爱序”。

然后就能按照所有人进行速配了,而且这个速配是稳定的,不会出现“私奔”的情况呢。

什么是不稳定,有人曾用一句不太雅但很形象的话来描述:不稳定婚姻意味着不但我家要有一枚奸夫,你家还要有一只淫妇才行。也就是说,A男喜欢B女胜过自己的妻子,同时B女喜欢A男胜过自己的丈夫,然后他们就私奔了。

在这场速配中,如果出现私奔,那它就是不稳定婚姻,反之则为稳定婚姻。

怎样速配:Gale & Shapley 方法

其实早在1962年,美国数学家戴维·戈尔(David Gale)和劳埃德·夏普利(Lloyd Shapley)就解决了这个问题。他们的思路是这样的:

第一天

上午,所有的男人都向自己最爱的女人求婚。

下午,每个女人清点自己的求婚列表。如果只收到一个男人的求婚,那么就和他订婚。如果收到多于一个男人的求婚,那么就和其中她最爱的那个男人订婚,同时把其他男人都拒绝掉。如果一个求婚都没有,不要着急,最后总会有的。

晚上,检查一遍,如果所有女人都订婚了,那么,万事大吉,第二天举行集体婚礼。

但如果还有女人没有订婚,那么事情还没完,第二天继续。

第二天

上午,所有还没订婚的男人向自己次爱的女人求婚。(昨天他们已经被最爱拒绝了)

下午,每个女人再看一遍自己收到订婚的情况。如果她已经订婚了,但是又有一个她更爱的男人来向她求婚,那就把原来那个拒绝掉,再和这个更爱的男人订婚;如果还没订婚,那就和第一天的下午的处理一样。

晚上再检查一遍,如果还是有人没有订婚,那第三天再重复。

第三天

上午,所有没有订婚的男人,包括第一天订了第二天又被踹出来的,再向还没有拒绝过他的女人中他最爱的那个求婚。

如此周而复始,直到最后大家都订了婚,就举行集体婚礼。

这是一个对男人有利的速配法

直觉上,女性在这个匹配算法中貌似更有优越感——男人们来向自己求婚,自己可以挑选一个自己最喜欢的。而男人们很可能会屡屡被拒。

那么这个算法是否真的是对女性比较有利呢?让我们分别考察男人和女人如何才能得到自己的最喜欢的人。设A男要得到他最喜欢的B女,首先要看还有多少别的男人同时也喜欢B,然后再与这些情敌竞争。而女人是否能与最喜欢的男人结婚,首先就要看她自己在对方的偏爱序中排老几,也就是说,一开始她就要和所有的同性竞争了。

在这个算法里,男人相比女人最大的优势就是他是主动的一方,即使像樱木花道一样被拒了50次,仍然可以追求他喜欢的晴子。你也许会说,漂亮的女生肯定会有很多男人追啊。话是没错,可是她心中的那个他不喜欢自己,那再多的追求者也枉然啊。

所以啊,姑娘们要想要好GG,还是得自己主动啊。

 

 

附:Gale & Shapley 方法的合理性说明

算法的可终止性可证:每个男人按照自己的偏爱序一个个求婚下来,一定有一个女人会要他——试想一个男人被一百个女人拒绝掉了,那他的偏爱序中已经没有人可以求婚了,所以他得不到配对,对应地对面也肯定有一个剩女,可是这个剩女曾经拒绝过他呀,也就是说她有更好的追求者呀,她怎么可能成为剩女呢?

算法的正确性也可证:假设有A男和B女私奔了。那么A在B的偏爱序中必然比B的丈夫靠前,按照算法,女人最后选择的一定是所有向她求婚的男人中她最喜欢的,这就是说A没有向B求过婚(要不然B选的就是他了)。然而,男人是按照自己的偏爱序依次求婚的,而A又喜欢B甚于自己的老婆,所以A又必然向B求过婚。推出矛盾,故不可能出现私奔。

编辑的话

速度固然重要,不过合适的才是最好的。理工男女多奇志,到底哪款适合你?来 理工男女配对 测测就知道。

热门评论

  • 2011-04-19 03:24 Sunyanzi

    这大半夜的 ... 不管怎么说我先沙发一个吧 ...

    看完这篇东西唯一的感想就是 ... 如果感情是可以理性计算的该多好 ...

    多简单的一个过程 ... if then else ... 在知道足够多数据的前提下 ... 起因经过结果都是可推算的 ...

    一方弯腰伸手 ... 一方行礼接受 ... 哪儿还会发生什么为情所困的事儿来 ...

    但说来如果感情这个东西无法迷惑人和扰乱人 ... 不是无法推测的 ... 那也就不叫感情了 ...

    说回这个算法 ... 我倒觉得这个算法是偏向女性的 ...

    男性角色好高骛远 ... 在稳定之前随时面临被更好的人替代掉 ... 心理上多大危机与压力 ...

    而女性是守株待兔 ... 在稳定之前随时面临遇到更好的人 ... 心理上多大幸福与期待 ...

    虽然最后结果一样 ... 两方得到的都是他们和她们能得到的最好的 ...

    但 退而求其次 和 邂逅更好的他 这可不是一个概念的事儿 ... 主动是需要付出代价滴 ...

    在一场追逐的游戏里总得有人先停下来 ... 找不到自己最爱的就找个特别特别爱自己的也不错 ...

    我似乎扯远了 ... 我真就只是想抢个沙发而已 ...

    顺便吐个槽 ... 那张题图 ... 越看越觉得充满了微妙的萌点 ... 难以形容啊 ...

    基础的意思是男人的爱都在心里而女人的爱都在 ... 额 ... 那个啥 ... 么 ..?

    [28] 评论
  • 2011-04-19 03:54 Ent 古生物学博士生,科学松鼠会成员

    http://songshuhui.net/archives/9259 by 木遥

    “它是对男生最优的。也就是说,对每个男生来说,按照这种方式最后找到的伴侣,是在所有的稳定组合中自己可能具有的伴侣中自己评价最高的。——注意这并不等于说被个男生都能追到自己最喜欢的女生,而只是说,他一定能追到“有可能和他在稳定组合中在一起的女生”中自己最喜欢的。有些女生虽然很好,但是和他在一起是不可能形成稳定组合的。这就是人生啊……

    另一方面,它是对女生最劣的。也就是说,对每个女生来说,按照这种方式最后找到的伴侣是在所有的稳定组合中自己可能具有的伴侣中自己评价最低的。同样的,这也不等于说每个女生都只有和自己最不喜欢的男生在一起,而只是说她最后的男朋友会是所有“有可能”的男生中自己觉得最勉强的。不过这样听起来也已经很悲惨了。”

    [5] 评论

显示所有评论

全部评论(213)
  • 1楼
    2011-04-19 03:24 Sunyanzi

    这大半夜的 ... 不管怎么说我先沙发一个吧 ...

    看完这篇东西唯一的感想就是 ... 如果感情是可以理性计算的该多好 ...

    多简单的一个过程 ... if then else ... 在知道足够多数据的前提下 ... 起因经过结果都是可推算的 ...

    一方弯腰伸手 ... 一方行礼接受 ... 哪儿还会发生什么为情所困的事儿来 ...

    但说来如果感情这个东西无法迷惑人和扰乱人 ... 不是无法推测的 ... 那也就不叫感情了 ...

    说回这个算法 ... 我倒觉得这个算法是偏向女性的 ...

    男性角色好高骛远 ... 在稳定之前随时面临被更好的人替代掉 ... 心理上多大危机与压力 ...

    而女性是守株待兔 ... 在稳定之前随时面临遇到更好的人 ... 心理上多大幸福与期待 ...

    虽然最后结果一样 ... 两方得到的都是他们和她们能得到的最好的 ...

    但 退而求其次 和 邂逅更好的他 这可不是一个概念的事儿 ... 主动是需要付出代价滴 ...

    在一场追逐的游戏里总得有人先停下来 ... 找不到自己最爱的就找个特别特别爱自己的也不错 ...

    我似乎扯远了 ... 我真就只是想抢个沙发而已 ...

    顺便吐个槽 ... 那张题图 ... 越看越觉得充满了微妙的萌点 ... 难以形容啊 ...

    基础的意思是男人的爱都在心里而女人的爱都在 ... 额 ... 那个啥 ... 么 ..?

    [28] 评论
  • 2楼
    2011-04-19 03:29 Shiva_guokr

    大半夜板凳。。。。。。
    这个算法的缺陷就是对那些中等甚至次等的男女很不公平,缺乏选择自由。

    [0] 评论
  • 3楼
    2011-04-19 03:41 鹰之舞 生态学硕士

    很给力
    “所以啊,姑娘们要想要好GG,还是得自己主动啊。”尤赞此句

    [0] 评论
  • 4楼
    2011-04-19 03:54 Ent 古生物学博士生,科学松鼠会成员

    http://songshuhui.net/archives/9259 by 木遥

    “它是对男生最优的。也就是说,对每个男生来说,按照这种方式最后找到的伴侣,是在所有的稳定组合中自己可能具有的伴侣中自己评价最高的。——注意这并不等于说被个男生都能追到自己最喜欢的女生,而只是说,他一定能追到“有可能和他在稳定组合中在一起的女生”中自己最喜欢的。有些女生虽然很好,但是和他在一起是不可能形成稳定组合的。这就是人生啊……

    另一方面,它是对女生最劣的。也就是说,对每个女生来说,按照这种方式最后找到的伴侣是在所有的稳定组合中自己可能具有的伴侣中自己评价最低的。同样的,这也不等于说每个女生都只有和自己最不喜欢的男生在一起,而只是说她最后的男朋友会是所有“有可能”的男生中自己觉得最勉强的。不过这样听起来也已经很悲惨了。”

    [5] 评论
  • 5楼
    2011-04-19 04:07 ruooumeng

    上学期俺拿了一个课,里面就讲到了这个算法.当时只是直观地觉得,这个算法对男方有利.没想到证明其实并不复杂啊

    [0] 评论
  • 6楼
    2011-04-19 06:13 Shiva_guokr

    本质上这算法只是把男性的表达勇气给正无穷了而已。
    非对称的算法肯定对某性别不公。

    [0] 评论
  • 7楼
    2011-04-19 06:17 一醉笑江湖

    男的至少有一次机会向自己最喜欢的人表白,而且能够根据序列依次寻找下去,总能找到一个最优选择。而女的完全被动,也许从开始到最后选择的都只是最差的那个。

    [0] 评论
  • 8楼
    2011-04-19 06:20 如小妞儿 营养与食品卫生学博士

    好想问问3楼4楼神马进展了>_<
    好吧,我承认我好八啊啊=。=

    [0] 评论
  • 9楼
    2011-04-19 07:33 sb

    如果那么简单,也许也就没那么多人为之疯狂了把~

    [0] 评论
  • 10楼
    2011-04-19 07:53 暴走紫罗兰

    死理性派就是不一样啊~

    [0] 评论
  • 11楼
    2011-04-19 08:03 openmist

    速配神马的最危险了.

    [0] 评论
  • 12楼
    2011-04-19 08:22 angwuy

    经典问题了,婚姻稳定系统

    [0] 评论
  • 13楼
    2011-04-19 08:25 逆刃
    引用的回应:如果那么简单,也许也就没那么多人为之疯狂了把~

    因为我们不能拿70亿人作实验再加上信息不对称还有人是会变的....

    [0] 评论
  • 14楼
    2011-04-19 08:28 鼠标遇上猫 基因工程硕士生
    引用的回应:男的至少有一次机会向自己最喜欢的人表白,而且能够根据序列依次寻找下去,总能找到一个最优选择。而女的完全被动,也许从开始到最后选择的都只是最差的那个。

    这个解释容易懂,俺太笨了

    [0] 评论
  • 15楼
    2011-04-19 08:33 吉良吉影

    每次看《非》不超过五分钟就会浑身起鸡皮疙瘩,为神马啊为神马

    [0] 评论
  • 16楼
    2011-04-19 08:47 无文的默默
    引用的回应:很给力“所以啊,姑娘们要想要好GG,还是得自己主动啊。”尤赞此句

    +1

    [0] 评论
  • 17楼
    2011-04-19 08:56 zuojiang6368

    楼主辛苦了,大半夜的写文章。
    其实关于男女配对不用那么辛苦,我们团队正在做的婚恋网站就可以轻易实现一对一配对。
    如意爱恋网,提供免费的在线相亲服务。单身宅男宅女可以试试。保证为国家节电省纸。

    [0] 评论
  • 18楼
    2011-04-19 09:20 浙大龙 植物控兼生态学博士

    ls有广告

    [0] 评论
  • 19楼
    2011-04-19 09:22 深深深蓝

    好强啊……

    [0] 评论
  • 20楼
    2011-04-19 09:30 被感动的洛都图斯

    我想知道,如果100个男女中间混入奇数个同性恋该怎么算?……

    [0] 评论
  • 21楼
    2011-04-19 09:39 queserasera

    女生主动,还得学会见好就收,否则。。。伤的几率比男人高。。。因为我还是觉得女人更是情感动物。。。这个不科学也不全面,俺知道。。。

    [0] 评论
  • 22楼
    2011-04-19 09:40 Norz

    "如果只收到一个男人的求婚,那么就和他订婚。"
    ...這...憑什麼,必須一定要結婚?

    [0] 评论
  • 23楼
    2011-04-19 09:48 wheeler 软件工程师

    FACEBOOK 的 在线测试 算法题。。 想当年我为了这题 推出了这么个配对模型 给它起名稳定婚姻理论。。 结果它真的叫这名

    [0] 评论
  • 24楼
    2011-04-19 10:02 弗洛伊德爆炸物

    配对和私奔好像是两个命题,这个矛盾不成立。

    [0] 评论
  • 25楼
    2011-04-19 10:03 yiran

    坚决反对楼主,感情是不能太理性的!

    [0] 评论
  • 26楼
    2011-04-19 11:27 yux 环境工程专业,图书主编
    引用的回应:很给力“所以啊,姑娘们要想要好GG,还是得自己主动啊。”尤赞此句

    这句好

    [0] 评论
  • 27楼
    2011-04-19 11:53 CiengGingvuj

    我想知道Sheldon和Amy速配的那个网站的算法。。。

    [0] 评论
  • 28楼
    2011-04-19 11:53 小青

    http://songshuhui.net/archives/9259

    如果仔细思考上面所描述的规则,会看到男生至少有一样优势——也许是至关重要的优势:他们是主动方。主动的好处是,即使一次又一次的被拒,他也仍然可以和剩下的女生中自己最喜欢的在一起。而对于女生来说,纵然有再多挑选的自由,可是一个女生也许永远也等不到自己最喜欢的男生来追自己——或者在她等到之前,游戏就已经结束了。

    在一切古典文学的叙事里,我们都满怀着希望注视着那些勇敢的孩子们,看着他们的努力和坚持,也许最后会失败,可是他们至少尝试过。

    现在连数学也在帮着说明这个道理了,你还等什么呢?

    [0] 评论
  • 29楼
    2011-04-19 12:04 DDVP

    这个要创造机会组织个小规模的试试……

    [0] 评论
  • 30楼
    2011-04-19 12:05 小园听风 医学硕士生

    感情是可以用理性来调剂的~~~

    引用的回应:坚决反对楼主,感情是不能太理性的!
    [0] 评论

显示所有评论

你的评论

登录 发表评论

万俟麻木
万俟麻木 数学控 程序猿

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区