穩(wěn)定婚姻匹配問題的一個快速枚舉算法

宋旭東， 紀(jì)秀花

（山東經(jīng)濟(jì)學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250014）

1962 年兩個數(shù)理經(jīng)濟(jì)學(xué)家David Gale 和Lloyd Shapley在一篇名為“College Admissions and the Stability of Marriage”[1]的論文中首次引出并介紹了穩(wěn)定婚姻問題?？紤]n個男人的集合M={m1，m2，…，mn}和n個女人的集合W={w1，w2，…，wn}。令M×W為所有可能的形如(m, w)的有序?qū)Φ募?。其中m∈M，w∈W。一個匹配S是來自M×W的有序?qū)Φ募希⑶揖哂邢率鲂再|(zhì)：每個M的成員和每個W的成員至多出現(xiàn)在S的一個有序?qū)χ?。一個完美匹配S′是具有下述性質(zhì)的匹配：M的每個成員和W的每個成員恰好出現(xiàn)在S′的一個對里。一個完美匹配僅僅對應(yīng)于一個男女配對的方式，以這種方式，每個人最終與某個人結(jié)婚，且沒有人與多個人結(jié)婚。在完美匹配的背景下又引入優(yōu)先的概念，每個男人m∈M 對所有的女人排名，如果m給w的排名高于w′，我們就說m偏愛w超過w′。我們將把m的按順序的排名作為他的優(yōu)先表，但不允許排名出現(xiàn)并列的情況。類似的，每個女人也對所有男人排名。給定一個完美匹配S，在S中存在兩個配對(m, w)和(m′, w′），他們具有m更偏愛w′而不愛w，且w′更偏愛m而不愛m′的性質(zhì)，在這種情況下，我們稱這個完美匹配S是不穩(wěn)定的，我們稱像(m, w′)這樣的對是一個相對于S的不穩(wěn)定因素。我們說一個匹配S是穩(wěn)定的，那么要滿足以下兩點：① S是完美匹配；② 不存在相對于S的不穩(wěn)定因素[2-9]。

這個問題被應(yīng)用到學(xué)生的入學(xué)、工作招聘等處理過程中，最早是在美國國家醫(yī)生匹配計劃中一個類似的過程被用來將醫(yī)生和醫(yī)院進(jìn)行匹 配[2]。 法[10]能有效的讓我們找到其中一個穩(wěn)定匹配結(jié)

目前，Gale-shapley算法[1-2]，回溯法和回跳果，其中最有名的算法是Gale-shapley算法。本文設(shè)計了一種基于先序遍歷森林的快速枚舉算法，以求得所有可能的穩(wěn)定匹配結(jié)果，并且由Gale-shapley算法的性質(zhì)推得一個定理及其推論，又根據(jù)推論進(jìn)一步改進(jìn)了這個枚舉算法。

1 Gale-Shapley 算法

1.1 Gale-Shapley 算法基本思想

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

（1） 初始，每個人都是未婚的。假設(shè)一個未婚的男人m選擇了他的優(yōu)先表上排名最高的女人w，并且向她求婚。我們不能立刻聲明(m, w)將是最后穩(wěn)定匹配中的一對，因為在將來的某個時候，女人w偏愛的男人m′可能向她求婚。另一方面，對w來說，立刻拒絕m可能是危險的，她之后可能沒有接收到來自她的優(yōu)先表上排名高于m的某個人的求婚。于是，一種自然的想法是使 (m,w) 這個對進(jìn)入一種中間狀態(tài)——約會。

（2） 假設(shè)我們現(xiàn)在處在某種狀態(tài)，某些男人和女人是自由的（沒有約會），某些是有約會的。任意一個自由的男人m選擇他還沒有求過婚的最高排名的女人w，并且向她求婚。如果w也是自由的，那么m和w就成為約會狀態(tài)。否則，w已經(jīng)在與某個其他的男人m′約會，在這種情況下，根據(jù)w的優(yōu)先表中m和m′的排名來選擇，排名較高的男人變成與w約會而另一個人變成自由的。

（3） 最后，當(dāng)沒有一個人是自由的時候，算法將結(jié)束；此刻所有的約會將被宣告為最后的結(jié)果，且將返回最終的完美匹配。文獻(xiàn)[2]中給出證明，該完美匹配是一個穩(wěn)定匹配。

在上述算法中，由于總是未婚的男人向女人求婚，它常常被稱為“man propose, women dispose”（“男性優(yōu)先選擇”，下文都用“男優(yōu)先”表示）。當(dāng)然該算法實現(xiàn)時也可以總是未婚的女人向男人求婚，這被稱為“woman propose, men dispose”（“女性優(yōu)先選擇”，下文都用“女優(yōu)先”表示）。

1.2 Gale-Shapley 算法的性質(zhì)

根據(jù)上述Gale-Shapley算法的基本思想，可以得到該算法的幾個性質(zhì)[1-3,9]。

在穩(wěn)定婚姻問題中，設(shè)有N個男人和N個女人，男人i 對女人j 的偏好排名用一個整數(shù) k=MXH(i, j)表示（MXH為 N×N 矩陣，表示男人對女人的偏愛程度列表）。 同理，女人i 對男人j 的偏好排名用一個整數(shù) t=WXH(i, j )表示（WXH為N×N矩陣，表示女人對男人的偏愛程度列表），1≤k (或t )≤N。

按照 Gale-Shapley 算法，我們一定能得到一個穩(wěn)定婚姻。也就是說，不管這N個男人和N個女人的優(yōu)先表是如何分布的，至少存在一個穩(wěn)定婚姻匹配。在“男優(yōu)先”算法實現(xiàn)中，得到的一個穩(wěn)定婚姻匹配具有如下三點性質(zhì)：

（1） 男性能夠獲得盡可能好的伴侶，結(jié)果是：如果還存在其他的穩(wěn)定匹配，那么里面任何一個男性的伴侶排名都不會比“男優(yōu)先”得到的結(jié)果更好，我們說此種情況每個男性獲得的是“最好”的伴侶。

（2） 女性卻只能被動地一步步接近她最愛的目標(biāo), 但最后往往達(dá)不到，結(jié)果是：如果還存在其他的穩(wěn)定匹配，那么里面任何一個女性的伴侶排名都不會比“男優(yōu)先”得到的結(jié)果更差，我們說此種情況每個女性獲得是“最差”的伴侶。

（3） 無論男性們求婚的先后順序如何，最終得到的是同一個穩(wěn)定婚姻匹配。

當(dāng)然，這個算法的實現(xiàn)也可是：“女優(yōu)先”，同樣，得到的此穩(wěn)定婚姻匹配具有對應(yīng)的三點性質(zhì)：

（1） 在所有可能的穩(wěn)定婚姻匹配中，“女優(yōu)先”得到的結(jié)果中每個女性獲得的是“最好”的伴侶。

（2） 在所有可能的穩(wěn)定婚姻匹配中，“女優(yōu)先”得到的結(jié)果中每個男性獲得的是“最差”的伴侶。

（3） 無論女性們求婚的先后順序如何，“女優(yōu)先”最終得到的是同一個穩(wěn)定婚姻匹配。

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

Gale-Shapley算法只是能找到一個穩(wěn)定匹配結(jié)果。如果我們想找到所有的穩(wěn)定匹配結(jié)果，若用窮舉法解決這個問題，對有N個男人和N個女人的情形，需要考慮N！種可能的婚姻匹配結(jié)果，并且需要對其中每一種婚配方式檢查其是否存在不穩(wěn)定因素。顯然，該算法的復(fù)雜度太大。

當(dāng)有k(＞1)種穩(wěn)定匹配結(jié)果，下面將設(shè)計算法找出這k種穩(wěn)定匹配。可將這N！種可能的婚姻匹配結(jié)果構(gòu)成一森林（見圖1，N=4情形）。樹中各結(jié)點的數(shù)字對應(yīng)女性序號，樹的每一層對應(yīng)同一男性序號（見圖1中最左側(cè)數(shù)字）。從森林中每棵樹的根到葉子結(jié)點路徑上，所有結(jié)點中的數(shù)字組成一個數(shù)字串表示一種完美婚姻匹配。

例1 第一棵樹最左邊路徑④③②①對應(yīng)的婚姻匹配為：

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

例2 第二棵樹最右邊路徑③①②④對應(yīng)的婚姻匹配為：

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

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

2.1 新算法基本思想

要檢查每一種婚配方式是否存在不穩(wěn)定因素，可按先序遍歷的順序訪問整個森林，當(dāng)每到一結(jié)點時，需要將此結(jié)點對應(yīng)的配對分別與其祖先的某一些結(jié)點（即滿足一定條件的結(jié)點，后面將做詳細(xì)說明）對應(yīng)的配對按照優(yōu)先表，檢查是否存在不穩(wěn)定因素：

（1） 假設(shè)不存在不穩(wěn)定因素，若訪問的結(jié)點為葉子結(jié)點，則輸出此穩(wěn)定婚姻匹配；若不是葉子節(jié)點則繼續(xù)向下層遍歷訪問。

（2） 假設(shè)存在不穩(wěn)定因素，則跳過此結(jié)點及其所有子孫結(jié)點，繼續(xù)向其他分支遍歷訪問。直到遍歷結(jié)束。

這樣做的優(yōu)點是消除了許多重復(fù)的操作，從而大大節(jié)省了時間。

2.2 新算法的具體描述

整個過程按照先序遍歷的順序訪問森林的每個結(jié)點，每到一個結(jié)點按照優(yōu)先表，檢查其配對情況與其祖先的配對情況，看是否存在不穩(wěn)定因素。下面給出求解所有穩(wěn)定婚姻匹配結(jié)果的算法實現(xiàn)描述。該算法實現(xiàn)主要包括兩個過程：一個是主過程GSM（），一個是子過程SM（）。

說明：當(dāng)每到一結(jié)點時，要檢測該結(jié)點對應(yīng)的配對(manX, womanY )加入后是否會出現(xiàn)不穩(wěn)定因素，只需考慮兩種情況[10]：① 男性manX是否會與其他已婚女性產(chǎn)生不穩(wěn)定因素，在這里并不需要考慮所有已婚女子（即其祖先的所有結(jié)點對應(yīng)的配對女性），而只需考慮男性優(yōu)先表中manX 對女性排名的前k-1(k=MXH(manX, womanY))個女性當(dāng)中的已婚女性，因為排名在k以后的已婚女性一定不會與男性manX產(chǎn)生不穩(wěn)定因素；② 女性womanY 是否會與其他已婚男性產(chǎn)生不穩(wěn)定因素，同樣在這里也不需要考慮其所有祖先結(jié)點對應(yīng)的所有已婚男子，而只需考慮女性優(yōu)先表中womanY 對男性排名的前L-1(L =WXH(womanY, manX))個男性中的已婚男性。只有上述兩種情況都為否定，才能繼續(xù)向下遍歷孩子結(jié)點。

此算法是以遞歸的方式實現(xiàn)。從算法的流程易看出，每種婚姻匹配都已考慮在內(nèi)，說明此算法是正確的。此算法的優(yōu)點：對于眾多不同的婚姻匹配，它們包含相同的配對部分是不會重復(fù)判斷的，這樣大大節(jié)省了時間。為了進(jìn)一步提高速度，還可對上述算法進(jìn)一步改進(jìn)。

3 改進(jìn)算法

通過對按照“男優(yōu)先”或“女優(yōu)先”實現(xiàn)的Gale-Shapley算法性質(zhì)的研究，可推得如下定理：

定理對某優(yōu)先表分布情況，分別按照“男優(yōu)先”和“女優(yōu)先”來求得兩個穩(wěn)定婚姻匹配，若這兩個穩(wěn)定婚姻匹配是相同的，則此種情況就只存在一個穩(wěn)定婚姻匹配；若這兩個穩(wěn)定婚姻匹配是不相同的，則此種情況就存在多于1個的穩(wěn)定婚姻匹配。

證明定理的后半部分顯然正確。下面對定理的前半部分給出證明。

假設(shè)有N個男人為：A、B、C、D、…、X、…、 Y、…，有N個女人為：a、b、c、d、…、x、…、y、…。“男優(yōu)先”和“女優(yōu)先”兩個穩(wěn)定婚姻匹配結(jié)果相同都是：A-a, B-b, C-c, D-d, …（記為α匹配）；

如果還存在另一個與上不同的穩(wěn)定婚姻匹配，對其中不相同的一部分，不妨可表示為：…, B-x, …, Y-b, …（記為β 匹配）。

因為α 匹配是按照“男優(yōu)先”或“女優(yōu)先”來求得的，所以根據(jù)前面提到的 Gale-Shapley 算法的性質(zhì)可知：在所有可能的穩(wěn)定婚姻匹配中，b是男性B獲得的最好的女性伴侶，同樣，B是女性b獲得的最好的男性伴侶，這樣，針對β 匹配中，男性B更喜歡女性b勝過x，同樣女性b也更喜歡男性B勝過Y，所以推得β 匹配不是穩(wěn)定婚姻匹配，與假設(shè)不符，所以不會存在其他的穩(wěn)定婚姻匹配?！?/p>

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

推論當(dāng)分別按照“男優(yōu)先”和“女優(yōu)先”求得兩個不同的穩(wěn)定婚姻匹配時，若這兩個不同的穩(wěn)定婚姻匹配中有一部分配對是相同的，則：若還存在其他穩(wěn)定婚姻匹配，仍會包含這部分相同的配對。

證明假設(shè)分別按照“男優(yōu)先”和“女優(yōu)先”求得兩個不同的穩(wěn)定婚姻匹配時，若這兩個不同的穩(wěn)定婚姻匹配中有m個配對是相同的，令：

這m個配對中男人為：A、B、C、D、…、X、…、Y、…

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

設(shè)按照“男優(yōu)先”和“女優(yōu)先”得到的兩個穩(wěn)定婚姻匹配中都共同含有如下m個配對：

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

假設(shè)還存在另一個穩(wěn)定匹配其中不完全包括這個公共部分，有不相同處，對其中不相同的一部分，不妨可表示為：

…, B-x, …, Y-b, …（記為β 匹配）

剩余部分證明與上述定理的證明相似，在此略?！?/p>

根據(jù)此推論，可得到改進(jìn)算法的基本思想：首先分別按照“男優(yōu)先”和“女優(yōu)先”求得兩個不同的穩(wěn)定婚姻匹配，根據(jù)推論可知，若這兩個不同的穩(wěn)定婚姻匹配中有m個配對是相同的，則所有穩(wěn)定婚姻匹配中的這一部分是已知的。這樣，在求解之前，可將這些已配對的m個男性和m個女性從問題中刪去。這樣問題就降為求N-m個男人和N-m個女人的穩(wěn)定婚姻匹配了。

改進(jìn)算法具體描述：

按“男優(yōu)先”求得一個穩(wěn)定婚姻匹配；

按“女優(yōu)先”求得另一個穩(wěn)定婚姻匹配； 若二者相同，則輸出這唯一的穩(wěn)定婚姻匹配，退出。

若二者不相同：

找出二者相同的配對部分； 若無相同的配對部分，則執(zhí)行GSM( )； 若有m(m≠0)個相同的配對部分，則：

輸出這m(m≠0)個相同的配對部分；

將MXH、WXH中的這些男、女對應(yīng)的行列刪除；

此改進(jìn)算法的正確性說明：此思想是依據(jù)推論，所以已證明。

此改進(jìn)算法的時間復(fù)雜性分析：

（1） 若求得的兩個穩(wěn)定婚姻匹配中有m個配對是相同的，問題可就轉(zhuǎn)化為求（N-m）對男女的婚配問題，則圖1中森林的規(guī)模將減小N(N-1)…(N-m+1)倍，所以算法的速度比原算法GSM( )的速度提高N(N-1)…(N-m+1)倍。

（2） 若求得的兩個穩(wěn)定婚姻匹配中無配對是相同時，也只是多了2次運(yùn)行Gale-Shapley算法的時間，相比之下，不會影響原算法GSM( )的時間復(fù)雜度。

4 結(jié) 束 語

穩(wěn)定婚姻問題被應(yīng)用到許多實際問題的處理過程中，例如學(xué)生的入學(xué)，工作招聘，醫(yī)生和醫(yī)院進(jìn)行匹配等。為快速找出所有可能的穩(wěn)定匹配結(jié)果，我們設(shè)計了基于先序遍歷森林的快速枚舉算法。利用此算法，對于眾多不同的婚姻匹配，不會重復(fù)判斷它們包含相同的配對子部分，這樣大大節(jié)省了時間。為了進(jìn)一步提高速度，由Gale-Shapley算法的性質(zhì)證明得到了一個定理及其推論，并利用推論對算法做了進(jìn)一步改進(jìn)。在滿足推論的特定狀況下，提高了原算法的執(zhí)行時間。

[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] 郭東亮, 張立臣. 用回跳法求解穩(wěn)定婚姻問題[J].計算機(jī)應(yīng)用研究, 2005, 22(1)： 59-60, 63.