图论算法：如何找到最适合自己的另一半 ？

什么是算法？

每当有人问我这样的问题，我总会引用下面这个例子。 

假如你是一个媒人，有若干名单身男子登门求助，还有同样多的单身 女子也来征婚。如果你已经知道这些女孩儿在每个男孩儿心目中的排名，以及男孩儿们在每个女孩儿心目中的排名，那么你该怎样为他们牵线配对呢？ 

最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。

这当然很完美，但绝大多数情况下都不可能实现。

比方说，男 1 号的最爱是女 1 号，而女 1 号的最爱不是男 1 号，这两个人的最佳选择就不可能被同时满足。如果出现了好几位男士的最爱是同一个女孩儿的情况，这几位男士的首选也不会同时得到满足。

当这种最为理想的配对方案无法实现时， 怎样的配对方案才能令人满意呢？

其实，找对象不见得需要那么完美，和谐才是关键。

如果男 1 号和女 1 号各有各的对象，但男 1 号觉得女 1 号比自己的现任更好，女 1 号也觉得对方比自己的现任更好，那么两人就可能扔下自己现在的另一半，走在一起——因为这个结果对他们两人都更好一些。

如果在一种男女配对方案中出现了这种情况，我们就说这种配对方案是不稳定的。作为一个红娘，你深深地知道，介绍对象就怕婚姻关系不稳定。因此，在给客户牵线配对时，虽然不能让每个人都得到最合适的，但婚姻搭配必须得是稳定的。

现在，我们的问题就是：稳定的婚姻搭配总是存在的吗？如果存在，又应该怎样寻找出一个稳定的婚姻搭配？ 

为了便于分析，下面我们做一些约定。我们用字母 A、B、C 对男性进行编号，用数字 1、2、3 对女性进行编号。我们把所有男性从上到下列在左侧，括号里的数字表示每个人心目中对所有女性的排名；再把所有女性列在右侧，用括号里的字母表示她们对各位男性的偏好。

图 1 所示就是有 2 男 2 女的一种情形，每个男的都更喜欢女 1 号，但女 1 号更喜欢男 B，女 2 号更喜欢男 A。若按 A—1、B—2 进行搭配，则男 B 和女 1 都更喜欢对方一些，这样的婚姻搭配显然是不稳定的。但若换一种搭配方案(如图 2 所 示)，这样的搭配就是稳定的了。

 图 1 一个不稳定的婚姻搭配(男 B 和女 1 都不满意现任伴侣)

 图 2 一个稳定的婚姻搭配

可能很多人会立即想到一种寻找稳定婚姻搭配的策略：不断修补当前搭配方案。如果两个人互相之间都觉得对方比自己当前的伴侣更好，那就让这两个人成为一对，刚刚被甩的那两个人组成一对。如果还有想要在一起的男女对，就继续按照他们的愿望对换情侣，直到最终消除所有的不稳定组合。

容易看出，应用这种“修补策略”所得到的最终结果一定满足婚姻的稳定性，但这种策略的问题在于，它不一定有一个“最终结果”。按照 上述方法反复调整搭配方案，最终有可能陷入一个死循环，无法得出一个确定的方案(如图 3 所示)。

 图 3 应用“修补策略”可能会产生死循环

1962年，美国数学家戴维·盖尔(David Gale)和罗伊德·沙普利(Lloyd Shapley)发明了一种寻找稳定婚姻的策略。

不管男女各有多少人，也不管他们各自的偏好如何，应用这种策略后总能得到一个稳定的婚姻搭配。换句话说，他们证明了稳定的婚姻搭配总是存在的。

有趣的是，这种策略反映了现实生活中的很多真实情况。 

在这种策略中，男士将一轮一轮地去追求他中意的女子，而女子可以选择接受或拒绝相应的追求者。第一轮，每位男士都选择向自己最心仪的女子表白。

此时，每个女子可能面对的情况有三种：没有人向她表白，只有一个人向她表白，有不止一个人向她表白。

在第一种情况下，这个女子什么都不用做，只需继续等待；在第二种情况下，接受那个人的表白，答应暂时和他做男女朋友；在第三种情况下，从所有追求者中选择自己最中意的那一位，答应暂时和他做男女朋友，并拒绝其他所有的追求者。

第一轮结束后，有些男士已经有女朋友了，有些男士仍然单身。第二轮，每位单身男士都从所有尚未拒绝他的女子中选出自己最中意的，并向她表白，无论她现在是否单身。

和第一轮一样，每位女子需要从表白者中选择自己最中意的一位，拒绝其他追求者。

注意，如果这个女子已经有男朋友，当遇到更好的追求者时，她必须抛开现任男友，投向新的追求者的怀抱。这样，一些单身男士将会找到女友，而那些已经有女友的也可能会恢复单身。

