“穩定婚姻演算法”雨夜談-M/N資源匹配問題
連續數月的陰雨綿綿，江南煙雨似乎沒有停止的跡象，近日又迎來了下半年目前為止最猛烈的寒潮，無論哪一個都是我超級期待和喜歡的，這樣的天氣，不適合睡覺。
一個很不錯的演算法， 穩定婚姻演算法 。
先給出一個概念，來自百度百科：
穩定婚姻問題 ：ofollow,noindex" target="_blank">https://baike.baidu.com/item/穩定婚姻問題/12760040
再給出一篇部落格連結：
什麼是演算法：如何尋找穩定的婚姻搭配 ：http://www.matrix67.com/blog/archives/2976
這個話題起源於一次相親活動，最終落實到了一個演算法。演算法簡要記述如下：
初始：兩個單身集合：男-M，女-F 演算法過程： whileM非空 m = M取出一個 f = 未拒絕過m的F集合中自己最心儀的 if f是單身 f嫁給m m從M集合移除 else if f比現有丈夫m'更喜歡m f和m'離婚 f重新嫁給m m'進入單身集合M else m重新進入單身集合M end-if end-if end-while
演算法本身本文不再贅述，本文聊一些不那麼技術的東西，來看看這個穩定婚姻匹配演算法都用在什麼場合。
名字說是 穩定婚姻演算法 ，但實際上，這個演算法 最不適用 的場景就是配婚的場景，或者說，真正的婚姻可能一輩子都在實施這個演算法，而不是在配婚的當時。至少可以肯定的是，婚姻完全是一個超級複雜的話題，不可能用算術加加減減就能理清的…
這個演算法有點名不符實了。
本質上，這個名不符實的演算法是一個 m對n的資源/使用者配對 演算法。典型的場景就是房產中介，網際網路公司獵頭，GSLB，推薦系統等。
-
房產中介
如果M集合為一群要買房子的人，F集合為一堆房子資源，那麼m對f的心儀程度要綜合考慮是否學區方，價格是否夠低，周邊配套設施等。
如果M集合是一堆房子資源，F集合是一群要買房子的人，那麼m對f的心儀程度則變成了是否能承受高價，付款是否快，是否全款等。
房產中介作為演算法的實施者，最終需要將房子賣給最適合的人，同時為找房子的人找到合適的房子。
-
網際網路公司獵頭
為什麼要加上定語“網際網路公司”？因為這個行業存在大量的公司，同時存在大量時刻蠢蠢欲動的從業人員，每年都會有固定的幾個月，海量的從業人員在海量的公司之間大洗牌，這個時候，獵頭就要實施穩定婚姻演算法了。具體就不描述了。
-
GSLB
隨著CDN的逐漸流行，當你訪問一個站點的時候，為你提供服務的已經不再是那唯一的源站或者執行著反向代理負載均衡的源站了，而是離你最近的CDN節點！
那麼，如果和來自各地的訪問不同資源的請求在分佈於各地的CDN節點中分配一個最適合它的，就需要DNS服務去實施穩定婚姻演算法了，當然這裡面可能是一個雙向實施的過程，即既要為使用者請求分配一個最適合的CDN節點，也要為CDN節點受理一個最合適的請求。
-
推薦系統
這個比較有意思。以廣告投放為例。
大量的商品如何精準對應大量的人群，這就需要推薦系統執行實施穩定婚姻演算法了。
當然，推薦系統本身複雜得很，不僅僅是一個穩定婚姻演算法就能覆蓋的
-
…
事實上，只要是m對n的匹配系統，均可以用穩定婚姻演算法來求最優解，這個和1對n的系統是不同的。我來簡單說明一下。
1對n系統，典型就是LVS負載均衡，當一個請求來到時，顯而易見，需要在n個伺服器中選擇一個最適合的，演算法就結束了。然而如果同時來了m個請求，就不能這麼簡單了，我們為這m個請求中的其中1個請求假設為c1，按照負載均衡演算法分配了一臺伺服器k，但是k是不是更適合服務另一個請求c2呢？這就是一個問題，所以為c1這個請求分配伺服器的過程並沒有就此結束，c1只是 暫時 和k配成了對，搞不好最終的結果會推翻這個結論，讓c2和k配成一對。
這裡要解釋的一點是，如果k已經許給了c1，那麼k為什麼不能再許給c2呢？並不是因為這可能會增加k的負載，構成一個非最優的匹配，而是因為 k許給了c1這件事會改變系統的穩定性 。
所以，m對n的匹配系統必須執行某種程度的 雙向匹配 機制，但是匹配的過程必然是按照某種順序在進行，每一輪的過程必然會沉澱下來一定的穩定組合，所以 必然存在匹配集合雙方一方越來越高概率匹配到更好的，而另一方則越來越高概率匹配到更差的 。因此，沒有什麼所謂的雙向選擇機制是 完全對等 的！這可以很好的解釋甲方和乙方的非對等性。
一直在下雨，非常爽！有幾多皮鞋:mans_shoe:進水溼，更有幾多皮鞋進水胖？
浙江溫州皮鞋溼，下雨進水不會胖！