什么是算法？

>>>>

每當(dāng)有人問(wèn)我這樣的問(wèn)題，我總會(huì)引用下面這個(gè)例子。?

假如你是一個(gè)媒人，有若干名單身男子登門(mén)求助，還有同樣多的單身 女子也來(lái)征婚。如果你已經(jīng)知道這些女孩兒在每個(gè)男孩兒心目中的排名，以及男孩兒們?cè)诿總€(gè)女孩兒心目中的排名，那么你該怎樣為他們牽線(xiàn)配對(duì)呢？?

最好的配對(duì)方案當(dāng)然是，每個(gè)人的另一半正好都是自己的“第一選擇”。

這當(dāng)然很完美，但絕大多數(shù)情況下都不可能實(shí)現(xiàn)。

比方說(shuō)，男 1 號(hào)的最?lèi)?ài)是女 1 號(hào)，而女 1 號(hào)的最?lèi)?ài)不是男 1 號(hào)，這兩個(gè)人的最佳選擇就不可能被同時(shí)滿(mǎn)足。如果出現(xiàn)了好幾位男士的最?lèi)?ài)是同一個(gè)女孩兒的情況，這幾位男士的首選也不會(huì)同時(shí)得到滿(mǎn)足。

當(dāng)這種最為理想的配對(duì)方案無(wú)法實(shí)現(xiàn)時(shí)， 怎樣的配對(duì)方案才能令人滿(mǎn)意呢？

其實(shí)，找對(duì)象不見(jiàn)得需要那么完美，和諧才是關(guān)鍵。

如果男 1 號(hào)和女 1 號(hào)各有各的對(duì)象，但男 1 號(hào)覺(jué)得女 1 號(hào)比自己的現(xiàn)任更好，女 1 號(hào)也覺(jué)得對(duì)方比自己的現(xiàn)任更好，那么兩人就可能扔下自己現(xiàn)在的另一半，走在一起——因?yàn)檫@個(gè)結(jié)果對(duì)他們兩人都更好一些。

如果在一種男女配對(duì)方案中出現(xiàn)了這種情況，我們就說(shuō)這種配對(duì)方案是不穩(wěn)定的。作為一個(gè)紅娘，你深深地知道，介紹對(duì)象就怕婚姻關(guān)系不穩(wěn)定。因此，在給客戶(hù)牽線(xiàn)配對(duì)時(shí)，雖然不能讓每個(gè)人都得到最合適的，但婚姻搭配必須得是穩(wěn)定的。

現(xiàn)在，我們的問(wèn)題就是：穩(wěn)定的婚姻搭配總是存在的嗎？如果存在，又應(yīng)該怎樣尋找出一個(gè)穩(wěn)定的婚姻搭配？?

為了便于分析，下面我們做一些約定。我們用字母 A、B、C 對(duì)男性進(jìn)行編號(hào)，用數(shù)字 1、2、3 對(duì)女性進(jìn)行編號(hào)。我們把所有男性從上到下列在左側(cè)，括號(hào)里的數(shù)字表示每個(gè)人心目中對(duì)所有女性的排名；再把所有女性列在右側(cè)，用括號(hào)里的字母表示她們對(duì)各位男性的偏好。

圖 1 所示就是有 2 男 2 女的一種情形，每個(gè)男的都更喜歡女 1 號(hào)，但女 1 號(hào)更喜歡男 B，女 2 號(hào)更喜歡男 A。若按 A—1、B—2 進(jìn)行搭配，則男 B 和女 1 都更喜歡對(duì)方一些，這樣的婚姻搭配顯然是不穩(wěn)定的。但若換一種搭配方案（如圖 2 所 示），這樣的搭配就是穩(wěn)定的了。

圖 1 一個(gè)不穩(wěn)定的婚姻搭配（男 B 和女 1 都不滿(mǎn)意現(xiàn)任伴侶）

圖 2 一個(gè)穩(wěn)定的婚姻搭配

可能很多人會(huì)立即想到一種尋找穩(wěn)定婚姻搭配的策略：不斷修補(bǔ)當(dāng)前搭配方案。如果兩個(gè)人互相之間都覺(jué)得對(duì)方比自己當(dāng)前的伴侶更好，那就讓這兩個(gè)人成為一對(duì)，剛剛被甩的那兩個(gè)人組成一對(duì)。如果還有想要在一起的男女對(duì)，就繼續(xù)按照他們的愿望對(duì)換情侶，直到最終消除所有的不穩(wěn)定組合。

