稳定婚姻问题

✍ dations ◷ 2025-04-04 11:19:38 #组合数学,数学问题

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

相关

  • 图像式思考辅助工具图像式思考辅助工具是一种将知识、概念或构思表利用视觉方式表达出来的方法,主要用于脑力激荡法(brainstorming)过程中,将各人的思想记录下来,以便将来向其他人重新覆述各人的思
  • 张干琦张干琦(1961年-)是台湾摄影师,英文名为Chien-Chi Chang,也是台湾唯一马格兰摄影通讯社的会员,已加入美国国籍。他最具代表性的作品是名为《The Chain》的摄影画册,内容是在一家台湾
  • 陆缘海缘海、陆陆缘海或称边陆缘海(英语:Marginal Sea)指的是大海的四周大部分是由半岛、岛屿或者陆地所环绕的大海;名称差异为陆缘海是地球科学名词,陆陆缘海是地质学名词,边陆缘海是海
  • 双三角锥在几何学中,双三角锥是一种基底为三角形的双锥体,其为三角柱的对偶。若每个面皆为正三角形,则为92种Johnson多面体(J12)中的其中一个,也是双角锥的其中一种。顾名思义,它可由正多面
  • 阿尔文·汉森阿尔文·哈维·汉森(英语:Alvin Harvey Hansen,1887年8月23日-1975年6月6日),又译为阿尔文·韩森,生于美国南达科他州维堡(Viborg),哈佛大学经济学教授,是美国最早开始倡导凯思斯经济学
  • 英国足球性侵丑闻英国足球性侵丑闻是从2016年11月中旬,已经退役的的职业足球运动员公开在1970、1980、1990年代,曾经被前足球教练虐待儿童的性虐待事件并进行了公开谈话。这导致了指控进一步的
  • 白喇叭杜鹃白喇叭杜鹃(学名:)为杜鹃花科杜鹃属下的一个种。
  • NGC 2510NGC 2510是位于小犬座的一个星系。它的赤经为 8h 2.2m,赤纬为 9° 29′。
  • 西丽玛沃·班达拉奈克西丽玛沃·拉特瓦特·迪亚斯·班达拉奈克(Sirimavo Ratwatte Dias Bandaranaike,僧伽罗语:සිරිමාවෝ රත්වත්තේ ඩයස් බණ්ඩාරනායක,泰米尔语:சிறி
  • 粉褶菌科见内文粉褶菌科(Entolomataceae)是担子菌门下伞菌目的一科。