标签： 情人节

趁着情人节的气氛，给大家介绍一个有趣的问题：稳定婚姻问题，青春期的GGMM一定要看…hehe会有收获的^^
这个问题曾在一个OIER的空间里看到过，他讲得是班级的男女生谈朋友的配对==….其实就是这个问题，可惜现在找不到那个空间了orz…不过这两天发现科学松鼠会的一篇文章我要我们在一起介绍了这个问题，于是自己修改了下，来给GGMM们上课啦，有空还准备编个程玩玩。
(PS:以前还讨论过最佳约会策略(摘取最大麦穗)，也推荐青春期的GGMM去受教~~)

稳定婚姻问题The Stable Marriage Problem最早是由两个美国数学家David Gale&Lloyd Shapley于1962年在American Mathematical Monthly上提出的，这个问题和图论有关(求完全二分图的稳定完备匹配，这是一个NP问题)。对于以前没有接触过这个问题的人，这个理论最出人意外的结论是：传统的求爱、结婚过程是male-optimal(男生主动)的，也就是说，男性能够得到尽可能好的心上人，女性却不然。这里我们就不科普了，直接上问题：

对于以上两个的问题的答案当然是肯定的。Gale 和Shapley不但提出了这个问题本身，而且给出了一种著名的解法Gale-Shapley算法(延迟认可算法)。
激动人心求婚过程是这样进行的(如果觉得太快了的话，那就认为是表白吧)：
第一天，让这些男生去向他们最心仪的女生表白。等所有男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了，不要着急，表白会有的。以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。
第二天还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白(无论人家是否已经有了男朋友)，然后，等所有单身男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友而表白者中有自己更喜欢的，不要犹豫，换之。等到尘埃落定之后，再开始如上所述的新的一轮表白。
依此类推。可以证明的是，这个过程一定是会终止的，也就是说，不会陷入任何死循环。并且一旦终止，每个人都会找到一个伴侣。更关键的是，这个过程最终得到的一定是如前所述的“稳定组合”。

真正有趣的部分还在后面。 继续阅读“情人节特别课堂: 稳定婚姻问题”