資訊專欄INFORMATION COLUMN
摘要：今天是特殊節(jié)日，你化身為丘比特，來(lái)設(shè)計(jì)一個(gè)算法分配對(duì)象。延遲接受算法蓋爾沙普利算法，也被稱為延遲接受算法，簡(jiǎn)稱算法。結(jié)尾語(yǔ)最后回到標(biāo)題，對(duì)于愛(ài)情問(wèn)題，上面的蓋爾沙普利算法告訴我們一點(diǎn)主動(dòng)追求比被動(dòng)等待更有希望獲得幸福。
假設(shè)有三男（分別是 A ，B ，C ）和三女（分別是 x，y ，z ），他（她）們對(duì)異性的心儀程度如對(duì)話框所示。
比如對(duì)于男 A 來(lái)說(shuō)，心儀對(duì)象排名為 x 排第一，y 排第二，z 排第三。
今天是特殊節(jié)日，你化身為丘比特，來(lái)設(shè)計(jì)一個(gè)算法分配對(duì)象。
立即接受算法
下面以男生主動(dòng)追求對(duì)象為例來(lái)講解 立即接受算法。
一開(kāi)始男生們都去追求自己 最 心儀的女生，而女生們面對(duì)追求者們立刻做出決定確定對(duì)象（如果有多個(gè)追求者則選擇他們之前心儀程度更高的那個(gè)，只有一個(gè)的話那就只能選他）。
然后，被拒絕的男生們馬上再去追求第二心儀的女生，以此類推，直到配對(duì)完畢，如動(dòng)圖所示。
這樣做法有一個(gè)很嚴(yán)重的問(wèn)題：當(dāng)你被你的 No.1拒絕后，再去追求你的 No.2 的時(shí)候，你心中的 No.2 可能已經(jīng)在第一輪中選擇了其他人，比如男生 B 在第一輪去表白女生 x，表白失敗后想去追求 y，但女生 y 已經(jīng)和 C 在一起了，悲劇的是 y 眼中的真命天子正是一開(kāi)始沒(méi)來(lái)表白的男生 B。
最終的匹配情況如下圖所示。
雖然現(xiàn)在匹配結(jié)束出結(jié)果了，每個(gè)男生和女生都有對(duì)象，但是會(huì)出現(xiàn)以下情況。
對(duì)于男生 B 來(lái)說(shuō)，雖然他和女生 z 在一起，但其實(shí)他更期望和 y 在一起（注意 A 與 x 都是雙方的摯愛(ài)，拆不開(kāi)的）。
同時(shí)，對(duì)于女生 y 來(lái)說(shuō)，雖然她和男生 C 在一起，但其實(shí)她更期望和 B 在一起。
即男生 B 和女生 y 都更愿意離開(kāi)自己的現(xiàn)任對(duì)象而彼此在一起。
所以，使用立即接受算法匹配后的結(jié)果是一種不穩(wěn)定的狀態(tài)結(jié)果。
延遲接受算法“蓋爾-沙普利算法”（the Gale-Shapley algorithm），也被稱為“延遲接受算法”（deferred-acceptance algorithm），簡(jiǎn)稱“GS算法”。
目前該算法在 高中擇校系統(tǒng)、腎臟移植 等實(shí)際應(yīng)用上起到了巨大的作用，你甚至可以在 2012 年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)中看到它的身影。
這個(gè)算法一個(gè)核心之處在于，合意的要約不會(huì)立即被接受，而只是被“抓住”（hold on to），也就是“延遲接受”。
還是以男生主動(dòng)追求對(duì)象為例來(lái)講解 延遲接受算法。
首先每個(gè)男生在第一輪中向自己最心儀的女生表白，但是各位女生不用立即做決定，而是先 hold 住。
第一輪，男生 A 和男生 B 都跟女生 x 表白，女生 x 按捺激動(dòng)的心情，矜持沒(méi)有表態(tài)直接選男生 A，只是把男生 A 放入考察范圍
男生 C 跟女生 y 表白，女生 y 略顯失望，但把男生 C 放入了考察范圍。
第二輪，每個(gè)男生再向心中的 No.2 示愛(ài)。并且從第二輪開(kāi)始，每位女生們只保留自己到現(xiàn)在為止所收獲的最心儀的男生（但是不用答應(yīng)他，只hold在心里），而拒絕其他所有人。
而被拒絕的男生（也就是現(xiàn)在尚沒(méi)有女生 hold 你的男生）則繼續(xù)在下一輪中向心中排名的下一個(gè)女生表白。
以此類推，一輪輪繼續(xù)下去，直到所有想示愛(ài)的男生都示完為止。
最后，每個(gè)女生手里都有 hold 的對(duì)象。
使用 延遲接受算法 后，最終 A - x ，B - y ，C - z 在一起，并且在這 6 人中，你不可能找到一男一女符合以下條件：他（她）們都更愿意拋棄已有的對(duì)象而與彼此在一起。
使用 延遲接受算法 匹配后的結(jié)果是一種穩(wěn)定的狀態(tài)結(jié)果。
結(jié)尾語(yǔ)最后回到標(biāo)題，對(duì)于愛(ài)情問(wèn)題，上面的蓋爾-沙普利算法告訴我們一點(diǎn)：
主動(dòng)追求比被動(dòng)等待更有希望獲得幸福。
所以，如果你無(wú)法讓表白成為你勝利的號(hào)角，那倒在進(jìn)攻的沖鋒號(hào)上也未嘗不可。
如果你覺(jué)得該文章不錯(cuò)，不妨：
1、點(diǎn)贊，讓更多的人也能看到這篇內(nèi)容（收藏不點(diǎn)贊，都是耍流氓 -_-）
2、關(guān)注我，讓我們成為長(zhǎng)期關(guān)系
3、關(guān)注公眾號(hào)「五分鐘學(xué)算法」，里面已有 100 多篇算法類原創(chuàng)文章，歡迎各位的關(guān)注，第一時(shí)間閱讀我的文章。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/6749.html
摘要：本文會(huì)介紹位圖處理，矢量圖和圖像處理，重點(diǎn)是，并且最后會(huì)附上一個(gè)小應(yīng)用。以上列舉部分，更多備胎在此矢量圖處理講完位圖再說(shuō)矢量圖。矢量圖在繪制圖標(biāo)商業(yè)動(dòng)畫元素上應(yīng)用非常廣范。 計(jì)算機(jī)圖像處理是一門很成熟的技術(shù)，任何一門可操作系統(tǒng)接口的語(yǔ)言都能很輕易的實(shí)現(xiàn)各種處理操作。但是前端限于瀏覽器環(huán)境和接口限制，處理起來(lái)會(huì)有諸多不便，這里所說(shuō)的前端圖像處理，是真的指不借助任何后端服務(wù)純前端實(shí)現(xiàn)的圖像...
摘要：本文會(huì)介紹位圖處理，矢量圖和圖像處理，重點(diǎn)是，并且最后會(huì)附上一個(gè)小應(yīng)用。以上列舉部分，更多備胎在此矢量圖處理講完位圖再說(shuō)矢量圖。矢量圖在繪制圖標(biāo)商業(yè)動(dòng)畫元素上應(yīng)用非常廣范。 計(jì)算機(jī)圖像處理是一門很成熟的技術(shù)，任何一門可操作系統(tǒng)接口的語(yǔ)言都能很輕易的實(shí)現(xiàn)各種處理操作。但是前端限于瀏覽器環(huán)境和接口限制，處理起來(lái)會(huì)有諸多不便，這里所說(shuō)的前端圖像處理，是真的指不借助任何后端服務(wù)純前端實(shí)現(xiàn)的圖像...
摘要：小麗總是會(huì)在朋友圈發(fā)布自己的各種生活狀態(tài)?？偨Y(jié)我們從觀察者模式特點(diǎn)入手，通過(guò)一個(gè)案例，一步一步完善了觀察著的寫法，特點(diǎn)組后介紹了總已有的實(shí)現(xiàn)關(guān)注我，這里只有干貨同系列文章從未這么明白的設(shè)計(jì)模式一單例模式 showImg(https://segmentfault.com/img/remote/1460000018874501); 本文原創(chuàng)地址，我的博客：https://jsbintask...
摘要：引言今天我們來(lái)聊聊，隨著互聯(lián)網(wǎng)發(fā)展，這兩年前后端分離的開(kāi)發(fā)模式興起，也從以住的幕后走上了臺(tái)面，讓更多的人而得知，以前傳統(tǒng)的開(kāi)發(fā)方式大多局限在后端人員接觸較多一些。 showImg(https://segmentfault.com/img/bVbi8JE?w=1008&h=298); 引言 ? 今天我們來(lái)聊聊Mock，隨著互聯(lián)網(wǎng)發(fā)展，這兩年前后端分離的開(kāi)發(fā)模式興起，Mock也從以住的幕...
閱讀 1943·2021-11-25 09:43
閱讀 2175·2021-11-19 09:40
閱讀 3459·2021-11-18 13:12
閱讀 1770·2021-09-29 09:35
閱讀 699·2021-08-24 10:00
閱讀 2536·2019-08-30 15:55
閱讀 1740·2019-08-30 12:56
閱讀 1847·2019-08-28 17:59
