The Stable Marriage Problem

时间:2021-12-30 23:02:54

经典稳定婚姻问题

“稳定婚姻问题(The Stable Marriage Problem)”大致说的就是100个GG和100个MM按照自己的喜欢程度给所有异性打分排序。每个帅哥都凭自己好恶给每个MM打分:我最爱a,其次爱b,再次爱c...每个帅哥打的分不同,你最爱的可能是我最讨厌的我最爱的可能是他不甚喜欢的。同样,每个美女也同样给每个帅哥打分。现在需要给他们搭配出100对新郎新娘,并且要保证所得到是稳定婚姻的搭配。那么,什么是不稳定的婚姻呢?所谓不稳婚姻是说, 比如说有两对夫妇(M1、F1)和(M2、F2),M1的老婆是F1,但他更爱F2;而F2的老公虽说是M2,但她更爱M1——这样的婚姻就是不稳婚姻,M1和F2理应结合,他们现在各自的婚姻都是错误。
那么,开始激动人心求婚过程啦
第一天上午, 所有的男生都向自己最爱的美眉求婚。下午,每个MM看看自己有没有收到, 收到了多少人的求婚。如果只收到一个男生的求婚,那么就和他订婚。如果收到多于一个GG的求婚,那么就和其中她最爱的那个男人订婚,同时把其他男人都拒掉。如果一个求婚都没有,不要着急,最后总会有的。晚上,检查一遍,如果所有MM都订婚了,OK,万事大吉,明天举行集体婚礼!
但如果还有人没有订婚,那么事情还没有完,第二天还得重复。
第二天上午,所有还没订婚的男生向自己次爱的美眉求婚(因为昨天已经被他们的最爱拒绝了)下午,每个MM再看一遍自己收到订婚的情况。如果她已经订婚了,但是又有一个她更爱的男人来向她求婚,那就把原来那个拒绝掉,再和这个更爱的男人订婚;如果还没订婚,那就和第一天的下午的处理一样。晚上再检查一遍,如果还是有人没有订婚,那第三天再重复。
第三天上午,所有没有订婚的GG,包括第一天订了第二天又被踹出来的(看来要有点忧患意识),再向还没有拒绝过他的MM中他最爱的那个求婚
......
如此周而复始,直到最后大家都订了婚,便一起结婚!哈哈,恭喜恭喜