容易看出，應(yīng)用這種“修補(bǔ)策略”所得到的最終結(jié)果一定滿(mǎn)足婚姻的穩(wěn)定性，但這種策略的問(wèn)題在于，它不一定有一個(gè)“最終結(jié)果”。按照 上述方法反復(fù)調(diào)整搭配方案，最終有可能陷入一個(gè)死循環(huán)，無(wú)法得出一個(gè)確定的方案（如圖 3 所示）。

圖 3 應(yīng)用“修補(bǔ)策略”可能會(huì)產(chǎn)生死循環(huán)

1962年，美國(guó)數(shù)學(xué)家戴維·蓋爾（David Gale）和羅伊德·沙普利（Lloyd Shapley）發(fā)明了一種尋找穩(wěn)定婚姻的策略。

不管男女各有多少人，也不管他們各自的偏好如何，應(yīng)用這種策略后總能得到一個(gè)穩(wěn)定的婚姻搭配。換句話(huà)說(shuō)，他們證明了穩(wěn)定的婚姻搭配總是存在的。

有趣的是，這種策略反映了現(xiàn)實(shí)生活中的很多真實(shí)情況。?

在這種策略中，男士將一輪一輪地去追求他中意的女子，而女子可以選擇接受或拒絕相應(yīng)的追求者。第一輪，每位男士都選擇向自己最心儀的女子表白。

此時(shí)，每個(gè)女子可能面對(duì)的情況有三種：沒(méi)有人向她表白，只有一個(gè)人向她表白，有不止一個(gè)人向她表白。

在第一種情況下，這個(gè)女子什么都不用做，只需繼續(xù)等待；在第二種情況下，接受那個(gè)人的表白，答應(yīng)暫時(shí)和他做男女朋友；在第三種情況下，從所有追求者中選擇自己最中意的那一位，答應(yīng)暫時(shí)和他做男女朋友，并拒絕其他所有的追求者。

第一輪結(jié)束后，有些男士已經(jīng)有女朋友了，有些男士仍然單身。第二輪，每位單身男士都從所有尚未拒絕他的女子中選出自己最中意的，并向她表白，無(wú)論她現(xiàn)在是否單身。

和第一輪一樣，每位女子需要從表白者中選擇自己最中意的一位，拒絕其他追求者。

注意，如果這個(gè)女子已經(jīng)有男朋友，當(dāng)遇到更好的追求者時(shí)，她必須拋開(kāi)現(xiàn)任男友，投向新的追求者的懷抱。這樣，一些單身男士將會(huì)找到女友，而那些已經(jīng)有女友的也可能會(huì)恢復(fù)單身。

在以后的每一輪中，單身的男士繼續(xù)按照心目中的排序追求下一個(gè)女子，而女子則從包括現(xiàn)男友在內(nèi)的所有追求者中選擇自己最中意的一個(gè)，并對(duì)其他人說(shuō)不。這樣一輪一輪地進(jìn)行下去，直到某個(gè)時(shí)候所有人都不再單身，接下來(lái)的一輪將不會(huì)發(fā)生任何表白，整個(gè)過(guò)程也就自動(dòng)結(jié)束 （如圖 4 所示）。此時(shí)的婚姻搭配就一定是穩(wěn)定的了。

圖 4 應(yīng)用上述策略，三輪之后將得出穩(wěn)定的婚姻搭配

這個(gè)策略會(huì)不會(huì)像之前的修補(bǔ)法一樣，出現(xiàn)永遠(yuǎn)也無(wú)法終止的情況呢？

不會(huì)。

下面我們將說(shuō)明，隨著輪數(shù)的增加，總有一個(gè)時(shí)候所有人都能配上對(duì)。

