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

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

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

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

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

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

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

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

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

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

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

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

確切地說是這樣：

它是對男生最優(yōu)的。也就是說，對每個男生來說，按照這種方式最后找到的伴侶，是在所有的穩(wěn)定組合中自己可能具有的伴侶中自己評價最高的。——注意這并不等于說被個男生都能追到自己最喜歡的女生，而只是說，他一定能追到“有可能和他在穩(wěn)定組合中在一起的女生”中自己最喜歡的。有些女生雖然很好，但是和他在一起是不可能形成穩(wěn)定組合的。這就是人生啊……

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

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

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

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

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

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

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

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

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

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

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