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

1、. .13/13穩(wěn)定婚姻問題和延遲認可算法 goal00001111 （高粱） 始發(fā)于goal00001111 的專欄；允許自由，但必須注明作者和出處摘要：延遲認可算法（Gale-Shapley算法）是解決穩(wěn)定婚姻問題的經(jīng)典算法，本文用C+來實現(xiàn)Gale-Shapley算法。文章詳細介紹了Gale-Shapley算法的原理和編碼思路，給出了一個直接從原理出發(fā)的原始算法與其改進版本，并對兩個版本進行了比較分析。關鍵詞：穩(wěn)定婚姻問題延遲認可算法二維數(shù)組以空間換時間穩(wěn)定婚姻問題 問題來自于一場“3分鐘相親”活動，參加活動的有n位男士和n位女士。要求每位男士都要和所有的女士進行短暫的單獨交流，并為她們

2、打分，然后按照喜歡程度，對每一位女士進行排序；同樣的，每位女士也要對所有男士進行打分和排序。 作為活動的組織者，當你拿到這些數(shù)據(jù)后，該如何為男，女士們配對，才能使大家皆大歡喜，組成穩(wěn)定的婚姻呢？ 插一句：什么樣的婚姻才能稱為穩(wěn)定的婚姻呢？ 所謂穩(wěn)定的婚姻，就是指男女結婚后，雙方都不會發(fā)生出軌行為。 那怎樣才能做到雙方都不出軌呢？ 如果雙方都是對方的最愛，自然不會出軌；如果有一方或雙方都不是對方的最愛，則必須保證想出軌的人找不到出軌的對象。例如，男子i認為其妻子不是自己的最愛，他更愛的人是j女士，可是j女士認為自己的丈夫比男子i強，則不會選擇與男子i出軌；另外有k女士很喜歡男子i，可是男子i又覺

3、得她不如自己的現(xiàn)任妻子，所以也不會選擇和k女士出軌。這樣男子i就找不到與之出軌的對象了；同理，如果他的妻子也找不到出軌對象的話，他們的婚姻就是穩(wěn)定的。簡言之，只要滿足“除妻子（丈夫）外，我愛的人不愛我，愛我的人我不愛”條件，就可形成穩(wěn)定的婚姻?；氐轿覀兊膯栴}：如何讓所有參加相親活動的男女都組成各自的“穩(wěn)定婚姻”?1962 年，美國數(shù)學家 David Gale 和 Lloyd Shapley 發(fā)明了一種尋找穩(wěn)定婚姻的策略，人們稱之為延遲認可算法（Gale-Shapley算法）。 先對所有男士進行落選標記，稱其為自由男。當存在自由男時，進行以下操作： 每一位自由男在所有尚未拒絕她的女士中選擇一位被

4、他排名最優(yōu)先的女士；每一位女士將正在追求她的自由男與其當前男友進行比較，選擇其中排名優(yōu)先的男士作為其男友，即若自由男優(yōu)于當前男友，則拋棄前男友；否則保留其男友，拒絕自由男。若某男士被其女友拋棄，重新變成自由男。在算法執(zhí)行期間，自由男們主動出擊，依次對最喜歡和次喜歡的女人求愛，一旦被接受，即失去自由身，進入訂婚狀態(tài)；而女人們則采取“守株待兔”和“喜新厭舊”策略，對前來求愛的男士進行選擇：若該男子比未婚夫強，則悔婚，選擇新的未婚夫；否則拒絕該男子的求婚。被女友拋棄的男人重獲自由身，重新?lián)碛辛俗非笈说臋嗬斎?，新的追求對象比不過前女友。這樣，在算法執(zhí)行期間，每個人都有可能訂婚多次也有可能一開始就找

