畢業(yè)生系統(tǒng)互選算法優(yōu)化

郭鳴宇 刁旭 沈陽城市學(xué)院

關(guān)鍵字：GS算法 穩(wěn)定匹配 師生互選

1 引言

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

本文主要是針對解決穩(wěn)定匹配問的GS算法。首先簡要介紹了穩(wěn)定匹配的含義以及在實(shí)踐過程中發(fā)現(xiàn)的穩(wěn)定匹配當(dāng)前存在的問題。然后針對這一問題對穩(wěn)定算法進(jìn)行了優(yōu)化，并應(yīng)用到學(xué)校的畢業(yè)師生互選系統(tǒng)中。

2 穩(wěn)定匹配

2.1 穩(wěn)定匹配問題內(nèi)容描述

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

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

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

2.2 穩(wěn)定匹配的不足

被動方會越來越好，主動方會越來越差。如某單身女性w從第一次跟別人組隊之后，如果另一個男性m繼續(xù)向她表示滿意，而且m剛好在w的排序表上的排名比w的現(xiàn)任更高，那么w會甩了現(xiàn)任然后與m結(jié)合。如果m在w的排序表上的排名比w的現(xiàn)任低，那么w不接受m，繼續(xù)和現(xiàn)任在一起。這個規(guī)律可以看出，w自從第一個跟別人組隊之后，她如果后面還有與其他人組合，那么跟她后面組合的人只會”越來越好”，即越來越符合她的排序表，也就是說，她得到的伴侶質(zhì)量會越來越好。若某男性向他排序表上的女性示愛，如果第一個示愛失敗之后只能再去找第二個，再失敗再找第三個，以此類推。于是這在他脫單之前，他能選擇的女性只會越來越不符合他的排序表，也就是說，他能選擇的異性質(zhì)量會越來越差。如果男性的排名表完全協(xié)調(diào)(他們?nèi)剂谐霾煌宰鳛樗麄兊牡谝贿x擇)，那么在GS算法的所有運(yùn)行中所有男人最終都與他們的第一選擇匹配，而與女人的排序表無關(guān)。假設(shè)男m1最喜歡女w1，m2最喜歡w2，…，mn最喜歡wn。那么所有男性單身者在選擇時都會進(jìn)入前面說到的這種情況，也就是直接和最喜歡的女性脫單了。這個時候女性就變成沒有選擇權(quán)了，如果這時候單身女性的排序表剛好跟單身男性完全沖突的話，也就是說，w1最不喜歡m1，w2最不喜歡m2，以此類推。那么這種情境下的匹配結(jié)果雖然是穩(wěn)定的，但卻也往往也不是最情投意合的，因?yàn)槟行远嫉玫搅俗钕矏鄣呐?，而女性卻都得到了最不喜愛的男性。

3 互選算法

3.1 互選算法的優(yōu)化

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

3.2 互選算法的實(shí)現(xiàn)

假設(shè)數(shù)量多的一方為主動方Zn，數(shù)量少的一方為被動方Bm。則首先選出第一批主動方，數(shù)量為m，去主動與被動方進(jìn)行穩(wěn)定匹配。匹配方式與傳統(tǒng)穩(wěn)定匹配算法相同，穩(wěn)定匹配后，換后面m個主動方與被動方進(jìn)行穩(wěn)定匹配。以此類推，直到最后一批主動方與被動方匹配結(jié)束。此時，所有的主動方都已匹配到了對應(yīng)的人員。由穩(wěn)定匹配的原理可知，每一輪匹配結(jié)束后，所有人全部都已經(jīng)匹配到了一位滿意對象。任意兩名被動方所匹配到的主動方只差都在小于等與一范圍內(nèi)。因?yàn)樽詈笠慌暗拿恳慌闹鲃臃胶捅粍臃蕉紩纬煞€(wěn)定匹配，只有最后一次可能會有人沒有被匹配，所以能夠保證數(shù)量之差最大為一。

4 互選算法的應(yīng)用

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

5 結(jié)論

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