更新时间：2024-09-21 17:16
“稳定婚姻问题”在生活中是一个典型的问题，通俗地可叙述为：当前有N位男生和N位女生最后要组成稳定的婚姻家庭，过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序。然后开始选择自己的对象，其规则是：男生第一天均向各自最喜欢的女生写一封“情书”。
问题来自于一场“3分钟相亲”活动，参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流，并为她们打分，然后按照喜欢程度，对每一位女士进行排序；同样的，每位女士也要对所有男士进行打分和排序。
对于典型“稳定婚姻问题”，借助矩阵(二维数组)给出了一种简明的实现方法。在本算法中，所采用的存储结构和实现方法灵活巧妙，通俗易懂，方便实现；而且用于存储所要处理数据的内存空间相对于其它一些算法节省了一半，空间复杂度为O(1)；由于存储结构的巧妙性，算法的时间复杂度在最好的情况下为线性时间N，在最坏的情况下为O(N2)。
这个是数学界切切实实研究过的问题。对于以前没有接触过这个问题的人，这个理论最出人意外的结论是：传统的求爱，结婚过程是male-optimal的，也就是说，男性能够得到尽可能好的心上人，女性却不然。这就是所谓的稳定匹配问题(StableMarriageProblem，也叫稳定婚姻问题）。
稳定婚姻问题。它有很多种可能的解法。为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特定的数学价值。当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？于是它就这样流传下来了。
有很多组合数学问题都可以如此这般的翻译为生活中的问题。比如著名的Hall定理：给定n个有限集合（其间可以有交集），如果其中任意m个集合的并集的元素个数都不小于m，那么一定存在n个不同的元素，使得它们正好依次存在于这n个集合之中。我相信没有人明白以上这是在说什么。可是它有一个很好的解释：把那n个集合想象成n个男生各自心仪的女孩子们（一般来说都不止一个），中间的那个条件是说，如果对于其中任意一部分男生，他们喜欢的女孩子的总数都不少于这组男生的人数（这个条件是必要的，否则就打起来了），那么总的说来一定存在一种办法给每个男生都分配一个女生恰好是他喜欢的。
1962年，美国数学家David Gale和Lloyd Shapley发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。
先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：
①每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
②每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。
③若某男士被其女友抛弃，重新变成自由男。
在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利——当然，新的追求对象比不过前女友。
这样，在算法执行期间，每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱，从一而终——每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。
第一天上午，所有的男人都向自己最爱的女人求婚，下午，每个女人看看自己有没有收到，收到了多少人的求婚，如果只收到一个男人的求婚，那么就和他订婚。如果收到多于一个男人的求婚，那么就和其中她最爱的那个男人订婚，同时把其他男人都锯掉。如果一个求婚都没有，不要着急，最后总会有的。晚上，检查一遍，如果所有女人都订婚了，，万事大吉，明天举行集体婚礼，但如果还有女人没有订婚，那么事情还没有完，第二天还得重复，第二天上午，所有还没订婚的男人向自己次爱的女人求婚(因为昨天已经被他们的最爱锯了)。下午，每个女人再看一遍自己收到订婚的情况，如果她已经订婚了，但是又有一个她更爱的男人来向她求婚，那就把原来那个锯掉，再和这个更爱的男人订婚；如果还没订婚，那就和第一天的下午的处理一样。晚上再检查一遍，如果还是有人没有订婚，那第三天再重复，第三天上午，所有没有订婚的男人，包括第一天订了第二天又被踹出来的，再向还没有锯过他的女人中他最爱的那个求婚如此周而复始，直到最后大家都订了婚，便一起结婚。
这么个过程数学上可以证明：
第一，这个过程会中止，也就是说，总有大家都订了婚的一天，不可能无限循环。
第二，中止后所有的婚姻是稳定婚姻。所谓不稳婚姻是说，比如说有两对夫妇M1,F1和M2,F2,M1的老婆是F1,但他更爱F2;而F2的老公虽说是M2.但她更爱M1,这样的婚姻就是不稳婚姻,M1和F2理应结合，他们现在各自的婚姻都是错误。我们能证明的是，通过上面那个求婚过程，所有的婚姻都是稳定的，没有人犯错误。
第三，比较引人注目的是，这个过程是male-optimal的，男性能够获得尽可能好的伴侣，比如说最后有二十个女人拒绝了他，他仍然能够得到剩下的八十个女人中他最爱的那一个。
第四，更有甚者，这个过程是female-pessimal的，女人总是在可能的情况下被最不喜欢的人追上。这一点没有那么直观的理解，勉强要解释的话，可以这么看：虽说女人每换一次订婚对象，都往上升一层，但起点可能很低，虽说在一步步接近她最爱的目标，但最后往往达不到。比如说还差三十名就达到她最爱的人了，但这时GameOver，所有的人都已订了婚，这样她也只能死了心了。还有三十个她更爱的人还没向她求过婚，可是她也无可奈何了，但她仍然能够得到剩下的七十个男人中她最爱的那一个。
用C++来实现Gale-Shapley算法，采用男士主动求爱，女士接受求爱的方式。
假设男女生人数均为MAX，对每位男士和女士均进行编号，用自然数0,1,2，。。。，MAX-1表示其序号（依照C++的习惯，序号从0开始）。
用二维数组liMan[MAX][MAX]来存储男士所喜欢的女士序号的排列表；同理，用二维数组libLady[MAX][MAX+1]来存储女士所喜欢的男士序号的排列表，例如v号女最喜欢i号男，则libLady[v]=i；若t号男比i号男更招v号女喜欢，则在数组libLady[v][]中，元素值t的下标小于元素值i的下标。
为了简化算法，增加一个“不存在”的男士（序号为MAX），作为女士最初的选择。在给二维数组libLady[MAX][MAX+1]赋初值时，对于任意一个女士v，总有libLady[v][MAX]=MAX。
为所有的男士（包括那个“不存在”的）建立一个数组man[MAX+1]，用来存储他们追求女士的次数，i号男目前追求的女士序号为libMan [man]。
例如，man =0表示i号男尚未追求过女士，其所追求的女士序号为libMan；man=2表示i号男已经追求过两位女士，他下次追求的女士序号为libMan（即在喜好表中排名第3位的女士）。
很明显，man[MAX+1]的每个元素初始值均为0，表示刚开始时，每位男士都去追求自己最喜欢的女士，man 值越大，男士对所选择的女士越不满意。
为所有的女士建立一个数组lady[MAX]，用来存储她所选择的男士序号，数组的所有元素初始值均为MAX，表示女士的当前男友为一个“不存在”的男士，他的分值比任何男士都低，以保证当有一个真正的男人追求该女士时，她会毫不犹豫的抛弃MAX，而选择该男子。
遍历数组man[MAX+1]，依次让每个男士去追求自己心仪的女士（当然不需要处理元素man[MAX]——那个“不存在”的男人）。例如现在正逢i号男追求v号女，若i号男不如v号女当前男友，则遭拒绝，i号男继续追求其“次喜欢女”；反之，若i号男比v号女当前男友优秀，则v抛弃前男友，选择i号男为新男友，而其前男友（设为t号男）重获自由身，可以去追求自己的“次喜欢女”了。
这里有一个地方要注意：因为是通过执行（i++）来遍历数组的，所以如果当t\u003ci时，必须要让i折回到t位置（使i=t)，否则会漏掉t。
当i==MAX时，表示所有男士都找到了自己的另一半，算法结束，输出结果。
C++代码如下：
#include\u003ciostream\u003e
usingnamespacestd;
constintMAX=4;
boolChangeFriend(constintlibLady[][MAX+1],intv,intoldF,intnewF);//判断是否需要换男友
intmain()
intlibMan[MAX][MAX]={{2,1,3,0},{0,2,3,1},{2,3,1,0},{1,3,2,0}};//存储男士所喜欢的女士序号的排列表
intlibLady[MAX][MAX+1]={{0,3,1,2,MAX},{1,3,2,3,MAX},{0,2,3,1,MAX},{1,0,3,2,MAX}};//存储女士所喜欢的男士序号的排列表
intman[MAX+1]={0};
intlady[MAX]={MAX,MAX,MAX,MAX};
inti=0;
while(i\u003cMAX)
intv=libMan [man];//i号男喜欢v号女
if(i==lady[v])//i号男就是v号女当前男友，跳过，处理下一个男士
i++;
elseif(ChangeFriend(libLady,v,lady[v],i))//若i号男比v号女当前男友优秀，则v抛弃前男友，重新选择i
intt=lady[v];//存储前男友序号
man[lady[v]]++;//抛弃前男友，即前男友选择其“次喜欢女”
lady[v]=i;//选择i号男为新男友
if(t\u003ei)//前男友序号t在新男友i之后，则今后顺序前行可以处理t
i++;//处理下一个男士
else//前男友序号t在新男友i之前，返回t，否则会漏掉t
i=t;
else//继续处理i号男的“次喜欢女”
man ++;
for(inti=0;i\u003cMAX;i++)//输出每位男士追求女士的次数
cout\u003c\u003cman +1\u003c\u003c",";
cout\u003c\u003cendl;
for(inti=0;i\u003cMAX;i++)//输出每位男士的妻子的序号
cout\u003c\u003clibMan [man]\u003c\u003c",";
cout\u003c\u003cendl;
for(inti=0;i\u003cMAX;i++)//输出每位女士的丈夫的序号
cout\u003c\u003clady \u003c\u003c",";
cout\u003c\u003cendl;
system("pause");
return0;
boolChangeFriend(constintlibLady[][MAX+1],intv,intoldF,intnewF)//判断是否需要换男友
for(inti=0;i\u003c=MAX;i++)
if(libLady[v] ==oldF)
oldF=i;
break;
for(inti=0;i\u003c=MAX;i++)
if(libLady[v] ==newF)
newF=i;
break;
return(oldF\u003enewF);
在上述实现中，设计了一个子函数，用来判断女士v是否需要换男友，若男子序号newF在数组libLady[v] 的位置比oldF靠前，则说明女士v更喜欢newF，需要换男友，否则不换。通过比较它们的下标，可以得出结论。
这个子函数的引入可以让程序完成工作，但也带来一些效率上问题，每次调用函数都要分别遍历数组libLady[v][]两次，去寻找oldF和newF的下标，这样在MAX值很大的时候，时间消耗是相当大的。
另外，由于我们是通过执行（i++）来遍历数组，每次遇到(t\u003ci)时，都要令i折回到t，然后再执行（i++），进行了很多重复的比较，浪费了宝贵的时间。
首先解决关于子函数的问题。之所以引入子函数，是因为数组libLady[v][]存储的是女士v所喜欢的男士序号的排列表，而不是男士的分值表。如果我们创建一个二维数组libladyValue[MAX][MAX+1]，用来存储女士v所喜欢的男士的分值，即数组元素libladyValue[v] 表示女士v给i号男打的分数，分数越高，则表示越招人喜欢。这样我们在判断女士v是否需要换男友时，就无需遍历数组，只要直接比较libladyValue[v]和libladyValue[v][t]的值就好了。
其次解决重复比较的问题。我们可以创建一个栈，把所有自由男的序号存储到栈中，每当有男子订婚，则将其序号出栈；每当有男子被抛弃，则将其序号入栈。这样就可以确保不会出现重复比较了。