稳定婚姻算法

浅谈稳定完备婚姻的算法及推广话说在1962年，两个数学家David Gale 和Lloyd Shapely 提出了下面的问题：给定若干个男生和同样多的女生，他们每个人都对所有的异性有一个心理的偏好次序。

是否存在一种男女配对组合构成一种稳定的组合关系？这里稳定组合的意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。

（可以理解，这样的异性太容易红杏出墙了，所以是某种不稳定因素。

）进一步的问题是，在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式（如果它存在的话）？你可以理解为这是数学家们替月老问的问题：给定一群孤男寡女，寻找一种牵红线的方式，以确保把红杏扼杀在摇篮里。

1、稳定完备婚姻上面这一问题被称为稳定婚姻问题。

它有很多种可能的解法。

为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特定的数学价值。

当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？我们看下面的例题： 某社团中有n 位女士和m 位男士。

假定每位女士按照其对每位男士作为配偶的偏爱程度排名次，无并列。

也就是说，这种排列是纯顺序的，每位女士将这些男士的排列成顺序 1,2,3,… ,n ，类似的,每位男士也对这些女士排列成顺序1，2，3,…，n,我们知道，在这个社团里配对成完备婚姻的方式有n!种。

假定某种婚姻匹配中存在女士A 和 B 及两位男士a 和b,使得i) A 和a 结婚；ii) B 和b 结婚；iii) A 更偏爱b （名次更优先）而非a ；iv) B 更偏爱A 而非B 。

那么，我们认为该完备婚姻是不稳定的。

因为在这种假设下，A 和b 可能会背着别人相伴逃跑，他们都认为，与当前配偶相比每个都更偏爱自己的新伴侣。

如果完备婚姻不是不稳定的，我们则称其为稳定的完备婚姻。

2、稳定完备婚姻的算法2.1 建立模型用二分图来为这个问题建立数学模型。

稳定婚姻匹配问题（Gale-Shapley算法）（转载）1962 年，美国数学家 David Gale 和 Lloyd Shapley 发明了⼀种寻找稳定婚姻的策略。

不管男⼥各有多少⼈，不管他们各⾃的偏好如何，应⽤这种策略后总能得到⼀个稳定的婚姻搭配。

换句话说，他们证明了稳定的婚姻搭配总是存在的。

有趣的是，这种策略反映了现实⽣活中的很多真实情况。

两对夫妻M1 F2，M2 F1。

M1⼼⽬中更喜欢F1，但是他和F2结婚了，M2⼼⽬中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的，随时都可能发⽣M1和F1私奔或者M2和F2私奔的情况。

所以在做出匹配选择的时候（也就是结婚的时候），我们需要做出稳定的选择，以防这种情况的发⽣。

稳定婚姻是组合数学⾥⾯的⼀个问题。

问题⼤概是这样：有⼀个社团⾥有n个⼥⽣和n个男⽣，每位⼥⽣按照她的偏爱程度将男⽣排序，同时每位男⽣也按照⾃⼰的偏爱程度将⼥⽣排序。

然后将这n个⼥⽣和n个男⽣配成完备婚姻。

如果存在两位⼥⽣A和B，两位男⽣a和b，使得A和a结婚，B和b结婚，但是A更偏爱b⽽不是a，b更偏爱A⽽不是B，则这个婚姻就是不稳定的，A和b可能背着别⼈相伴⽽⾛，因为他俩都认为，与当前配偶⽐起来他们更偏爱各⾃的新伴侣。

如果完备婚姻不是不稳定的，则称其是稳定的。

通过证明，可以得到每⼀个n⼥n男的社团，都存在稳定婚姻的结论。

但是这种情况只在异性的社团中存在。

也就是说在同性的社团⾥⾯，稳定婚姻的存在性将不再被保证。

解决思路如下⾸先选择⼀个单⾝男⽣，他会按照他的喜欢程度对⼀个还没有表⽩过的⼥⽣表⽩。

如果⼥⽣此时处于单⾝状态，则恭喜，他们两⼈将进⼊约会状态。

如果⼥⽣已经有男朋友，则⼥⽣会⽐较当前男朋友与表⽩的男⽣，如果更喜欢表⽩的男⽣，则恭喜，男⽣成功上位，⼥⽣之间的男朋友则进⼊单⾝状态；若⼥⽣还是更喜欢⾃⼰的男朋友，则不好意思，男⽣表⽩失败。

