稳定婚姻问题

✍ dations ◷ 2025-06-08 03:00:13 #组合数学,数学问题

在组合数学、经济学、计算机科学中,稳定婚姻问题(英语: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男:

相关

  • 痳疯树桐油树(学名:Jatropha curcas),又名麻风树、痳疯树、南洋油桐、黄肿树、假白榄等,为大戟科落叶灌木。其发源地在加勒比海的岛上,但葡萄牙商人把它引进了非洲和亚洲各地,现已分布在
  • 焦璐焦璐,唐朝官员。早年事迹不详。咸通九年(868年)官徐泗观察判官、副使。庞勋军抵达宿州(今安徽宿县)附近的符离(今安徽宿县北符离),与宿州大将乔翔五百余人战于虹县灵壁东的濉水,乔翔
  • 爪哇野牛爪哇野牛(学名:Bos javanicus),别名白臀野牛,牛的一种,生活在南亚和东南亚。体形似黄牛,肩高160厘米,体长230厘米,体重500-810公斤,尾长65-70厘米。臀部有一独特的、圆盘状白斑。和印度
  • 凯文·费吉凯文·费奇,PGA(英语:Kevin Feige,PGA,/ˌfaɪɡiː/; FY-ghee;1973年6月2日-)是一位美国男监制和漫威影业总裁。他制作的电影全球票房合计共超过140亿美元。并且在全美累计票房收
  • 十文字青十文字青(日语:十文字 青/じゅうもんじ あお ),是一位日本的轻小说家,出身于北海道北斗市,于北海道大学文学系毕业。笔名原为十神霙。
  • 细胞色素b5结构 / ECOD细胞色素b5(英语:Cytochrome b5)是一种存在于动物、植物、真菌以及紫色光养菌中遍及的电子传递血红素蛋白。该细胞色素于微粒体及线粒体中的变体是与膜相结合的,而细
  • 芬莱森芬莱森(芬兰语:Finlayson)是芬兰一家纺织品制造公司。该公司创立于1820年,当时苏格兰工程师詹姆斯·芬莱森(英语:James Finlayson (industrialist))在坦佩雷开设了一家棉布厂。公司
  • 日本职棒本垒打王日本职棒本垒打王为日本职棒成立以来,为表扬单季最多本垒打的选手,而设立的奖项。1936年到1949年为单一联盟时代,只表扬一位选手。1950年后,分为中央联盟与太平洋联盟,分开表扬各
  • 澳大利亚州花列表澳洲州花列表,澳洲各州及领地的花卉象征。
  • 自动化定理证明自动化定理证明(Automated theorem proving,简称ATP)目前是自动推理(Automated reasoning,简称AR)体系中发展最好的部分,它的目的是为使用电子计算机程序来进行数学定理的证明。对