国家互联网信息办公室|优秀程序员必会算法之延迟认可算法网络安全

文章图片

一些优秀的算法就好像围棋中的定式，或者是程序设计中的设计模式一样，前人已经在总结了该类问题的基础之上，给出了完备的解决方法。那么对于一名优秀的程序员来说，就需要了解这些算法，并且在遇到类似的问题的时候，第一时间就会想到应用这种算法。这样会大大地提高编程的效率。
今天我们就来看一下延迟认可算法。了解延迟认可算法之前，我们先需要了解一下稳定婚姻问题。
所以稳定婚姻问题，通俗地可叙述为：当前有N位男生和N位女生最后要组成稳定的婚姻家庭，过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序，男生和女生结婚后，对于每一对男生女生，不会出现比起当前匹配的伴侣互相更喜爱的一对男生女生，即可认为婚姻是稳定的。
【国家互联网信息办公室|优秀程序员必会算法之延迟认可算法】
稳定婚姻问题可以用在很多领域，例如将用户分配给大型分布式Internet服务中的服务器。数十亿用户访问Internet上的网页，视频和其他服务，要求每个用户都与全球提供该服务的数十万台服务器之一匹配。用户希望服务器足够近，以便为所请求的服务提供更快的响应时间，从而导致每个用户对服务器的（部分）优先排序。每个服务器都希望以较低的成本为用户提供服务，从而导致每个服务器的用户（部分）优先排序。分发世界上许多内容和服务的内容交付网络每数十秒就解决了用户与服务器之间这个庞大而又复杂的稳定婚姻问题，使数十亿用户可以与各自的服务器进行匹配，以提供所需的网页，视频或其他内容服务。
1962年，美国数学家David Gale和Lloyd Shapley发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。
该算法的执行步骤如下，在计算策略中，男性将一轮轮的去追求他中意的女性，而女性则可以选择接受或者拒绝她的追求者。
那么，首先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：
1、每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
2、每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。
3、若某男士被其女友抛弃，重新变成自由男。

在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利，当然，新的追求对象比不过前女友。
这样，在算法执行期间，每个人都有可能订婚多次，也有可能一开始就找到了自己的最爱，从一而终。
而每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣，虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。