國府深深
從紅橋到劍橋
一些朋友喜歡看江蘇衛視的《非誠勿擾》，不過在裏麵，四五個男生對二十四個姑娘，磨磨唧唧一個多小時，還常常配對失敗……死理性派表示：給我100 個男人100個女人，就可使其一一配對，還不會有人私奔。
聽起來很扯吧？然而數學家們可是切切實實地研究過這個問題哦。這就是所謂的穩定匹配問題(Stable Marriage Problem，也叫穩定婚姻問題）。
先對意中人排個名
要進行速配，當然要考慮男女雙方的意願。不幸的是，要讓每一個人都剛好能和自己最喜歡的人在一起基本上是不可能的（所以才有那麽多三角戀多角戀 啊），總不免有人最終得不到自己最愛的那個TA，這時候他就不得不考慮“第一喜歡”的人、“第六喜歡”的人……所以，每個人都必須將對麵的100個異性按 最喜歡到最不喜歡排個序，不妨稱之為“偏愛序”。
然後就能按照所有人進行速配了，而且這個速配是穩定的，不會出現“私奔”的情況呢。
什麽是不穩定，有人曾用一句不太雅但很形象的話來描述：不穩定婚姻意味著不但我家要有一枚奸夫，你家還要有一隻淫婦才行。也就是說，A男喜歡B女勝過自己的妻子，同時B女喜歡A男勝過自己的丈夫，然後他們就私奔了。
在這場速配中，如果出現私奔，那它就是不穩定婚姻，反之則為穩定婚姻。
怎樣速配：Gale & Shapley 方法
其實早在1962年，美國數學家戴維·戈爾（David Gale）和勞埃德·夏普利（Lloyd Shapley）就解決了這個問題。他們的思路是這樣的：
第一天
上午，所有的男人都向自己最愛的女人求婚。
下午，每個女人清點自己的求婚列表。如果隻收到一個男人的求婚，那麽就和他訂婚。如果收到多於一個男人的求婚，那麽就和其中她最愛的那個男人訂婚，同時把其他男人都拒絕掉。如果一個求婚都沒有，不要著急，最後總會有的。
晚上，檢查一遍，如果所有女人都訂婚了，那麽，萬事大吉，第二天舉行集體婚禮。
但如果還有女人沒有訂婚，那麽事情還沒完，第二天繼續。
第二天
上午，所有還沒訂婚的男人向自己次愛的女人求婚。（昨天他們已經被最愛拒絕了）
下午，每個女人再看一遍自己收到訂婚的情況。如果她已經訂婚了，但是又有一個她更愛的男人來向她求婚，那就把原來那個拒絕掉，再和這個更愛的男人訂婚；如果還沒訂婚，那就和第一天的下午的處理一樣。
晚上再檢查一遍，如果還是有人沒有訂婚，那第三天再重複。
第三天
上午，所有沒有訂婚的男人，包括第一天訂了第二天又被踹出來的，再向還沒有拒絕過他的女人中他最愛的那個求婚。
如此周而複始，直到最後大家都訂了婚，就舉行集體婚禮。
這是一個對男人有利的速配法
直覺上，女性在這個匹配算法中貌似更有優越感——男人們來向自己求婚，自己可以挑選一個自己最喜歡的。而男人們很可能會屢屢被拒。
那麽這個算法是否真的是對女性比較有利呢？讓我們分別考察男人和女人如何才能得到自己的最喜歡的人。設A男要得到他最喜歡的B女，首先要看還有多少 別的男人同時也喜歡B，然後再與這些情敵競爭。而女人是否能與最喜歡的男人結婚，首先就要看她自己在對方的偏愛序中排老幾，也就是說，一開始她就要和所有 的同性競爭了。
在這個算法裏，男人相比女人最大的優勢就是他是主動的一方，即使像櫻木花道一樣被拒了50次，仍然可以追求他喜歡的晴子。你也許會說，漂亮的女生肯定會有很多男人追啊。話是沒錯，可是她心中的那個他不喜歡自己，那再多的追求者也枉然啊。
所以啊，姑娘們要想要好GG，還是得自己主動啊。
附：Gale & Shapley 方法的合理性說明
算法的可終止性可證：每個男人按照自己的偏愛序一個個求婚下來，一定有一個女人會要他——試想一個男人被一百個女人拒絕掉了，那他的偏愛序中已經沒 有人可以求婚了，所以他得不到配對，對應地對麵也肯定有一個剩女，可是這個剩女曾經拒絕過他呀，也就是說她有更好的追求者呀，她怎麽可能成為剩女呢？
算法的正確性也可證：假設有A男和B女私奔了。那麽A在B的偏愛序中必然比B的丈夫靠前，按照算法，女人最後選擇的一定是所有向她求婚的男人中她最 喜歡的，這就是說A沒有向B求過婚（要不然B選的就是他了）。然而，男人是按照自己的偏愛序依次求婚的，而A又喜歡B甚於自己的老婆，所以A又必然向B求 過婚。推出矛盾，故不可能出現私奔。轉帖
