其实这个东西比较好玩……
意义比较深远……
尤其是对广大屌丝和穷搓矮和魔法师而言……
这个问题在组合数学第9章出现
问的是:
n男n女,每个男的对每个女的有一个评分,每个女的对每个男的有一个评分,然后……
他们两两配对……
当然结婚以后有可能不幸福,所以希望找到一种配对方案,满足
不存在这样的一对(狗)男女,他们不在一起,同时对对方的评分比对自己配偶高……如果这样他们就会私奔啊私奔~~~~
这个很明显是二分图,但是不是单纯的二分图……
有一个Gale-Shapley算法(应该是叫这两个名字的两个人提出的),又称延迟认可算法
有两种做法,一种男性最优,一种女性最优
以男性最优为例:
①每一个男生向自己评分最高且没拒绝过自己的女性求婚(有可能有女性获得多个人的求婚)
②如果有女性获得多个人的求婚(即使已经订婚),那么挑选自己评分最高的,与其订婚,拒绝其他人
注意在②中,如果有女性已经订婚,那么她会比较订婚的人和向自己提出请求的人,选择评分高的那一个(这就是为什么是“订婚”而非结婚)
算法的正确性随便google一下就有
我想说的是为什么这个方案男性最优……一开始我也没太弄清
这与我们平常的观念不符——如果一个女生很受欢迎,那么她更容易挑到自己满意的人
但是有一点,有可能女生心仪的男生并不喜欢她,因此没能向她求婚
举个例子,有可能n个男生互相不是情敌,那么第一轮求婚以后,算法就结束了,此时每个男生都心满意足,而女生不一定……
然后接下来每次男生求婚都是挑的他觉得最好而且自己有机会的,而女生等啊等有可能都等不到想要的那个人……
而且需要注意的是稳定婚姻问题一定有解(就像屌丝最终会找到一个黑木耳……)
这给我们一个启示……手快有手慢无,一定要主动啊主动~~~~
特别说明以上对基佬不适用……(说不定也适用??)
题目有POJ3487,ZOJ1576,NOJ1710(南开大学OJ……第一次听说)
题目都差不多,都是裸的,输入的处理可能麻烦点(ZOJMS最麻烦,得用map……虽然实际上也比较好写)
POJ3487code:
//其实在处理被拒绝的男生的时候可以开队列,应该可以加快速度,但是事后才想起,就算了……反正数据范围小……
//在处理字符这一点上自认为写的很丑……暴丑……其实可以把数组开大,就可以不用减'A'了,当时有点脑残……
分享到:
相关推荐
稳定婚姻问题 算法 代码 匹配 思考 学习
该问题可解决n男n女配对问题:每个人有自己理想对象排名,而要使配对后不存在一对男女不是配偶且对于彼此的好感优于当前配偶。 算法流程: 1.每一轮未订婚的男士向其未求过婚的女士求婚; 2.女士若有男士X向其...
介绍了稳定婚姻问题和解决该问题的回溯法;在回溯法的基础上提出了改进算法回跳法;从理论上和实验上证明了回跳法的效率远高于回溯法的效率。
单身男女的稳定婚姻匹配 ,用c++实现,gale算法。
稳定婚姻匹配问题,典型算法题,Stable marriage matching problem typical algorithm problem
图论- 稳定婚姻问题与延迟认可算法.rar
稳定婚姻匹配 算法作业
数据结构实验报告-稳定婚姻匹配问题.doc
在Scala和Ruby中实现的稳定婚姻问题变体_Ruby_Scala_源码_下载.zip
基于稳定婚姻算法的时域匹配频谱接入方案研究,刘帅军,李博,随着移动通信的快速发展,频谱紧缺问题日益突出,认知无线电通过机会式占用空闲频谱可有效改善频谱紧缺问题。本文旨在针对认知无
【资源说明】 1、该资源内项目代码都是经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计...基于稳定婚姻算法和cloudsim框架的云计算任务调度模拟Java源码(本科毕设).zip
稳定婚姻算法 这是Python中的的实现,是在佐治亚理工学院了解CS 2051中的问题后实施的。
媒体云转码的演进:MapReduce、DASH 与稳定婚姻.pdf
此实现是在获得 publicatoin (Permission of publishingpdf) 许可的情况下对作业 (Homework1.pdf) 中问题 1 的回答。 每个文件的简要说明: InputGenerator.m:它在一个文本文件中提供了 n * n 两个随机的男性和...
给定N个男人和N个女人,以及他们每个人对异性成员的偏好,稳定匹配是N个男人和女人之间的匹配,使得没有男人和女人更喜欢彼此伙伴。 Gale-Shapley 算法确定了这种稳定的匹配。 根据配方,它提供男性最佳或女性最佳...
文章利用 2018 年中国家庭追踪调查数据(CFPS),采用对角参照 模型分析教育婚姻匹配模式对夫妻婚姻满意度的影响。研究发现:(1)受教育程 ...性,婚姻匹配中的女高男低现象将不断增加,婚姻稳定性将会面临更大挑战。
当两者都不是这样时,匹配是稳定的: a. 第一个匹配集合的某个给定元素 A 更喜欢该集合的某个给定元素 B 在 A 已经匹配到的元素上的第二个匹配集,以及湾B 也比 B 已经匹配的元素更喜欢 A 这种情况下的搭配是根据...
稳定婚姻二郎 问题的 Erlang 解决方案。 测试数据取自 。