（算法）穩(wěn)定婚姻匹配

婚介所登記了N位男孩和N位女孩，每個男孩都對N個女孩的喜歡程度做了排序，每個女孩都對N個男孩的喜歡程度做了排序，你作為月老，能否給出穩(wěn)定的牽手方案？

穩(wěn)定的定義：如果男孩i和女孩a牽手，但男孩i對女孩b更喜歡，而女孩b的男朋友j拼不過男孩i，則沒有力量阻礙男孩i和女孩b的私奔，這即是不穩(wěn)定的。

?? 1962 年，美國數(shù)學家 David Gale 和 Lloyd Shapley 發(fā)明了一種尋找穩(wěn)定婚姻的策略。不管男女各有多少人，不管他們各自的偏好如何，應(yīng)用這種策略后總能得到一個穩(wěn)定的婚姻搭配。換句話說，他們證明了穩(wěn)定的婚姻搭配總是存在的。有趣的是，這種策略反映了現(xiàn)實生活中的很多真實情況。

??? 算法中采用了男生主動追求女孩的形式。

算法步驟描述：

? ? 第一輪，每個男人都選擇自己名單上排在首位的女人，并向她表白。這種時候會出現(xiàn)兩種情況：

　（1）該女士還沒有被男生追求過，則該女士接受該男生的請求。

　（2）若該女生已經(jīng)接受過其他男生的追求，那么該女生會將該男士與她的現(xiàn)任男友進行比較，若更喜歡她的男友，那么拒絕這個人的追求，否則，拋棄其男友

? ? 第一輪結(jié)束后，有些男人已經(jīng)有女朋友了，有些男人仍然是單身。

? ? 在第二輪追女行動中，每個單身男都從所有還沒拒絕過他的女孩中選出自己最中意的那一個，并向她表白，不管她現(xiàn)在是否是單身。這種時候還是會遇到上面所說的兩種情況，還是同樣的解決方案。直到所有人都不再是單身。

怎么證明這個算法肯定能夠得到穩(wěn)定的婚姻？

（1）隨著輪數(shù)的增加，總有一個時候所有人都能配上對。因為男生根據(jù)自己心目中的排名依次對女士進行表白，假如有一個人沒有配上對，那么這個人必定是向所有的女孩進行表白了。但是女孩只要被表白過一次，就不可能是單身，也就是說此時所有的女生都不是單身的，這與有一個人沒有配上對是相悖的。所以假設(shè)不成立。該算法一定會使得所有人都能夠配對成功。

（2）隨著輪數(shù)的增加，男士追求的對象越來越糟，而女士的男友則可能變得越來越好。假設(shè)男A和女1各有各自的對象，但是比起現(xiàn)在的對象，男A更喜歡女1，所以，在此之前男A肯定已經(jīng)跟女1表白過的，并且女1拒絕了男A，也就是女1有了比男A更好的男友，不會出現(xiàn)私奔的情況……。