易坊好文馆

  1. 首页 > 玩科技 >

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

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

什么是算法？
【方案|【文末福利】图论算法：稳定婚姻问题，如何找到最适合自己的另一半】>>>>
每当有人问我这样的问题 ， 我总会引用下面这个例子 。
假如你是一个媒人 ， 有若干名单身男子登门求助 ， 还有同样多的单身 女子也来征婚 。 如果你已经知道这些女孩儿在每个男孩儿心目中的排名 ， 以及男孩儿们在每个女孩儿心目中的排名 ， 那么你该怎样为他们牵线配对呢？
最好的配对方案当然是 ， 每个人的另一半正好都是自己的“第一选择” 。
这当然很完美 ， 但绝大多数情况下都不可能实现 。
比方说 ， 男 1 号的最爱是女 1 号 ， 而女 1 号的最爱不是男 1 号 ， 这两个人的最佳选择就不可能被同时满足 。 如果出现了好几位男士的最爱是同一个女孩儿的情况 ， 这几位男士的首选也不会同时得到满足 。
当这种最为理想的配对方案无法实现时 ，怎样的配对方案才能令人满意呢？
其实 ， 找对象不见得需要那么完美 ， 和谐才是关键 。
如果男 1 号和女 1 号各有各的对象 ， 但男 1 号觉得女 1 号比自己的现任更好 ， 女 1 号也觉得对方比自己的现任更好 ， 那么两人就可能扔下自己现在的另一半 ， 走在一起——因为这个结果对他们两人都更好一些 。
如果在一种男女配对方案中出现了这种情况 ， 我们就说这种配对方案是不稳定的 。 作为一个红娘 ， 你深深地知道 ， 介绍对象就怕婚姻关系不稳定 。 因此 ， 在给客户牵线配对时 ， 虽然不能让每个人都得到最合适的 ， 但婚姻搭配必须得是稳定的 。
现在 ， 我们的问题就是：稳定的婚姻搭配总是存在的吗？如果存在 ， 又应该怎样寻找出一个稳定的婚姻搭配？
为了便于分析 ， 下面我们做一些约定 。 我们用字母 A、B、C 对男性进行编号 ， 用数字 1、2、3 对女性进行编号 。 我们把所有男性从上到下列在左侧 ， 括号里的数字表示每个人心目中对所有女性的排名；再把所有女性列在右侧 ， 用括号里的字母表示她们对各位男性的偏好 。
图 1 所示就是有 2 男 2 女的一种情形 ， 每个男的都更喜欢女 1 号 ， 但女 1 号更喜欢男 B ， 女 2 号更喜欢男 A 。 若按 A—1、B—2 进行搭配 ， 则男 B 和女 1 都更喜欢对方一些 ， 这样的婚姻搭配显然是不稳定的 。 但若换一种搭配方案（如图 2 所 示） ， 这样的搭配就是稳定的了 。
图 1 一个不稳定的婚姻搭配（男 B 和女 1 都不满意现任伴侣）
图 2 一个稳定的婚姻搭配
可能很多人会立即想到一种寻找稳定婚姻搭配的策略：不断修补当前搭配方案 。 如果两个人互相之间都觉得对方比自己当前的伴侣更好 ， 那就让这两个人成为一对 ， 刚刚被甩的那两个人组成一对 。 如果还有想要在一起的男女对 ， 就继续按照他们的愿望对换情侣 ， 直到最终消除所有的不稳定组合 。

推荐阅读


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

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