goal00001111

 

穩(wěn)定婚姻問題和延遲認可算法

作者：goal00001111 （高粱）

           始發(fā)于goal00001111 的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處

 

 摘要：延遲認可算法（Gale-Shapley算法）是解決穩(wěn)定婚姻問題的經(jīng)典算法，本文用C++來實現(xiàn)Gale-Shapley算法。文章詳細介紹了Gale-Shapley算法的原理和編碼思路，給出了一個直接從原理出發(fā)的原始算法及其改進版本，并對兩個版本進行了比較分析。

 

關(guān)鍵詞：穩(wěn)定婚姻問題 延遲認可算法 二維數(shù)組 以空間換時間

 

穩(wěn)定婚姻問題

       問題來自于一場“3分鐘相親”活動，參加活動的有n位男士和n位女士。要求每位男士都要和所有的女士進行短暫的單獨交流，并為她們打分，然后按照喜歡程度，對每一位女士進行排序；同樣的，每位女士也要對所有男士進行打分和排序。

       作為活動的組織者，當你拿到這些數(shù)據(jù)后，該如何為男，女士們配對，才能使大家皆大歡喜，組成穩(wěn)定的婚姻呢？

       插一句：什么樣的婚姻才能稱為穩(wěn)定的婚姻呢？

       所謂穩(wěn)定的婚姻，就是指男女結(jié)婚后，雙方都不會發(fā)生出軌行為。   

那怎樣才能做到雙方都不出軌呢？

       如果雙方都是對方的最愛，自然不會出軌；如果有一方或雙方都不是對方的最愛，則必須保證想出軌的人找不到出軌的對象。例如，男子i認為其妻子不是自己的最愛，他更愛的人是j女士，可是j女士認為自己的丈夫比男子i強，則不會選擇與男子i出軌；另外有k女士很喜歡男子i，可是男子i又覺得她不如自己的現(xiàn)任妻子，所以也不會選擇和k女士出軌。這樣男子i就找不到與之出軌的對象了；同理，如果他的妻子也找不到出軌對象的話，他們的婚姻就是穩(wěn)定的。

簡言之，只要滿足“除妻子（丈夫）外，我愛的人不愛我，愛我的人我不愛”條件，就可形成穩(wěn)定的婚姻。

回到我們的問題：如何讓所有參加相親活動的男女都組成各自的“穩(wěn)定婚姻”?

1962 年，美國數(shù)學家 David Gale 和 Lloyd Shapley 發(fā)明了一種尋找穩(wěn)定婚姻的策略，人們稱之為延遲認可算法（Gale-Shapley算法）。

    先對所有男士進行落選標記，稱其為自由男。當存在自由男時，進行以下操作：

    ① 每一位自由男在所有尚未拒絕她的女士中選擇一位被他排名最優(yōu)先的女士；

② 每一位女士將正在追求她的自由男與其當前男友進行比較，選擇其中排名優(yōu)先的男士作為其男友，即若自由男優(yōu)于當前男友，則拋棄前男友；否則保留其男友，拒絕自由男。

③ 若某男士被其女友拋棄，重新變成自由男。

在算法執(zhí)行期間，自由男們主動出擊，依次對最喜歡和次喜歡的女人求愛，一旦被接受，即失去自由身，進入訂婚狀態(tài)；而女人們則采取“守株待兔”和“喜新厭舊”策略，對前來求愛的男士進行選擇：若該男子比未婚夫強，則悔婚，選擇新的未婚夫；否則拒絕該男子的求婚。被女友拋棄的男人重獲自由身，重新?lián)碛辛俗非笈说臋?quán)利——當然，新的追求對象比不過前女友。

這樣，在算法執(zhí)行期間，每個人都有可能訂婚多次——也有可能一開始就找到了自己的最愛，從一而終——每訂一次婚，女人們的選擇就會更有利，而男人們的品味則越來越差。只要男女生的數(shù)量相等，則經(jīng)過多輪求婚，訂婚，悔婚和再訂婚之后，每位男女最終都會找到合適的伴侶——雖然不一定是自己的最愛（男人沒能追到自己的最愛，或女人沒有等到自己的最愛來追求），但絕對不會出現(xiàn)“雖然彼此相愛，卻不能在一起”的悲劇，所有人都會組成穩(wěn)定的婚姻。

 

