大名鼎鼎的穩(wěn)定婚姻算法

這個問題是我學(xué)到的比較有趣的算法問題前幾名了，也是當(dāng)年我們ACM校隊面向新生宣講的時候選擇的例題。我們覺得用找對象這種新生會比較感興趣的問題來忽悠他們，他們上鉤的可能性比較大XD。

問題描述

婚姻匹配也可以叫做CP匹配，問題的場景非常簡單。我們模擬真實的婚戀匹配的場景，比如線下的N男 vs N女的相親活動。很自然的，男生和女生都會對異性在心里有一個評價，覺得自己中意哪個討厭哪個，會有一個優(yōu)先級排名。

我們要做的事情就是設(shè)計一個算法，將這N男和N女組成穩(wěn)定的CP。因為如果是隨便組CP的話非常簡單，隨便配對就好了，但是隨便組成的CP并不一定和諧，很有可能不穩(wěn)定，我們希望情侶們能夠快樂地生活在一起。

解釋一下穩(wěn)定這個概念，我們假設(shè)男生有兩個，男1和男2，女生也有兩個女1和女2。假設(shè)我們組成的CP是男1和女2，男2和女1，但是呢，在女生當(dāng)中，男1更喜歡女1，同樣在男生當(dāng)中女1也更喜歡男1。

也就是說和自己的對象相比，他們對彼此的喜歡要大于各自的伴侶。那么這種情況的CP就是不穩(wěn)定的，時間長了有可能會出問題。為了簡化問題模型，我們假設(shè)一定會出問題，男1最終會和女1在一起，他們各自和自己現(xiàn)在的CP”分手“。

我們希望能夠把N男和N女組成CP，并且希望他們都不會分手，也就是說整個局面是穩(wěn)定的。

問題的解法

關(guān)于這個問題，可能大家會有很多種想法，比如有些人會覺得應(yīng)該給每個男生和女生根據(jù)受對方歡迎的情況打一個分。看看誰是被許多女生喜愛的優(yōu)質(zhì)男生，誰又是受男生歡迎的優(yōu)質(zhì)女生。

因為優(yōu)質(zhì)男生和優(yōu)質(zhì)女生受到對方的關(guān)注比較多，所以先把他們安排好，防止他們出現(xiàn)不穩(wěn)定的情況。之后再去安排那些相對不那么受歡迎的男女生。

這種方法看似可以，但是實現(xiàn)起來非常復(fù)雜，可行性不高，因為優(yōu)質(zhì)男女之間以及優(yōu)質(zhì)男女和非優(yōu)質(zhì)男女之間都有可能出現(xiàn)不穩(wěn)定的情況。本質(zhì)上關(guān)于避免不穩(wěn)定情況出現(xiàn)的邏輯還是欠缺的。

我們還可以用搜索算法來解，這個搜索空間其實是明確的，就是男女生配對，我們就是要搜索出一個穩(wěn)定的配對情況。我們也可以用搜索問題來做，搜索出所有的可能，然后一個一個篩選，找到其中穩(wěn)定的解。

這種方法當(dāng)然是可以的，但是復(fù)雜度非常高，因為我們絕大多數(shù)的搜索情況是無效的。

有沒有效率既高又可以充分解決問題的方法呢？

當(dāng)然也是有的，并且還非常簡單，就是讓這些男生根據(jù)自己心中的排名去追求女生。那么就會出現(xiàn)多個男生同時或者先后追求同一名女生的情況，這里我們做一個非常簡單的假設(shè)，假設(shè)女生始終會選擇在自己列表上排名高的那一個男生作為自己的CP。

第一輪我們讓所有的男生都去追求自己最心儀的女生，經(jīng)過一系列競爭，必然會有一些男生成功的組成了CP。第二輪，我們讓單身的男生再去追求自己第二喜歡的女生，經(jīng)過一輪競爭，又有一些人脫單了。我們?nèi)绱搜h(huán)往復(fù)，直到所有的人都配對。

這樣，我們的算法就介紹完了。

就這么簡單嗎？是的就這么簡單，但是這樣能保證所有男女都能找到對象嗎？會不會有一些男女和女生剩下，或者是會出現(xiàn)不穩(wěn)定的情況呢？

其實是不會的，證明也非常容易。

首先，可以證明不會出現(xiàn)有人沒有配對成功的情況。我們假設(shè)存在一男一女最后落單的情況，那么假設(shè)的前提就是剩男已經(jīng)向所有的女生都表過白并且被拒絕了。但女生在只有一個追求者的情況下是不會拒絕的，所以這就與假設(shè)矛盾了。所以算法不會出現(xiàn)沒有結(jié)果的情況，可以保證所有男女都組成CP。

其次，我們可以證明不會出現(xiàn)男女不穩(wěn)定的情況。我們也可以使用反證法，我們假設(shè)存在男1和女1彼此都是各自更加喜歡的，但是又沒有在一起。但是根據(jù)我們算法的規(guī)則，那么男1必然先于當(dāng)前的對象追求女1。那么對于女1來說，如果男1大于她當(dāng)前的對象，她不可能不和男1在一起，所以這也是矛盾的。

