穩(wěn)定婚姻問題算法_sunhaowen_百度空間

穩(wěn)定婚姻問題算法

轉(zhuǎn)自： http://teruterubouzu-laputa.spaces.live.com/

話說在1962年，兩個(gè)數(shù)學(xué)家David Gale 和Lloyd Shapley提出了下面的問題：

給定若干個(gè)男生和同樣多的女生，他們每個(gè)人都對(duì)所有的異性有一個(gè)心理的偏好次序。是否存在一種男女配對(duì)組合構(gòu)成一種穩(wěn)定的組合關(guān)系？這里穩(wěn)定組合的意思是說，不存在兩個(gè)非伴侶的異性對(duì)彼此的評(píng)價(jià)比對(duì)各自伴侶的評(píng)價(jià)還要高。（可以理解，這樣的異性太容易紅杏出墻了，所以是某種不穩(wěn)定因素。）進(jìn)一步的問題是，在已知每個(gè)人對(duì)異性的偏好順序的情況下，怎樣求出這種穩(wěn)定組合方式（如果它存在的話）？你可以理解為這是數(shù)學(xué)家們替月老問的問題：給定一群孤男寡女，尋找一種牽紅線的方式，以確保把紅杏扼殺在搖籃里。

這一問題被稱為穩(wěn)定婚姻問題。它有很多種可能的解法。為了讓大家相信數(shù)學(xué)家不是真得如此無(wú)聊，我要指出它確確實(shí)實(shí)是一個(gè)地道的組合數(shù)學(xué)問題，有其特定的數(shù)學(xué)價(jià)值。當(dāng)然啦，它也有很多別的背景和應(yīng)用，比如用來(lái)在若干個(gè)公司和應(yīng)聘者之間進(jìn)行招聘中介……但是數(shù)學(xué)家們?cè)趺磿?huì)放過如此八卦的一個(gè)名字呢？于是它就這樣流傳下來(lái)了。

給定每個(gè)人關(guān)于異性的偏好排序，要尋找一種男女配對(duì)組合構(gòu)成穩(wěn)定的組合。Gale和Shapley不但提出了這個(gè)問題本身，而且給出了一種著名的解法。這個(gè)解法可以描述為如下的求偶過程：

首先，讓這些男生去向他們最心儀的女生求婚——這是數(shù)學(xué)家們的原本的用詞。如果你覺得太快了的話，讓我們暫時(shí)改成表白吧……

然后，等所有男生表白完畢后，所有的收到表白女生們都從自己的表白者中選擇自己最喜歡的人接受為男朋友。沒人表白的女生只能暫時(shí)等一等了，不要著急，表白會(huì)有的。

以上過程稱為“一輪”。之后的每一輪都按照類似的方式進(jìn)行。首先由還處于單身狀態(tài)的男生們每個(gè)人再次向自己還沒有表白過的女生中自己最喜歡的人表白（無(wú)論人家是否已經(jīng)有了男朋友），然后，等所有單身男生表白完畢后，所有的收到表白女生們都從自己的表白者中選擇自己最喜歡的人接受為男朋友。如果原來(lái)有男朋友而表白者中有自己更喜歡的，不要猶豫，換之。等到塵埃落定之后，再開始如上所述的新的一輪表白。

依此類推?？梢宰C明的是，這個(gè)過程一定是會(huì)終止的，也就是說，不會(huì)陷入任何死循環(huán)。并且一旦終止，每個(gè)人都會(huì)找到一個(gè)伴侶。更關(guān)鍵的是，這個(gè)過程最終得到的一定是如前所述的“穩(wěn)定組合”：不存在兩個(gè)非伴侶的異性對(duì)彼此的評(píng)價(jià)比對(duì)各自伴侶的評(píng)價(jià)還要高。——這幾個(gè)事實(shí)都不難證明，有興趣的話可以自己試試看。

所以這就得到了穩(wěn)定婚姻問題的一個(gè)解（順便也證明了解的存在性）。但是真正有趣的部分還在后面。一般來(lái)說，給定若干個(gè)男生女生和他們之間的偏好關(guān)系，穩(wěn)定組合存在不止一種。上述“算法”只是給出了所有可能的穩(wěn)定組合其中之一而已。但是這個(gè)特定的解具有某些特別的性質(zhì)：可以證明（這一次證明不很容易了），上述方式得到的穩(wěn)定組合和所有其他的可能的穩(wěn)定組合相比，是對(duì)男生最優(yōu)而對(duì)女生最劣的。

