稳定匹配问题

Ywrby

发布于 2023-10-16 19:24:01

3820

发布于 2023-10-16 19:24:01

文章被收录于专栏：Ywrby

参考：经典算法问题——稳定匹配（Stable Matching）

Gale-Shapley Algorithms

简称“GS 算法”，也称为延迟接受算法。是 Gale 和 Shapley 为了寻找一个稳定匹配而设计出的市场机制。运行时间在算法输入的大小上是线性的。根据其使用方式，它可以找到对匹配一侧的参与者或另一侧的参与者最佳的解决方案。

问题描述给出一个 n 个男性的集合 M，和 n 个女性的集合 W，其中：

每位男性根据对所有女性的心仪程度从高至低进行排名；
每位女性根据对所有男性的心仪程度从高至低进行排名。

根据以上条件，我们需要找到一个“稳定匹配”。

基本概念

匹配 Matching

匹配 S 是一个包含有序数对 m-w 的集合，其中 m \in M 且w \in W，其中：

每个男性最多出现在一个数对中；
每个女性最多出现在一个数对中。

完美匹配 Perfect matching

不稳定因素 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 删除

int