由于在每一輪中，至少會(huì)有一個(gè)男士向某個(gè)女子告白，因此總的告白次數(shù)將隨著輪數(shù)的增加而增加。倘若整個(gè)流程一直沒(méi)有因所有人都配上對(duì)而結(jié)束，最終必然會(huì)出現(xiàn)某個(gè)男子追遍了所有女孩兒的情況。而一個(gè)女孩兒只要被人追過(guò)一次，以后就不可能再單身了。既然所有女孩兒都被這個(gè)男人追過(guò)，就說(shuō)明所有女孩兒現(xiàn)在都不是單身，也就是說(shuō)此時(shí)所有人都配上對(duì)了。?

接下來(lái)，我們還需要證明，這樣得出的配對(duì)方案確實(shí)是穩(wěn)定的。

首先注意到，隨著輪數(shù)的增加，一個(gè)男人追求的對(duì)象總是越來(lái)越糟，而一個(gè)女孩兒的男友只可能變得越來(lái)越好。假設(shè)男 A 和女 1 各自有各自的對(duì)象，但比起現(xiàn)在的對(duì)象來(lái)，男 A 更喜歡女 1。

因此，在此之前男 A 肯定已經(jīng)跟女 1 表白過(guò)。既然女 1 最后沒(méi)有跟男 A 在一起，說(shuō)明女 1 拒絕了男 A，也就是說(shuō)她有了比男 A 更好的男人。這就證明了，兩個(gè)人雖然不是一對(duì)，但都覺(jué)得對(duì)方比自己現(xiàn)在的伴侶好，這樣的情況絕不可能發(fā)生。

我們把用來(lái)解決某種問(wèn)題的一個(gè)策略，或者說(shuō)一個(gè)方案，或者說(shuō)一個(gè) 處理過(guò)程，或者說(shuō)一系列操作規(guī)則，或者更貼切的，一套計(jì)算方法，叫作“算法”（algorithm）。

上面這個(gè)用來(lái)尋找穩(wěn)定婚姻的策略就叫作“蓋爾–沙普利算法”（Gale-Shapley algorithm），有些人也管它叫“延遲認(rèn)可算法”（deferred acceptance algorithm）。

蓋爾–沙普利算法帶給我們很多啟發(fā)。作為一個(gè)為這些男女牽線(xiàn)的媒人，你并不需要親自使用這個(gè)算法來(lái)計(jì)算穩(wěn)定匹配，甚至根本不需要了解每個(gè)人的偏好，而只需按照這個(gè)算法組織一個(gè)男女配對(duì)活動(dòng)即可。你要做的僅僅是把算法流程當(dāng)作游戲規(guī)則告訴大家，游戲結(jié)束后會(huì)自動(dòng)得到一個(gè)大家都滿(mǎn)意的婚姻匹配。

整個(gè)算法可以簡(jiǎn)單地描述為：每個(gè)人都去做自己想做的事情。

對(duì)于男性來(lái)說(shuō)，從最喜歡的女子開(kāi)始追起是順理成章的事；對(duì)于女性來(lái)說(shuō)，不斷選擇最好的男子也正好符合她的利益。因此，大家會(huì)自動(dòng)遵守游戲規(guī)則，無(wú)須擔(dān)心有人虛報(bào)自己的偏好。?

歷史上，這樣的“配對(duì)游戲”還真有過(guò)實(shí)際應(yīng)用，并且更有意思的是， 這個(gè)算法的應(yīng)用居然比算法本身的提出還早 10 年。

早在 1952 年，美國(guó)就開(kāi)始用這種辦法給醫(yī)學(xué)院的學(xué)生安排工作，這被稱(chēng)為“全國(guó)住院醫(yī)師配對(duì)項(xiàng)目”。

配對(duì)的基本流程就是，各醫(yī)院從尚未拒絕這一職位的醫(yī)學(xué)院學(xué)生中 選出最佳人選并發(fā)送聘用通知，當(dāng)學(xué)生收到來(lái)自各醫(yī)院的聘用通知后，系統(tǒng)會(huì)根據(jù)他所填寫(xiě)的意愿表自動(dòng)將其分配到意愿最高的職位，并拒絕掉其他的職位。如此反復(fù)，直到每個(gè)學(xué)生都分配到了工作。

當(dāng)然，那時(shí)人們并不知道這樣的流程可以保證工作分配的穩(wěn)定性，只是憑直覺(jué)認(rèn)為這是很合理的。直到 10 年之后，蓋爾和沙普利才系統(tǒng)地研究了這個(gè)流程，提出了穩(wěn)定婚姻問(wèn)題，并證明了這個(gè)算法的正確性。

