查看“稳定匹配”的源代码

{{#seo:
|keywords=稳定匹配,二分图,匹配问题
|description=图网络,图,网络科学
}}

在数学、经济学和计算机科学中，稳定匹配即为在两个大小相同且给定了每种元素的匹配喜好的元素集合中寻找稳定的匹配方案。匹配是从一个集合的元素到另外一个集合的元素的双射问题。如果有下列情况，匹配是不稳定的：
* 第一个匹配集合的元素A比第二个匹配集的某个给定元素B优先于已匹配A的元素。
* B也优于A，并且B已经与之匹配。

换句话说，当没有任何匹配（A，B），并且在当前的匹配情况下都喜欢对方，匹配是稳定的。

稳定的匹配问题（以婚姻匹配问题为例）定义如下：

给定n个男人，n个女人，每个人都按照喜好的顺序将所有异性成员排序，那么把这些男人和女人组合，没有任何两个异性会愿意喜欢对方（除了自己的配偶外），那么这样子的匹配就被认为是稳定的。

需要相互匹配两个类（例子中为男人和女人）的问题应该与稳定的室友问题区分开来。

==应用==

寻找稳定的匹配问题的解决方案在现实生活中有许多的应用。其中最著名的是给应届医学专业的学生匹配第一次医院的会诊。2012年， Lloyd S. Shapley和Alvin E. Roth凭借“稳定分配的理论的市场设计实践”而被授予以纪念Alfred Nobel的Sveriges Riksbank经济科学奖。

稳定匹配的一个大规模应用是为大型分布式网络服务分配用户。数十亿的用户访问网页、视频和其他网络服务，要求每个用户都与世界各地提供该项服务的数十万台服务器之一进行匹配。用户喜欢较近的服务器，因为可以提供更快的响应时间，所以每个用户对服务器的匹配都有优先排序。每个服务器都希望以最低的成本为用户提供服务，所以每个服务器匹配用户也有优先排序。内容分发网络（CDN）是分配内容和服务器的程序服务，每个几十秒就解决了用户和服务器之间这个庞大又复杂的稳定匹配问题，使得数十亿用户与各自的服务器相匹配，服务器可以提供用户所需要的网页、视频和其他内容。

==其他稳定匹配问题==

通常，可能存在许多不同的稳定匹配。例如，假设有三个男人（A，B，C）和三个女人（X，Y，Z）具有以下偏好：

*A：YXZ B：ZYX C：XZY  

*X：BAC Y：CBA Z：ACB

此匹配安排有三种稳定的解决方案：

* 男人得到第一选择，女人得到第三选择-（AY，BZ，CX）;

* 所有参与者都有他们的第二选择-（AX，BY，CZ）；

* 女人得到第一选择，男人得到第三选择-（AZ，BX，CY）。

这三者都是稳定的，因为不稳定代表双方都有更加喜欢的其他匹配对象。给定一个小组的第一选择确保匹配稳定因为他们会对其他任何提出的匹配方案不满意。通常，任何稳定匹配问题的解族都可以由优先分布格的结构提供，并且这种结构确保了解决稳定匹配问题算法的有效性。

在n个男人和n个女人的稳定匹配随机实例中，稳定匹配的平均数是渐近<math>e^{-1}n\ln n</math>的。在一个稳定匹配的例子中，选择最大化不同的稳定匹配的数量，这个数字是n的指数函数。

==算法的解决方案==


[[File:Gale-Shapley.gif|thumb|G-S算法]]

1962年，David Gale和Lloyd Shapley证明，无论男女人数相同，始终有可能解决SMP并使所有婚姻稳定下来。他们提出了一种算法，被命名为 Gale–Shapley算法，也被称为延迟接受算法，涉多次迭代。

* 第一次迭代时，首先a）每个未婚男子向他最喜欢的女人求婚，然后b）每个妇女对她最喜欢的求婚者“可能”回复，对所有其他求婚者“不”回复。然后，她暂时“与”到目前为止最喜欢的求婚者“订婚”，并且那个求婚者也同样暂时与她订婚。

* 在随后的每个回合中，首先a）每个未婚男士向尚未推荐的最喜欢的女人求婚（无论该女人是否已订婚），然后b）每个女人如果当前正在回答“可能”未订婚或如果她比现在的临时伴侣更喜欢这个男人（在这种情况下，她会拒绝当前未订婚的临时伴侣）。订婚的临时性质保留了已订婚妇女“更换”的权利。

* 重复此过程，直到每个人都被考虑到匹配中。

该算法保证在O(n^2)时间内所有参与者都能建立稳定的婚姻。其中n是男人或者女人的数量。

==乡村医院定理==

乡村医院定理涉及稳定匹配问题的一个更一般的变体，如在医生与医院职位匹配问题中的应用，与稳定婚姻问题的基本 n-to-n 形式有以下不同:

* 每个参与者可能只愿意与匹配另一侧的参与者子集进行匹配。

* 匹配项（医院）一侧的参与者可能具有数字能力，并指定了他们愿意雇用的医生数量。

* 一侧的参与者总数可能不等于另一侧要与之匹配的总容量。

* 结果匹配可能不匹配所有参与者。

在这种情况下，稳定性的条件是在匹配过程中，未匹配的配对会比彼此更喜欢对方（无论对方是对方还是不匹配）。在这种情况下，仍然会存在稳定的匹配，并且仍然可以通过Gale-Shapley算法找到它。

对于这种稳定的匹配问题，乡村医院定理指出：

* 在所有稳定的匹配中，分配的医生的集合以及每个医院的填补职位数量均相同。

* 任何在某些稳定匹配中具有空缺职位的医院，在所有稳定匹配中都将接收完全相同的一组医生。

==相关问题==

在稳定的室友问题是类似的稳定的婚姻问题，但所有参与者都属于一个池（而不是婚姻匹配中被分为“男”和“女”且人数相等）。

医院/居民的问题 -也被称为高校招生问题 -和稳定的婚姻问题不同之处在于医院可以采取多个居民，或大学可以录取多个学生。解决医院/居民问题的算法可以是面向医院的（如NRMP在1995年）或面向居民的。在Gale和Shapley的同一篇原始论文中，使用算法解决了这个问题，其中解决了稳定婚姻问题。

夫妇的医院/居民问题允许居民集中包括必须一起分配到同一家医院或夫妇选择的特定医院对的夫妇。

在分配问题试图找到一个加权匹配的二分图有最大重量。最大加权匹配不必一定要稳定，但是在某些应用中，最大加权匹配要比稳定匹配好。

合同的匹配问题也是一种，其中参与者与不同的合同进行匹配。合同的一个重要特殊情况是灵活的工资。

==参考==
* [https://en.wikipedia.org/wiki/Stable_marriage_problem 稳定匹配英文维基百科]
* [[网络科学导论]]. 汪小帆， 李翔， 陈关荣. 高等教育出版社, 2012. 133, 2012.



本中文词条由zq用户参与编译，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

[[category:旧词条迁移]]