易坊好文馆

  1. 首页 > 玩科技 >

方案|【文末福利】图论算法：稳定婚姻问题，如何找到最适合自己的另一半( 三 )

算法 方案 策略 女子 单身 男士 婚姻 文末 追求者 Gale


不会 。
下面我们将说明 ， 随着轮数的增加 ， 总有一个时候所有人都能配上对 。
由于在每一轮中 ， 至少会有一个男士向某个女子告白 ， 因此总的告白次数将随着轮数的增加而增加 。 倘若整个流程一直没有因所有人都配上对而结束 ， 最终必然会出现某个男子追遍了所有女孩儿的情况 。 而一个女孩儿只要被人追过一次 ， 以后就不可能再单身了 。 既然所有女孩儿都被这个男人追过 ， 就说明所有女孩儿现在都不是单身 ， 也就是说此时所有人都配上对了 。
接下来 ， 我们还需要证明 ， 这样得出的配对方案确实是稳定的 。
首先注意到 ， 随着轮数的增加 ， 一个男人追求的对象总是越来越糟 ， 而一个女孩儿的男友只可能变得越来越好 。 假设男 A 和女 1 各自有各自的对象 ， 但比起现在的对象来 ， 男 A 更喜欢女 1 。
因此 ， 在此之前男 A 肯定已经跟女 1 表白过 。 既然女 1 最后没有跟男 A 在一起 ， 说明女 1 拒绝了男 A ， 也就是说她有了比男 A 更好的男人 。 这就证明了 ， 两个人虽然不是一对 ， 但都觉得对方比自己现在的伴侣好 ， 这样的情况绝不可能发生 。
我们把用来解决某种问题的一个策略 ， 或者说一个方案 ， 或者说一个 处理过程 ， 或者说一系列操作规则 ， 或者更贴切的 ， 一套计算方法 ， 叫作 “算法”（algorithm） 。
上面这个用来寻找稳定婚姻的策略就叫作 “盖尔–沙普利算法”（Gale-Shapley algorithm） ， 有些人也管它叫“延迟认可算法”（deferred acceptance algorithm） 。
盖尔–沙普利算法带给我们很多启发 。 作为一个为这些男女牵线的媒人 ， 你并不需要亲自使用这个算法来计算稳定匹配 ， 甚至根本不需要了解每个人的偏好 ， 而只需按照这个算法组织一个男女配对活动即可 。 你要做的仅仅是把算法流程当作游戏规则告诉大家 ， 游戏结束后会自动得到一个大家都满意的婚姻匹配 。
整个算法可以简单地描述为： 每个人都去做自己想做的事情 。
对于男性来说 ， 从最喜欢的女子开始追起是顺理成章的事；对于女性来说 ， 不断选择最好的男子也正好符合她的利益 。 因此 ， 大家会自动遵守游戏规则 ， 无须担心有人虚报自己的偏好 。
历史上 ， 这样的“配对游戏”还真有过实际应用 ， 并且更有意思的是 ，这个算法的应用居然比算法本身的提出还早 10 年 。
早在 1952 年 ， 美国就开始用这种办法给医学院的学生安排工作 ， 这被称为“全国住院医师配对项目” 。
配对的基本流程就是 ， 各医院从尚未拒绝这一职位的医学院学生中 选出最佳人选并发送聘用通知 ， 当学生收到来自各医院的聘用通知后 ， 系统会根据他所填写的意愿表自动将其分配到意愿最高的职位 ， 并拒绝掉其他的职位 。 如此反复 ， 直到每个学生都分配到了工作 。

推荐阅读


上一篇：半导体|小米 15 亿在上海成立新公司，经营范围含集成电路芯片设计

下一篇：图书|图书防盗磁条 图书馆防盗标签 书店防盗磁条贴 钴基图书防盗磁条