稳定婚姻匹配问题的一个快速枚举算法

宋旭东， 纪秀花

（山东经济学院计算机科学与技术学院，山东 济南 250014）

1962 年两个数理经济学家David Gale 和Lloyd Shapley在一篇名为“College Admissions and the Stability of Marriage”[1]的论文中首次引出并介绍了稳定婚姻问题。考虑n个男人的集合M={m1，m2，…，mn}和n个女人的集合W={w1，w2，…，wn}。令M×W为所有可能的形如(m, w)的有序对的集合。其中m∈M，w∈W。一个匹配S是来自M×W的有序对的集合，并且具有下述性质：每个M的成员和每个W的成员至多出现在S的一个有序对中。一个完美匹配S′是具有下述性质的匹配：M的每个成员和W的每个成员恰好出现在S′的一个对里。一个完美匹配仅仅对应于一个男女配对的方式，以这种方式，每个人最终与某个人结婚，且没有人与多个人结婚。在完美匹配的背景下又引入优先的概念，每个男人m∈M 对所有的女人排名，如果m给w的排名高于w′，我们就说m偏爱w超过w′。我们将把m的按顺序的排名作为他的优先表，但不允许排名出现并列的情况。类似的，每个女人也对所有男人排名。给定一个完美匹配S，在S中存在两个配对(m, w)和(m′, w′），他们具有m更偏爱w′而不爱w，且w′更偏爱m而不爱m′的性质，在这种情况下，我们称这个完美匹配S是不稳定的，我们称像(m, w′)这样的对是一个相对于S的不稳定因素。我们说一个匹配S是稳定的，那么要满足以下两点：① S是完美匹配；② 不存在相对于S的不稳定因素[2-9]。

这个问题被应用到学生的入学、工作招聘等处理过程中，最早是在美国国家医生匹配计划中一个类似的过程被用来将医生和医院进行匹 配[2]。 法[10]能有效的让我们找到其中一个稳定匹配结

目前，Gale-shapley算法[1-2]，回溯法和回跳果，其中最有名的算法是Gale-shapley算法。本文设计了一种基于先序遍历森林的快速枚举算法，以求得所有可能的稳定匹配结果，并且由Gale-shapley算法的性质推得一个定理及其推论，又根据推论进一步改进了这个枚举算法。

1 Gale-Shapley 算法

1.1 Gale-Shapley 算法基本思想

Gale-Shapley算法的基本思想如下[2]：

（1） 初始，每个人都是未婚的。假设一个未婚的男人m选择了他的优先表上排名最高的女人w，并且向她求婚。我们不能立刻声明(m, w)将是最后稳定匹配中的一对，因为在将来的某个时候，女人w偏爱的男人m′可能向她求婚。另一方面，对w来说，立刻拒绝m可能是危险的，她之后可能没有接收到来自她的优先表上排名高于m的某个人的求婚。于是，一种自然的想法是使 (m,w) 这个对进入一种中间状态——约会。

（2） 假设我们现在处在某种状态，某些男人和女人是自由的（没有约会），某些是有约会的。任意一个自由的男人m选择他还没有求过婚的最高排名的女人w，并且向她求婚。如果w也是自由的，那么m和w就成为约会状态。否则，w已经在与某个其他的男人m′约会，在这种情况下，根据w的优先表中m和m′的排名来选择，排名较高的男人变成与w约会而另一个人变成自由的。

（3） 最后，当没有一个人是自由的时候，算法将结束；此刻所有的约会将被宣告为最后的结果，且将返回最终的完美匹配。文献[2]中给出证明，该完美匹配是一个稳定匹配。

在上述算法中，由于总是未婚的男人向女人求婚，它常常被称为“man propose, women dispose”（“男性优先选择”，下文都用“男优先”表示）。当然该算法实现时也可以总是未婚的女人向男人求婚，这被称为“woman propose, men dispose”（“女性优先选择”，下文都用“女优先”表示）。

1.2 Gale-Shapley 算法的性质

根据上述Gale-Shapley算法的基本思想，可以得到该算法的几个性质[1-3,9]。

在稳定婚姻问题中，设有N个男人和N个女人，男人i 对女人j 的偏好排名用一个整数 k=MXH(i, j)表示（MXH为 N×N 矩阵，表示男人对女人的偏爱程度列表）。 同理，女人i 对男人j 的偏好排名用一个整数 t=WXH(i, j )表示（WXH为N×N矩阵，表示女人对男人的偏爱程度列表），1≤k (或t )≤N。

按照 Gale-Shapley 算法，我们一定能得到一个稳定婚姻。也就是说，不管这N个男人和N个女人的优先表是如何分布的，至少存在一个稳定婚姻匹配。在“男优先”算法实现中，得到的一个稳定婚姻匹配具有如下三点性质：

（1） 男性能够获得尽可能好的伴侣，结果是：如果还存在其他的稳定匹配，那么里面任何一个男性的伴侣排名都不会比“男优先”得到的结果更好，我们说此种情况每个男性获得的是“最好”的伴侣。

（2） 女性却只能被动地一步步接近她最爱的目标, 但最后往往达不到，结果是：如果还存在其他的稳定匹配，那么里面任何一个女性的伴侣排名都不会比“男优先”得到的结果更差，我们说此种情况每个女性获得是“最差”的伴侣。

（3） 无论男性们求婚的先后顺序如何，最终得到的是同一个稳定婚姻匹配。

当然，这个算法的实现也可是：“女优先”，同样，得到的此稳定婚姻匹配具有对应的三点性质：

（1） 在所有可能的稳定婚姻匹配中，“女优先”得到的结果中每个女性获得的是“最好”的伴侣。

（2） 在所有可能的稳定婚姻匹配中，“女优先”得到的结果中每个男性获得的是“最差”的伴侣。

（3） 无论女性们求婚的先后顺序如何，“女优先”最终得到的是同一个稳定婚姻匹配。

2 基于先序遍历森林的算法

Gale-Shapley算法只是能找到一个稳定匹配结果。如果我们想找到所有的稳定匹配结果，若用穷举法解决这个问题，对有N个男人和N个女人的情形，需要考虑N！种可能的婚姻匹配结果，并且需要对其中每一种婚配方式检查其是否存在不稳定因素。显然，该算法的复杂度太大。

当有k(＞1)种稳定匹配结果，下面将设计算法找出这k种稳定匹配。可将这N！种可能的婚姻匹配结果构成一森林（见图1，N=4情形）。树中各结点的数字对应女性序号，树的每一层对应同一男性序号（见图1中最左侧数字）。从森林中每棵树的根到叶子结点路径上，所有结点中的数字组成一个数字串表示一种完美婚姻匹配。

例1 第一棵树最左边路径④③②①对应的婚姻匹配为：

man 4 – woman ④、man 3 – woman ③、man 2 – woman ②、man 1 – woman ①

例2 第二棵树最右边路径③①②④对应的婚姻匹配为：

man 4 – woman ③、man 3 – woman ①、man 2 – woman ②、man 1 – woman ④

图1 婚姻匹配森林（N = 4）

2.1 新算法基本思想

要检查每一种婚配方式是否存在不稳定因素，可按先序遍历的顺序访问整个森林，当每到一结点时，需要将此结点对应的配对分别与其祖先的某一些结点（即满足一定条件的结点，后面将做详细说明）对应的配对按照优先表，检查是否存在不稳定因素：

（1） 假设不存在不稳定因素，若访问的结点为叶子结点，则输出此稳定婚姻匹配；若不是叶子节点则继续向下层遍历访问。

（2） 假设存在不稳定因素，则跳过此结点及其所有子孙结点，继续向其他分支遍历访问。直到遍历结束。

这样做的优点是消除了许多重复的操作，从而大大节省了时间。

2.2 新算法的具体描述

整个过程按照先序遍历的顺序访问森林的每个结点，每到一个结点按照优先表，检查其配对情况与其祖先的配对情况，看是否存在不稳定因素。下面给出求解所有稳定婚姻匹配结果的算法实现描述。该算法实现主要包括两个过程：一个是主过程GSM（），一个是子过程SM（）。

说明：当每到一结点时，要检测该结点对应的配对(manX, womanY )加入后是否会出现不稳定因素，只需考虑两种情况[10]：① 男性manX是否会与其他已婚女性产生不稳定因素，在这里并不需要考虑所有已婚女子（即其祖先的所有结点对应的配对女性），而只需考虑男性优先表中manX 对女性排名的前k-1(k=MXH(manX, womanY))个女性当中的已婚女性，因为排名在k以后的已婚女性一定不会与男性manX产生不稳定因素；② 女性womanY 是否会与其他已婚男性产生不稳定因素，同样在这里也不需要考虑其所有祖先结点对应的所有已婚男子，而只需考虑女性优先表中womanY 对男性排名的前L-1(L =WXH(womanY, manX))个男性中的已婚男性。只有上述两种情况都为否定，才能继续向下遍历孩子结点。

此算法是以递归的方式实现。从算法的流程易看出，每种婚姻匹配都已考虑在内，说明此算法是正确的。此算法的优点：对于众多不同的婚姻匹配，它们包含相同的配对部分是不会重复判断的，这样大大节省了时间。为了进一步提高速度，还可对上述算法进一步改进。

3 改进算法

通过对按照“男优先”或“女优先”实现的Gale-Shapley算法性质的研究，可推得如下定理：

定理对某优先表分布情况，分别按照“男优先”和“女优先”来求得两个稳定婚姻匹配，若这两个稳定婚姻匹配是相同的，则此种情况就只存在一个稳定婚姻匹配；若这两个稳定婚姻匹配是不相同的，则此种情况就存在多于1个的稳定婚姻匹配。

证明定理的后半部分显然正确。下面对定理的前半部分给出证明。

假设有N个男人为：A、B、C、D、…、X、…、 Y、…，有N个女人为：a、b、c、d、…、x、…、y、…。“男优先”和“女优先”两个稳定婚姻匹配结果相同都是：A-a, B-b, C-c, D-d, …（记为α匹配）；

如果还存在另一个与上不同的稳定婚姻匹配，对其中不相同的一部分，不妨可表示为：…, B-x, …, Y-b, …（记为β 匹配）。

因为α 匹配是按照“男优先”或“女优先”来求得的，所以根据前面提到的 Gale-Shapley 算法的性质可知：在所有可能的稳定婚姻匹配中，b是男性B获得的最好的女性伴侣，同样，B是女性b获得的最好的男性伴侣，这样，针对β 匹配中，男性B更喜欢女性b胜过x，同样女性b也更喜欢男性B胜过Y，所以推得β 匹配不是稳定婚姻匹配，与假设不符，所以不会存在其他的稳定婚姻匹配。□

由上述定理，可得如下推论：

推论当分别按照“男优先”和“女优先”求得两个不同的稳定婚姻匹配时，若这两个不同的稳定婚姻匹配中有一部分配对是相同的，则：若还存在其他稳定婚姻匹配，仍会包含这部分相同的配对。

证明假设分别按照“男优先”和“女优先”求得两个不同的稳定婚姻匹配时，若这两个不同的稳定婚姻匹配中有m个配对是相同的，令：

这m个配对中男人为：A、B、C、D、…、X、…、Y、…

女人为：a、b、c、d、…、x、…、y、…

设按照“男优先”和“女优先”得到的两个稳定婚姻匹配中都共同含有如下m个配对：

A-a, B-b, C-c, D-d, …（记为α 匹配）

假设还存在另一个稳定匹配其中不完全包括这个公共部分，有不相同处，对其中不相同的一部分，不妨可表示为：

…, B-x, …, Y-b, …（记为β 匹配）

剩余部分证明与上述定理的证明相似，在此略。□

根据此推论，可得到改进算法的基本思想：首先分别按照“男优先”和“女优先”求得两个不同的稳定婚姻匹配，根据推论可知，若这两个不同的稳定婚姻匹配中有m个配对是相同的，则所有稳定婚姻匹配中的这一部分是已知的。这样，在求解之前，可将这些已配对的m个男性和m个女性从问题中删去。这样问题就降为求N-m个男人和N-m个女人的稳定婚姻匹配了。

改进算法具体描述：

按“男优先”求得一个稳定婚姻匹配；

按“女优先”求得另一个稳定婚姻匹配； 若二者相同，则输出这唯一的稳定婚姻匹配，退出。

若二者不相同：

找出二者相同的配对部分； 若无相同的配对部分，则执行GSM( )； 若有m(m≠0)个相同的配对部分，则：

输出这m(m≠0)个相同的配对部分；

将MXH、WXH中的这些男、女对应的行列删除；

此改进算法的正确性说明：此思想是依据推论，所以已证明。

此改进算法的时间复杂性分析：

（1） 若求得的两个稳定婚姻匹配中有m个配对是相同的，问题可就转化为求（N-m）对男女的婚配问题，则图1中森林的规模将减小N(N-1)…(N-m+1)倍，所以算法的速度比原算法GSM( )的速度提高N(N-1)…(N-m+1)倍。

（2） 若求得的两个稳定婚姻匹配中无配对是相同时，也只是多了2次运行Gale-Shapley算法的时间，相比之下，不会影响原算法GSM( )的时间复杂度。

4 结 束 语

稳定婚姻问题被应用到许多实际问题的处理过程中，例如学生的入学，工作招聘，医生和医院进行匹配等。为快速找出所有可能的稳定匹配结果，我们设计了基于先序遍历森林的快速枚举算法。利用此算法，对于众多不同的婚姻匹配，不会重复判断它们包含相同的配对子部分，这样大大节省了时间。为了进一步提高速度，由Gale-Shapley算法的性质证明得到了一个定理及其推论，并利用推论对算法做了进一步改进。在满足推论的特定状况下，提高了原算法的执行时间。

[1] Gale D, Shapley L S. College admissions and the stability of marriage [J]. American Mathematical Monthly, 1962, 69： 9-15.

[2] Jon Kleinberg, Éva Tardos. Algorithm design [M]. Addition Wesley, 2005. 1-12.

[3] Hpfieldand J J, Tank D W. Neural computation of decisions in optimization problems [J]. Biological Cybernetics, 1985, (52)： 141-152.

[4] McVitie D G, Wilson L B. The stable marriage problem [J]. Communications of the ACM, 1971, 14(7)： 486-492.

[5] Irving R W, Leather P. The complexity of counting stable marriages [J]. SIAM Journal on Computing, 1986, 15(3)： 655-667.

[6] Knuth D E. Marriage satble [J]. Les Presses de L'universite de Montreal, Montreal, 1976, (8)： 66-68.

[7] Wirving R. An efficient algorithmfor the “stable roommates” problem [J]. J. Algorithms, 1985, (6)： 577-595.

[8] Wilson L B. An analsis of the stable marriage assignment problem [J]. BIT, 1972, (12)： 569-575.

[9] Gusfield D, Irving R W. The stable marriage problem, structure and algorithms [M]. MIT Press, 1989. 1-3, 5-20.

[10] 郭东亮, 张立臣. 用回跳法求解稳定婚姻问题[J].计算机应用研究, 2005, 22(1)： 59-60, 63.