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

维特容易

一些朋友喜欢看江苏卫视的《非诚勿扰》，不过在里面，四五个男生对二十四个姑娘，磨磨唧唧一个多小时，还常常配对失败……死理性派表示：给我100 个男人100个女人，就可使其一一配对，还不会有人私奔。
' o) r# t$ k% q" Y4 I( X( L/ |* ^听起来很扯吧？然而数学家们可是切切实实地研究过这个问题哦。这就是所谓的稳定匹配问题(Stable Marriage Problem，也叫稳定婚姻问题）。
1 c9 c# g6 [- m8 N5 O+ u( M. c) X先对意中人排个名要进行速配，当然要考虑男女双方的意愿。不幸的是，要让每一个人都刚好能和自己最喜欢的人在一起基本上是不可能的（所以才有那么多三角恋多角恋啊），总不免有人最终得不到自己最爱的那个TA，这时候他就不得不考虑“第一喜欢”的人、“第六喜欢”的人……所以，每个人都必须将对面的100个异性按最喜欢到最不喜欢排个序，不妨称之为“偏爱序”。
, A# `4 j2 G$ E" i  Y1 G+ o然后就能按照所有人进行速配了，而且这个速配是稳定的，不会出现“私奔”的情况呢。
什么是不稳定，有人曾用一句不太雅但很形象的话来描述：不稳定婚姻意味着不但我家要有一枚奸夫，你家还要有一只淫妇才行。也就是说，A男喜欢B女胜过自己的妻子，同时B女喜欢A男胜过自己的丈夫，然后他们就私奔了。
在这场速配中，如果出现私奔，那它就是不稳定婚姻，反之则为稳定婚姻。
怎样速配：Gale & Shapley 方法其实早在1962年，美国数学家戴维·戈尔（David Gale）和劳埃德·夏普利（Lloyd Shapley）就解决了这个问题。他们的思路是这样的：
第一天
: G  Z5 W6 B, \8 @$ n: C0 M上午，所有的男人都向自己最爱的女人求婚。
下午，每个女人清点自己的求婚列表。如果只收到一个男人的求婚，那么就和他订婚。如果收到多于一个男人的求婚，那么就和其中她最爱的那个男人订婚，同时把其他男人都拒绝掉。如果一个求婚都没有，不要着急，最后总会有的。
* p9 J8 z0 T5 ^晚上，检查一遍，如果所有女人都订婚了，那么，万事大吉，第二天举行集体婚礼。
* n9 a8 q1 k& d5 k, L但如果还有女人没有订婚，那么事情还没完，第二天继续。
9 p- T! M  b# @6 Z3 w/ V% h第二天
上午，所有还没订婚的男人向自己次爱的女人求婚。（昨天他们已经被最爱拒绝了）
  {+ t* e; X  M+ \: j下午，每个女人再看一遍自己收到订婚的情况。如果她已经订婚了，但是又有一个她更爱的男人来向她求婚，那就把原来那个拒绝掉，再和这个更爱的男人订婚；如果还没订婚，那就和第一天的下午的处理一样。
! y$ |  ]) r8 [* x4 R2 e: a晚上再检查一遍，如果还是有人没有订婚，那第三天再重复。
& }4 I9 S; J/ H) H& j第三天
3 }+ z- @& k- Y: x; [* f上午，所有没有订婚的男人，包括第一天订了第二天又被踹出来的，再向还没有拒绝过他的女人中他最爱的那个求婚。
- m3 V) m, W2 }" M9 ~% X如此周而复始，直到最后大家都订了婚，就举行集体婚礼。
这是一个对男人有利的速配法直觉上，女性在这个匹配算法中貌似更有优越感——男人们来向自己求婚，自己可以挑选一个自己最喜欢的。而男人们很可能会屡屡被拒。
那么这个算法是否真的是对女性比较有利呢？让我们分别考察男人和女人如何才能得到自己的最喜欢的人。设A男要得到他最喜欢的B女，首先要看还有多少别的男人同时也喜欢B，然后再与这些情敌竞争。而女人是否能与最喜欢的男人结婚，首先就要看她自己在对方的偏爱序中排老几，也就是说，一开始她就要和所有的同性竞争了。
0 I/ D8 |0 q2 ^% t' A; ~在这个算法里，男人相比女人最大的优势就是他是主动的一方，即使像樱木花道一样被拒了50次，仍然可以追求他喜欢的晴子。你也许会说，漂亮的女生肯定会有很多男人追啊。话是没错，可是她心中的那个他不喜欢自己，那再多的追求者也枉然啊。
所以啊，姑娘们要想要好GG，还是得自己主动啊。
  附：Gale & Shapley 方法的合理性说明