這套理論成功地解決了諸多市場(chǎng)資源配置問(wèn)題，羅伊德·沙普利也因此獲得了 2012 年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。很可惜，戴維·蓋爾沒(méi)能與他共享這一榮譽(yù)——他在 2008 年就已經(jīng)離開(kāi)人 世了。

蓋爾–沙普利算法還有很多有趣的性質(zhì)。比如說(shuō)，大家可能會(huì)想，這種男追女女拒男的方案對(duì)男性更有利還是對(duì)女性更有利呢？答案是，這種方案對(duì)男性更有利。

事實(shí)上，穩(wěn)定婚姻搭配往往不止一種，然而上述算法的結(jié)果可以保證，每一位男性得到的伴侶都是所有可能的穩(wěn)定婚姻搭配方案中最理想的，同時(shí)每一位女性得到的伴侶都是所有可能的穩(wěn)定婚姻搭配方案中最差的。受篇幅限制，我們略去證明的過(guò)程。

當(dāng)然，為了得到一種對(duì)女性最優(yōu)的穩(wěn)定婚姻搭配，我們只需要把整個(gè)算法反過(guò)來(lái)，讓女孩兒去追男孩兒，男孩兒拒絕女孩兒就行了。

這個(gè)算法還有一些局限性。例如，它無(wú)法處理 2𝑛 個(gè)人不分男女的穩(wěn)定搭配問(wèn)題。

一個(gè)簡(jiǎn)單的應(yīng)用場(chǎng)景便是宿舍分配問(wèn)題：假設(shè)每個(gè)宿舍住兩個(gè) 人，已知 2𝑛 個(gè)學(xué)生中每一個(gè)學(xué)生對(duì)其余 尋找一個(gè)穩(wěn)定的宿舍分配？此時(shí)，蓋爾 2𝑛 ? 1 個(gè)學(xué)生的偏好評(píng)價(jià)，如何 –沙普利算法就不再有用武之地了。

而事實(shí)上，宿舍分配問(wèn)題中很可能根本就不存在穩(wěn)定的搭配。例如，有 A、 B、C、D 四個(gè)人，其中 A 把 B 排在第一，B 把 C 排在第一，C 把 A 排在第 一，而且他們?nèi)硕及?D 排在最后。容易看出，此時(shí)一定不存在穩(wěn)定的宿舍分配方案。倘若 A、D 同宿舍，B、C 同宿舍，那么 C 會(huì)認(rèn)為 A 是更好的室友（因?yàn)?C 把 A 排在了第一），同時(shí) A 會(huì)認(rèn)為 C 是更好的室友（因?yàn)樗?把 D 排在了最后）。同理，B、D 同宿舍或者 C、D 同宿舍也都是不行的，因而穩(wěn)定的宿舍分配是不存在的。

此時(shí)，重新定義宿舍分配的優(yōu)劣性便是一個(gè)更為基本的問(wèn)題。穩(wěn)定婚姻問(wèn)題還有很多其他的變種，有些問(wèn)題至今仍然沒(méi)有一種有效的算法。這些問(wèn)題都是圖論當(dāng)中非常有趣的話(huà)題。

* 本文摘自《神機(jī)妙算：一本關(guān)于算法的閑書(shū)》一書(shū)，歡迎閱讀此書(shū)了解更多有關(guān)算法的內(nèi)容！

推薦閱讀

《神機(jī)妙算：一本關(guān)于算法的閑書(shū)》

顧森 著，蔡雪琴 繪

***粉絲福利時(shí)間***

評(píng)論區(qū)留言，點(diǎn)贊數(shù)超過(guò)60即可

按照留言質(zhì)量選擇前十可獲得此書(shū)！！！

以48個(gè)小時(shí)計(jì)！

注：若是在活動(dòng)截止日期后24小時(shí)內(nèi)無(wú)法取得用戶(hù)回復(fù)或聯(lián)系，將按照留言點(diǎn)贊排名順延。

總結(jié)

以上是生活随笔為你收集整理的【文末福利】图论算法：稳定婚姻问题，如何找到最适合自己的另一半的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。