【算法笔记】稳定婚姻匹配问题-GS算法

最近在做算法复健，鉴于我的blog域名难产，暂时寄居在何dalao这里。

什么是稳定(婚姻)匹配问题

这里是百度百科。有N男N女，均为异性恋，每个人都对异性有好感度排序。如何将他们两两配对，才能尽可能使结果令每个人都满意。

当然也有N男M女、多对一的情况，这里先不讨论（网上有些大牛写了论文）。

处理方案

被广泛认可的算法是由美国数学家 David Gale 和 Lloyd Shapley 于1962年发明的 Gale-Shapley算法，简称GS算法。GS算法的思路如下：

先给N男N女从0~N-1分别编号，然后要求每个人写出他们对异性的好感度排序。为了方便，这里N取4.比如0号男最喜欢3号女，其次是0号女，再次是1号女，最后是2号女，则0号男给出的排序为3 0 1 2.

下图中展示了好感排序情况（随机给出）：

GS_data

第一轮，先让每个男性向他们最喜欢的女性表白（也可以女性表白男性，同理）。例如0号男会先向3号女表白。如果一个女性同时收到了两个表白，她会选择接受自己最喜欢的那个男性。如3号女同时收到0号和2号的表白，接受0号。
第一次匹配结束后的情况：
0号男-3号女    1号男-0号女    3号男-1号女

第二轮，由于第一轮时只有2号男落单（惨），这次2号男选择向自己第二喜欢的1号女表白。1号女接到表白后，会比较现任对象（3号男）和2号男，发现自己更喜欢2号男，于是与3号男分手，投入2号男的怀抱。
第二次匹配结束后的情况：
0号男-3号女    1号男-0号女    2号男-1号女

第三轮，3号男向自己第二喜欢的0号女表白，0号女比较现任配偶（1号男）和3号男，觉得自己还是更喜欢现任配偶，3号男被残忍拒绝。这次匹配关系没有发生变化。

第四轮，3号男向自己第三喜欢的2号女表白。2号女还没有收到过表白，直接接受。
第四次匹配结束后的情况：
0号男-3号女    1号男-0号女    2号男-1号女    3号男-2号女

此时每个人都找到了配偶，匹配结束。

简单总结一下，每一轮开始时：
①没有配偶的男性选择自己好感度最高而且没表白过的女性表白。
②接到表白的女性比较现任配偶和新追求者的好感度，选择与好感度更高的男性重新匹配。

GS算法的局限性

从算法过程容易看出，按照“男性表白女性”的策略对女性更有利，因为女性的配偶质量会不断提升，而男性的配偶质量会不断变差。相反则对男性有利。不同的表白策略得出的匹配结果很可能是不同的。

GS算法能否保证每个人都有对象

假设有一个男性A落单，由于男女人数相等，则必定还有一个女性B落单。
根据算法，B是被动接受表白，只要收到过一次表白，B就不可能落单。
而如果A没有配偶，他会一直表白下去，将N个女性全部表白一遍。这个过程中B一定会收到表白，两人匹配。

上述内容同时可以证明，该算法会在有限次运算后结束（运算次数小于n*n）。

GS算法的结果是否稳定

“稳定”是指：算法结束后，如果再进行一轮表白，一定不会出现男女双方的选择都更优的情况。
这一点容易证明。根据算法局限性，再进行表白，男性对新配偶的好感度只会下降。

假设男性A与女性B本应匹配（也就是说现在两个人分别有自己的配偶，但是从好感度角度来说，他们都更希望彼此形成新的匹配），可以分两种情况讨论：
1.男性A曾对女性B表白，但此时两人没有匹配，说明女性B后来遇到了好感度更高的男性，假设不成立。
2.男性A不曾对女性B表白，说明男性A的配偶好感度排在女性B前面，假设不成立。

代码实现

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>

using namespace std;

const int MAXN = 0 + 5;

int Num,nowMatch;
int Match_A[MAXN], Match_B[MAXN], Preference_A[MAXN][MAXN], Preference_B[MAXN][MAXN], Now[MAXN];
//Match数组记录匹配情况，Preference[i][1..n]记录好感排序

inline void init()
{//读入、预处理
  scanf("%d", &Num);
  for (int i = 0; i < Num; ++i)
    for (int j = 0; j < Num; ++j)
      scanf("%d", &Preference_A[i][j]);
  for (int i = 0; i < Num; ++i)
    for (int j = 0; j < Num; ++j)
      scanf("%d", &Preference_B[i][j]);
  for (int i = 0; i < Num; ++i)
    Match_A[i] = -1, Match_B[i] = -1;
}

bool Compare(int a, int b, int Obj)
{//比较追求当前的B[i]的两个人在B[i]处的好感排序
  int index_a = -1, index_b = -1;
  for (int i = 0; i < Num; ++i)
  {
    if (Preference_B[Obj][i] == a)
      index_a = i;
    else if (Preference_B[Obj][i] == b)
      index_b = i;
  }
  if (index_a < index_b) return true;
  return false;

}

bool AllMatch()
{//判断是否完成匹配
  int count = 0;
  for (int i = 0; i < Num; ++i)
    if (Match_A[i] != -1)
      count++;
  if (count < Num) return false;
  return true;
}

void Gale_Shapley()
{
  while (! AllMatch())
  {//算法会在所有人完成匹配后终止
    for (int i = 0; i < Num; i ++)
    {
      if (Match_A[i] != -1) continue;
      nowMatch = Match_B[Preference_A[i][Now[i]]];
      //nowMatch是A[i]想要表白的B[i]目前的对象，没有则为-1
      if (nowMatch == -1 || Compare(i, nowMatch, Preference_A[i][Now[i]]))
      {//如果B[i]没有对象，或者B[i]对A[i]更有好感，则A[i]和B[i]匹配
        Match_A[i] = Preference_A[i][Now[i]];
        Match_A[nowMatch] = -1;
        Match_B[Preference_A[i][Now[i]]] = i;
      }
      Now[i] ++;
    }
  }

}

inline void Output()
{//随便写了个输出qwq
  for (int i = 0; i < Num; ++i)
  {
    printf("A-%d is matched to B-%d\n", i, Match_A[i]);
  }
}

int main()
{
  init();
  Gale_Shapley();
  Output();
  return 0;
}

code

上面的代码是我自己写的，也没有题目可以检验是否正确，有问题欢迎联系我orz

应用

虽然算法解决的问题是“稳定婚姻匹配”，但是真的按照这个算法来选对象岂不太简单粗暴了…不过这好歹还是对象包分配
GS算法可以用于解决工作岗位的分配问题，例如某公司有n个岗位，m(m>=n)人竞争，可以根据公司和应聘者对彼此的好感度排序，利用算法算出最合适的人选。

漫谈

如果把上文中的人视为点，好感关系视为线，就构成了一个二分图匹配问题。问题就可以转化为：根据已有的好感度排序，如何连线才能使得左右两侧的点一一相连，且连线结果尽量令人满意。

匹配成功后的结果如图所示，是一个一一映射：

GS_grape

如果把这个问题削弱一下，条件可以改为：每个人都对M(M<=N)名异性有好感，这种好感不分大小。如何使尽量多对互有好感的人相匹配。这个问题称作二分图最大匹配问题，可以用匈牙利算法求解。

匈牙利算法等我记起来怎么写再写（咕咕咕咕）。

算法归算法，祝天下有情人终成眷属！

老来多健忘，唯不忘相思

发表回复