参考：经典算法问题——稳定匹配（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 算法中女性一定分配到的是最差的正当配偶。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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());
        }

    }
}