在以后的每一轮中，单身的男士继续按照心目中的排序追求下一个女子，而女子则从包括现男友在内的所有追求者中选择自己最中意的一个，并对其他人说不。这样一轮一轮地进行下去，直到某个时候所有人都不再单身，接下来的一轮将不会发生任何表白，整个过程也就自动结束 (如图 4 所示)。此时的婚姻搭配就一定是稳定的了。

 图 4 应用上述策略，三轮之后将得出稳定的婚姻搭配

这个策略会不会像之前的修补法一样，出现永远也无法终止的情况呢？

不会。

下面我们将说明，随着轮数的增加，总有一个时候所有人都能配上对。

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

接下来，我们还需要证明，这样得出的配对方案确实是稳定的。

首先注意到，随着轮数的增加，一个男人追求的对象总是越来越糟，而一个女孩儿的男友只可能变得越来越好。假设男 A 和女 1 各自有各自的对象，但比起现在的对象来，男 A 更喜欢女 1。

因此，在此之前男 A 肯定已经跟女 1 表白过。既然女 1 最后没有跟男 A 在一起，说明女 1 拒绝了男 A，也就是说她有了比男 A 更好的男人。这就证明了，两个人虽然不是一对，但都觉得对方比自己现在的伴侣好，这样的情况绝不可能发生。

我们把用来解决某种问题的一个策略，或者说一个方案，或者说一个 处理过程，或者说一系列操作规则，或者更贴切的，一套计算方法，叫作“算法”(algorithm)。

上面这个用来寻找稳定婚姻的策略就叫作“盖尔–沙普利算法”(Gale-Shapley algorithm)，有些人也管它叫“延迟认可算法”(deferred acceptance algorithm)。

盖尔–沙普利算法带给我们很多启发。作为一个为这些男女牵线的媒人，你并不需要亲自使用这个算法来计算稳定匹配，甚至根本不需要了解每个人的偏好，而只需按照这个算法组织一个男女配对活动即可。你要做的仅仅是把算法流程当作游戏规则告诉大家，游戏结束后会自动得到一个大家都满意的婚姻匹配。

整个算法可以简单地描述为：每个人都去做自己想做的事情。

对于男性来说，从最喜欢的女子开始追起是顺理成章的事；对于女性来说，不断选择最好的男子也正好符合她的利益。因此，大家会自动遵守游戏规则，无须担心有人虚报自己的偏好。 

历史上，这样的“配对游戏”还真有过实际应用，并且更有意思的是， 这个算法的应用居然比算法本身的提出还早 10 年。

早在 1952 年，美国就开始用这种办法给医学院的学生安排工作，这被称为“全国住院医师配对项目”。

配对的基本流程就是，各医院从尚未拒绝这一职位的医学院学生中 选出最佳人选并发送聘用通知，当学生收到来自各医院的聘用通知后，系统会根据他所填写的意愿表自动将其分配到意愿最高的职位，并拒绝掉其他的职位。如此反复，直到每个学生都分配到了工作。

当然，那时人们并不知道这样的流程可以保证工作分配的稳定性，只是凭直觉认为这是很合理的。直到 10 年之后，盖尔和沙普利才系统地研究了这个流程，提出了稳定婚姻问题，并证明了这个算法的正确性。

这套理论成功地解决了诸多市场资源配置问题，罗伊德·沙普利也因此获得了 2012 年诺贝尔经济学奖。很可惜，戴维·盖尔没能与他共享这一荣誉——他在 2008 年就已经离开人 世了。

盖尔–沙普利算法还有很多有趣的性质。比如说，大家可能会想，这种男追女女拒男的方案对男性更有利还是对女性更有利呢？答案是，这种方案对男性更有利。

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

当然，为了得到一种对女性最优的稳定婚姻搭配，我们只需要把整个算法反过来，让女孩儿去追男孩儿，男孩儿拒绝女孩儿就行了。

这个算法还有一些局限性。例如，它无法处理 2𝑛 个人不分男女的稳定搭配问题。

一个简单的应用场景便是宿舍分配问题：假设每个宿舍住两个 人，已知 2𝑛 个学生中每一个学生对其余 寻找一个稳定的宿舍分配？此时，盖尔 2𝑛 − 1 个学生的偏好评价，如何 –沙普利算法就不再有用武之地了。

而事实上，宿舍分配问题中很可能根本就不存在稳定的搭配。例如，有 A、 B、C、D 四个人，其中 A 把 B 排在第一，B 把 C 排在第一，C 把 A 排在第 一，而且他们三人都把 D 排在最后。容易看出，此时一定不存在稳定的宿舍分配方案。倘若 A、D 同宿舍，B、C 同宿舍，那么 C 会认为 A 是更好的室友(因为 C 把 A 排在了第一)，同时 A 会认为 C 是更好的室友(因为他 把 D 排在了最后)。同理，B、D 同宿舍或者 C、D 同宿舍也都是不行的，因而稳定的宿舍分配是不存在的。

此时，重新定义宿舍分配的优劣性便是一个更为基本的问题。稳定婚姻问题还有很多其他的变种，有些问题至今仍然没有一种有效的算法。这些问题都是图论当中非常有趣的话题。