最近在做算法复健,鉴于我的blog域名难产,暂时寄居在何dalao这里。
什么是稳定(婚姻)匹配问题
这里是百度百科。有N男N女,均为异性恋,每个人都对异性有好感度排序。如何将他们两两配对,才能尽可能使结果令每个人都满意。
当然也有N男M女、多对一的情况,这里先不讨论(网上有些大牛写了论文)。
处理方案
被广泛认可的算法是由美国数学家 David Gale 和 Lloyd Shapley 于1962年发明的 Gale-Shapley算法,简称GS算法。GS算法的思路如下:
先给N男N女从0~N-1分别编号,然后要求每个人写出他们对异性的好感度排序。为了方便,这里N取4.比如0号男最喜欢3号女,其次是0号女,再次是1号女,最后是2号女,则0号男给出的排序为3 0 1 2.
下图中展示了好感排序情况(随机给出):
第一轮,先让每个男性向他们最喜欢的女性表白(也可以女性表白男性,同理)。例如0号男会先向3号女表白。如果一个女性同时收到了两个表白,她会选择接受自己最喜欢的那个男性。如3号女同时收到0号和2号的表白,接受0号。
第一次匹配结束后的情况:
0号男-3号女 1号男-0号女 3号男-1号女
第二轮,由于第一轮时只有2号男落单(惨),这次2号男选择向自己第二喜欢的1号女表白。1号女接到表白后,会比较现任对象(3号男)和2号男,发现自己更喜欢2号男,于是与3号男分手,投入2号男的怀抱。
第二次匹配结束后的情况:
0号男-3号女 1号男-0号女 2号男-1号女
第三轮,3号男向自己第二喜欢的0号女表白,0号女比较现任配偶(1号男)和3号男,觉得自己还是更喜欢现任配偶,3号男被残忍拒绝。这次匹配关系没有发生变化。
第四轮,3号男向自己第三喜欢的2号女表白。2号女还没有收到过表白,直接接受。
第四次匹配结束后的情况:
0号男-3号女 1号男-0号女 2号男-1号女 3号男-2号女
此时每个人都找到了配偶,匹配结束。
简单总结一下,每一轮开始时:
①没有配偶的男性选择自己好感度最高而且没表白过的女性表白。
②接到表白的女性比较现任配偶和新追求者的好感度,选择与好感度更高的男性重新匹配。
GS算法的局限性
从算法过程容易看出,按照“男性表白女性”的策略对女性更有利,因为女性的配偶质量会不断提升,而男性的配偶质量会不断变差。相反则对男性有利。不同的表白策略得出的匹配结果很可能是不同的。
GS算法能否保证每个人都有对象
假设有一个男性A落单,由于男女人数相等,则必定还有一个女性B落单。
根据算法,B是被动接受表白,只要收到过一次表白,B就不可能落单。
而如果A没有配偶,他会一直表白下去,将N个女性全部表白一遍。这个过程中B一定会收到表白,两人匹配。
上述内容同时可以证明,该算法会在有限次运算后结束(运算次数小于n*n)。
GS算法的结果是否稳定
“稳定”是指:算法结束后,如果再进行一轮表白,一定不会出现男女双方的选择都更优的情况。
这一点容易证明。根据算法局限性,再进行表白,男性对新配偶的好感度只会下降。
假设男性A与女性B本应匹配(也就是说现在两个人分别有自己的配偶,但是从好感度角度来说,他们都更希望彼此形成新的匹配),可以分两种情况讨论:
1.男性A曾对女性B表白,但此时两人没有匹配,说明女性B后来遇到了好感度更高的男性,假设不成立。
2.男性A不曾对女性B表白,说明男性A的配偶好感度排在女性B前面,假设不成立。
代码实现
#include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #include<cstring> #include<string> using namespace std; const int MAXN = 0 + 5; int Num,nowMatch; int Match_A[MAXN], Match_B[MAXN], Preference_A[MAXN][MAXN], Preference_B[MAXN][MAXN], Now[MAXN]; //Match数组记录匹配情况,Preference[i][1..n]记录好感排序 inline void init() {//读入、预处理 scanf("%d", &Num); for (int i = 0; i < Num; ++i) for (int j = 0; j < Num; ++j) scanf("%d", &Preference_A[i][j]); for (int i = 0; i < Num; ++i) for (int j = 0; j < Num; ++j) scanf("%d", &Preference_B[i][j]); for (int i = 0; i < Num; ++i) Match_A[i] = -1, Match_B[i] = -1; } bool Compare(int a, int b, int Obj) {//比较追求当前的B[i]的两个人在B[i]处的好感排序 int index_a = -1, index_b = -1; for (int i = 0; i < Num; ++i) { if (Preference_B[Obj][i] == a) index_a = i; else if (Preference_B[Obj][i] == b) index_b = i; } if (index_a < index_b) return true; return false; } bool AllMatch() {//判断是否完成匹配 int count = 0; for (int i = 0; i < Num; ++i) if (Match_A[i] != -1) count++; if (count < Num) return false; return true; } void Gale_Shapley() { while (! AllMatch()) {//算法会在所有人完成匹配后终止 for (int i = 0; i < Num; i ++) { if (Match_A[i] != -1) continue; nowMatch = Match_B[Preference_A[i][Now[i]]]; //nowMatch是A[i]想要表白的B[i]目前的对象,没有则为-1 if (nowMatch == -1 || Compare(i, nowMatch, Preference_A[i][Now[i]])) {//如果B[i]没有对象,或者B[i]对A[i]更有好感,则A[i]和B[i]匹配 Match_A[i] = Preference_A[i][Now[i]]; Match_A[nowMatch] = -1; Match_B[Preference_A[i][Now[i]]] = i; } Now[i] ++; } } } inline void Output() {//随便写了个输出qwq for (int i = 0; i < Num; ++i) { printf("A-%d is matched to B-%d\n", i, Match_A[i]); } } int main() { init(); Gale_Shapley(); Output(); return 0; }
上面的代码是我自己写的,也没有题目可以检验是否正确,有问题欢迎联系我orz
应用
虽然算法解决的问题是“稳定婚姻匹配”,但是真的按照这个算法来选对象岂不太简单粗暴了…不过这好歹还是对象包分配
GS算法可以用于解决工作岗位的分配问题,例如某公司有n个岗位,m(m>=n)人竞争,可以根据公司和应聘者对彼此的好感度排序,利用算法算出最合适的人选。
漫谈
如果把上文中的人视为点,好感关系视为线,就构成了一个二分图匹配问题。问题就可以转化为:根据已有的好感度排序,如何连线才能使得左右两侧的点一一相连,且连线结果尽量令人满意。
匹配成功后的结果如图所示,是一个一一映射:
如果把这个问题削弱一下,条件可以改为:每个人都对M(M<=N)名异性有好感,这种好感不分大小。如何使尽量多对互有好感的人相匹配。这个问题称作二分图最大匹配问题,可以用匈牙利算法求解。
匈牙利算法等我记起来怎么写再写(咕咕咕咕)。
算法归算法,祝天下有情人终成眷属!
老来多健忘,唯不忘相思