易坊好文馆

  1. 首页 > 玩科技 >

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

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


当然 ， 那时人们并不知道这样的流程可以保证工作分配的稳定性 ， 只是凭直觉认为这是很合理的 。 直到 10 年之后 ， 盖尔和沙普利才系统地研究了这个流程 ， 提出了稳定婚姻问题 ， 并证明了这个算法的正确性 。
这套理论成功地解决了诸多市场资源配置问题 ， 罗伊德·沙普利也因此获得了 2012 年诺贝尔经济学奖 。 很可惜 ， 戴维·盖尔没能与他共享这一荣誉——他在 2008 年就已经离开人 世了 。
盖尔–沙普利算法还有很多有趣的性质 。 比如说 ， 大家可能会想 ， 这种男追女女拒男的方案对男性更有利还是对女性更有利呢？答案是 ，这种方案对男性更有利 。
事实上 ， 稳定婚姻搭配往往不止一种 ， 然而上述算法的结果可以保证 ， 每一位男性得到的伴侣都是所有可能的稳定婚姻搭配方案中最理想的 ， 同时每一位女性得到的伴侣都是所有可能的稳定婚姻搭配方案中最差的 。 受篇幅限制 ， 我们略去证明的过程 。
当然 ， 为了得到一种对女性最优的稳定婚姻搭配 ， 我们只需要把整个算法反过来 ， 让女孩儿去追男孩儿 ， 男孩儿拒绝女孩儿就行了 。
这个算法还有一些 局限性 。 例如 ， 它无法处理 2?? 个人不分男女的稳定搭配问题 。
一个简单的应用场景便是宿舍分配问题：假设每个宿舍住两个 人 ， 已知 2?? 个学生中每一个学生对其余 寻找一个稳定的宿舍分配？此时 ， 盖尔 2?? ? 1 个学生的偏好评价 ， 如何 –沙普利算法就不再有用武之地了 。
而事实上 ， 宿舍分配问题中很可能根本就不存在稳定的搭配 。 例如 ， 有 A、 B、C、D 四个人 ， 其中 A 把 B 排在第一 ， B 把 C 排在第一 ， C 把 A 排在第 一 ， 而且他们三人都把 D 排在最后 。 容易看出 ， 此时一定不存在稳定的宿舍分配方案 。 倘若 A、D 同宿舍 ， B、C 同宿舍 ， 那么 C 会认为 A 是更好的室友（因为 C 把 A 排在了第一） ， 同时 A 会认为 C 是更好的室友（因为他 把 D 排在了最后） 。 同理 ， B、D 同宿舍或者 C、D 同宿舍也都是不行的 ， 因而稳定的宿舍分配是不存在的 。
此时 ， 重新定义宿舍分配的优劣性便是一个更为基本的问题 。 稳定婚姻问题还有很多其他的变种 ， 有些问题至今仍然没有一种有效的算法 。 这些问题都是图论当中非常有趣的话题 。
* 本文摘自 《神机妙算：一本关于算法的闲书》一书 ， 欢迎阅读此书了解更多有关算法的内容！
推荐阅读

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

《神机妙算：一本关于算法的闲书》
顾森 著 ， 蔡雪琴 绘
***粉丝福利时间***

推荐阅读


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

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