未分类

稳定匹配问题与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)

分享到
文章
微信小程序入坑: 写一个简化版知乎日报

最近开始入坑微信小程序，发现想要练手也不容易，找免费的基于HTTPS的API就要花点时间。在看了网上一些介绍后，决定采用知乎日报的API，写一个简单版的知乎日报作为入坑练习。本文尝试使用微信小程序写一个小demo，实现知乎日报的3个主要页面以及部分功能。3个页面分别为“首页”、“详情页”和“评论页”

NodeJS C++ Addons之C++类实例包装与异步操作

本文是对NodeJS C++ Addons原生写法的进一步探索，介绍了利用原生的Node和V8提供的API实现类包装和异步调用的具体做法。在阅读本文之前，如果对NodeJS C++ Addons的基础不熟悉的话，建议先阅读上一篇博客【NodeJS C++ Addons基础】进行了解之后再回来阅读本文

NodeJS C++ Addons基础

NodeJS C++插件是一种动态链接库，采用C/C++语言编写，可以通过require()将插件加载进NodeJS中进行使用。利用V8提供的API，可以实现JavaScript和C++的互相调用，打通JavaScript和C++之间的接口。在做一些高性能或者底层模块的时候，需要用到一些C++库，N

试玩NodeJS多进程

NodeJS的JavaScript运行在单个进程的单个线程上，一个JavaScript执行进程只能利用一个CPU核心，而如今大多数CPU均为多核CPU，为了充分利用CPU资源，Node提供了child_process和cluster模块来实现多进程以及进程管理。本文将根据Master-Worker模

MonkeyEye电影售票系统-性能优化总结

案例来源：SYSU SE305 课程大作业。互联网售票软件是比较常见的软件系统。通常由多个零售系统和多个供给系统系统。 机票、酒店房间、电影票似乎是风马牛大相关的系统，但它们之间存在极其相似的业务模型。 以电影票为例，格瓦拉、蜘蛛网、腾讯等等都做类似的电影票分销、推广业务，但票是由各大院线排期提供的

页面
about
标签
前端前端
NodeJSNodeJS
WebWeb
JavaScriptJavaScript
数据结构与算法数据结构与算法