稳定匹配问题
参考：经典算法问题——稳定匹配（Stable Matching）
Gale-Shapley Algorithms
简称“GS 算法”，也称为延迟接受算法。是 Gale 和 Shapley 为了寻找一个稳定匹配而设计出的市场机制。运行时间在算法输入的大小上是线性的。根据其使用方式，它可以找到对匹配一侧的参与者或另一侧的参与者最佳的解决方案。
问题描述给出一个 n 个男性的集合 M，和 n 个女性的集合 W，其中：
- 每位男性根据对所有女性的心仪程度从高至低进行排名；
- 每位女性根据对所有男性的心仪程度从高至低进行排名。
根据以上条件，我们需要找到一个“稳定匹配”。
基本概念
匹配 Matching
匹配 S 是一个包含有序数对 m-w 的集合，其中 m \in M 且w \in W，其中：
- 每个男性最多出现在一个数对中；
- 每个女性最多出现在一个数对中。
完美匹配 Perfect matching
如果 \left| S \right|=\left| M \right|=\left| W \right|=n 则匹配S是完美匹配，也就是说，男女数量相等且都有唯一匹配的对象。
不稳定因素 Unstable pair
给出一个完美匹配 S，如果其中存在一个男性m和一个女性w同时满足下列条件：
- 不在匹配S中；
- m比起他当前配偶，更喜欢w;
- w比起她当前配偶，更喜欢m。
则称男性m和女性w是不稳定的，也就是说，(m,w)是不稳定因素。
稳定匹配 Stable matching
一个不存在不稳定因素的完美匹配。
Gale-Shapley 算法
一个直观的，确保能找到一个稳定匹配的算法
算法策略
- 男性策略：单身的男性会主动出击，根据喜好降序向所有女性求婚，直到有配偶为止；
- 女性策略：被动等待男性求婚，如果女性仍处于单身，则直接接受；有配偶的情况下被更心仪的男性求婚，则会抛弃原来的，接受更好的。
算法特征
G-S算法具有：有穷性、完美性、稳定性、男性最佳分配、女性最劣分配等特征
- 有穷性：算法最多在n^2次 while 迭代后一定会结束。
- 完美性：算法中所有男性和女性都匹配完毕。
- 稳定性：算法产生的匹配中，不会有不稳定因素
- 男性最佳分配 Man-optimal Assignment：GS 算法中每个男性都能分配到最佳的正当配偶，所以 GS 算法得到的分配一定是男性最佳分配。
- 正当配偶 Valid Partner：如果存在一个稳定匹配中男性和女性匹配在一起，则称女性是男性的正当配偶。
- 女性最劣分配：GS 算法中女性一定分配到的是最差的正当配偶。
算法实现
import Gender.Man;
import Gender.Woman;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
/*
* 盖尔沙普利算法的实现
* */
public class GaleShapley {
public Man[] ManGroup;
public Woman[] WomanGroup;
public GaleShapley(In in1,In in2){
CreateManGroup(in1);
CreateWomanGroup(in2);
InsertManFavor();
}
public void CreateManGroup(In in){
int numMan=in.readInt();
int numWoman=in.readInt();
ManGroup=new Man[numMan];
for(int i=0;i<numMan;i++){
int manName=in.readInt();
Man man=new Man((char) manName,numWoman);
for(int j=0;j<numWoman;j++){
int Num=in.readInt()-1;
man.favorNum[j]=Num;
}
ManGroup[i]=man;
}
}
public void CreateWomanGroup(In in){
int numMan=in.readInt();
int numWoman=in.readInt();
WomanGroup=new Woman[numWoman];
for(int i=0;i<numWoman;i++){
int womanName=in.readInt();
Man[] men=new Man[numMan];
for(int j=0;j<numMan;j++){
int favorNum=in.readInt()-1;
if (favorNum<0) continue;
Man favorMan=ManGroup[favorNum];
men[j]=favorMan;
}
WomanGroup[i]=new Woman((char)womanName,men);
}
}
public void InsertManFavor(){
for(Man man:ManGroup){
man.EntryQueue(WomanGroup);
}
}
public static void main(String[] args) {
GaleShapley GS=new GaleShapley(new In(args[0]),new In(args[1]));
//初始化num=1
int num=1;
//开始循环进行邀请
while(num!=0){
StdOut.printf("-------------------------------------------" +
"\n开始一轮邀请" +
"\n-------------------------------------------\n");
num=0; //将num设为0
//男方进行一轮邀请
for(Man man:GS.ManGroup){
num+=man.Invitation(); //不断将返回值加入num
}
//num仍然等于0说明一整轮都没有成功“发出”邀请
//注意是发出邀请，只要女方成功接收到邀请就返回1（不需要女方一定同意邀请），否则返回0.
//说明所有男性要么已经有暂时配对成功的对象，要么已经出局
//这种情况就可以结束循环，打印结果了
}
StdOut.println("\n最终结果\n");
for(Man man:GS.ManGroup){
StdOut.printf("man:%c --> woman:%c\n",man.name(),man.GirlName());
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-07-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录