优秀程序员必会算法之延迟认可算法

一些优秀的算法就好像围棋中的定式，或者是程序设计中的设计模式一样，前人已经在总结了该类问题的基础之上，给出了完备的解决方法。那么对于一名优秀的程序员来说，就需要了解这些算法，并且在遇到类似的问题的时候，第一时间就会想到应用这种算法。这样会大大的提高编程的效率。

今天我们就来看一下延迟认可算法。了解延迟认可算法之前，我们先需要了解一下稳定婚姻问题。

所以稳定婚姻问题，通俗地可叙述为：当前有N位男生和N位女生最后要组成稳定的婚姻家庭，过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序，男生和女生结婚后，对于每一对男生女生，不会出现比起当前匹配的伴侣互相更喜爱的一对男生女生，即可认为婚姻是稳定的。

稳定婚姻问题可以用在很多领域，例如将用户分配给大型分布式Internet服务中的服务器。数十亿用户访问Internet上的网页，视频和其他服务，要求每个用户都与全球提供该服务的数十万台服务器之一匹配。用户希望服务器足够近，以便为所请求的服务提供更快的响应时间，从而导致每个用户对服务器的（部分）优先排序。每个服务器都希望以较低的成本为用户提供服务，从而导致每个服务器的用户（部分）优先排序。分发世界上许多内容和服务的内容交付网络每数十秒就解决了用户与服务器之间这个庞大而又复杂的稳定婚姻问题，使数十亿用户可以与各自的服务器进行匹配，以提供所需的网页，视频或其他内容服务。

1962年，美国数学家David Gale和Lloyd Shapley发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。

该算法的执行步骤如下，在计算策略中，男性将一轮轮的去追求他中意的女性，而女性则可以选择接受或者拒绝她的追求者。

那么，首先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：

1、每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；

2、每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。

3、若某男士被其女友抛弃，重新变成自由男。

在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利，当然，新的追求对象比不过前女友。

这样，在算法执行期间，每个人都有可能订婚多次，也有可能一开始就找到了自己的最爱，从一而终。

而每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣，虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。

下面我们来看一下算法的稳定性：

1、随着轮数的增加，总有一个时候所有人都能配对，因此不会出现无法终止一直循环的情况。

2、由于在每一轮中，至少有一个男性向某个女性告白，因此总的告白次数将随着轮数的增加而增加，倘若这个流程一直没有因所有人都配上对了而终止，最终必然会出现某个男性追遍了所有女性的情况，而一个女性只要被人追过一次，以后就不可能单身了。既然所有女性都被这个男性追过，那么就说明所有女性现在都不是单身，也就是说此时所有人都已配对。

3、随着轮数的增加，一个男性追求女性的对象总是越来越糟，但一个女性的男友只可能变得越来越好。假设男 A 和女 1 各有各自的对象，但比起现在的对象，男 A 更喜欢女 1，因此男 A 之前肯定向女 1 表白过，既然女 1 最后没有跟男 A 在一起，那么说明女 1 拒绝了男 A，也即说明女 1 有了比男 A 更好的男性。

这就证明了，两个人虽然不是一对，但都觉得对方比自己现在的伴侣好的情况绝不会发生。

这个问题是数学界认真研究过的问题，但是相关理论最终给出的结果却很有意思，结果显示，对于传统的求爱过程来说，男性能够得到尽可能好的心上人，女性却不然。或者这也就是目前北上广深等大城市里面大龄剩女如此的多的原因。

事实上，稳定婚姻搭配往往不止一种，然而上述算法的结果可以保证，每一位男性得到的伴侣都是所有可能的稳定婚姻搭配方案中最理想的，同时每一位女性得到的伴侣都是所有可能的稳定婚姻搭配方案中最差的。

因此，这个算法告诉我们：要主动出击，不能守株待兔。