【算法笔记】稳定婚姻匹配问题-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)名异性有好感,这种好感不分大小。如何使尽量多对互有好感的人相匹配。这个问题称作二分图最大匹配问题,可以用匈牙利算法求解。

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

算法归算法,祝天下有情人终成眷属!

老来多健忘,唯不忘相思

发表回复