当所有的男⽣都脱离单⾝状态时，此时的约会状态应是稳定的，证明如下：若存在之前描述的不稳定因素，即虽然男⽣i和⼥⽣a牵⼿，但男⽣i对⼥⽣b更喜欢，⽽⼥⽣b发现，相⽐⾃⼰的男朋友j，她更喜欢男⽣i。

基于稳定婚姻问题的最大权匹配模型分析稳定婚姻问题（Stable Marriage Problem）是一个经典的组合优化问题，最早由美国数学家D.Gale和L.S.Shapley于1962年提出，它解决的是在配对过程中如何以最优的方式匹配男女双方，使得不存在任何一对男女在匹配过程中想要放弃自己当前的匹配并改匹配到对方。

该问题可以用一个图论模型来表示，其中男性和女性分别被表示为两组节点，边代表男性对女性的偏好程度。

假设有n个男性和n个女性，每个人按照自己对异性的喜好对另一组进行排序。

稳定婚姻问题的目标是找到一个稳定的匹配，即不存在双方有更高偏好的配对。

为了解决这个问题，可以使用最大权匹配模型（Maximum Weight Matching）。

最大权匹配是一种图论算法，它的目标是找到图中权重之和最大的边集合，使得没有两个边共享相同顶点。

首先，我们需要建立一个稳定婚姻问题的图模型。

假设有两组顶点，男性集合M和女性集合W，共有n个顶点。

每个男性对女性的偏好程度可以表示为一个n×n的矩阵，矩阵中的元素表示男性对女性的排名。

同样，每个女性对男性的偏好程度也可以表示为一个n×n的矩阵。

接下来，我们需要使用最大权匹配算法来找到一个稳定的匹配。

最大权匹配算法采用了增广路径（Augmenting Path）的思想来不断寻找能够增大匹配权重的路径。

具体步骤如下：1. 随机选择一个男性，并让他向他排名最高的女性求婚。

如果女性尚未被任何男性求婚，或者她对当前求婚的男性更有好感，则将她与该男性匹配。

2. 如果女性已经与某个男性匹配，但是她对当前求婚的男性更有好感，则她与当前匹配的男性分手，与新的男性匹配。

3. 重复进行步骤1和步骤2，直到每个男性都结束了求婚。

4. 检查当前匹配是否稳定。

如果存在一对男女，他们彼此都有更高偏好的配对，那么该匹配不是稳定的。

5. 如果当前匹配是稳定的，则算法结束。

否则，从不稳定的一对中选择一个男性和女性，将他们分开，并再次进行求婚。

盖尔-沙普利算法流程和应用案例盖尔-沙普利算法（Gale-Shapley Algorithm），也被称为稳定婚姻算法或者情人节算法，是解决稳定婚姻问题的一种算法。

该算法首先是由David Gale和Lloyd Shapley两位数学家在1962年提出的，用于解决社会经济学领域中的配对问题，后来被应用到人工智能领域中的任务分配问题、交通流分配问题等等。

盖尔-沙普利算法的核心思想是通过迭代，使每个人都选择自己最喜爱的对象，并且这个选择是可交换的，直到所有人都被配对。

算法分为两个阶段：第一阶段，每个男士都要向自己最喜欢的女士求婚，如果女士没有男友，就接受这个男子的求婚；如果女士已有男友，就比较女士已有男友和该男子之间的差异，如果该男子比女士已有男友更合适，该女士就与该男子配对，女士的原男友就成为自由人。

这个过程将一直持续到所有女性都有了伴侣。

第二阶段，男性根据每个女性的新伴侣向次喜欢的女性提出求婚，并将其中没有匹配的女性作为新的迭代对象。

如果已经拒绝了所有的女性，那么这个男士就成为自由人。

此过程将一直进行到男性都有了伴侣。

应用案例：例如，在安排医生和病人之间的预约时，有三个医生和三个病人。

三个医生分别是A、B、C，三个病人分别是X、Y、Z。

