稳定婚姻问题学习笔记
问题阐述
给定 \(n\) 个男性和 \(n\) 个女性，每个男性对女性有偏好度，女性对男性也是。要求一个完美匹配，使得没有一对未匹配的男女，对对方的偏好度都比目前的伴侣骗号度高。
性质
稳定婚姻匹配一定存在，不一定唯一。
算法
Mating Ritual 算法
早上：男性找到自己最喜欢的女性，给她唱歌
中午：女性如果有很多男的给她唱歌，选自己最喜欢的，然后让别的走
晚上：男的再也不去给那个拒绝他的女的唱歌
如此重复最多 \(n^2\) 天，每个女性只有一个男的给她唱歌，就是最终匹配。
/*
实际代码跟算法有出入，一次只计算一个男人，编码方便，原理一致
*/
int wp[210],mp[210];//女/男人匹配的
int p1[210][210],q1[210][210];
int p2[210][210],q2[210][210];
// 优先级越大表排名越靠前 p1 代表男人对女人 p2 代表女人对男人 q1,q2为这个人所对应优先级
void stable_marriage(){
for(int i=1;i<=n;++i)mp[i]=wp[i]=0;
int cnt=n;
while(cnt>0){
int m=1;
while(mp[m]>0)m++;
assert(m<=n);
for(int i=1;i<=n;++i){
int w=p1[m][i];
if(wp[w]==0){
mp[m]=w;
wp[w]=m;
cnt--;
break;
}else if(q2[w][m]<q2[w][wp[w]]){
mp[wp[w]]=0;
wp[w]=m;
mp[m]=w;
break;
}
}
}
}
算法趣谈
看似女性充满了主动权，实则男性收获最大。
这个算法得到的男性对应的女性，是可能女性里偏好度最大的。女性对应的男性，是可能男性里偏好都最小的。
反直觉的事实。