未分类

稳定匹配问题与GS算法-单身狗脱单秘籍

数据结构与算法

稳定匹配问题

稳定匹配问题(stable matching)是一个常见的问题，GS算法是解决稳定匹配问题的一个优秀的算法。下面，我将以男女配对的例子来介绍稳定匹配问题并阐述GS算法的具体步骤。GS算法，全称Gale-Shapley算法。学习完稳定匹配问题和整个算法流程之后，我觉得它还可以起另外一个别名，Get-rid-of-Single算法，单身狗脱单算法。

问题描述

有n只男性单身狗的集合M = {m1, m2, ..., mn}和n只女性单身狗的集合W = {w1, w2, ..., wn}。假设每只男性单身狗对n只女性单身狗的喜好程度都不同，每只女性单身狗对n只男性单身狗亦如是。男单身狗mi(1 <= i <= n)有一张属于自己的关于对面n只女单身狗的排序表，mi把他最爱慕的女性放在第一位，第二爱慕的女性放在第二位，以此类推，排名越靠前女性表示mi越爱慕的女性。同样地，女单身狗wi(1 <= i <= n)也有一张属于自己的关于对面n只男单身狗的排序表，排名越靠前的男性越受wi的喜爱。每只单身狗都希望与自己最喜爱的对象结为侠侣，浪迹江湖。现在，有一个名唤月老的NPC在为这2*n只单身狗牵红线，月老收集了这些单身狗各自的排序表，并根据他们的排序表来牵红线让这些单身狗结成n对侠侣，使得这n对侠侣达成一个稳定匹配，和谐地浪迹江湖。

【稳定匹配】假设有两对伴侣(m1, w1)、(m2, w2)，在m1的排序表中w2的排名比w1高，也就是说，m1喜欢w2比喜欢他现任w1要多一点。此时，若w2正好喜欢m1比喜欢她现任m2要多一点，那么m1和w2就很有可能背叛他们目前各自的侠侣关系重新与更喜欢的对象结为侠侣，剩下被甩的w1和m2继续沦落为单身狗。上面这种情况我们称为不稳定因素，要是一个匹配之中没有任何不稳定因素，那么这个匹配称为稳定匹配。再举个例子，同样是(m1, w1)、(m2, w2)，m1更喜欢w2，但是w2不喜欢m1。此时，这个匹配是稳定的。因为m1和w2并非相互之间都更喜欢对方，因此他们不会”私奔”，不会打破现有的匹配关系。这样一个匹配，虽然m1无法得到自己最喜欢的w2，但这个匹配的关系是和谐稳定的。因此，我们定义稳定匹配的概念如下：给定的一组匹配结果里面，n对侠侣之间任何两对侠侣都不会存在有人想”私奔”的不稳定因素。

输入输出

输入： 每个男单身狗对n个女单身狗的排序表，每个女单身狗对n各男单身狗的排序表

输出： n对满足稳定匹配的伴侣

算法基本思想

初始，每个人都是单身狗，分别根据自己对异性的排序表开始找对象。假设一只男性单身狗mi选择了他的排序表上排名最高的女性w，并且向她示爱。这个时候就可能存在下面3种情况：

  • 【1】w也是单身狗，于是他们两个结为侠侣，成功脱单
  • 【2】w已经和某男性mj脱单，但是w更喜欢mi，于是w把mj甩了，重新和mi结为侠侣。mi成功挖到墙脚，换mj变成单身狗
  • 【3】w已经和某男性mj脱单，而且w不喜欢mi，于是mi挖墙脚失败，为了脱单只能继续寻找排名表上下一个喜欢的女性示爱

对于每个单身狗都重复上述的过程，不断地去”骚扰”排名表上的女性，找到还没脱单的就一起脱单，找到脱单的就挖墙脚，挖不动就找下一个喜欢的对象继续重复上述过程。这就是”伟大”的单身狗脱单(GS)算法。

算法的伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
初始化所有M和W集合中元素为单身狗
初始化侠侣集合S为空集
While 存在男单身狗mi
    令w是mi的排名表中mi还未示爱的女性中排名最高的女性
    If w也是单身狗 then
        (mi, w)组成侠侣，加入侠侣集合S
    Else w已经和mj脱单
        If w更偏爱mj而不爱mi then
            mi挖墙脚没戏，保持单身
        Else w更偏爱mi而不爱mj then
            (mj, w)解除侠侣关系，从侠侣集合S中移除
            mj沦落为单身狗
            mi挖墙脚成功，(mi, w)组成侠侣，加入侠侣集合S
        Endif
    Endif
Endwhile
输出集合S中的所有侠侣配对情况

算法分析

仔细分析一下这个单身狗脱单算法我们可以发现它具备下面几个特性：

某只女单身狗w从第一次跟别人组成侠侣之后，如果某个男单身狗m继续向她示爱，而且m刚好在w的排序表上的排名比w的现任更高，那么w会甩了现任然后与m“私奔”。如果m在w的排序表上的排名比w的现任低，那么w不理睬m，继续和现任保持关系。这个规律可以看出，w自从第一个跟别人组成侠侣之后，她如果后面还有与其他人组成侠侣，那么跟她组成侠侣的人只会”越来越好”，即越来越符合她的排序表，也就是说，她得到的异性质量会越来越好。

某只男单身狗向他排序表上的女性示爱，第一个示爱失败之后只能找第二个，再失败再找第三个，以此类推。于是这个那单身狗在他脱单之前，他能选择的女性只会越来越不符合他的排序表，也就是说，他能选择的异性质量会越来越差。

