稳定婚姻问题

来自计算思维百科
跳转至: 导航搜索
稳定婚姻问题.jpg

稳定婚姻问题指的是一定数量的男士按照自己的喜好程度对相同数量的女士进行排序,然后进行配对形成稳定婚姻关系。这种配对关系对双方都是比较满意的。

基本概念

为了介绍稳定婚姻问题中的“稳定”的意思,我们先介绍一下什么是“不稳定”:在当前所有匹配中存在A男士和B女士,他们没有配对,但是比起当前的伴侣,他们更加喜欢对方。不存在这种情况的配对就是稳定婚姻。稳定婚姻问题就是要根据给定的男士和女士的优先选择,求出一个稳定的婚姻匹配。

例如,男士有小王、小李、小赵,女士有翠花、舒敏、月儿,下面是他们各自对异性的喜好排序情况,求出一个稳定婚姻匹配。

男士:

 

第一

第二

第三

小王

舒敏

翠花

月儿

小李

舒敏

月儿

翠花

小赵

月儿

舒敏

翠花

女士:

 

第一

第二

第三

翠花

小李

小赵

小王

舒敏

小赵

小王

小李

月儿

小李

小赵

小王

解决步骤如下:

1)自由男士:小王、小李、小赵

小王向舒敏求婚,舒敏接受(小王、舒敏配对);

 

第一

第二

第三

小王

舒敏

翠花

月儿

小李

舒敏

月儿

翠花

小赵

月儿

舒敏

翠花

2)自由男士:小李、小赵

小李向舒敏求婚,比起小李,舒敏更加喜欢小王,舒敏拒绝;

 

第一

第二

第三

舒敏

小赵

小王

小李

3)自由男士:小李、小赵

小李向月儿求婚,月儿接受(小李、月儿配对)

 

第一

第二

第三

小王

舒敏

翠花

月儿

小李

舒敏

月儿

翠花

小赵

月儿

舒敏

翠花

4)自由男士:小赵

小赵向月儿求婚,比起小赵,月儿更喜欢小李,月儿拒绝;

 

第一

第二

第三

月儿

小李

小赵

小王

5)小赵向舒敏求婚,比起小王,舒敏更喜欢小赵,所以舒敏抛弃小王,跟小赵配对(小赵、舒敏配对);

 

 

第一

第二

第三

小王

舒敏

翠花

月儿

小李

舒敏

月儿

翠花

小赵

月儿

舒敏

翠花

6)自由男士:小王

小王向翠花求婚,翠花接受(小王、翠花配对)。

 

第一

第二

第三

小王

舒敏

翠花

月儿

小李

舒敏

月儿

翠花

小赵

月儿

舒敏

翠花

应用范围

稳定婚姻问题代表一类分配问题,例如产品与客户、公司与应聘者,可以最大程度的满足双方需要。

使用方法及步骤

步骤一:从自由男士中选择一个,向他的优先列表中的没有拒绝过他且优先权最高的女士求婚,如果该女士未配对,则接受,如果该女士已配对,则女士比较该自由男士和当前与她配对的男士的优先权,选择优先权高的男士;

步骤二:继续下一次配对。

应用案例

应用1-实习医院分配

案例:明明、荣荣和天天准备去医院实习,目前有三家医院,人民医院、解放军医院和中医院,双方之间的优先权列表如下,那么该怎样分配才能使得双方都满意?

 

第一

第二

第三

明明

人民

解放

荣荣

人民

人民

天天

解放

人民

 

第一

第二

第三

人民

荣荣

天天

明明

解放

明明

天天

荣荣

天天

荣荣

明明

解决步骤:

1)明明向人民医院提出申请,人民医院接受;

2)荣荣向人民医院提出申请,人民医院更喜欢荣荣,拒绝明明,接受荣荣;

3)明明向解放医院提出申请,解放医院接受;

4)天天向中医院提出申请,中医院接受。

应用2-宿舍安排

案例:宿舍人员安排,每个人都想和自己更喜欢的人一起住,那么怎样进行宿舍安排以满足大多数人的要求?

解决步骤: 与上个例子相同

可以体现的计算思维

在解决实际问题时,常常需要在多个因素中进行权衡,这种就是能够调和各方面的因素,使问题得到可以接受的解。稳定婚姻问题体现的是计算思维中的“优化”特点。