稳定婚姻问题

✍ dations ◷ 2025-05-10 11:10:39 #组合数学,数学问题

在组合数学、经济学、计算机科学中,稳定婚姻问题(英语:stable marriage problem,简称SMP)又称为稳定配对问题(stable matching problem),是指在两组同样大小的元素集合中(例如集合1是男子组、集合2是女子组,而他们各有偏好),寻求一个稳定配对组合所遇到的问题。一个组合在以下情况下并不稳定:

在集合1中有一个元素A更偏好于集合2的一些元素B,但元素A已被配对;而元素B亦更偏好于元素A多于配对给他的元素。在男女婚姻的角度来说,可以写成一名男子A获安排与女子D结婚,但A实际上是更喜欢女子B的。反之,女子B亦被安排与男子C结婚,但B实际上也是更喜欢A的。

简单来说,一个稳定的组合是指在任何一个组合中(含A及B),每一个元素都是最偏好目前的组合多于任何其他的元素。亦即是说,稳定婚姻配对是指在同等数量男女当中,每一名男子皆能与自己最喜欢的女子结婚,反之亦然。然而,这个配对方式却引来不少难题。

1962年David Gale和Lloyd Shapley提出了Gale–Shapley算法,这个系统可以确保如果男子组跟女子组的成员数皆相同(即N男N女)中,每一名男子和女子都能找到一名伴侣,以及每个婚姻都是稳定的。

假设在n男n女中的存在两对夫妇(M, W)和(m, w),M男对w女喜好度大于现任妻子W女,并且w女对M男喜好度也大于现任丈夫m男:

相关

  • 分子遗传学分子遗传学(英语:Molecular genetics)是生物学中的一个领域,专门在分子层次下研究遗传学,这一学门使用许多分子生物学与遗传学的研究方法 。对生物体染色体和基因表达的研究可以
  • 腹足类见内文腹足纲(学名:Gastropoda)是软体动物门中重要的组成部分,包括通常所说的蜗牛、海螺和蛞蝓,也是当中最大的纲,约6.5万到8万个物种。腹足纲是动物中仅次于昆虫纲(Insecta)的第二
  • 迁都迁都是指一个国家把首都或行政中心从某城市迁至另一城市。古代由于政治环境的不稳定、以及迁都成本远低于现代,因此迁都事件比较多见,例如中国历史上就曾多次迁都。迁都通常基
  • 第一届联邦国会第1届美国国会是美国国会第一次召开,任期由1789年3月4日至1791年3月4日,也是乔治·华盛顿总统第一个任期的前两年。国会原在纽约市的联邦厅(现联邦国家纪念堂)集会,然后搬到费城
  • 肌醇单磷酸酶肌醇单磷酸酶(英语:Inositol monophosphatase,EC 3.1.3.25)是一种存在于所有细胞中的酶并被认为是双相障碍中的关键点。卡巴咪嗪在临床中备用作为一种肌醇单磷酸酶抑制剂。此酶
  • 天空天空是大气层或太空可被天体表面的观测者看到的部分。在地球,晴朗的日间,天空看起来是蓝色的。在日出和日落时,天空会偏红色,但其实天空是无色的。对晴朗天空的能见度一般用视觉
  • 孤独中的恐惧《孤独中的恐惧》(Fears in Solitude)是塞缪尔·泰勒·柯勒律治于1798年4月所作的一首对话诗,写于法国威胁要入侵英国之时。尽管柯勒律治反对英国政府,这首诗还是站在英国人民的
  • 袁钧英袁钧瑛(1958年10月3日-)著名华裔分子生物学家。哈佛医学院教授。袁钧瑛以研究细胞凋亡的分子机理而闻名世界。1958年出生在中国上海,其外祖父是著名法国文学翻译家李青崖,祖父是
  • 溥植正蓝旗总族长(光绪三十年~?年)奉恩镇国公溥植(1882年7月4日-1936年5月23日),奉恩将军载鹤第一子,母妻佟佳氏,其父为佟玉赉,履亲王系第八代。他在光绪八年五月(1882年)出生,光绪十一年四月(1
  • 凌宁凌宁 (英语:Gilbert Ning Ling, 1919年12月26日-)是一位美籍华人分子生物学家,分子物理学家,细胞生物学家。1919年出生在江苏南京,成长于北京。考入国立中央大学畜牧专业,后来转系