穩定婚姻問題算法_sunhaowen_百度空間

穩定婚姻問題算法

轉自： http://teruterubouzu-laputa.spaces.live.com/

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

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

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

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

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

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

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

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

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

確切地說是這樣：

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

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

這兩個結論并不直觀，因為看起來在上面所描述的過程中，女生是相對占有優勢的。作為男生，需要很辛苦地去不斷表白，然后被拒，再表白，再被拒……而女生只要隨心所欲挑選就好，而且還有隨時更換男友的權利（在上面的規則里男生是不能主動提出分手的）。為什么結局會是如此？

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

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

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

現在連數學也在幫著說明這個道理了，你還等什么呢？

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

這個問題確實是組合數學上的經典問題。具體算法的證明可以參考《組合數學》二分圖匹配中的穩定婚姻問題。

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

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

穩定婚姻問題算法