Gale-Shapley
Gale-Shapley
GS算法全称Gale-Shapley算法,用于解决Stable matching问题,Gale-Shapley算法效率要高于Brute Force算法 Brute Force 算法interation的次数是N! 而gs算法interation 次数是N^2.
Brute Force 算法 interation的次数是N!
gs算法 interation 次数是N^2
基本思想
GS算法 aka. Get-rid-of-single算法 手动狗头
基本思想
while ((some man is free and has not proposed to every woman) and (do choose such a man)):
# w is 1st woman on m's list to whom m has not yet proposed
if (w is free):
assign m to w
esle if (w prefers m to her fiance' m1):
assign m to w and m1 is free
else:
w reject m
For Example
4 men(W-Z)with preference list (left)
4women(A-D)with preference list(right)
Implication
Implication by Python
'
!/user/bin/env python
-- coding:utf-8 --
Author : Zhuangzhi Gao
Date :2021.10.18
from collections import deque
初始化
Man = ["W","X","Y","Z"]
Woman = ["A","B","C","D"]
偏爱列表
pre_boy_to_girl = [[2,1,3,4],[3,2,1,4],[2,3,1,4],[2,1,4,3]]
pre_girl_to_boy = [[2,1,3,4],[1,3,2,4],[4,3,1,2],[2,1,3,4]]
def find_partner(Man,Woman,pre_boy_to_girl,pre_girl_to_boy):
#写一个字典
corrent_Man = {Man[0]:None,Man[1]:None,Man[2]:None,Man[3]:None}
corrent_Woman = {Woman[0]:None,Woman[0]:None,Woman[0]:None,Woman[0]:None}
index = len(Man)
#建立队列选择女孩
new_match = {}
for i in range(index):
new_match[Man[i]] = deque();
argsort_p = sorted(range(index), key = lambda k:pre_boy_to_girl[i][k])
for j in range(index):
new_match[Man[i]].append(Woman[argsort_p[j]])
#女孩选择男孩字典
sort_girl = {}
for i in range(index):
sort_girl[Woman[i]] = {}
for j in range(index):
sort_girl[Woman[i]][Man[j]] = pre_girl_to_boy[i][j]
while None in new_match.values():
for i in range(index):
bid = Man[i]
if new_match[bid]:
continue
else:
select = new_match[bid][0]
if corrent_Woman[select] == None:
#女孩没对象两者结合
corrent_Man[bid] = select
corrent_Woman [select] = bid
new_match[bid].popleft()
else:
if sort_girl[select][corrent_Woman[select]]<sort_girl[select][bid]:
new_match[bid].popleft()
else:
corrent_Man[corrent_Woman[select]]= None
corrent_Man[bid] = select
corrent_Woman[select] = bid
new_match[bid].popleft()
return corrent_Man
print (find_partner(Man,Woman,pre_boy_to_girl,pre_girl_to_boy))
'