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