畢業生系統互選算法優化

郭鳴宇 刁旭 沈陽城市學院

關鍵字：GS算法 穩定匹配 師生互選

1 引言

當前高速發展的經濟現狀衍生了很多研究成果，穩定匹配問題就是其中之一。2012年，美國學者羅斯和沙普利在“穩定匹配理論和市場設計實踐”領域做出了突出貢獻并因此獲得諾貝爾經濟學獎。1962 年，美國數學家 David Gale 和 Lloyd Shapley 發明了一種尋找穩定婚姻的策略。不管男女各有多少人，不管他們各自的偏好如何，應用這種策略后總能得到一個穩定的婚姻搭配。

本文主要是針對解決穩定匹配問的GS算法。首先簡要介紹了穩定匹配的含義以及在實踐過程中發現的穩定匹配當前存在的問題。然后針對這一問題對穩定算法進行了優化，并應用到學校的畢業師生互選系統中。

2 穩定匹配

2.1 穩定匹配問題內容描述

穩定匹配問題(stable matching)是一個生活中經常能夠遇到的問題，GS算法是解決穩定匹配問題的一個算法。所謂穩定匹配難題，是指：有n個男人，還有n個女人，男人心目中有自己的心上人列表，從最喜歡的女神一直排列下去，而女人心中也有相同的列表。很明顯的，某男性喜歡的女人，她可能根本看不上他。而多個女人喜歡的男人，也不可能同時娶這些女人。所以要找出一個讓所有人都能結婚，且大家都滿意的方案是很難的。

有n個男人和n個女人(n＞=2)，每個男人對所有女人有一個好感度排名，每個女人對所有男人也有一個好感度排名。將男女兩兩配對，得到n對男女，稱之為一個完美匹配。如果有一組男女A和B，他們在匹配中沒有被配對，且對對方的好感度均大于對現有配偶的好感度（男人A覺得女人B好過現在的妻子C，女人B覺得A好過現在的丈夫D），則稱之為一個不穩定配對。如果一個完美匹配中沒有不穩定配對，則稱改匹配為一個穩定匹配。

算法邏輯如下：如果存在男人m是自由的且還沒對每個女人都求過婚則選擇這個男人m，令w是m的優先表中還沒求過婚的最高排名的女人。然后判斷w是自由的情況下m，w變成約會狀態。如果w隨后又與m1約會并且w更偏愛m1而不愛m，那么m恢復自由。當然如果w更偏愛m而不愛m1，則m1仍自由。

2.2 穩定匹配的不足

被動方會越來越好，主動方會越來越差。如某單身女性w從第一次跟別人組隊之后，如果另一個男性m繼續向她表示滿意，而且m剛好在w的排序表上的排名比w的現任更高，那么w會甩了現任然后與m結合。如果m在w的排序表上的排名比w的現任低，那么w不接受m，繼續和現任在一起。這個規律可以看出，w自從第一個跟別人組隊之后，她如果后面還有與其他人組合，那么跟她后面組合的人只會”越來越好”，即越來越符合她的排序表，也就是說，她得到的伴侶質量會越來越好。若某男性向他排序表上的女性示愛，如果第一個示愛失敗之后只能再去找第二個，再失敗再找第三個，以此類推。于是這在他脫單之前，他能選擇的女性只會越來越不符合他的排序表，也就是說，他能選擇的異性質量會越來越差。如果男性的排名表完全協調(他們全都列出不同女性作為他們的第一選擇)，那么在GS算法的所有運行中所有男人最終都與他們的第一選擇匹配，而與女人的排序表無關。假設男m1最喜歡女w1，m2最喜歡w2，…，mn最喜歡wn。那么所有男性單身者在選擇時都會進入前面說到的這種情況，也就是直接和最喜歡的女性脫單了。這個時候女性就變成沒有選擇權了，如果這時候單身女性的排序表剛好跟單身男性完全沖突的話，也就是說，w1最不喜歡m1，w2最不喜歡m2，以此類推。那么這種情境下的匹配結果雖然是穩定的，但卻也往往也不是最情投意合的，因為男性都得到了最喜愛的女性，而女性卻都得到了最不喜愛的男性。

3 互選算法

3.1 互選算法的優化

鑒于GS算法只能做到n對n相同數量的兩隊人員進行穩定匹配，并且應用于相親場景時還會有主動方越來越好，被動方越來越差這一不足，我設想了一個優化后的算法，可以實現任意數量被動方對任意數量主動方的穩定匹配。并將這一算法應用到不需要高要求“情投意合”的使用場景中，可以將該算法得到有效利用。如師生互選系統、就業系統、選拔系統等。最終結果會使每個互選雙方都有相互人選或者匹配的崗位，且數量差距小于等于一，滿足師生互選、就業或者選拔系統資源均衡的要求。

3.2 互選算法的實現

假設數量多的一方為主動方Zn，數量少的一方為被動方Bm。則首先選出第一批主動方，數量為m，去主動與被動方進行穩定匹配。匹配方式與傳統穩定匹配算法相同，穩定匹配后，換后面m個主動方與被動方進行穩定匹配。以此類推，直到最后一批主動方與被動方匹配結束。此時，所有的主動方都已匹配到了對應的人員。由穩定匹配的原理可知，每一輪匹配結束后，所有人全部都已經匹配到了一位滿意對象。任意兩名被動方所匹配到的主動方只差都在小于等與一范圍內。因為最后一批之前的每一批的主動方和被動方都會形成穩定匹配，只有最后一次可能會有人沒有被匹配，所以能夠保證數量之差最大為一。

4 互選算法的應用

互選算法優化了主動方與被動方數量可以不一致的問題，并且可以使每個被動方所匹配的主動方人數之差不超過一。這一特性可以應用于更多的場景之中，不只局促在“相親”這一場景下。因此，我將它應用于比較貼近當前情況的場景中——畢業系統師生互選。該算法可以很好的完成導師、學生的互選。老師的數量多于學生，則可將學生看作主動方，學生看做被動方。我們將學生按照每一批的數量等于老師的數量去進行穩定匹配，直到最后一輪結束，即可完成老師與學生的互選。最終得到的結果可以保證任兩位導師名下匹配的學生數之差不會大于一。解決了平時導師、學生互選時數量不均衡的問題。

5 結論

通過對GS算法的研究，以及使用“相親”的場景模擬了穩定匹配問題，更加深刻地了解了GS算法的原理。并通過實踐驗證，得出GS算法可以有效解決穩定匹配的問題。但是通過一步步觀察發現，GS算法得出的結果會有被動方所匹配的人會越來越好，而主動方匹配的卻是越來越不符合心意的弊端。基于這一發現，我將互選算法進行了優化，使被動方與主動方數量可以不一定一致，通過分批次進行穩定匹配，最后可以得到多對多的穩定匹配，且任意被動方所匹配的主動方之差小于等于一。這一結果可以應用于畢業師生互選系統之中。解決了之前師生互選資源的不均衡問題。通過這次課題，提高了對算法優化以及對問題剖析的能力。