最近在做算法复健,鉴于我的blog域名难产,暂时寄居在何dalao这里。
什么是稳定(婚姻)匹配问题
这里是百度百科。有N男N女,均为异性恋,每个人都对异性有好感度排序。如何将他们两两配对,才能尽可能使结果令每个人都满意。
当然也有N男M女、多对一的情况,这里先不讨论(网上有些大牛写了论文)。
处理方案
被广泛认可的算法是由美国数学家 David Gale 和 Lloyd Shapley 于1962年发明的 Gale-Shapley算法,简称GS算法。GS算法的思路如下:
先给N男N女从0~N-1分别编号,然后要求每个人写出他们对异性的好感度排序。为了方便,这里N取4.比如0号男最喜欢3号女,[……]