一些優(yōu)秀的算法就好像圍棋中的定式，或者是程序設(shè)計(jì)中的設(shè)計(jì)模式一樣，前人已經(jīng)在總結(jié)了該類問題的基礎(chǔ)之上，給出了完備的解決方法。那么對(duì)于一名優(yōu)秀的程序員來說，就需要了解這些算法，并且在遇到類似的問題的時(shí)候，第一時(shí)間就會(huì)想到應(yīng)用這種算法。這樣會(huì)大大的提高編程的效率。
今天我們就來看一下延遲認(rèn)可算法。了解延遲認(rèn)可算法之前，我們先需要了解一下穩(wěn)定婚姻問題。
所以穩(wěn)定婚姻問題，通俗地可敘述為：當(dāng)前有N位男生和N位女生最后要組成穩(wěn)定的婚姻家庭，過程開始之前男生和女生在各自的心目中都按照喜愛程度對(duì)N位異性有了各自的排序，男生和女生結(jié)婚后，對(duì)于每一對(duì)男生女生，不會(huì)出現(xiàn)比起當(dāng)前匹配的伴侶互相更喜愛的一對(duì)男生女生，即可認(rèn)為婚姻是穩(wěn)定的。
穩(wěn)定婚姻問題可以用在很多領(lǐng)域，例如將用戶分配給大型分布式Internet服務(wù)中的服務(wù)器。數(shù)十億用戶訪問Internet上的網(wǎng)頁，視頻和其他服務(wù)，要求每個(gè)用戶都與全球提供該服務(wù)的數(shù)十萬臺(tái)服務(wù)器之一匹配。用戶希望服務(wù)器足夠近，以便為所請(qǐng)求的服務(wù)提供更快的響應(yīng)時(shí)間，從而導(dǎo)致每個(gè)用戶對(duì)服務(wù)器的（部分）優(yōu)先排序。每個(gè)服務(wù)器都希望以較低的成本為用戶提供服務(wù)，從而導(dǎo)致每個(gè)服務(wù)器的用戶（部分）優(yōu)先排序。分發(fā)世界上許多內(nèi)容和服務(wù)的內(nèi)容交付網(wǎng)絡(luò)每數(shù)十秒就解決了用戶與服務(wù)器之間這個(gè)龐大而又復(fù)雜的穩(wěn)定婚姻問題，使數(shù)十億用戶可以與各自的服務(wù)器進(jìn)行匹配，以提供所需的網(wǎng)頁，視頻或其他內(nèi)容服務(wù)。
1962年，美國數(shù)學(xué)家David Gale和Lloyd Shapley發(fā)明了一種尋找穩(wěn)定婚姻的策略，人們稱之為延遲認(rèn)可算法（Gale-Shapley算法）。
該算法的執(zhí)行步驟如下，在計(jì)算策略中，男性將一輪輪的去追求他中意的女性，而女性則可以選擇接受或者拒絕她的追求者。
那么，首先對(duì)所有男士進(jìn)行落選標(biāo)記，稱其為自由男。當(dāng)存在自由男時(shí)，進(jìn)行以下操作：
1、每一位自由男在所有尚未拒絕她的女士中選擇一位被他排名最優(yōu)先的女士；
2、每一位女士將正在追求她的自由男與其當(dāng)前男友進(jìn)行比較，選擇其中排名優(yōu)先的男士作為其男友，即若自由男優(yōu)于當(dāng)前男友，則拋棄前男友；否則保留其男友，拒絕自由男。
3、若某男士被其女友拋棄，重新變成自由男。
在算法執(zhí)行期間，自由男們主動(dòng)出擊，依次對(duì)最喜歡和次喜歡的女人求愛，一旦被接受，即失去自由身，進(jìn)入訂婚狀態(tài)；而女人們則采取“守株待兔”和“喜新厭舊”策略，對(duì)前來求愛的男士進(jìn)行選擇：若該男子比未婚夫強(qiáng)，則悔婚，選擇新的未婚夫；否則拒絕該男子的求婚。被女友拋棄的男人重獲自由身，重新?lián)碛辛俗非笈说臋?quán)利，當(dāng)然，新的追求對(duì)象比不過前女友。
這樣，在算法執(zhí)行期間，每個(gè)人都有可能訂婚多次，也有可能一開始就找到了自己的最愛，從一而終。
而每訂一次婚，女人們的選擇就會(huì)更有利，而男人們的品味則越來越差。只要男女生的數(shù)量相等，則經(jīng)過多輪求婚，訂婚，悔婚和再訂婚之后，每位男女最終都會(huì)找到合適的伴侶，雖然不一定是自己的最愛（男人沒能追到自己的最愛，或女人沒有等到自己的最愛來追求），但絕對(duì)不會(huì)出現(xiàn)“雖然彼此相愛，卻不能在一起”的悲劇，所有人都會(huì)組成穩(wěn)定的婚姻。
下面我們來看一下算法的穩(wěn)定性：
1、隨著輪數(shù)的增加，總有一個(gè)時(shí)候所有人都能配對(duì)，因此不會(huì)出現(xiàn)無法終止一直循環(huán)的情況。
2、由于在每一輪中，至少有一個(gè)男性向某個(gè)女性告白，因此總的告白次數(shù)將隨著輪數(shù)的增加而增加，倘若這個(gè)流程一直沒有因所有人都配上對(duì)了而終止，最終必然會(huì)出現(xiàn)某個(gè)男性追遍了所有女性的情況，而一個(gè)女性只要被人追過一次，以后就不可能單身了。既然所有女性都被這個(gè)男性追過，那么就說明所有女性現(xiàn)在都不是單身，也就是說此時(shí)所有人都已配對(duì)。
3、隨著輪數(shù)的增加，一個(gè)男性追求女性的對(duì)象總是越來越糟，但一個(gè)女性的男友只可能變得越來越好。假設(shè)男 A 和女 1 各有各自的對(duì)象，但比起現(xiàn)在的對(duì)象，男 A 更喜歡女 1，因此男 A 之前肯定向女 1 表白過，既然女 1 最后沒有跟男 A 在一起，那么說明女 1 拒絕了男 A，也即說明女 1 有了比男 A 更好的男性。
這就證明了，兩個(gè)人雖然不是一對(duì)，但都覺得對(duì)方比自己現(xiàn)在的伴侶好的情況絕不會(huì)發(fā)生。
這個(gè)問題是數(shù)學(xué)界認(rèn)真研究過的問題，但是相關(guān)理論最終給出的結(jié)果卻很有意思，結(jié)果顯示，對(duì)于傳統(tǒng)的求愛過程來說，男性能夠得到盡可能好的心上人，女性卻不然?；蛘哌@也就是目前北上廣深等大城市里面大齡剩女如此的多的原因。
事實(shí)上，穩(wěn)定婚姻搭配往往不止一種，然而上述算法的結(jié)果可以保證，每一位男性得到的伴侶都是所有可能的穩(wěn)定婚姻搭配方案中最理想的，同時(shí)每一位女性得到的伴侶都是所有可能的穩(wěn)定婚姻搭配方案中最差的。
因此，這個(gè)算法告訴我們：要主動(dòng)出擊，不能守株待兔。
聯(lián)系客服