这个算法在执行结束之后会返回一个稳定的匹配。为什么呢？因为该脱单的都脱单了，能挖动的墙脚也都被挖了，最后组成的匹配结果中，任何两对侠侣之间不会再存在任何能够挖墙脚私奔的不稳定因素了。

乍一看GS算法好像是偏爱女性的一种算法。但实际上，GS算法在某些情况下也存在偏爱男性的情况。如果男性的排名表完全协调(他们全都列出不同女性作为他们的第一选择)，那么在GS算法的所有运行中所有男人最终都与他们的第一选择匹配，而与女人的排序表无关。怎么理解呢？假设男单身狗m1最喜欢女单身狗w1，m2最喜欢w2，…，mn最喜欢wn。那么所有男单身狗在选择时都会进入前面说到的【1】这种情况，也就是直接和最喜欢的女性脱单了。这个时候女性就变成没有选择权了，如果这时候女单身狗的排序表刚好跟男单身狗完全冲突的话，也就是说，w1最不喜欢m1，w2最不喜欢m2，以此类推。那么这种情境下的匹配结果虽然是稳定的，但却也往往也是带着一股不太好的气息，因为男性都得到了最喜爱的女性，而女性却都得到了最不喜爱的男性。

算法实现

经过前面的讨论我们基本清楚了稳定匹配问题和GS算法是怎么一回事了。下面，我用C++简单实现了GS算法的整个过程。为了在O(1)的时间内判断出女性w是否更加偏爱mi或mj，我将女性对男性的排序表的存储方式小小调整了一下，跟男性对女性排序表的存储方式有所不同。另外，侠侣集合S的数据结构也采用数组表示以便更简单地在O(1)的时间内增加或删除侠侣。

GS算法的时间复杂度为O(n^2)，但是不同代码实现可能会有不同的复杂度。如果判断女性w是否更加偏爱mi或mj这个地方使用遍历女性w的排序表的方法的话会造成更高的复杂度。集合的增删元素操作这里也会有相应的复杂度影响。有了上面两个O(1)复杂度的改进之后，下面整个算法实现的时间复杂度为O(n^2)。下面是实现代码：

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
using namespace std;

class GSModel {
public:
  GSModel(int cpNum): cpNum(cpNum) {
    free_m  = new bool[cpNum];
    free_w  = new bool[cpNum];
    result  = new int[cpNum];
    order_m = new int*[cpNum];
    order_w = new int*[cpNum];
    for (int i = 0; i < cpNum; ++i) {
      order_m[i] = new int[cpNum];
      order_w[i] = new int[cpNum];
    }
  }
  ~GSModel() {
    for (int i = 0; i < cpNum; ++i) {
      delete [] order_m[i];
      delete [] order_w[i];
    }
    delete [] free_m;
    delete [] free_w;
    delete [] result;
    delete [] order_m;
    delete [] order_w;
  }
  // 输入男性和女性的排序表
  void init() {
    cout << "[man's order list of women]\n";
    for (int i = 0; i < cpNum; ++i) {
      cout << "[m-" << i << "]: ";
      for (int j = 0; j < cpNum; ++j) {
        cin >> order_m[i][j];
      }
      free_m[i] = true;
    }
    cout << "[woman's order list of man]\n";
    for (int i = 0; i < cpNum; ++i) {
      cout << "[w-" << i << "]: ";
      int man;
      for (int j = 0; j < cpNum; ++j) {
        cin >> man;
        order_w[i][man] = cpNum - j;
      }
      free_w[i] = true;
      result[i] = -1;
    }
  }
  // 判断是否全部人都脱单
  bool isOk() const {
    for (int i = 0; i < cpNum; ++i)
      if (free_m[i]) return false;
    return true;
  }
  void solve() {
    while (true) {
      for (int i = 0; i < cpNum; ++i) {
        if (free_m[i]) {
          for (int j = 0; j < cpNum && free_m[i]; ++j) {
            int w = order_m[i][j];
            // 女方自由
            if (free_w[w]) {
              result[w] = i;
              free_m[i] = false;
              free_w[w] = false;
            }
            // 女方已有对象，但爱此男比爱现任多一点
            else {
              if (order_w[w][i] > order_w[w][result[w]]) {
                free_m[result[w]] = true;
                result[w] = i;
                free_m[i] = false;
              }
            }
          }
        }
      }
      if (isOk()) break;
    }
  }
  // 输出匹配结果
  void print() const {
    for (int i = 0; i < cpNum; ++i) {
      cout << "(w-" << i << ", m-" << result[i] << ")\n";
    } 
  }
private:
  bool* free_m;
  bool* free_w;
  int** order_m;
  int** order_w;
  int*  result;
  int   cpNum;
};

int main() {
  int cpNum;
  cin >> cpNum;
  GSModel gsm(cpNum);
  gsm.init();
  gsm.solve();
  gsm.print();
  return 0;
}

输入输出示例：

1
2
3
4
5
6
7
8
9
10
11
12
3
[man's order list of women]
[m-0]: 0 1 2
[m-1]: 1 0 2
[m-2]: 0 2 1
[woman's order list of man]
[w-0]: 1 2 0
[w-1]: 0 1 2
[w-2]: 1 0 2
(w-0, m-1)
(w-1, m-0)
(w-2, m-2)

分享到