5、到了自己的最愛，從一而終每訂一次婚，女人們的選擇就會更有利，而男人們的品味則越來越差。只要男女生的數(shù)量相等，則經(jīng)過多輪求婚，訂婚，悔婚和再訂婚之后，每位男女最終都會找到合適的伴侶雖然不一定是自己的最愛（男人沒能追到自己的最愛，或女人沒有等到自己的最愛來追求），但絕對不會出現(xiàn)“雖然彼此相愛，卻不能在一起”的悲劇，所有人都會組成穩(wěn)定的婚姻。本文用C+來實現(xiàn)Gale-Shapley算法，采用男士主動求愛，女士接受求愛的方式。假設男女生人數(shù)均為MAX，對每位男士和女士均進行編號，用自然數(shù)0,1,2，。，MAX-1表示其序號（依照C+的習慣，序號從0開始）。用二維數(shù)組liManMAXMAX來存儲男士所喜

6、歡的女士序號的排列表；同理，用二維數(shù)組libLadyMAXMAX+1來存儲女士所喜歡的男士序號的排列表，例如v號女最喜歡i號男，則libLadyv0 = i；若t號男比i號男更招v號女喜歡，則在數(shù)組libLadyv中，元素值t的下標小于元素值i的下標。為了簡化算法，增加一個“不存在”的男士（序號為MAX），作為女士最初的選擇。在給二維數(shù)組libLadyMAXMAX+1賦初值時，對于任意一個女士v，總有l(wèi)ibLadyvMAX = MAX。 為所有的男士（包括那個 “不存在”的）建立一個數(shù)組manMAX+1，用來存儲他們追求女士的次數(shù)，i號男目前追求的女士序號為libManimani。例如，man

7、i=0表示i號男尚未追求過女士，其所追求的女士序號為libMani0；mani=2表示i號男已經(jīng)追求過兩位女士，他下次追求的女士序號為libMani2（即在喜好表中排名第3位的女士）。很明顯，manMAX+1的每個元素初始值均為0，表示剛開始時，每位男士都去追求自己最喜歡的女士，mani值越大，男士對所選擇的女士越不滿意。為所有的女士建立一個數(shù)組ladyMAX，用來存儲她所選擇的男士序號，數(shù)組的所有元素初始值均為MAX，表示女士的當前男友為一個“不存在”的男士，他的分值比任何男士都低，以保證當有一個真正的男人追求該女士時，她會毫不猶豫的拋棄MAX，而選擇該男子。我們遍歷數(shù)組manMAX+1，依

8、次讓每個男士去追求自己心儀的女士（當然不需要處理元素manMAX那個“不存在”的男人）。例如現(xiàn)在正逢i號男追求v號女，若i號男不如v號女當前男友，則遭拒絕，i號男繼續(xù)追求其“次喜歡女”；反之，若i號男比v號女當前男友優(yōu)秀，則v拋棄前男友，選擇i號男為新男友，而其前男友（設為t號男）重獲自由身，可以去追求自己的“次喜歡女”了。這里有一個地方要注意：因為我們是通過執(zhí)行（i+）來遍歷數(shù)組的，所以如果當ti時，必須要讓i折回到t位置（使i=t)，否則會漏掉t。當i = MAX時，表示所有男士都找到了自己的另一半，算法結束，輸出結果。C+代碼如下：#include using namespace std

9、; const int MAX = 4;bool ChangeFriend(const int libLadyMAX+1, int v, int oldF, int newF);/判斷是否需要換男友 int main() int libManMAXMAX = 2,1,3,0,0,2,3,1,2,3,1,0,1,3,2,0;/存儲男士所喜歡的女士序號的排列表 int libLadyMAXMAX+1 = 0,3,1,2,MAX,1,3,2,3,MAX,0,2,3,1,MAX,1,0,3,2,MAX;/存儲女士所喜歡的男士序號的排列表 int manMAX+1 = 0; int ladyMAX =

