问题描述
“稳定婚姻问题”在生活中是一个典型的问题,通俗地可叙述为:当前有N位男生和N位女生最后要组成稳定的婚姻家庭,过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序.然后开始选择自己的对象,其规则是:男生第一天均向各自最喜欢的女生写一封“情书”。
算法概述
1962年，美国数学家David Gale和Lloyd Shapley发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。 先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作： 1 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士； 2 每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。 3 若某男士被其女友抛弃，重新变成自由男； 4 重复以上过程直到没有求婚发生。
代码如下
# -*- coding: utf-8 -*-
"""
Created on Fri Aug 28 08:43:33 2020
@author: ljc545w
"""
def find_stable_matching(man_preferences,woman_preferences):
#初始将每个人的自由状况设定为True
length = len(man_preferences)
is_man_free = [True] * length
is_woman_free = [True] * length
#初始化互动状况，刚开始时没有任何互动
isManProposed = [[False for i in range(length)] for j in range(length)]
#初始化牵手列表
match = [(-1,-1)] * length
#当还有男嘉宾是单身时就持续循环
while True in is_man_free:
#获取男嘉宾的牌号
indexM = is_man_free.index(True)
#如果男嘉宾还有未曾互动过的女嘉宾（以男嘉宾心中排行为序）
if False in isManProposed[indexM]:
#初始化女嘉宾牌号
indexW = -1
#查找未曾互动的女嘉宾中最中意的那一个
for i in range(length):
w = man_preferences[indexM][i]
if isManProposed[indexM][w] is False:
#选定女嘉宾牌号
indexW = w
#找到以后跳出循环
break
#更改互动状况
isManProposed[indexM][indexW] = True
#如果女嘉宾仍是自由身，则两人牵手成功
if is_woman_free[indexW] is True:
#修改男女嘉宾的当前状况，并存储牵手信息
is_woman_free[indexW] = False
is_man_free[indexM] = False
match[indexM] = (indexM,indexW)
#如果女嘉宾已经名花有主，则当前男嘉宾与当前女嘉宾的‘男朋友’进行PK
else:
#从牵手信息中查找当前女嘉宾的‘男朋友’牌号
indexM1 = -1
for j in range(length):
if match[j][1] == indexW:
indexM1 = j
break
#如果在当前女嘉宾心中，相较于‘男朋友’更中意当前的男嘉宾
if woman_preferences[indexW].index(indexM) < woman_preferences[indexW].index(indexM1):
#当前女嘉宾的‘前男友’恢复自由身
is_man_free[indexM1] = True
#当前男嘉宾牵手成功，修改其自由状况
is_man_free[indexM] = False
#修改牵手信息
match[indexM] = (indexM,indexW)
#返回最终牵手信息
return match
#男嘉宾心中最中意的女嘉宾排行
MP = [
[1, 4, 3, 6, 2, 5, 8, 7, 9, 0],
[2, 1, 0, 3, 4, 8, 5, 9, 7, 6],
[4, 3, 8, 9, 0, 2, 1, 7, 6, 5],
[2, 7, 6, 1, 4, 3, 8, 0, 9, 5],
[5, 3, 8, 4, 2, 0, 7, 6, 1, 9],
[5, 0, 1, 7, 2, 8, 9, 4, 6, 3],
[6, 2, 9, 8, 0, 7, 5, 1, 4, 3],
[9, 7, 1, 8, 0, 2, 5, 6, 3, 4],
[8, 0, 5, 9, 6, 7, 1, 2, 4, 3],
[7, 9, 1, 6, 2, 0, 5, 8, 4, 3]
]
#女嘉宾心中最中意的男嘉宾排行
WP = [
[3, 5, 0, 6, 9, 4, 8, 7, 2, 1],
[0, 1, 3, 2, 7, 8, 5, 9, 4, 6],
[1, 0, 7, 9, 3, 2, 5, 8, 6, 4],
[2, 0, 6, 3, 4, 1, 5, 7, 9, 8],
[5, 6, 8, 3, 2, 0, 9, 4, 1, 7],
[3, 0, 1, 7, 9, 8, 2, 4, 6, 5],
[6, 2, 7, 8, 0, 9, 4, 1, 5, 3],
[9, 3, 1, 2, 0, 7, 5, 6, 8, 4],
[4, 1, 5, 9, 6, 7, 0, 2, 8, 3],
[6, 0, 1, 7, 2, 9, 5, 8, 4, 3]
]
print(find_stable_matching(MP,WP))
最终结果
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (6, 6), (7, 9), (8, 8), (9, 7)]
#即0号男嘉宾与1号女嘉宾牵手，以此类推