確切地說是這樣：

它是對(duì)男生最優(yōu)的。也就是說，對(duì)每個(gè)男生來(lái)說，按照這種方式最后找到的伴侶，是在所有的穩(wěn)定組合中自己可能具有的伴侶中自己評(píng)價(jià)最高的?！⒁膺@并不等于說被個(gè)男生都能追到自己最喜歡的女生，而只是說，他一定能追到“有可能和他在穩(wěn)定組合中在一起的女生”中自己最喜歡的。有些女生雖然很好，但是和他在一起是不可能形成穩(wěn)定組合的。這就是人生啊……

另一方面，它是對(duì)女生最劣的。也就是說，對(duì)每個(gè)女生來(lái)說，按照這種方式最后找到的伴侶是在所有的穩(wěn)定組合中自己可能具有的伴侶中自己評(píng)價(jià)最低的。同樣的，這也不等于說每個(gè)女生都只有和自己最不喜歡的男生在一起，而只是說她最后的男朋友會(huì)是所有“有可能”的男生中自己覺得最勉強(qiáng)的。不過這樣聽起來(lái)也已經(jīng)很悲慘了。

這兩個(gè)結(jié)論并不直觀，因?yàn)榭雌饋?lái)在上面所描述的過程中，女生是相對(duì)占有優(yōu)勢(shì)的。作為男生，需要很辛苦地去不斷表白，然后被拒，再表白，再被拒……而女生只要隨心所欲挑選就好，而且還有隨時(shí)更換男友的權(quán)利（在上面的規(guī)則里男生是不能主動(dòng)提出分手的）。為什么結(jié)局會(huì)是如此？

但是如果仔細(xì)思考上面所描述的規(guī)則，會(huì)看到男生至少有一樣優(yōu)勢(shì)——也許是至關(guān)重要的優(yōu)勢(shì)：他們是主動(dòng)方。主動(dòng)的好處是，即使一次又一次的被拒，他也仍然可以和剩下的女生中自己最喜歡的在一起。而對(duì)于女生來(lái)說，縱然有再多挑選的自由，可是一個(gè)女生也許永遠(yuǎn)也等不到自己最喜歡的男生來(lái)追自己——或者在她等到之前，游戲就已經(jīng)結(jié)束了。

毫無(wú)疑問，你已經(jīng)看出在上面的設(shè)定里“男生”和“女生”都只是代號(hào)而已，它符合古典文學(xué)的一貫敘事，但是在當(dāng)代語(yǔ)境里也許并不政治正確。另一方面，這個(gè)定理也不是真的用來(lái)描述愛情的——數(shù)學(xué)家們還沒有這么瘋狂，認(rèn)為可以用邏輯來(lái)推理情感。它只是一個(gè)過于簡(jiǎn)化的模型而已，比張生和維特的故事還要不靠譜的多。

但是我也相信你一定已經(jīng)看出了我這篇文章的主題。在一切古典文學(xué)的敘事里，我們都滿懷著希望注視著那些勇敢的孩子們，看著他們的努力和堅(jiān)持，也許最后會(huì)失敗，可是他們至少嘗試過。

現(xiàn)在連數(shù)學(xué)也在幫著說明這個(gè)道理了，你還等什么呢？

**********************************************************************************

這個(gè)問題確實(shí)是組合數(shù)學(xué)上的經(jīng)典問題。具體算法的證明可以參考《組合數(shù)學(xué)》二分圖匹配中的穩(wěn)定婚姻問題。

這個(gè)算確實(shí)是在一個(gè)偶然的機(jī)會(huì)下接觸到的，但在認(rèn)真看完書后，確實(shí)頗有感想：男生不斷地去像女生表白，然后不斷地被拒絕···看似十分郁悶，但得到的結(jié)果卻是在所有可能的結(jié)果中對(duì)男生最有利的結(jié)果。而女生看似十分幸福，但得到的確實(shí)是最差的結(jié)果。

其實(shí)不僅追mm如此，我們的人生也是如此啊，要敢于去追求自己的目標(biāo)，無(wú)論她看起來(lái)是否是屬于你的，都要勇敢地去嘗試而且一定要堅(jiān)持到底，這樣才能獲得你應(yīng)有的最好的結(jié)果。

穩(wěn)定婚姻問題算法