下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 稳定婚姻问题和延迟认可算法

稳定婚姻问题和延迟认可算法.doc

稳定婚姻问题和延迟认可算法

罗密欧煮你爷很快乐
2018-04-09 0人阅读 举报 0 0 暂无简介

简介:本文档为《稳定婚姻问题和延迟认可算法doc》,可适用于领域

稳定婚姻问题和延迟认可算法稳定婚姻问题和延迟认可算法稳定婚姻问题和延迟认可算法作者:goal(高粱)始发于goal的专栏允许自由转载但必须注明作者和出处摘要:延迟认可算法(GaleShapley算法)是解决稳定婚姻问题的经典算法本文用C来实现GaleShapley算法。文章详细介绍了GaleShapley算法的原理和编码思路给出了一个直接从原理出发的原始算法及其改进版本并对两个版本进行了比较分析。稳定婚姻问题延迟认可算法二维数组以空间换时间稳定婚姻问题问题来自于一场"分钟相亲"活动参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流并为她们打分然后按照喜欢程度对每一位女士进行排序同样的每位女士也要对所有男士进行打分和排序。作为活动的组织者当你拿到这些数据后该如何为男女士们配对才能使大家皆大欢喜组成稳定的婚姻呢插一句:什么样的婚姻才能称为稳定的婚姻呢所谓稳定的婚姻就是指男女结婚后双方都不会发生出轨行为。那怎样才能做到双方都不出轨呢如果双方都是对方的最爱自然不会出轨如果有一方或双方都不是对方的最爱则必须保证想出轨的人找不到出轨的对象。例如男子i认为其妻子不是自己的最爱他更爱的人是j女士可是j女士认为自己的丈夫比男子i强则不会选择与男子i出轨另外有k女士很喜欢男子i可是男子i又觉得她不如自己的现任妻子所以也不会选择和k女士出轨。这样男子i就找不到与之出轨的对象了同理如果他的妻子也找不到出轨对象的话他们的婚姻就是稳定的。简言之只要满足"除妻子(丈夫)外我爱的人不爱我爱我的人我不爱"条件就可形成稳定的婚姻。回到我们的问题:如何让所有参加相亲活动的男女都组成各自的"稳定婚姻"年美国数学家DavidGale和LloydShapley发明了一种寻找稳定Shapley算法)。婚姻的策略人们称之为延迟认可算法(Gale先对所有男士进行落选标记称其为自由男。当存在自由男时进行以下操作:每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士每一位女士将正在追求她的自由男与其当前男友进行比较选择其中排名优先的男士作为其男友即若自由男优于当前男友则抛弃前男友否则保留其男友拒绝自由男。若某男士被其女友抛弃重新变成自由男。在算法执行期间自由男们主动出击依次对最喜欢和次喜欢的女人求爱一旦被接受即失去自由身进入订婚状态而女人们则采取"守株待兔"和"喜新厌旧"策略对前来求爱的男士进行选择:若该男子比未婚夫强则悔婚选择新的未婚夫否则拒绝该男子的求婚。被女友抛弃的男人重获自由身重新拥有了追求女人的权利当然新的追求对象比不过前女友。这样在算法执行期间每个人都有可能订婚多次也有可能一开始就找到了自己的最爱从一而终每订一次婚女人们的选择就会更有利而男人们的品味则越来越差。只要男女生的数量相等则经过多轮求婚订婚悔婚和再订婚之后每位男女最终都会找到合适的伴侣虽然不一定是自己的最爱(男人没能追到自己的最爱或女人没有等到自己的最爱来追求)但绝对不会出现"虽然彼此相爱却不能在一起"的悲剧所有人都会组成稳定的婚姻。本文用C来实现GaleShapley算法采用男士主动求爱女士接受求爱的方式。假设男女生人数均为MAX对每位男士和女士均进行编号用自然数MAX表示其序号(依照C的习惯序号从开始)。,,。用二维数组liManMAXMAX来存储男士所喜欢的女士序号的排列表同理用二维数组libLadyMAXMAX来存储女士所喜欢的男士序号的排列表例如v号女最喜欢i号男则libLadyv=i若t号男比i号男更招v号女喜欢则在数组libLadyv中元素值t的下标小于元素值i的下标。为了简化算法增加一个"不存在"的男士(序号为MAX)作为女士最初的选择。在给二维数组libLadyMAXMAX赋初值时对于任意一个女士v总有libLadyvMAX=MAX。为所有的男士(包括那个"不存在"的)建立一个数组manMAX用来存储他们追求女士的次数i号男目前追求的女士序号为libManimani。例如mani=表示i号男尚未追求过女士其所追求的女士序号为libManimani=表示i号男已经追求过两位女士他下次追求的女士序号为libMani(即在喜好表中排名第位的女士)。很明显manMAX的每个元素初始值均为表示刚开始时每位男士都去追求自己最喜欢的女士mani值越大男士对所选择的女士越不满意。为所有的女士建立一个数组ladyMAX用来存储她所选择的男士序号数组的所有元素初始值均为MAX表示女士的当前男友为一个"不存在"的男士他的分值比任何男士都低以保证当有一个真正的男人追求该女士时她会毫不犹豫的抛弃MAX而选择该男子。我们遍历数组manMAX依次让每个男士去追求自己心仪的女士(当然不需要处理元素manMAX那个"不存在"的男人)。例如现在正逢i号男追求v号女若i号男不如v号女当前男友则遭拒绝i号男继续追求其"次喜欢女"反之若i号男比v号女当前男友优秀则v抛弃前男友选择i号男为新男友而其前男友(设为t号男)重获自由身可以去追求自己的"次喜欢女"了。这里有一个地方要注意:因为我们是通过执行(i)来遍历数组的所以如果当ti时必须要让i折回到t位置(使i=t)否则会漏掉t。当i=MAX时表示所有男士都找到了自己的另一半算法结束输出结果。C代码如下:#includeiostreamusingnamespacestdconstintMAX=boolChangeFriend(constintlibLadyMAX,intv,intoldF,intnewF)判断是否需要换男友intmain(){intlibManMAXMAX={{,,,},{,,,},{,,,},{,,,}}存储男士所喜欢的女士序号的排列表intlibLadyMAXMAX={{,,,,MAX},{,,,,MAX},{,,,,MAX},{,,,,MAX}}存储女士所喜欢的男士序号的排列表intmanMAX={}intladyMAX={MAX,MAX,MAX,MAX}inti=while(iMAX){intv=libManimanii号男喜欢v号女if(i==ladyv)i号男就是v号女当前男友跳过处理下一个男士ielseif(ChangeFriend(libLady,v,ladyv,i))若i号男比v号女当前男友优秀则v抛弃前男友重新选择i{intt=ladyv存储前男友序号manladyv抛弃前男友即前男友选择其"次喜欢女"ladyv=i选择i号男为新男友if(ti)前男友序号t在新男友i之后则今后顺序前行可以处理ti处理下一个男士else前男友序号t在新男友i之前返回t否则会漏掉ti=t}else继续处理i号男的"次喜欢女"mani}for(inti=iMAXi)输出每位男士追求女士的次数coutmani","coutendlfor(inti=iMAXi)输出每位男士的妻子的序号coutlibManimani","coutendlfor(inti=iMAXi)输出每位女士的丈夫的序号coutladyi","coutendlsystem("pause")return}boolChangeFriend(constintlibLadyMAX,intv,intoldF,intnewF)判断是否需要换男友{for(inti=i=MAXi){if(libLadyvi==oldF){oldF=ibreak}}for(inti=i=MAXi){if(libLadyvi==newF){newF=ibreak}}return(oldFnewF)}在上述实现中我设计了一个子函数boolChangeFriend(constintlibLadyMAX,intv,intoldF,intnewF)用来判断女士v是否需要换男友若男子序号newF在数组libLadyvi的位置比oldF靠前则说明女士v更喜欢newF需要换男友否则不换。通过比较它们的下标可以得出结论。这个子函数的引入可以让程序完成工作但也带来一些效率上问题每次调用函数都要分别遍历数组libLadyv两次去寻找oldF和newF的下标这样在MAX值很大的时候时间消耗是相当大的。另外由于我们是通过执行(i)来遍历数组每次遇到(ti)时都要令i折回到t然后再执行(i)进行了很多重复的比较浪费了宝贵的时间。那么如何改进代码解决上述两个问题首先解决关于子函数的问题。之所以引入子函数是因为数组libLadyv存储的是女士v所喜欢的男士序号的排列表而不是男士的分值表。如果我们创建一个二维数组libladyValueMAXMAX用来存储女士v所喜欢的男士表示女士v给i号男打的分数分数的分值即数组元素libladyValuevi越高则表示越招人喜欢。这样我们在判断女士v是否需要换男友时就无需遍历数组只要直接比较libladyValuevi和libladyValuevt的值就好了。其次解决重复比较的问题。我们可以创建一个栈把所有自由男的序号存储到栈中每当有男子订婚则将其序号出栈每当有男子被抛弃则将其序号入栈。这样就可以确保不会出现重复比较了。在解决上述两个问题的时候我都采用了"以空间换时间"的策略小小的自夸一下呵呵~代码如下:改进后的C#includeiostreamusingnamespacestdconstintMAX=intmain(){intlibManMAXMAX={{,,,},{,,,},{,,,},{,,,}}存储男士所喜欢的女士序号的排列表intlibLadyMAXMAX={{,,,,MAX},{,,,,MAX},{,,,,MAX},{,,,,MAX}}存储女士所喜欢的男士序号的排列表intlibladyValueMAXMAX={}for(inti=iMAXi)把女士喜好的男士序号的排列表转换为男士分值表{for(intj=MAX,k=j=j,k){libladyValueilibLadyij=k}}intmanMAX={}存储各个男士追求女士的次数intladyMAX={MAX,MAX,MAX,MAX}序号初始值MAX表示一个"不存在"的男士即其分值比任何男士都低intSMAX={}一个栈用来存储所有自由男的序号inttop=while(topMAX)把所有自由男的序号存储到栈中Stop=toptoptop指向栈顶while(top=)让自由男主动去追求自己喜欢的女士直到所有的人都配对{intv=libManStopmanStop处在栈顶(序号为Stop)的男士喜欢v号女if(libladyValuevladyvlibladyValuevStop)若栈顶男比v号女当前男友优秀则v抛弃前男友接受栈顶男{intt=ladyv存储前男友序号mant抛弃前男友即前男友选择其"次喜欢女"选择栈顶男为新男友同时栈顶男出栈ladyv=Stopif(t~=MAX)如果t号男不是那个"不存在"的男士Stop=tt号男作为新的栈顶男}else栈顶男追求下一号目标manStop}for(inti=iMAXi)输出每位男士追求女士的次数coutmani","coutendlfor(inti=iMAXi)输出每位男士的妻子的序号coutlibManimani","coutendlfor(inti=iMAXi)输出每位女士的丈夫的序号coutladyi","coutendlsystem("pause")return}参考文献:matrix《引言什么是算法如何寻找稳定的婚姻搭配》孙《稳定婚姻问题和延迟认可算法》发表于年月日::|||

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/10

稳定婚姻问题和延迟认可算法

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利