7 u# R2 ~/ i" I" Z) a算法的可终止性可证：每个男人按照自己的偏爱序一个个求婚下来，一定有一个女人会要他——试想一个男人被一百个女人拒绝掉了，那他的偏爱序中已经没有人可以求婚了，所以他得不到配对，对应地对面也肯定有一个剩女，可是这个剩女曾经拒绝过他呀，也就是说她有更好的追求者呀，她怎么可能成为剩女呢？
算法的正确性也可证：假设有A男和B女私奔了。那么A在B的偏爱序中必然比B的丈夫靠前，按照算法，女人最后选择的一定是所有向她求婚的男人中她最喜欢的，这就是说A没有向B求过婚（要不然B选的就是他了）。然而，男人是按照自己的偏爱序依次求婚的，而A又喜欢B甚于自己的老婆，所以A又必然向B求过婚。推出矛盾，故不可能出现私奔。
, I* h- m' c2 T2 [编辑的话速度固然重要，不过合适的才是最好的。理工男女多奇志，到底哪款适合你？来 理工男女配对 测测就知道。

过渡一下！

这大半夜的 ... 不管怎么说我先沙发一个吧 ...
看完这篇东西唯一的感想就是 ... 如果感情是可以理性计算的该多好 ...
多简单的一个过程 ... if then else ... 在知道足够多数据的前提下 ... 起因经过结果都是可推算的 ...
8 k( M; d* |- X3 j  U% q* w一方弯腰伸手 ... 一方行礼接受 ... 哪儿还会发生什么为情所困的事儿来 ...
但说来如果感情这个东西无法迷惑人和扰乱人 ... 不是无法推测的 ... 那也就不叫感情了 ...
, v2 p& e  }+ \* Q说回这个算法 ... 我倒觉得这个算法是偏向女性的 ...
男性角色好高骛远 ... 在稳定之前随时面临被更好的人替代掉 ... 心理上多大危机与压力 ...
而女性是守株待兔 ... 在稳定之前随时面临遇到更好的人 ... 心理上多大幸福与期待 ...
虽然最后结果一样 ... 两方得到的都是他们和她们能得到的最好的 ...
但 退而求其次 和 邂逅更好的他 这可不是一个概念的事儿 ... 主动是需要付出代价滴 ...
7 ]; r: \: {1 b8 E' e$ {在一场追逐的游戏里总得有人先停下来 ... 找不到自己最爱的就找个特别特别爱自己的也不错 ...
我似乎扯远了 ... 我真就只是想抢个沙发而已 ...
顺便吐个槽 ... 那张题图 ... 越看越觉得充满了微妙的萌点 ... 难以形容啊 ...
$ h8 J- v4 Q' a. L基础的意思是男人的爱都在心里而女人的爱都在 ... 额 ... 那个啥 ... 么 ..?

岸上的水草

http://songshuhui.net/archives/9259  by  木遥
“它是对男生最优的。也就是说，对每个男生来说，按照这种方式最后找到的伴侣，是在所有的稳定组合中自己可能具有的伴侣中自己评价最高的。——注意这并不等于说被个男生都能追到自己最喜欢的女生，而只是说，他一定能追到“有可能和他在稳定组合中在一起的女生”中自己最喜欢的。有些女生虽然很好，但是和他在一起是不可能形成稳定组合的。这就是人生啊……
9 }! v4 e8 I5 _' C# X+ z. z另一方面，它是对女生最劣的。也就是说，对每个女生来说，按照这种方式最后找到的伴侣是在所有的稳定组合中自己可能具有的伴侣中自己评价最低的。同样的，这也不等于说每个女生都只有和自己最不喜欢的男生在一起，而只是说她最后的男朋友会是所有“有可能”的男生中自己觉得最勉强的。不过这样听起来也已经很悲惨了。”

e9165

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