假设这三个医生和三个病人之间的相关顺位如下表所示：A: X > Y > ZB: Y > X > ZC: X > Z > YX: A > B > CY: B > A > CZ: A > C > B按照盖尔-沙普利算法，医生A会优先选择病人X，病人X会选择医生A，他们将成为一对。

医生B会选择病人Y，病人Y会选择医生B，他们将成为一对。

医生C会选择病人Z，病人Z会选择医生A，这时病人X成为自由人。

接下来，病人X会选择他次喜欢的医生B，医生B也会选择他次喜欢的病人X，这时他们成为一对。

最后，病人Z会选择他次喜欢的医生C，医生C也会选择他次喜欢的病人Z，他们将成为一对。

稳定婚姻问题和延迟认可算法作者：goal00001111 （高粱）始发于goal00001111 的专栏；允许自由转载，但必须注明作者和出处摘要：延迟认可算法（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算法）。

gs算法代码GS算法，即Gale-Shapley算法，用于解决稳定婚姻问题。

以下是GS算法的伪代码：```function GaleShapley(n, menPrefs, womenPrefs):// 初始化所有男士和女士都未匹配menStatus = new Array(n)womenStatus = new Array(n)for i = 0 to n-1:menStatus[i] = -1womenStatus[i] = -1// 当还有未匹配的男士时，进行循环while there are unmatched men:// 选择一个未匹配的男士m = the first unmatched man// 找到该男士的首选女士w = menPrefs[m][0]if womenStatus[w] == -1:// 如果女士尚未匹配，则将男士和女士匹配menStatus[m] = wwomenStatus[w] = melse:// 如果女士已经匹配，则比较当前男士和已匹配男士的偏好m2 = womenStatus[w]if womenPrefs[w].index(m) < womenPrefs[w].index(m2): // 如果当前男士更受女士青睐，则与女士匹配，将原匹配男士置为未匹配menStatus[m] = wwomenStatus[w] = mmenStatus[m2] = -1else:// 如果原匹配男士更受女士青睐，则当前男士保持未匹配状态// 在该男士的偏好列表中删除首选女士menPrefs[m].remove(w)return menStatus```上述伪代码描述了GS算法的主要逻辑。

其中，`n`表示男士和女士的数量，`menPrefs`和`womenPrefs`分别表示男士和女士的偏好列表。

`menStatus`和`womenStatus`分别表示男士和女士的匹配状态，初始值都为-1，表示未匹配。

稳定婚姻问题算法
稳定婚姻问题是一个组合优化问题，可以使用算法求解。

一个常用的解决稳定婚姻问题的算法是Gale-Shapley算法。

下面是Gale-Shapley算法的伪代码：
1. 初始化所有人未匹配
2. 当存在一个男性未匹配的时候，选择一个未匹配男性m
3. 选择m的最喜欢的尚未婚配的女性w
4. 如果w未婚配，则将m和w配对
5. 如果w已婚配，但是m在w的排名上比当前配偶更好，则
将m和w配对，并将当前配偶变为未匹配状态
6. 重复步骤2-5直到所有男性都匹配
Gale-Shapley算法保证了最终的婚配结果是稳定的，即不存在
一个男性和一位女性，他们彼此喜欢对方胜过当前配偶的情况。

当然，除了Gale-Shapley算法，还有其他一些算法可以解决稳定婚姻问题，比如Stable Marriage with Incomplete Lists（SMI）算法等。

具体选择哪个算法取决于问题的规模和特点。

Stable Matching Problem(上)问题的提出《算法》的第一堂课讲了关于稳定匹配（Stable Matching）的问题，这是一个由现实情况引出的一个很有趣的问题。

假设说现有一堆学生准备到一堆公司实习，每个学生心目中对这些公司都有一个喜好排序，但为了保证成功率，每个学生都向所有的公司投递了申请。

公司收到学生申请后，根据各自的要求和喜好对所有学生也有一个满意度排序，并依据排序向一部分学生发出了offer，现在假设A公司向学生X 发出了offer，由于各个公司的进度不一样，在学生X接到A公司的offer后他又收到了B公司的offer，相较而言，X更喜欢B公司，于是他决定放弃A公司的offer转投到B公司门下。

