今天的算法设计与分析课程讲到了一个非常有趣的问题，于是拿来博客分享一下。
首先，先来介绍一下稳定婚姻问题。
“稳定婚姻问题”在生活中是一个典型的问题，通俗地可叙述为：当前有n位男生和n位女生最后要组成稳定的婚姻家庭。在过程的开始之前，男生和女生在各自的心目中都按照喜爱程度对n位异性有了各自的排序，然后他们开始选择自己的对象。问如何组合才能使得他们之间得婚姻是稳定的。
这个问题刚刚拿出来看可能让人一头雾水，怎么匹配他们才算稳定啊？不稳定的定义又是什么呢？
于是问题来到了解决稳定的定义上，通过题目很容易看出，每个男生和女生对异性都有一个排序，而稳定的前提就建立在这排序上。通过分析，我们很容易看出，当一对男女在对方的排序上都是第一，但他们却不能在一起，将就地和另一个伴侣在一起时，那么他们的婚姻就是不稳定的。
那么要怎么配对才会使得所有的婚姻都是稳定的呢？
可能很多人会想到一种策略：那就是先通过一种不稳定的配对方式，再不断地去修改这种配对方式使得所有人的婚姻都是稳定的。例如有一对想私奔（即不稳定）的情侣，则按他们的愿望进行情侣对换，直到最终消除所有的不稳定组合。这种方法虽然有一定程度上能满足稳定性，但这种策略的局限在于它不一定存在一个“最终结果”。因为有可能这种对换会不停持续下去，形成一个死循环，无法确定一个完整的方案。
那么，到底应该如何进行配对呢？
这里，我们来介绍一个算法，叫Gale-Shapley算法。
1962年，美国数学家David Gale和Lloyd Shapley发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。
先对所有男生进行落选标记，称其为自由男。当存在自由男时，进行以下操作：
- 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
- 每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。
- 若某男士被其女友抛弃，重新变成自由男。
这样重复上述过程有限轮后，有些男生已经有女朋友了，然而有些仍然是单身。再继续这个过程下去，直到某个时候所有人都不再是单身，下一轮也就不会有任何追求产生，这个配对算法也就自动结束了。此时的婚姻匹配就一定是稳定的了。
那么如何说明这个配对算法是可以终止的呢？
随着轮数的不断重复，总有一个时候所有人都能配对上。倘若整个流程一直没有因所有人配上对而结束，那么必然会有一个男生追遍了所有女生。而女生只要被人追过，就不可能是单身。既然所有女生都被这个男生追过，就说明所有女生都已不是单身，也就说明所有人都已配对了。
接下来，我们再来证明这种配对方案是稳定的。
首先，我们可以看出，男生所追求的对象总是越来越差（对于自身排名），而一个女生的男友却只可能越来越好。假设有一个男1和女1各自有自己的对象，比起现在的对象来说，男1更喜欢女1。那么男1之前一定跟女1表白过。既然女1并没有跟男1在一起，说明了女1有了比男1更好的男生。这从侧面证明了两人虽然不是一对，但都觉得对方比自己现在的对象好的情况绝不可能发生。
这个算法有趣的地方就在于它是以一种游戏的形式来解决问题的。这个算法应用领域十分广泛，因为它能有效地解决很多生活中关于稳定匹配的问题。它还曾经因解决过经济市场中稳定匹配的问题获得过2012年诺贝尔经济学奖。