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

稳定婚姻问题和延迟认可算法 作者：goa（高粱） 始发于goa的专栏；允许自由转载，但必须注明作者和出处?摘要：延迟认可算法（Gale-Shapley算法）是解决稳定婚姻问题的经典算法，本文用C++来实现Gale-Shapley算法。文章详细介绍了Gale-Shapley算法的原理和编码思路，给出了一个直接从原理出发的原始算法及其改进版本，并对两个版本进行了比较分析。 ? 关键词：稳定婚姻问题?延迟认可算法?二维数组?以空间换时间 ? 稳定婚姻问题 ?????? 问题来自于一场“3分钟相亲”活动，参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流，并为她们打分，然后按照喜欢程度，对每一位女士进行排序；同样的，每位女士也要对所有男士进行打分和排序。 ?????? 作为活动的组织者，当你拿到这些数据后，该如何为男，女士们配对，才能使大家皆大欢喜，组成稳定的婚姻呢？ ?????? 插一句：什么样的婚姻才能称为稳定的婚姻呢？ ?????? 所谓稳定的婚姻，就是指男女结婚后，双方都不会发生出轨行为。??? 那怎样才能做到双方都不出轨呢？ ?????? 如果双方都是对方的最爱，自然不会出轨；如果有一方或双方都不是对方的最爱，则必须保证想出轨的人找不到出轨的对象。例如，男子i认为其妻子不是自己的最爱，他更爱的人是j女士，可是j女士认为自己的丈夫比男子i强，则不会选择与男子i出轨；另外有k女士很喜欢男子i，可是男子i又觉得她不如自己的现任妻子，所以也不会选择和k女士出轨。这样男子i就找不到与之出轨的对象了；同理，如果他的妻子也找不到出轨对象的话，他们的婚姻就是稳定的。 简言之，只要满足“除妻子（丈夫）外，我爱的人不爱我，爱我的人我不爱”条件，就可形成稳定的婚姻。 回到我们的问题：如何让所有参加相亲活动的男女都组成各自的“稳定婚姻”? 1962 年，美国数学家 David Gale 和 Lloyd Shapley 发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。 ??? 先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作： ??? 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士； 每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。 若某男士被其女友抛弃，重新变成自由男。 在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利——当然，新的追求对象比不过前女友。 这样，在算法执行期间，每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱，从一而终——每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。 ? 本文用C++来实现Gale-Shapley算法，采用男士主动求爱，女士接受求爱的方式。 假设男女生人数均为MAX，对每位男士和女士均进行编号，用自然数0,1,2，。。。，MAX-1表示其序号（依照C++的习惯，序号从0开始）。 用二维数组liMan[MAX][MAX]来存储男士所喜欢的女士序号的排列表；同理，用二维数组libLady[MAX][MAX+1]来存储女士所喜欢的男士序号的排列表，例如v号女最喜欢i号男，则libLady[v][0] = i；若t号男比i号男更招v号女喜欢，则在数组libLady[v][]中，元素值t的下标小于元素值i的下标。 为了简化算法，增加一个“不存在”的男士（序号为MAX），作为女士最初的选择。在给二维数组libLady[MAX][MAX+1]赋初值时，对于任意一个女士v，总有libLady[v][MAX] = MAX。 为所有的男士（包括那个 “不存在”的）建立一个数组man[MAX+1]，用来存储他们追求女士的次数，i号男目前追求的女士序号为libMan[i][man[i]]。 例如，man[i]=0表示i号男尚未追求过女士，其所追求的女士序号为libMan[i][0]；man[i]=2表示i号男已经追求过两位女士，他下次追求的女士序号为libMan[