由于X的离去，A公司就少了一个实习生，于是它又向待聘的学生Y发出offer，学生Y于是放弃已经接受的公司C，转投到公司A门下，那么就这样情况开始连续失控….以上混乱情况的出现，在于公司和学生之间没有一个要求保持现状的强制体系，用专业的话语来讲也即是该过程不是自强化（self-reinforcing）的。

大家都可以根据自己喜好随时改变自己之前做出的决定，于是整个情况开始不可控制。

在上述情况下，提出了我们的问题：给定一组雇主E和申请人A之间的优先权，我们能否把A合理的分配给E，以使得对于每个雇主E和未分配为E工作的申请人A之间，以下两种情况至少存在其一：1、E对于它接受的所有人都比A满意2、A对于为他分配的公司比E满意。

如果上述情况成立，那么这种分配就是稳定的，个人兴趣将制止申请人A和公司E之间出现幕后交易。

这里，我们引出几个概念：1、不稳定对（unstable pair）：在以下情况同时存在的时候，申请人x和公司y是不稳定的：A、相对已经分配好的公司，x更喜欢y；B、相对其中一个已经录用的学生，y更喜欢x。

2、稳定分配（stable assignment）：不存在不稳定对的分配经典的男女配对问题OK！马上就将进入我们今天的经典问题，给定一组男人和一组女人，每个人在心目中都对所有的异性有一个倾慕度排序，从最喜欢到最不喜欢依次排序1、2、3。

稳定婚姻问题算法稳定婚姻问题算法话说在1962年，两个数学家David Gale 和Lloyd Shapley提出了下⾯的问题：给定若⼲个男⽣和同样多的⼥⽣，他们每个⼈都对所有的异性有⼀个⼼理的偏好次序。

是否存在⼀种男⼥配对组合构成⼀种稳定的组合关系？这⾥稳定组合的意思是说，不存在两个⾮伴侣的异性对彼此的评价⽐对各⾃伴侣的评价还要⾼。

（可以理解，这样的异性太容易红杏出墙了，所以是某种不稳定因素。

）进⼀步的问题是，在已知每个⼈对异性的偏好顺序的情况下，怎样求出这种稳定组合⽅式（如果它存在的话）？你可以理解为这是数学家们替⽉⽼问的问题：给定⼀群孤男寡⼥，寻找⼀种牵红线的⽅式，以确保把红杏扼杀在摇篮⾥。

这⼀问题被称为稳定婚姻问题。

它有很多种可能的解法。

为了让⼤家相信数学家不是真得如此⽆聊，我要指出它确确实实是⼀个地道的组合数学问题，有其特定的数学价值。

当然啦，它也有很多别的背景和应⽤，⽐如⽤来在若⼲个公司和应聘者之间进⾏招聘中介……但是数学家们怎么会放过如此⼋卦的⼀个名字呢？于是它就这样流传下来了。

给定每个⼈关于异性的偏好排序，要寻找⼀种男⼥配对组合构成稳定的组合。

Gale和Shapley不但提出了这个问题本⾝，⽽且给出了⼀种著名的解法。

这个解法可以描述为如下的求偶过程：⾸先，让这些男⽣去向他们最⼼仪的⼥⽣求婚——这是数学家们的原本的⽤词。

如果你觉得太快了的话，让我们暂时改成表⽩吧……然后，等所有男⽣表⽩完毕后，所有的收到表⽩⼥⽣们都从⾃⼰的表⽩者中选择⾃⼰最喜欢的⼈接受为男朋友。

没⼈表⽩的⼥⽣只能暂时等⼀等了，不要着急，表⽩会有的。

以上过程称为“⼀轮”。

之后的每⼀轮都按照类似的⽅式进⾏。

⾸先由还处于单⾝状态的男⽣们每个⼈再次向⾃⼰还没有表⽩过的⼥⽣中⾃⼰最喜欢的⼈表⽩（⽆论⼈家是否已经有了男朋友），然后，等所有单⾝男⽣表⽩完毕后，所有的收到表⽩⼥⽣们都从⾃⼰的表⽩者中选择⾃⼰最喜欢的⼈接受为男朋友。

简单的稳定婚姻匹配⼀、相关的定义1.有⼀个男⼠集合和⼀个⼥⼠集合。

每个男⼠都有⼀个优先级列表，把⼥⼠按潜在结婚对象进⾏优先级排序。

同样的，⼥⼠也有⼀个对潜在结婚对象的优先级列表。

