“稳定婚姻算法”雨夜谈M/N资源匹配问题

连续数月的阴雨绵绵&＃xff0c;江南烟雨似乎没有停止的迹象&＃xff0c;近日又迎来了下半年目前为止最猛烈的寒潮&＃xff0c;无论哪一个都是我超级期待和喜欢的&＃xff0c;这样的天气&＃xff0c;不适合睡觉。

一个很不错的算法&＃xff0c;稳定婚姻算法。

先给出一个概念&＃xff0c;来自百度百科&＃xff1a;
稳定婚姻问题&＃xff1a;https://baike.baidu.com/item/稳定婚姻问题/12760040

再给出一篇博客链接&＃xff1a;
什么是算法&＃xff1a;如何寻找稳定的婚姻搭配&＃xff1a;http://www.matrix67.com/blog/archives/2976

这个话题起源于一次相亲活动&＃xff0c;最终落实到了一个算法。算法简要记述如下&＃xff1a;

初始&＃xff1a;两个单身集合&＃xff1a;男-M&＃xff0c;女-F
算法过程&＃xff1a;while M非空m &＃61; M取出一个f &＃61; 未拒绝过m的F集合中自己最心仪的if f是单身 f嫁给mm从M集合移除elseif f比现有丈夫m&＃39;更喜欢mf和m&＃39;离婚f重新嫁给mm&＃39;进入单身集合Melsem重新进入单身集合Mend-ifend-ifend-while


算法本身本文不再赘述&＃xff0c;本文聊一些不那么技术的东西&＃xff0c;来看看这个稳定婚姻匹配算法都用在什么场合。

名字说是 稳定婚姻算法&＃xff0c;但实际上&＃xff0c;这个算法 最不适用 的场景就是配婚的场景&＃xff0c;或者说&＃xff0c;真正的婚姻可能一辈子都在实施这个算法&＃xff0c;而不是在配婚的当时。至少可以肯定的是&＃xff0c;婚姻完全是一个超级复杂的话题&＃xff0c;不可能用算术加加减减就能理清的…

这个算法有点名不符实了。

本质上&＃xff0c;这个名不符实的算法是一个 m对n的资源/用户配对 算法。典型的场景就是房产中介&＃xff0c;互联网公司猎头&＃xff0c;GSLB&＃xff0c;推荐系统等。

• 房产中介
  如果M集合为一群要买房子的人&＃xff0c;F集合为一堆房子资源&＃xff0c;那么m对f的心仪程度要综合考虑是否学区方&＃xff0c;价格是否够低&＃xff0c;周边配套设施等。
  如果M集合是一堆房子资源&＃xff0c;F集合是一群要买房子的人&＃xff0c;那么m对f的心仪程度则变成了是否能承受高价&＃xff0c;付款是否快&＃xff0c;是否全款等。
  房产中介作为算法的实施者&＃xff0c;最终需要将房子卖给最适合的人&＃xff0c;同时为找房子的人找到合适的房子。

• 互联网公司猎头
  为什么要加上定语“互联网公司”&＃xff1f;因为这个行业存在大量的公司&＃xff0c;同时存在大量时刻蠢蠢欲动的从业人员&＃xff0c;每年都会有固定的几个月&＃xff0c;海量的从业人员在海量的公司之间大洗牌&＃xff0c;这个时候&＃xff0c;猎头就要实施稳定婚姻算法了。具体就不描述了。

• GSLB
  随着CDN的逐渐流行&＃xff0c;当你访问一个站点的时候&＃xff0c;为你提供服务的已经不再是那唯一的源站或者运行着反向代理负载均衡的源站了&＃xff0c;而是离你最近的CDN节点&＃xff01;
  那么&＃xff0c;如果和来自各地的访问不同资源的请求在分布于各地的CDN节点中分配一个最适合它的&＃xff0c;就需要DNS服务去实施稳定婚姻算法了&＃xff0c;当然这里面可能是一个双向实施的过程&＃xff0c;即既要为用户请求分配一个最适合的CDN节点&＃xff0c;也要为CDN节点受理一个最合适的请求。

• 推荐系统
  这个比较有意思。以广告投放为例。
  大量的商品如何精准对应大量的人群的用户画像集合&＃xff0c;这就需要推荐系统运行实施稳定婚姻算法了。
  当然&＃xff0c;推荐系统本身复杂得很&＃xff0c;不仅仅是一个稳定婚姻算法就能覆盖的

• …

事实上&＃xff0c;只要是m对n的匹配系统&＃xff0c;均可以用稳定婚姻算法来求最优解&＃xff0c;这个和1对n的系统是不同的。我来简单说明一下。

1对n系统&＃xff0c;典型就是LVS负载均衡&＃xff0c;当一个请求来到时&＃xff0c;显而易见&＃xff0c;需要在n个服务器中选择一个最适合的&＃xff0c;算法就结束了。然而如果同时来了m个请求&＃xff0c;就不能这么简单了&＃xff0c;我们为这m个请求中的其中1个请求假设为c1&＃xff0c;按照负载均衡算法分配了一台服务器k&＃xff0c;但是k是不是更适合服务另一个请求c2呢&＃xff1f;这就是一个问题&＃xff0c;所以为c1这个请求分配服务器的过程并没有就此结束&＃xff0c;c1只是 暂时 和k配成了对&＃xff0c;搞不好最终的结果会推翻这个结论&＃xff0c;让c2和k配成一对。

这里要解释的一点是&＃xff0c;如果k已经许给了c1&＃xff0c;那么k为什么不能再许给c2呢&＃xff1f;并不是因为这可能会增加k的负载&＃xff0c;构成一个非最优的匹配&＃xff0c;而是因为 k许给了c1这件事会改变系统的稳定性。

所以&＃xff0c;m对n的匹配系统必须执行某种程度的 双向匹配 机制&＃xff0c;但是匹配的过程必然是按照某种顺序在进行&＃xff0c;每一轮的过程必然会沉淀下来一定的稳定组合&＃xff0c;所以 必然存在匹配集合双方一方越来越高概率匹配到更好的&＃xff0c;而另一方则越来越高概率匹配到更差的 。因此&＃xff0c;没有什么所谓的双向选择机制是 完全对等 的&＃xff01;这可以很好的解释甲方和乙方的非对等性。

一直在下雨&＃xff0c;非常爽&＃xff01;有几多皮鞋?进水湿&＃xff0c;更有几多皮鞋进水胖&＃xff1f;
浙江温州皮鞋湿&＃xff0c;下雨进水不会胖&＃xff01;