10、MAX,MAX,MAX,MAX; int i = 0; while (i i) /前男友序號t在新男友i之后，則今后順序前行可以處理t i+; /處理下一個男士 else /前男友序號t在新男友i之前，返回t，否則會漏掉t i = t; else/繼續(xù)處理i號男的“次喜歡女” mani+; for (int i=0; iMAX; i+)/輸出每位男士追求女士的次數(shù) cout mani + 1 , ; cout endl; for (int i=0; iMAX; i+)/輸出每位男士的妻子的序號 cout libManimani , ; cout endl; for (int i=0; iMAX

11、; i+)/輸出每位女士的丈夫的序號 cout ladyi , ; cout endl; system(pause); return 0;bool ChangeFriend(const int libLadyMAX+1, int v, int oldF, int newF)/判斷是否需要換男友 for (int i=0; i=MAX; i+) if (libLadyvi = oldF) oldF = i; break; for (int i=0; i newF);在上述實現(xiàn)中，我設計了一個子函數(shù)bool ChangeFriend(const int libLadyMAX+1, int v, i

12、nt oldF, int newF)，用來判斷女士v是否需要換男友，若男子序號newF在數(shù)組libLadyvi的位置比oldF靠前，則說明女士v更喜歡newF，需要換男友，否則不換。通過比較它們的下標，可以得出結論。這個子函數(shù)的引入可以讓程序完成工作，但也帶來一些效率上問題，每次調(diào)用函數(shù)都要分別遍歷數(shù)組libLadyv兩次，去尋找oldF和newF的下標，這樣在MAX值很大的時候，時間消耗是相當大的。另外，由于我們是通過執(zhí)行（i+）來遍歷數(shù)組，每次遇到(t i)時，都要令i折回到t，然后再執(zhí)行（i+），進行了很多重復的比較，浪費了寶貴的時間。那么，如何改進代碼，解決上述兩個問題？首先解決關于子

13、函數(shù)的問題。之所以引入子函數(shù)，是因為數(shù)組libLadyv存儲的是女士v所喜歡的男士序號的排列表，而不是男士的分值表。如果我們創(chuàng)建一個二維數(shù)組libladyValueMAXMAX+1，用來存儲女士v所喜歡的男士的分值，即數(shù)組元素libladyValuevi表示女士v給i號男打的分數(shù)，分數(shù)越高，則表示越招人喜歡。這樣我們在判斷女士v是否需要換男友時，就無需遍歷數(shù)組，只要直接比較libladyValuevi和libladyValuevt的值就好了。其次解決重復比較的問題。我們可以創(chuàng)建一個棧，把所有自由男的序號存儲到棧中，每當有男子訂婚，則將其序號出棧；每當有男子被拋棄，則將其序號入棧。這樣就可以確保

14、不會出現(xiàn)重復比較了。在解決上述兩個問題的時候，我都采用了“以空間換時間”的策略，小小的自夸一下，呵呵！改進后的C+代碼如下：#include using namespace std; const int MAX = 4;int main() int libManMAXMAX = 2,1,3,0,0,2,3,1,2,3,1,0,1,3,2,0;/存儲男士所喜歡的女士序號的排列表 int libLadyMAXMAX+1 = 0,3,1,2,MAX,1,3,2,3,MAX,0,2,3,1,MAX,1,0,3,2,MAX;/存儲女士所喜歡的男士序號的排列表 int libladyValueMAXMAX

15、+1 = 0; for (int i=0; i=0; j-,k+) libladyValueilibLadyij = k; int manMAX+1 = 0;/存儲各個男士追求女士的次數(shù) int ladyMAX = MAX,MAX,MAX,MAX;/序號初始值MAX表示一個“不存在”的男士，即其分值比任何男士都低 int SMAX = 0;/一個棧，用來存儲所有自由男的序號 int top = 0; while (top = 0)/讓自由男主動去追求自己喜歡的女士，直到所有的人都配對 int v = libManStopmanStop; /處在棧頂（序號為Stop）的男士喜歡v號女 if (l

16、ibladyValuevladyv libladyValuevStop) /若棧頂男比v號女當前男友優(yōu)秀，則 v拋棄前男友，接受棧頂男 int t = ladyv; /存儲前男友序號 mant+; /拋棄前男友，即前男友選擇其“次喜歡女” ladyv = Stop-; /選擇棧頂男為新男友，同時棧頂男出棧 if (t != MAX) /如果t號男不是那個“不存在”的男士 S+top = t; /t號男作為新的棧頂男 else/棧頂男追求下一號目標 manStop+; for (int i=0; iMAX; i+)/輸出每位男士追求女士的次數(shù) cout mani + 1 , ; cout endl; for (int i=0; iMAX; i+)/輸出每位男士的妻子的序號 cout libManimani , ;