婚姻匹配：⼀个婚姻匹配Ｍ是⼀个包含ｎ个（ｍ，ｗ）对的集合，每⼀对的成员都按照⼀对⼀的模式从两个不相交的ｎ元素集合Ｙ和Ｘ中选出。

也就是说，Ｙ中的每个男⼠ｍ都只和Ｘ中的⼀位⼥⼠ｗ配对，反正亦然。

相当于⼀个⼆分图中，边来连接可能结婚的对象，两边的顶点代表Ｘ和Ｙ，婚姻匹配也是图中的⼀个完美匹配。

婚姻的稳定：如果在匹配Ｍ中，，男⼠ｍ和⼥⼠ｗ没有匹配，但他们都更倾向对⽅，⽽不是Ｍ中彼此的伴侣，那么（ｍ，ｗ）称为受阻对，如果婚姻匹配存在受阻对，那么我们说婚姻是不稳定的，如果不存在，则婚姻是稳定的。

⼆、稳定婚姻算法输⼊：含有⼀个ｎ个男⼠的集合和⼀个ｎ个⼥⼠的集合，以及各⾃选择结婚对象的优先级。

输出：⼀个稳定的婚姻匹配关系１. 开始所有的男⽣和⼥⼠都是⾃由的。

２. 如果存在⾃由男⽣，任选⼀个男⽣，执⾏下⾯步骤：（１）求婚：选中的男⼠ｍ向ｗ求婚。

ｗ是优先级最⾼的，⽽且没有拒绝过他。

（２）回应：如果ｗ是⾃由的，她接受求婚，如果ｗ不是⾃由的，她把ｍ和当前的配偶作⽐较，如果更喜欢ｍ接受求婚，否则拒绝。

３. 返回ｎ个配对的集合。

三、代码的实现因为这次的实现⽐较简单，所以⽤了matlab来编写函数//dequeue函数function [Q] = dequeue(Q )n=size(Q,2);for i=1:n-1Q(i)=Q(i+1);endQ(n)=[];end//enqueue函数function [ Q] = enqueue( Q ,x)n=size(Q,2);Q(n+1)=x;end//判断队列否为空function [ flag] = empty( Q)if size(Q,2)==0flag=true;endend//判断男⽣和⼥⼠现有配偶的优先级顺序，如果排在该配偶前⾯function [j] = shunxu(B,x,y)%%输⼊⼀个矩阵的第x⾏,判断输⼊的值y在这⾏的位置n=size(B ,2);j=1;for i=1:nj=j+1;if (B(x,i)==y)break;endendend//婚姻匹配函数function [ D ] = Match( A,B )%A,B分别是男⼥的优先选择矩阵%返回稳定的匹配n=size(A,2);B1=zeros(1,n); %B1⼥⼠是否已经匹配，储存匹配的男⼠编号for i=1:nQ(i)=i;end %Q为待匹配的男⼠的队列，初始化为全部男⼠while(~empty(Q))m=Q(1);Q=dequeue(Q);for i=1:nk=A(m,i); %m男⼠第i喜欢的是k⼥⼠if(B1(k)~=0) %如果k⼥⼠已经匹配了if(shunxu(B,k,B1(k))>(shunxu(B,k,m))) %且如果第m个男⼠的优先级⽐现有配偶要⾼ Q=enqueue(Q,B1(k));B1(k)=m;break;endelse %如果没匹配B1(k)=m;endendenda=1:n;D=[a;B1]; %%这⾥输出的是1到n编号⼥⼠对应的配偶的编号End输⼊说明：这⾥的A，B存储的是编号，⽽不是第⼀喜欢的⼈Matlab的⽂件输⼊输出问题：四、案例的测试⽤书上那个例⼦：见算法设计与分析基础293页性别编号123男⼠Bob Jim Tom⼥⼠Ann Lea Sue那么男⼠的优先级顺序为：⼥⼠的优先级顺序为：A= [2,1,3 B= [2,3,12,3,1 3,1,23,2,1] 2,3,1]A的每⼀⾏分别是Bob ,Jim 和Tom⼼中对理想对象的优先级顺序同理，B的每⼀⾏分别是Ann,Lea和Sue⼼中对理想对象的优先级顺序。