BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ mo (叉烧包) 于 (Mon Nov 6 11:08:53 2006) 提到: 不知道有没有人在这个BBS上讲过这个问题. 这个理论比较奇特, 但是和排骨那些BT理论不同的是, 这个是数学界切切实实研究过的问题. 对于以前没有接触过这个问题的人, 这个理论最出人意外的结论是: 传统的求爱, 结婚过程是male-optimal的, 也就是说, 男性能够得到尽可能好的心上人, 女性却不然. 这个问题和图论有关, 最早是由两个美国数学家1962年在American Mathematical Monthly上提出的, 相关的参考文献其实很多, 下面这个网页大概是讲得最通俗易懂的: http://www.cs.columbia.edu/~evs/intro/stable/writeup.html 俺可以在这里大概讲一下. 假设有一百个男人和一百个女人, 每个男人都凭自己好恶给每个女人打分, 我最爱a, 其次爱b, 再次爱c...每个男人打的分不同, 你最爱的可能是我最讨厌的, 我最爱的可能是他不甚喜欢的. 每个女人也同样给每个男人打分. 然后就是求婚过程. 第一天上午, 所有的男人都向自己最爱的女人求婚. 下午, 每个女人看看自己有没有收到, 收到了多少人的求婚. 如果只收到一个男人的求婚, 那么就和他订婚. 如果收到多于一个男人的求婚, 那么就和其中她最爱的那个男人订婚, 同时把其他男人都锯掉. 如果一个求婚都没有, 不要着急, 最后总会有的. 晚上, 检查一遍, 如果所有女人都订婚了, OK, 万事大吉, 明天举行集体婚礼. 但如果还有女人没有订婚, 那么事情还没有完, 第二天还得重复. 第二天上午, 所有还没订婚的男人向自己次爱的女人求婚(因为昨天已经被他们的最爱锯了). 下午, 每个女人再看一遍自己收到订婚的情况. 如果她已经订婚了, 但是又有一个她更爱的男人来向她求婚, 那就把原来那个锯掉, 再和这个更爱的男人订婚; 如果还没订婚, 那就和第一天的下午的处理一样. 晚上再检查一遍, 如果还是有人没有订婚, 那第三天再重复. 第三天上午, 所有没有订婚的男人, 包括第一天订了第二天又被踹出来的, 再向还没有锯过他的女人中他最爱的那个求婚 ... 如此周而复始, 直到最后大家都订了婚, 便一起结婚. 这么个过程, 数学上可以证明: 第一, 这个过程会中止, 也就是说, 总有大家都订了婚的一天, 不可能无限循环. 第二, 中止后所有的婚姻是稳定婚姻. 所谓不稳婚姻是说, 比如说有两对夫妇M1, F1和M2, F2, M1的老婆是F1, 但他更爱F2; 而F2的老公虽说是M2. 但她更爱M1, 这样的婚姻就是不稳婚姻, M1和F2理应结合, 他们现在各自的婚姻都是错误. 我们能证明的是, 通过上面那个求婚过程, 所有的婚姻都是稳定的, 没有人犯错误. 第三, 比较引人注目的是, 这个过程是male-optimal的, 男性能够获得尽可能好的伴侣, 比如说最后有二十个女人拒绝了他, 他仍然能够得到剩下的八十个女人中他最爱的那一个. 第四, 更有甚者, 这个过程是female-pessimal的, 女人总是在可能的情况下被最不喜欢的人追上. 这一点没有那么直观的理解, 勉强要解释的话, 可以这么看: 虽说女人每换一次订婚对象, 都往上升一层, 但起点可能很低, 虽说在一步步接近她最爱的目标, 但最后往往达不到. 比如说还差三十名就达到她最爱的人了, 但这时Game Over, 所有的人都已订了婚, 这样她也只能死了心了. 还有三十个她更爱的人还没向她求过婚, 可是她也无可奈何了... 俺们上算法课的时候有一整节课专讲这个问题, 上完课男生一个个眉花眼笑, 不过女生们的嘴撅得可以挂酱油瓶了... 课后哥们几个聊起来, 这个理论给mm们的最大教训是, 想要好gg, 自己就得主动. ☆─────────────────────────────────────☆ CO0LFANTASY (Cool) 于 (Mon Nov 6 11:17:08 2006) 提到: 【在 mo (叉烧包) 的大作中提到: 】 : 标题: 稳定婚姻(Stable Marriage Problem) [转帖] : 发信站: 北邮人论坛 (Mon Nov 6 11:08:53 2006), 站内 : : : : 不知道有没有人在这个BBS上讲过这个问题. 这个理论比较奇特, : 但是和排骨那些BT理论不同的是, 这个是数学界切切实实研究过 : 的问题. 对于以前没有接触过这个问题的人, 这个理论最出人意 : 外的结论是: 传统的求爱, 结婚过程是male-optimal的, 也就是 : 说, 男性能够得到尽可能好的心上人, 女性却不然. : : 这个问题和图论有关, 最早是由两个美国数学家1962年在American : Mathematical Monthly上提出的, 相关的参考文献其实很多, 下 : 面这个网页大概是讲得最通俗易懂的: : : http://www.cs.columbia.edu/~evs/intro/stable/writeup.html : : 俺可以在这里大概讲一下. 假设有一百个男人和一百个女人, 每 : 个男人都凭自己好恶给每个女人打分, 我最爱a, 其次爱b, 再次 : 爱c...每个男人打的分不同, 你最爱的可能是我最讨厌的, 我最 : 爱的可能是他不甚喜欢的. 每个女人也同样给每个男人打分. : : 然后就是求婚过程. : : 第一天上午, 所有的男人都向自己最爱的女人求婚. : : 下午, 每个女人看看自己有没有收到, 收到了多少人的求婚. 如 : 果只收到一个男人的求婚, 那么就和他订婚. 如果收到多于一个 : 男人的求婚, 那么就和其中她最爱的那个男人订婚, 同时把其他 : 男人都锯掉. 如果一个求婚都没有, 不要着急, 最后总会有的. ~~~~~~~好可怕。。。。 : : 晚上, 检查一遍, 如果所有女人都订婚了, OK, 万事大吉, 明天 : 举行集体婚礼. : : 但如果还有女人没有订婚, 那么事情还没有完, 第二天还得重复. : : 第二天上午, 所有还没订婚的男人向自己次爱的女人求婚(因为 : 昨天已经被他们的最爱锯了). : : 下午, 每个女人再看一遍自己收到订婚的情况. 如果她已经订婚 : 了, 但是又有一个她更爱的男人来向她求婚, 那就把原来那个锯 : 掉, 再和这个更爱的男人订婚; 如果还没订婚, 那就和第一天的 : 下午的处理一样. : : 晚上再检查一遍, 如果还是有人没有订婚, 那第三天再重复. : : 第三天上午, 所有没有订婚的男人, 包括第一天订了第二天又被 : 踹出来的, 再向还没有锯过他的女人中他最爱的那个求婚 : : ... : : 如此周而复始, 直到最后大家都订了婚, 便一起结婚. : : 这么个过程, 数学上可以证明: : : 第一, 这个过程会中止, 也就是说, 总有大家都订了婚的一天, : 不可能无限循环. : : 第二, 中止后所有的婚姻是稳定婚姻. 所谓不稳婚姻是说, 比 : 如说有两对夫妇M1, F1和M2, F2, M1的老婆是F1, 但他更爱F2; : 而F2的老公虽说是M2. 但她更爱M1, 这样的婚姻就是不稳婚姻, : M1和F2理应结合, 他们现在各自的婚姻都是错误. 我们能证明 : 的是, 通过上面那个求婚过程, 所有的婚姻都是稳定的, 没有 : 人犯错误. : : 第三, 比较引人注目的是, 这个过程是male-optimal的, 男性 : 能够获得尽可能好的伴侣, 比如说最后有二十个女人拒绝了他, : 他仍然能够得到剩下的八十个女人中他最爱的那一个. : : 第四, 更有甚者, 这个过程是female-pessimal的, 女人总是 : 在可能的情况下被最不喜欢的人追上. 这一点没有那么直观的 : 理解, 勉强要解释的话, 可以这么看: 虽说女人每换一次订婚 : 对象, 都往上升一层, 但起点可能很低, 虽说在一步步接近她 : 最爱的目标, 但最后往往达不到. 比如说还差三十名就达到她 : 最爱的人了, 但这时Game Over, 所有的人都已订了婚, 这样 : 她也只能死了心了. 还有三十个她更爱的人还没向她求过婚, : 可是她也无可奈何了... : : 俺们上算法课的时候有一整节课专讲这个问题, 上完课男生一个 : 个眉花眼笑, 不过女生们的嘴撅得可以挂酱油瓶了... : : 课后哥们几个聊起来, 这个理论给mm们的最大教训是, 想要好gg, : 自己就得主动. : -- : 他们那些做上帝的，虽然不能让每个生命无虑地活着，但会尽力让每个生命无怨的死去。 : 我们这些做程序员的，虽然不能让每个程序无错地运行，但会尽力让每个程序无悔地结束。 : : ※ 来源:·北邮人论坛 http://forum.byr.edu.cn·[FROM: 59.64.152.*] ☆─────────────────────────────────────☆ hhllnnnn (Bomb) 于 (Mon Nov 6 17:08:54 2006) 提到: Orz~~ ☆─────────────────────────────────────☆ ReLive (223守护神) 于 (Mon Nov 6 19:30:28 2006) 提到: 当年做过这个的程序实现可惜代码没留着…… ☆─────────────────────────────────────☆ linandmin (吃饭是人生第一大事－－－《星星语录》) 于 (Mon Nov 6 22:56:00 2006) 提到: 确实好可怕【在 CO0LFANTASY 的大作中提到: 】 : ~~~~~~~好可怕。。。。 ☆─────────────────────────────────────☆ pseudocodes (伪代码) 于 (Wed Nov 8 07:18:08 2006) 提到: 果然很可怕

[合集] 稳定婚姻(Stable Marriage Problem) [转帖]