JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
问题来自于一场“3分钟相亲”活动,参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流,并为她们打分,然后按照喜欢程度,对每一位女士进行排序;同样的,每位女士也要对所有男士进行打分和排序。
在这之后我们为选择策略为这n位男士和n位女士配对。使得在婚后不会有“出轨”的情况发生。
这里的“出轨”是什么意思:图片来自网络,仅作举例之用

如果以下两种情况之一发生,则会发生出轨:
  1. 如果第一对夫妻中的妻子在婚后觉得自己的丈夫没有第二对夫妻中的丈夫帅;第二对夫妻中的丈夫同样也觉得自己的妻子没有第一对夫妻中的妻子漂亮
  2. 如果第一对夫妻中的丈夫在婚后觉得自己的妻子没有第二对夫妻中的妻子美;第二对夫妻中的妻子同样也觉得自己的丈夫没有第一对夫妻中的丈夫帅
解决稳定婚姻的算法之一:
延迟认可算法(Gale-Shapley算法)
先对所有男士进行落选标记,称其为自由男。当存在自由男时,进行以下操作:
  1. 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士;
  2. 每一位女士将正在追求她的自由男与其当前男友进行比较,选择其中排名优先的男士作为其男友,即若自由男优于当前男友,则抛弃前男友;否则保留其男友,拒绝自由男。
  3. 若某男士被其女友抛弃,重新变成自由男。
在算法执行期间,自由男们主动出击,依次对最喜欢和次喜欢的女人求爱,一旦被接受,即失去自由身,进入订婚状态;而女人们则采取“守株待兔”“喜新厌旧”策略,对前来求爱的男士进行选择:若该男子比未婚夫强,则悔婚,选择新的未婚夫;否则拒绝该男子的求婚。被女友抛弃的男人重获自由身,重新拥有了追求女人的权利——当然,新的追求对象比不过前女友。
这样,在算法执行期间,每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱,从一而终——每订一次婚,女人们的选择就会更有利,而男人们的品味则越来越差。只要男女生的数量相等,则经过多轮求婚,订婚,悔婚和再订婚之后,每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱(男人没能追到自己的最爱,或女人没有等到自己的最爱来追求),但绝对不会出现“虽然彼此相爱,却不能在一起”的悲剧,所有人都会组成稳定的婚姻。
posted on 2015-03-09 18:57 JulyRina 阅读(148) 评论(0)  编辑 收藏 引用 所属分类: 算法专题

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理