只做dnf的网站,规划馆网站建设,谷歌网站入口,平面设计能做什么工作#xff08;一#xff09;问题的引出
在组合数学、经济学、计算机科学中#xff0c;稳定婚姻问题#xff08;英语#xff1a;stable marriage problem#xff0c;简称SMP#xff09;又称为稳定配对问题#xff08;stable matching problem#xff09;#xff0c;是指…一问题的引出
在组合数学、经济学、计算机科学中稳定婚姻问题英语stable marriage problem简称SMP又称为稳定配对问题stable matching problem是指在两组同样大小的元素集合中例如集合1是男子组、集合2是女子组而他们各有偏好寻求一个稳定配对组合所遇到的问题。一个组合在以下情况下并不稳定 在集合1中有一个元素A更偏好于集合2的一些元素B但元素A已被配对而元素B亦更偏好于元素A多于配对给他的元素。在男女婚姻的角度来说可以写成一名男子A获安排与女子D结婚但A实际上是更喜欢女子B的。反之女子B亦被安排与男子C结婚但B实际上也是更喜欢A的。 简单来说一个稳定的组合是指在任何一个组合中含A及B每一个元素都是最偏好目前的组合多于任何其他的元素。亦即是说稳定婚姻配对是指在同等数量男女当中每一名男子皆能与自己最喜欢的女子结婚反之亦然。然而这个配对方式却引来不少难题。
有两对夫妻M1 F2M2 F1。M1心目中更喜欢F1但是他和F2结婚了M2心目中更喜欢F2但是命运却让他和F1结婚了显然这样的婚姻是不稳定的随时都可能发生M1和F1私奔或者M2和F2私奔的情况。所以在做出匹配选择的时候也就是结婚的时候我们需要做出稳定的选择以防这种情况的发生。
二算法介绍
参考http://www.matrix67.com/blog/archives/2976
1962 年美国数学家 David Gale 和 Lloyd Shapley 发明了一种寻找稳定婚姻的策略。不管男女各有多少人不管他们各自的偏好如何应用这种策略后总能得到一个稳定的婚姻搭配。换句话说他们证明了稳定的婚姻搭配总是存在的。有趣的是这种策略反映了现实生活中的很多真实情况。
算法中采用了男生主动追求女孩的形式。算法步骤描述第一轮每个男人都选择自己名单上排在首位的女人并向她表白。这种时候会出现两种情况1该女士还没有被男生追求过则该女士接受该男生的请求。2若该女生已经接受过其他男生的追求那么该女生会将该男士与她的现任男友进行比较若更喜欢她的男友那么拒绝这个人的追求否则抛弃其男友囧……第一轮结束后有些男人已经有女朋友了有些男人仍然是单身。在第二轮追女行动中每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个并向她表白不管她现在是否是单身。这种时候还是会遇到上面所说的两种情况还是同样的解决方案。直到所有人都不在是单身。怎么证明这个算法肯定能够得到稳定的婚姻
1随着轮数的增加总有一个时候所有人都能配上对。因为男生根据自己心目中的排名依次对女士进行表白假如有一个人没有配上对那么这个人必定是向所有的女孩进行表白了。但是女孩只要被表白过一次就不可能是单身也就是说此时所有的女生都不是单身的这与有一个人没有配上对是相悖的。所以假设不成立。该算法一定会使得所有人都能够配对成功。
2随着轮数的增加男士追求的对象越来越糟而女士的男友则可能变得越来越好。假设男A和女1各有各自的对象但是比起现在的对象男A更喜欢女1所以在此之前男A肯定已经跟女1表白过的并且女1拒绝了男A也就是女1有了比男A更好的男友不会出现私奔的情况……。
———————————————— 版权声明本文部分转自CSDN博主「csc_csc_csc」的原创文章遵循CC 4.0 BY-SA版权协议转载请附上原文出处链接及本声明。 原文链接https://blog.csdn.net/cscmaker/article/details/8291131
