穩(wěn)定婚姻問題和延遲認(rèn)可算法
作者：goal00001111 （高粱）
始發(fā)于goal00001111 的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
摘要：延遲認(rèn)可算法（Gale-Shapley算法）是解決穩(wěn)定婚姻問題的經(jīng)典算法，本文用C++來實(shí)現(xiàn)Gale-Shapley算法。文章詳細(xì)介紹了Gale-Shapley算法的原理和編碼思路，給出了一個(gè)直接從原理出發(fā)的原始算法及其改進(jìn)版本，并對兩個(gè)版本進(jìn)行了比較分析。
關(guān)鍵詞：穩(wěn)定婚姻問題 延遲認(rèn)可算法 二維數(shù)組 以空間換時(shí)間
穩(wěn)定婚姻問題
問題來自于一場“3分鐘相親”活動(dòng)，參加活動(dòng)的有n位男士和n位女士。要求每位男士都要和所有的女士進(jìn)行短暫的單獨(dú)交流，并為她們打分，然后按照喜歡程度，對每一位女士進(jìn)行排序；同樣的，每位女士也要對所有男士進(jìn)行打分和排序。
作為活動(dòng)的組織者，當(dāng)你拿到這些數(shù)據(jù)后，該如何為男，女士們配對，才能使大家皆大歡喜，組成穩(wěn)定的婚姻呢？
插一句：什么樣的婚姻才能稱為穩(wěn)定的婚姻呢？
所謂穩(wěn)定的婚姻，就是指男女結(jié)婚后，雙方都不會(huì)發(fā)生出軌行為。
那怎樣才能做到雙方都不出軌呢？
如果雙方都是對方的最愛，自然不會(huì)出軌；如果有一方或雙方都不是對方的最愛，則必須保證想出軌的人找不到出軌的對象。例如，男子i認(rèn)為其妻子不是自己的最愛，他更愛的人是j女士，可是j女士認(rèn)為自己的丈夫比男子i強(qiáng)，則不會(huì)選擇與男子i出軌；另外有k女士很喜歡男子i，可是男子i又覺得她不如自己的現(xiàn)任妻子，所以也不會(huì)選擇和k女士出軌。這樣男子i就找不到與之出軌的對象了；同理，如果他的妻子也找不到出軌對象的話，他們的婚姻就是穩(wěn)定的。
簡言之，只要滿足“除妻子（丈夫）外，我愛的人不愛我，愛我的人我不愛”條件，就可形成穩(wěn)定的婚姻。
回到我們的問題：如何讓所有參加相親活動(dòng)的男女都組成各自的“穩(wěn)定婚姻”?
1962 年，美國數(shù)學(xué)家 David Gale 和 Lloyd Shapley 發(fā)明了一種尋找穩(wěn)定婚姻的策略，人們稱之為延遲認(rèn)可算法（Gale-Shapley算法）。
先對所有男士進(jìn)行落選標(biāo)記，稱其為自由男。當(dāng)存在自由男時(shí)，進(jìn)行以下操作：
① 每一位自由男在所有尚未拒絕她的女士中選擇一位被他排名最優(yōu)先的女士；
② 每一位女士將正在追求她的自由男與其當(dāng)前男友進(jìn)行比較，選擇其中排名優(yōu)先的男士作為其男友，即若自由男優(yōu)于當(dāng)前男友，則拋棄前男友；否則保留其男友，拒絕自由男。
③ 若某男士被其女友拋棄，重新變成自由男。
在算法執(zhí)行期間，自由男們主動(dòng)出擊，依次對最喜歡和次喜歡的女人求愛，一旦被接受，即失去自由身，進(jìn)入訂婚狀態(tài)；而女人們則采取“守株待兔”和“喜新厭舊”策略，對前來求愛的男士進(jìn)行選擇：若該男子比未婚夫強(qiáng)，則悔婚，選擇新的未婚夫；否則拒絕該男子的求婚。被女友拋棄的男人重獲自由身，重新?lián)碛辛俗非笈说臋?quán)利——當(dāng)然，新的追求對象比不過前女友。
這樣，在算法執(zhí)行期間，每個(gè)人都有可能訂婚多次——也有可能一開始就找到了自己的最愛，從一而終——每訂一次婚，女人們的選擇就會(huì)更有利，而男人們的品味則越來越差。只要男女生的數(shù)量相等，則經(jīng)過多輪求婚，訂婚，悔婚和再訂婚之后，每位男女最終都會(huì)找到合適的伴侶——雖然不一定是自己的最愛（男人沒能追到自己的最愛，或女人沒有等到自己的最愛來追求），但絕對不會(huì)出現(xiàn)“雖然彼此相愛，卻不能在一起”的悲劇，所有人都會(huì)組成穩(wěn)定的婚姻。
本文用C++來實(shí)現(xiàn)Gale-Shapley算法，采用男士主動(dòng)求愛，女士接受求愛的方式。
假設(shè)男女生人數(shù)均為MAX，對每位男士和女士均進(jìn)行編號(hào)，用自然數(shù)0,1,2，。。。，MAX-1表示其序號(hào)（依照C++的習(xí)慣，序號(hào)從0開始）。
用二維數(shù)組liMan[MAX][MAX]來存儲(chǔ)男士所喜歡的女士序號(hào)的排列表；同理，用二維數(shù)組libLady[MAX][MAX+1]來存儲(chǔ)女士所喜歡的男士序號(hào)的排列表，例如v號(hào)女最喜歡i號(hào)男，則libLady[v][0] = i；若t號(hào)男比i號(hào)男更招v號(hào)女喜歡，則在數(shù)組libLady[v][]中，元素值t的下標(biāo)小于元素值i的下標(biāo)。
為了簡化算法，增加一個(gè)“不存在”的男士（序號(hào)為MAX），作為女士最初的選擇。在給二維數(shù)組libLady[MAX][MAX+1]賦初值時(shí)，對于任意一個(gè)女士v，總有libLady[v][MAX] = MAX。
為所有的男士（包括那個(gè) “不存在”的）建立一個(gè)數(shù)組man[MAX+1]，用來存儲(chǔ)他們追求女士的次數(shù)，i號(hào)男目前追求的女士序號(hào)為libMan[i][man[i]]。
例如，man[i]=0表示i號(hào)男尚未追求過女士，其所追求的女士序號(hào)為libMan[i][0]；man[i]=2表示i號(hào)男已經(jīng)追求過兩位女士，他下次追求的女士序號(hào)為libMan[i][2]（即在喜好表中排名第3位的女士）。
很明顯，man[MAX+1]的每個(gè)元素初始值均為0，表示剛開始時(shí)，每位男士都去追求自己最喜歡的女士，man[i]值越大，男士對所選擇的女士越不滿意。
為所有的女士建立一個(gè)數(shù)組lady[MAX]，用來存儲(chǔ)她所選擇的男士序號(hào)，數(shù)組的所有元素初始值均為MAX，表示女士的當(dāng)前男友為一個(gè)“不存在”的男士，他的分值比任何男士都低，以保證當(dāng)有一個(gè)真正的男人追求該女士時(shí)，她會(huì)毫不猶豫的拋棄MAX，而選擇該男子。
我們遍歷數(shù)組man[MAX+1]，依次讓每個(gè)男士去追求自己心儀的女士（當(dāng)然不需要處理元素man[MAX]——那個(gè)“不存在”的男人）。例如現(xiàn)在正逢i號(hào)男追求v號(hào)女，若i號(hào)男不如v號(hào)女當(dāng)前男友，則遭拒絕，i號(hào)男繼續(xù)追求其“次喜歡女”；反之，若i號(hào)男比v號(hào)女當(dāng)前男友優(yōu)秀，則v拋棄前男友，選擇i號(hào)男為新男友，而其前男友（設(shè)為t號(hào)男）重獲自由身，可以去追求自己的“次喜歡女”了。
這里有一個(gè)地方要注意：因?yàn)槲覀兪峭ㄟ^執(zhí)行（i++）來遍歷數(shù)組的，所以如果當(dāng)t<i時(shí)，必須要讓i折回到t位置（使i=t)，否則會(huì)漏掉t。
當(dāng)i == MAX時(shí)，表示所有男士都找到了自己的另一半，算法結(jié)束，輸出結(jié)果。
C++代碼如下：
#include <iostream>
using namespace std;
const int MAX = 4;
bool ChangeFriend(const int libLady[][MAX+1], int v, int oldF, int newF);//判斷是否需要換男友
int main()
{
int libMan[MAX][MAX] = {{2,1,3,0},{0,2,3,1},{2,3,1,0},{1,3,2,0}};//存儲(chǔ)男士所喜歡的女士序號(hào)的排列表
int libLady[MAX][MAX+1] = {{0,3,1,2,MAX},{1,3,2,3,MAX},{0,2,3,1,MAX},{1,0,3,2,MAX}};//存儲(chǔ)女士所喜歡的男士序號(hào)的排列表
int man[MAX+1] = {0};
int lady[MAX] = {MAX,MAX,MAX,MAX};
int i = 0;
while (i < MAX )
{
int v = libMan[i][man[i]]; //i號(hào)男喜歡v號(hào)女
if (i == lady[v]) //i號(hào)男就是v號(hào)女當(dāng)前男友，跳過，處理下一個(gè)男士
i++;
else if (ChangeFriend(libLady, v, lady[v], i)) //若i號(hào)男比v號(hào)女當(dāng)前男友優(yōu)秀，則v拋棄前男友，重新選擇i
{
int t = lady[v]; //存儲(chǔ)前男友序號(hào)
man[lady[v]]++; //拋棄前男友，即前男友選擇其“次喜歡女”
lady[v] = i; //選擇i號(hào)男為新男友
if (t > i) //前男友序號(hào)t在新男友i之后，則今后順序前行可以處理t
i++; //處理下一個(gè)男士
else //前男友序號(hào)t在新男友i之前，返回t，否則會(huì)漏掉t
i = t;
}
else //繼續(xù)處理i號(hào)男的“次喜歡女”
man[i]++;
}
for (int i=0; i<MAX; i++)//輸出每位男士追求女士的次數(shù)
cout << man[i] + 1 << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//輸出每位男士的妻子的序號(hào)
cout << libMan[i][man[i]] << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//輸出每位女士的丈夫的序號(hào)
cout << lady[i] << ", ";
cout << endl;
system("pause");
return 0;
}
bool ChangeFriend(const int libLady[][MAX+1], int v, int oldF, int newF)//判斷是否需要換男友
{
for (int i=0; i<=MAX; i++)
{
if (libLady[v][i] == oldF)
{
oldF = i;
break;
}
}
for (int i=0; i<=MAX; i++)
{
if (libLady[v][i] == newF)
{
newF = i;
break;
}
}
return (oldF > newF);
}
在上述實(shí)現(xiàn)中，我設(shè)計(jì)了一個(gè)子函數(shù)bool ChangeFriend(const int libLady[][MAX+1], int v, int oldF, int newF)，用來判斷女士v是否需要換男友，若男子序號(hào)newF在數(shù)組libLady[v][i]的位置比oldF靠前，則說明女士v更喜歡newF，需要換男友，否則不換。通過比較它們的下標(biāo)，可以得出結(jié)論。
這個(gè)子函數(shù)的引入可以讓程序完成工作，但也帶來一些效率上問題，每次調(diào)用函數(shù)都要分別遍歷數(shù)組libLady[v][]兩次，去尋找oldF和newF的下標(biāo)，這樣在MAX值很大的時(shí)候，時(shí)間消耗是相當(dāng)大的。
另外，由于我們是通過執(zhí)行（i++）來遍歷數(shù)組，每次遇到(t < i)時(shí)，都要令i折回到t，然后再執(zhí)行（i++），進(jìn)行了很多重復(fù)的比較，浪費(fèi)了寶貴的時(shí)間。
那么，如何改進(jìn)代碼，解決上述兩個(gè)問題？
首先解決關(guān)于子函數(shù)的問題。之所以引入子函數(shù)，是因?yàn)閿?shù)組libLady[v][]存儲(chǔ)的是女士v所喜歡的男士序號(hào)的排列表，而不是男士的分值表。如果我們創(chuàng)建一個(gè)二維數(shù)組libladyValue[MAX][MAX+1]，用來存儲(chǔ)女士v所喜歡的男士的分值，即數(shù)組元素libladyValue[v][i]表示女士v給i號(hào)男打的分?jǐn)?shù)，分?jǐn)?shù)越高，則表示越招人喜歡。這樣我們在判斷女士v是否需要換男友時(shí)，就無需遍歷數(shù)組，只要直接比較libladyValue[v][i]和libladyValue[v][t]的值就好了。
其次解決重復(fù)比較的問題。我們可以創(chuàng)建一個(gè)棧，把所有自由男的序號(hào)存儲(chǔ)到棧中，每當(dāng)有男子訂婚，則將其序號(hào)出棧；每當(dāng)有男子被拋棄，則將其序號(hào)入棧。這樣就可以確保不會(huì)出現(xiàn)重復(fù)比較了。
在解決上述兩個(gè)問題的時(shí)候，我都采用了“以空間換時(shí)間”的策略，小小的自夸一下，呵呵！
改進(jìn)后的C++代碼如下：
#include <iostream>
using namespace std;
const int MAX = 4;
int main()
{
int libMan[MAX][MAX] = {{2,1,3,0},{0,2,3,1},{2,3,1,0},{1,3,2,0}};//存儲(chǔ)男士所喜歡的女士序號(hào)的排列表
int libLady[MAX][MAX+1] = {{0,3,1,2,MAX},{1,3,2,3,MAX},{0,2,3,1,MAX},{1,0,3,2,MAX}};//存儲(chǔ)女士所喜歡的男士序號(hào)的排列表
int libladyValue[MAX][MAX+1] = {0};
for (int i=0; i<MAX; i++) //把女士喜好的男士序號(hào)的排列表轉(zhuǎn)換為男士分值表
{
for (int j=MAX, k=0; j>=0; j--,k++)
{
libladyValue[i][libLady[i][j]] = k;
}
}
int man[MAX+1] = {0};//存儲(chǔ)各個(gè)男士追求女士的次數(shù)
int lady[MAX] = {MAX,MAX,MAX,MAX};//序號(hào)初始值MAX表示一個(gè)“不存在”的男士，即其分值比任何男士都低
int S[MAX] = {0};//一個(gè)棧，用來存儲(chǔ)所有自由男的序號(hào)
int top = 0;
while (top < MAX) //把所有自由男的序號(hào)存儲(chǔ)到棧中
S[top] = top++;
top--; //top指向棧頂
while (top >= 0)//讓自由男主動(dòng)去追求自己喜歡的女士，直到所有的人都配對
{
int v = libMan[S[top]][man[S[top]]]; //處在棧頂（序號(hào)為S[top]）的男士喜歡v號(hào)女
if (libladyValue[v][lady[v]] < libladyValue[v][S[top]]) //若棧頂男比v號(hào)女當(dāng)前男友優(yōu)秀，則 v拋棄前男友，接受棧頂男
{
int t = lady[v]; //存儲(chǔ)前男友序號(hào)
man[t]++; //拋棄前男友，即前男友選擇其“次喜歡女”
lady[v] = S[top--]; //選擇棧頂男為新男友，同時(shí)棧頂男出棧
if (t != MAX) //如果t號(hào)男不是那個(gè)“不存在”的男士
S[++top] = t; //t號(hào)男作為新的棧頂男
}
else //棧頂男追求下一號(hào)目標(biāo)
man[S[top]]++;
}
for (int i=0; i<MAX; i++)//輸出每位男士追求女士的次數(shù)
cout << man[i] + 1 << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//輸出每位男士的妻子的序號(hào)
cout << libMan[i][man[i]] << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//輸出每位女士的丈夫的序號(hào)
cout << lady[i] << ", ";
cout << endl;
system("pause");
return 0;
}
參考文獻(xiàn)：
（1） matrix67的博客 《[0]引言 什么是算法 如何尋找穩(wěn)定的婚姻搭配》
http://www.matrix67.com/blog/archives/2976
（2） 孫 劼的博客 《穩(wěn)定婚姻問題和延遲認(rèn)可算法》
http://intowater.spaces.live.com/Blog/cns!1pe4f-ndtin3u1qQCckqiIWQ!949.entry