gale-shapley算法

《gale-shapley算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、什么是算法？每当有人问作者这样的问题时，他总会引用这个例子：假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩儿在每个男孩儿心目中的排名，以及男孩儿们在每个女孩儿心中的排名，你应该怎样为他们牵线配对呢？最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。这虽然很完美，但绝大多数情况下都不可能实现。比方说，男1号最喜欢的是女1号，而女1号的最爱不是男1号，这两个人的最佳选择就不可能被同时满足。如果好几个男孩儿最喜欢的都是同一个女孩儿，这几个男孩儿的首选也不会同时得到满足。当这种最为理想的配对方案无法实现时，怎样的配对方案才

2、能令人满意呢？其实，找的对象太完美不见得是好事儿，和谐才是婚姻的关键。如果男1号和女1号各有各的对象，但男1号觉得，比起自己现在的，女1号更好一些；女1号也发现，在自己心目中，男1号的排名比现男友更靠前。这样一来，这两人就可能抛弃各自现在的对象——如果出现了这种情况，我们就说婚姻搭配是不稳定的。作为一个红娘，你深知，对象介绍得不好没关系，就怕婚姻关系不稳定。给客户牵线配对时，虽然不能让每个人都得到最满意的，但搭配必须得稳定。换句话说，对于每一个人，在他心目中比他当前伴侣更好的异性，都不会认为他也是一个更好的选择。现在，我们的问题是：稳定的婚姻搭配总是存在吗？应该怎样寻找？一次失败

3、的尝试为了便于分析，我们下面做一些约定。我们用字母A、B、C对男性进行编号，用数字1、2、3对女性进行编号。我们把所有男性从上到下列在左侧，括号里的数字表示每个人心目中对所有女性的排名；再把所有女性列在右侧，用括号里的字母表示她们对男性的偏好。图1所示的就是2男2女的一种情形，每个男的都更喜欢女1号，但女1号更喜欢男B，女2号更喜欢男A。若按A-1、B-2进行搭配，则男B和女1都更喜欢对方一些，这样的婚姻搭配就是不稳定的。但若换一种搭配方案（如图2），这样的搭配就是稳定的了。图1一个不稳定的婚姻搭配图可能很多人会立即想到一种寻找稳定婚姻搭配的策略：不断修补当前搭配方案。如果两个人

4、互相都觉得对方比自己当前的伴侣更好，就让这两个人成为一对，剩下被甩的那两个人组成一对。图2一个稳定的婚姻搭配如果还有想要私奔的男女对，就继续按照他们的愿望对换情侣，直到最终消除所有的不稳定组合。容易看出，应用这种“修补策略”所得到的最终结果一定满足稳定性，但这种策略的问题在于，它不一定存在“最终结果”。事实上，按照上述方法反复调整搭配方案，最终可能会陷入一个死循环，因此该策略甚至不能保证得出一个确定的方案来，如图3所示。图3应用“修补策略”可能会产生死循环Gale-Shapley算法1962年，美国数学家DavidGale和LloydShapley发明了一种寻找稳定婚姻的策略。不

5、管男女各有多少人，也不管他们的偏好如何，应用这种策略后总能得到一个稳定的搭配。换句话说，他们证明了稳定的婚姻搭配总是存在的。有趣的是，这种策略反映了现实生活中的很多真实情况。在这种策略中，男孩儿将一轮一轮地去追求他中意的女子，女子可以选择接受或者拒绝他的追求者。第一轮，每个男孩儿都选择自己名单上排在首位的女孩儿，并向她表白。此时，一个女孩儿可能面对的情况有三种：没有人跟她表白，只有一个人跟她表白，有不止一个人跟她表白。在第一种情况下，这个女孩儿什么都不用做，只需要继续等待；在第二种情况下，接受那个人的表白，答应暂时和他做情侣；在第三种情况下，从所有追求者中选择自己最中意的那一位，

6、答应和他暂时做情侣，并拒绝所有其他追求者。第一轮结束后，有些男孩儿已经有女朋友了，有些男孩儿仍然是单身。在第二轮追女行动中，每个单身男孩儿都从所有还没拒绝过他的女孩儿中选出自己最中意的那一个，并向她表白，不管她现在是否是单身。和第一轮一样，女孩儿们需要从表白者中选择最中意的一位，拒绝其他追求者。注意，如果这个女孩儿已经有男朋友了，当她遇到了更好的追求者时，她必须拒绝掉现在的男友，投向新的追求者的怀抱。这样，一些单身男孩儿将会得到女友，那些已经有了女友的人也可能重新变成光棍。在以后的每一轮中，单身男孩儿继续追求列表中的下一个女孩儿，女孩儿则从包括现男友在内的所有追求者中选择最好的一

7、个，并对其他人说不。这样一轮一轮地进行下去，直到某个时候所有人都不再单身，下一轮将不会有任何新的表白发生，整个过程自动结束。此时的婚姻搭配就一定是稳定的了。这个策略会不会像之前的修补法一样，出现永远也无法终止的情况呢？不会。下面我们将说明，随着轮数的增加，总有一个时候所有人都能配对。由于在每一轮中，至少会有一个男孩儿向某个女孩儿告白，因此总的告白次数将随着轮数的增加而增加。倘若整个流程一直没有因所有人都配上对了而结束，最终必然会出现某个男孩儿追遍了所有女孩儿的情况。而一个女孩儿只