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