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