到這里，整個算法的過程就介紹完了。這個算法其實是有來頭的，并不是我們自己YY的，它的學(xué)名叫做Gale-Shapley算法。顧名思義是由Gale和Shapley兩個人在1962年共同研究發(fā)表的，據(jù)說在該算法發(fā)表的10年之前，美國一些地方就使用這個算法來給醫(yī)學(xué)院的畢業(yè)生分配工作?？梢娫诤茉缰埃藗兙鸵庾R到了穩(wěn)定匹配的重要性，并且依據(jù)直覺開始應(yīng)用了。

算法實現(xiàn)

這個算法其實很容易實現(xiàn)，我們只需要記錄下面男生和女生當(dāng)前的匹配情況，以及男生向女生發(fā)起追求的輪次，中間的邏輯非常簡單。

女生如果單身，那么一定接受男生的追求，否則比較一下和現(xiàn)在對象的優(yōu)先級。如果優(yōu)先級更高，后來的男生競爭上崗，前面的男生下崗，回到單身狀態(tài)。我們只需要把這些狀態(tài)厘清，代碼實現(xiàn)非常簡單。我實現(xiàn)了一個版本，給大家提供一下參考：

import?random
import?sys

#?生產(chǎn)測試數(shù)據(jù)，生成男生和女生心中的對象排序
def?generate_list(n):
????base?=?list(range(n))
????random.shuffle(base)
????return?base

if?__name__?==?"__main__":
????boys,?girls?=?[],?[]
????n?=?int(sys.argv[1])
????for?i?in?range(n):
????????boys.append(generate_list(n))
????????girls.append(generate_list(n))

????print('The?preference?of?boys')
????print(boys)
????print('The?preference?of?girls')
????print(girls)

????#?一開始的時候匹配狀態(tài)記為-1
????girls_matched?=?[-1?for?_?in?range(n)]
????#?男生發(fā)起輪次記為0，表示下一次追求第幾偏好的女生
????boys_round?=?[0?for?_?in?range(n)]
????boys_matched?=?[-1?for?_?in?range(n)]

????while?True:
????????all_matched?=?True
????????for?i?in?range(n):
????????????#?如果已經(jīng)匹配了，則跳過
????????????if?boys_matched[i]?!=?-1:
????????????????continue

????????????all_matched?=?False
????????????girl?=?boys[i][boys_round[i]]
????????????boys_round[i]?+=?1

????????????#?如果女生沒有對象，直接答應(yīng)
????????????if?girls_matched[girl]?==?-1:
????????????????girls_matched[girl]?=?i
????????????????boys_matched[i]?=?girl
????????????else:
????????????????#?否則和現(xiàn)在對象比較一下順序
????????????????idx?=?girls[girl].index(i)
????????????????mate?=?girls_matched[girl]
????????????????mate_idx?=?girls[girl].index(mate)
????????????????if?idx?????????????????????boys_matched[i]?=?girl
????????????????????boys_matched[mate]?=?-1
????????????????????girls_matched[girl]?=?i

????????if?all_matched:
????????????break

????print('The?match?result?of?boys:')
????print(boys_matched)

????print('The?match?result?of?girls:')
????print(girls_matched)

我們運行一下代碼，查看結(jié)果：

我們可以模擬一下，第一輪結(jié)果是[0-3], [1-4], [3-0], [4-2]。其中2和3號男生都向0號女生發(fā)起追求，0號女生接受了3號拒絕了2號。于是第二輪2號男生向2號女生發(fā)起追求，由于2號女已經(jīng)和最佳心儀對象4號男組成了CP，所以2號男失敗。繼續(xù)向3號女發(fā)起追求，3號女的原來對象是0號男，由于0號男排名非常低，于是0號男被甩。所以第二輪的結(jié)果是[1-4],[2-3],[3-0],[4-2]。

第二輪的結(jié)果是0號男落下，0號男向4號以及0號女發(fā)起追求都宣告失敗，最終和1號女組成CP。所有的男女都組成了CP，并且沒有不穩(wěn)定的情況出現(xiàn)。我們?nèi)斯ね评淼玫降慕Y(jié)果和我們程序給出的結(jié)果完全一致。

總結(jié)

這個算法并不難，但是勝在非常有趣。實際上在生活當(dāng)中有許多分配方案直接或者是間接使用了Gale-Shapley算法。如果大家熟悉算法的話，會發(fā)現(xiàn)其實這個問題的本質(zhì)是二分圖匹配。我們可以用二分圖匹配的算法來解決這個問題。

如果我們研究一下這個算法的核心邏輯，會發(fā)現(xiàn)其實是對男生有優(yōu)勢的，雖然女生看起來有最終的選擇權(quán)，但男生更有機會追求自己最心儀的對象，而女生只能被動地等待男生發(fā)起追求來進(jìn)行挑選。如果某個女生喜歡的男生不選她，那么她永遠(yuǎn)沒有和他在一起的機會。這個故事告訴我們，喜歡的對象要自己挑，主動才是王道。

如果你還單身的話，希望對你有所幫助。