有趣的演算法(一)：如何讓有情人終成眷屬

04-21

數學與演算法告訴我們，有情人必將終成眷屬，只是缺少方法

看過《非誠勿擾》的同學一定還記得節目中的相親模式，當男嘉賓入場後會首先選擇最喜歡的心動女生，然後在幾輪「面試」後由最後亮燈的女生，也就是心儀男嘉賓的女生與男嘉賓一開始選擇的心動女生做比較。結果有三種可能性：

男嘉賓心儀的女生就是最後留燈的女生
男嘉賓的心動女生滅燈了，而心儀男嘉賓的女生留燈
沒有人為男嘉賓留燈

有趣的是，有時候，留燈的女生即便是男嘉賓不喜歡的類型，很多時候也會被牽手，而也有女嘉賓在台上站了很多期節目，被優質的人翻號，卻沒有被所帶走，到最後反而被一些很普通的男生牽手成功。

現在，考慮將上述過程的選擇次數增加至多次，並允許與女嘉賓人數（假設為N）相同的男嘉賓同時上台。此時情況略微複雜，我們假定每位男嘉賓可以有多位心動女生，並且排名有先後，女嘉賓同樣如此。

那麼在這個男女雙方互選的過程中，如何得到最優的配對，即自己喜歡的人總能與喜歡自己的人在一起呢？答案是，選擇的次數與心儀對象在心中的先後位次不同。

如果將兩個相互喜歡的戀人之間的相遇相識，視為一次配對，那麼對於任意多次配對，如何最優化輸出結果，令配對完成後所有人都能找到自己最優的伴侶，便是演算法的目標。

羅斯在《共享經濟》中說，「市場的核心是配對」。數學中我們對市場行為做出了最優解的預測，此類解會給出收益最大化，風險最小化的可行項。那麼，如果我們將感情關係中的相互選擇看做是市場的交易行為，很容易發現，我們的核心也同樣是這兩個字——配對

情侶配對問題

一．立即接受演算法：

對於約會的配對，大家都去追自己最心儀的女生。而這個女生面對幾位追求者，要立刻做個決定。
被拒絕的男生們調整一下心情，再去追求心中的 No. 2。以此類推。

這樣做法有一個嚴重的問題：當你被你的No.1拒絕後，再去追求你的No.2的時候，你心中的No.2可能已經在第一輪中選擇了其他人。

但坑爹的是，有可能你正是你心中No.2心中的No.1，但是她並不知道。所以她在第一輪中，因為沒有被你追求，而屈就他人。當你你在第一輪中表白失敗，再去找你的No.2 時，已然晚矣。

假設班上有三位男生（分別是A，B，C），三位女同學（分別是x，y，z）

見圖一（左女右男）：

他們心中對異性的排名見圖二。在女x的心中A>B，意味著A要好於B。

第一輪中，男生們向心中的No.1女示好，即A，B兩男向心中最喜歡的x女示好，而C男向y女示好。如圖三所示。

（在第一輪，女y 只有一個追求者，只能屈就）

如果採用立即接受演算法，此輪之後的結果是，x-A，y-C兩對結成情侶。注意，y女雖然心中首選是B男，但是由於B男在此輪中正在追逐x女，無奈下y女屈就於唯一來獻殷勤的C男。比及第二輪開始時，唯一還沒配對的就是z女和B男了，所以B男只能接受z女。

最後的結果是x-A，y-C，z-B三對戀人。

注意：y女和B男兩人都更願意離開自己的現任伴侶而彼此在一起。如果二人結為伴侶，那麼彼此的忠誠度與長久的穩定度必然小於A女與X男，也就是相互不喜歡的人在一起白頭偕老的可能性，會更低於那些相互喜歡的人。

這種不穩定的「婚姻系統」狀態就是很多文學影視作品的來源，也是生活中的八卦來源。而在數學上，這也恰恰被稱為是「不穩定」的組合。

所以，顧名思義，我們希望能夠有種演算法，給我們的結果是所有配對都是穩定的，讓天下有情人都終成眷屬。

怎麼做呢？一個詞：hold住

二．延遲接受演算法

延遲接受演算法的步驟如下：

Round 1

每個男生向自己心中的No.1示愛。但是各位姑娘們不用立即決定，而是先hold住。

Round 2

每個男生再向心中的No.2示愛。從第二輪開始，每位姑娘們只保留自己到現在為止所收穫的最心儀的男生（但是不用答應他，只hold在心理），而拒絕其他所有人。

而被拒絕的男生（也就是現在尚沒有人hold著你的男生）則繼續在下一輪中向心中排名的下一個姑娘表白。

Round 3 to n

以此類推，一輪輪繼續下去，直到所有想示愛的男生都示完為止。此時，每個手中有offer的姑娘，可以選擇接受。也就是說，先讓女生獲得完全信息（這類情況在生活中也較為常見）

以上就是延遲接受演算法的做法。大家仔細算一下就會發現，在這個簡單的例子中，最後的結果是x-A，y-B，z-C三組戀人終成眷侶。而這是一個穩定的系統輸出結果，即：

所有6人中，你不可能找到一男一女符合以下條件：

他們都更願意拋棄已有的伴侶而與彼此在一起。

因此，這些配對的情侶之間，由於他人因素的分手，以及單方面的出軌行為發生的概率，會明顯低於第一種演算法所配對的情侶

延遲接受演算法（deferred-acceptance algorithm）能夠從數學上證明是一定會產生穩定配對的演算法，也叫做蓋爾-沙普利演算法（the Gale-Shapley algorithm），因為具體的演算法是始於蓋爾和沙普利的配對實驗。

羅斯在《共享經濟》中介紹了他將延遲接受演算法分別運用於腎臟移植市場，全國住院醫生配對程市場和高中擇校系統，實現了穩定的配對，取得了非常好的成果。

感情中我們難免都會略有遺憾，完美的情感演算法並不存在，也不會有一個萬能的觀測者（比如月老）來為我們選擇配對。但是如何決定自己的預期與選擇，如何最好地在現實與理想型之間均衡選擇，卻是我們可以改變的。

有句話叫「求而不得，往往不求而得」。其實生活中，在我們遇到這樣邏輯上並不複雜，但選擇起來卻無比困難的情況時，也不應該不要急於眼前的境況，不要因為一時的感動或是長輩的催促，就潦草的將自己託付給他人。

是妥協，還是等待？沒人能給出固定的答案，或者說，每個人心底都有一個答案，即使不是你心目中最好的。

懂得等待，寧缺毋濫，才是最好的選擇標準。hold住自己的情感，多珍惜身邊的人，當你在執著的追求你的男神/女神卻苦苦無終，陷入單戀的鬱鬱寡歡時，

等等看，也許你真正的另一半，互相愛慕的另一半，就在不遠的未來靜靜地等待著你

等等看，也許這段等待並不會漫長，當你進化成更好的人，櫻花墜落的一瞬，這個人就會出現

參考文章：

[Algorithm] Deferred Acceptance Algorithm

Discrete Mathematics & Applications, Kenneth H.Rosen. 7th edition