1833.经典算法–稳定婚姻问题
问题描述
“稳定婚姻问题”在生活中是一个典型的问题,通俗地可叙述为:当前有N位男生和N位女生最后要组成稳定的婚姻家庭,过程开始之前男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序.然后开始选择自己的对象,其规则是:男生第一天均向各自最喜欢的女生写一封“情书”。
算法概述
1962年，美国数学家David Gale和Lloyd Shapley发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。
先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：
①每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
②每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。
③若某男士被其女友抛弃，重新变成自由男。
举个例子
下表是男生和女生分别对异性在心里的钟意排序，编程输出最终的配对结果
证明算法的稳定性
假设Zeus与Amy是不稳定的，他们两个有私奔的动向。
按照算法逻辑，Zeus和Amy有两种互动关系：
Zeus没有追求过（现在和以后）Amy：
=>Zeus找到了比Amy更好的女人，Amy心服
=>Zeus与Amy是稳定的
Zeus追求Amy（现在和以后）：
（1） Zeus追到了Amy，两人在一起,两情相悦。
=>Zeus与Amy是稳定的
（2） Amy拒绝了Zeus
=>Amy找到了比Zeus更好的男人，Zeus心服
=> Zeus与Amy是稳定的
综上，假设不成立，即证。
算法伪代码
- 初始化每个人都单身.
- while (某个男孩单身m，并且他有没约会的女孩) do
-
选择这个男孩m他没约会过的女孩中最喜欢的 w= 1st -
if (w 单身) -
then m 和 w 成为一对 -
else if (w 喜欢m甚于现在的男朋友m') -
then m 和 w 成为一对, 并且 m‘ 成为单身 -
else w 拒绝 m
Python实现
用0,1代表配对情况
查找女生单身状况
def find_Girl_state(girl_Name):
for girl in girls_loveSort:
if girl[0] == girl_Name:
return girl[-1]
两人牵手成功
def marry(man, woman):
man[-1] = 1
for girl in girls_loveSort:
if girl[0] == woman:
girl[-1] = 1
for man_Situation in love_Situation:
if man_Situation[0] == man[0]:
man_Situation[1] = woman
两人分手
def divorce(old_man):
for man in boys_loveSort:
if man[0] == old_man:
man[-1] = 0
for man2 in love_Situation:
if man2[0] == old_man:
man2[1] = “no girl”
两个男人竞争，看女人更喜欢谁
def complete(man, woman):
old_Man = “”
new_index = 0
old_index = 0
for partner in love_Situation:
if partner[1] == woman:
old_Man = partner[0]
for girl in girls_loveSort:
if girl[0] == woman:
for index, husband in enumerate(girl):
if husband == old_Man:
old_index = index
elif husband == man[0]:
new_index = index
else:
pass
return [new_index < old_index, old_Man]
要输入分析的男女生资料
row_Number, col_Number = map(int, input(“请输入表格的行数，列数（第一行不用，以空格隔开）\n”).split())
boys_loveSort = []
girls_loveSort = []
love_Situation = []
for item in range(row_Number):
boys_loveSort.extend([input(“请输入男生喜爱表格，按行输入（第一行不用,以空格隔开）\n”).split()])
boys_loveSort[item].append(0)
for item in range(row_Number):
girls_loveSort.extend([input(“请输入女生喜爱表格，按行输入（第一行不用，以空格隔开）\n”).split()])
girls_loveSort[item].append(0)
for item in range(row_Number):
a, *b = boys_loveSort[item]
love_Situation.extend([[a, “no girl”]])
开始配对
for item in range(1, col_Number):
for boy in boys_loveSort:
if boy[-1] == 1:
continue
girl_State = find_Girl_state(boy[item])
if girl_State == 0:
marry(boy, boy[item])
elif complete(boy, boy[item])[0] == True:
marry(boy, boy[item])
divorce(complete(boy, boy[item])[1])
else:
pass
结果
print(love_Situation)
输入
请输入表格的行数，列数（第一行不用，以空格隔开）
3 4
请输入男生喜爱表格，按行输入（第一行不用,以空格隔开）
x a b c
请输入男生喜爱表格，按行输入（第一行不用,以空格隔开）
y b a c
请输入男生喜爱表格，按行输入（第一行不用,以空格隔开）
z a b c
请输入女生喜爱表格，按行输入（第一行不用，以空格隔开）
a y x z
请输入女生喜爱表格，按行输入（第一行不用，以空格隔开）
b x y z
请输入女生喜爱表格，按行输入（第一行不用，以空格隔开）
c x y z
输出
[[‘x’, ‘a’], [‘y’, ‘b’], [‘z’, ‘c’]]
即x配对a，y配对b，z配对z 是稳定婚姻的