本文用C++來實現(xiàn)Gale-Shapley算法，采用男士主動求愛，女士接受求愛的方式。

假設(shè)男女生人數(shù)均為MAX，對每位男士和女士均進行編號，用自然數(shù)0,1,2，。。。，MAX-1表示其序號（依照C++的習慣，序號從0開始）。

用二維數(shù)組liMan[MAX][MAX]來存儲男士所喜歡的女士序號的排列表；同理，用二維數(shù)組libLady[MAX][MAX+1]來存儲女士所喜歡的男士序號的排列表，例如v號女最喜歡i號男，則libLady[v][0] = i；若t號男比i號男更招v號女喜歡，則在數(shù)組libLady[v][]中，元素值t的下標小于元素值i的下標。

為了簡化算法，增加一個“不存在”的男士（序號為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，表示女士的當前男友為一個“不存在”的男士，他的分值比任何男士都低，以保證當有一個真正的男人追求該女士時，她會毫不猶豫的拋棄MAX，而選擇該男子。

我們遍歷數(shù)組man[MAX+1]，依次讓每個男士去追求自己心儀的女士（當然不需要處理元素man[MAX]——那個“不存在”的男人）。例如現(xiàn)在正逢i號男追求v號女，若i號男不如v號女當前男友，則遭拒絕，i號男繼續(xù)追求其“次喜歡女”；反之，若i號男比v號女當前男友優(yōu)秀，則v拋棄前男友，選擇i號男為新男友，而其前男友（設(shè)為t號男）重獲自由身，可以去追求自己的“次喜歡女”了。

這里有一個地方要注意：因為我們是通過執(zhí)行（i++）來遍歷數(shù)組的，所以如果當t<i時，必須要讓i折回到t位置（使i=t)，否則會漏掉t。

當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號女當前男友，跳過，處理下一個男士

                   i++;

         else if (ChangeFriend(libLady, v, lady[v], i)) //若i號男比v號女當前男友優(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，需要換男友，否則不換。通過比較它們的下標，可以得出結(jié)論。

這個子函數(shù)的引入可以讓程序完成工作，但也帶來一些效率上問題，每次調(diào)用函數(shù)都要分別遍歷數(shù)組libLady[v][]兩次，去尋找oldF和newF的下標，這樣在MAX值很大的時候，時間消耗是相當大的。

另外，由于我們是通過執(zhí)行（i++）來遍歷數(shù)組，每次遇到(t < i)時，都要令i折回到t，然后再執(zhí)行（i++），進行了很多重復的比較，浪費了寶貴的時間。

那么，如何改進代碼，解決上述兩個問題？

首先解決關(guān)于子函數(shù)的問題。之所以引入子函數(shù)，是因為數(shù)組libLady[v][]存儲的是女士v所喜歡的男士序號的排列表，而不是男士的分值表。如果我們創(chuàng)建一個二維數(shù)組libladyValue[MAX][MAX+1]，用來存儲女士v所喜歡的男士的分值，即數(shù)組元素libladyValue[v][i]表示女士v給i號男打的分數(shù)，分數(shù)越高，則表示越招人喜歡。這樣我們在判斷女士v是否需要換男友時，就無需遍歷數(shù)組，只要直接比較libladyValue[v][i]和libladyValue[v][t]的值就好了。

其次解決重復比較的問題。我們可以創(chuàng)建一個棧，把所有自由男的序號存儲到棧中，每當有男子訂婚，則將其序號出棧；每當有男子被拋棄，則將其序號入棧。這樣就可以確保不會出現(xià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號女當前男友優(yōu)秀，則 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++)//輸出每位男士追求女士的次數(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;

}

 

 

參考文獻：

（1）       matrix67的博客 《[0]引言 什么是算法 如何尋找穩(wěn)定的婚姻搭配》

http://www.matrix67.com/blog/archives/2976

（2）       孫 劼的博客 《穩(wěn)定婚姻問題和延遲認可算法》

http://intowater.spaces.live.com/Blog/cns!1pe4f-ndtin3u1qQCckqiIWQ!949.entry