[算法]Gale-Shapley Algorithm-稳定匹配算法的设计、实现与探讨（上）

本文主要是介绍[算法]Gale-Shapley Algorithm-稳定匹配算法的设计、实现与探讨（上），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、背景描述

Gale-Shapley Algorithm，简称为GS算法。也被成为Deferred-Acceptance Algorithm.
是盖尔和沙普利为了寻找一个稳定匹配而设计出的市场机制。市场一方中的对象（医疗机构）向另一方中的对象（医学院学生）提出要约，每个学生会对自己接到的要约进行考虑，然后抓住自己青睐的（认为它是可接受的），拒绝其它的。该算法一个关键之处在于，合意的要约不会立即被接受，而只是被“抓住”（hold on to），也就是“延迟接受”。要约被拒绝后，医疗机构才可以向另一名医学院学生发出新的要约。整个程序一直持续到没有机构再希望发出新的要约为止，到那个时候，学生们才最终接受各自“抓住”的要约。
1962年，沙普利与同事戴维·盖尔在《高校招生与婚姻稳定性》一文中写到：以10名男子和10名女子“婚配”为范例，设想如果由每一名女子先作选择并向最中意男子“求婚”，然后再由每一名男子审视所获所有“求婚”并回绝除了最中意女子以外的其他所有“求婚”，就可以实现稳定分配。设想的核心，是男子保留并延迟接受最中意女子的“求婚”。这一方法获称“盖尔-沙普利运算法则”，又称“延迟接受运算法则”。

以上背景描述来源于百度百科。

二、场景描述

假设有10个男生和10个女生，已知每个男生对每个女生的喜欢程度排序，以及每个女生对每个男生的喜欢程度排序。我们分别用一个二维数组来表示男生和女生，如下：
男生：
1 4 3 6 2 5 8 7 9 0
2 1 0 3 4 8 5 9 7 6
4 3 8 9 0 2 1 7 6 5
2 7 6 1 4 3 8 0 9 5
5 3 8 4 2 0 7 6 1 9
5 0 1 7 2 8 9 4 6 3
6 2 9 8 0 7 5 1 4 3
9 7 1 8 0 2 5 6 3 4
8 0 5 9 6 7 1 2 4 3
7 9 1 6 2 0 5 8 4 3
女生：
3 5 0 6 9 4 8 7 2 1
0 1 3 2 7 8 5 9 4 6
1 0 7 9 3 2 5 8 6 4
2 0 6 3 4 1 5 7 9 8
5 6 8 3 2 0 9 4 1 7
3 0 1 7 9 8 2 4 6 5
6 2 7 8 0 9 4 1 5 3
9 3 1 2 0 7 5 6 8 4
4 1 5 9 6 7 0 2 8 3
6 0 1 7 2 9 5 8 4 3

其中每行表示这个男/女生对于全部女/男生的一个喜好程度排序排列，比如第一行的这个男生是1 4 3 6 2 5 8 7 9 0 ，则表示他是喜欢1号女生、其次是4号，再是3号……最后才是0号女生。

求出最为妥当的男女配对方案。比如从上面的数据中，第二个男生（索引为1，表示第1号）的喜好程度排序列表是2 1 0 3 4 8 5 9 7 6，表示最喜欢第2号女生，而第2号女生的喜好列表是1 0 7 9 3 2 5 8 6 4，刚好她最喜欢的是第1号男生。那么既然他们彼此是最喜欢的，应该要为他们搭桥牵线，成全他们。而对于其他种情况，则尽可能的让男生匹配到他更喜欢的女生，同时匹配到的这个女生也是相对来说比较喜欢这个男生的，之所以用“相对”这个词，是因为由于大家有各自的喜好程度排序，不可能匹配到的双方都一定是相互很喜欢的，只能说从一个最大的彼此喜欢程度排序上来做出匹配。由于最后每个人都会匹配到一个伴，不会存在有人匹配成功，有人找不到伴的情况。所以这个是一种稳定的匹配策略，因此也称之为“稳定婚姻匹配算法”。

三、算法设计

1、首先获取男女生的喜好程度排序列表到二维数组里P_m和P_w，并且创建两个数组M_m和M_w分别储存男生和女生的婚姻配对情况。把这两个数组初始化为-1，-1表示没有配对；

2、从M_m里获取第一个还没配对的男生M，记录索引为i。如果取不出男生，即i=-1的话，说明全部已经配对好了，那么跳到第8步；

3、从P_m[i]里取出男生的喜好列表里的第W(j)个女生（j初始化为0）；

4、如果取出的这个女生W(j)还没配对过，那么他们就可以完成配对；

5、如果该女生W(j)是配对过的了，那么从M_w[j]中取出与这个女生配对的那个男生m，记录索引为i2，跟现在要匹配的男生M进行喜好程度排序的比较，如果说M在m前面，也就是表示对于男生m来说，女生更喜欢的是男生M，那么则把女生的配对结果M_w[j]改为与男生M配对，即让M_w[j]=i，同时男生M配对了女生W(j)，即让P_m[i]=j。而男生m则暂时沦落为单身狗，P_m[i2]被设置为-1，表示没有匹配；

6、如果说女生更喜欢的是男生m，就拒绝了这个男生M。那么男生M就对这个女生没戏了，只能在他的喜好列表P_m[i]里找第j+i个女生(前面喜欢的女生被抢走了，只能考虑后面喜欢的女生咯)，把j = j+1后，跳到前面的第3步；

7、经过前面3-6步的操作后，这个男生M就算配对完了，在他配对成功后，有可能其他已经配对过的男生就被踢出来了。不过我们不用关心是哪个被踢出来，只要再继续循环第2步查询第一个没有配对过的男生，对他进行配对就行了。所以，我们跳到第2步去；

8、会到达这一步说明全部男生是已经配对好的了，表示全部男女生已经配对完毕，我们把匹配结果进行输出。

经过上面的步骤，我们就完成了稳定匹配。可能有读者提出对于第8步的疑问，第8步说了全部男生已经配对好，表示全部男女生已经配对完毕，怎么能知道女生也全部有配对了呢。我们在核心的第4-6部=步中可以看出来，每个男生匹配到的女生都是与其他男生不同的，因为如果相同的话则会计算这两个男生在女生心中的喜好程度排序，从而得出一个男生，而踢掉另外一个，所以最终配对结果不可能存在有多个男生同时配对到同个女生、或者是多个女生同时配对到一个男生的情况。另外，为什么说是稳定的呢？不稳定婚姻是说比如M1与W1匹配了，但是M1却更喜欢W2，而M2与W2匹配了，但是M2却更喜欢W1，这种情况下称之为不稳定婚姻，因为男生没有找到其实自己喜欢的女生，而这女生也比较喜欢自己。在这个算法中，不存在这个问题，因为男生都会优先去选取他最喜欢的女生，而如果女生已经匹配过了的话，则会考虑是不是要换人。比如这里M2与W2虽然匹配了，但是因为M1更喜欢W2，而W2也是比较喜欢M1的，那么W2会果断接受M1而拒绝了M2。所以不存在婚姻的不稳定。

四、算法的实现

经过上面的算法分析，其实也不难写出对应的代码了。在这里我采用的是C++代码，语言不重要，相信不了解C++的读者只有有语言基础的话，也可以根据算法分析而读懂代码流程。
我先讲解一下代码流程，然后再贴出全部实现代码。

首先，我们定义一个Marriage类，有以下成员变量：

    int no_of_couples;vector <vector <int> > Preference_of_men;vector <vector <int> > Preference_of_women;vector <int> match_for_men;vector <int> match_for_women;

no_of_couples表示婚姻数量，Preference_of_men和Preference_of_women分别表示的是男/女生的喜好程度排序列表，对应上文的算法分析中的P_m和P_w。

match_for_men和match_for_women则是存储了每个男/女生配对的女/男生，对应上文的算法分析中的M_m和M_w。

我们先写出读取文本中的喜好程度排序数据：

  // fill the necessary code here.  The first entry in the input// file is the #couples, followed by the preferences of the men// and preferences of the women.  Keep in mind all indices start// from 0.void read_data(){int value_just_read_from_file;int value;int i=0,j=0;vector <int> *v; ifstream input_file("input.txt");if (input_file.is_open()){input_file >> no_of_couples;for(i=0;i<no_of_couples;i++){v = new vector<int>();for(j=0;j<no_of_couples;j++){input_file >> value;//  cout<<value<<endl;v->push_back(value);}Preference_of_men.push_back(*v);}for(i=0;i<no_of_couples;i++){v = new vector<int>();for(j=0;j<no_of_couples;j++){input_file >> value;v->push_back(value);}Preference_of_women.push_back(*v);}}else{std::cout << "Input file  does not exist" << endl;}}

读取的源码很简单，就是文本中的第一个数据表示的是婚姻数量，读取给了no_of_couples，然后再分别读取男生和女生的喜好程度排序列表。

在算法实现之前，我们先来完成两个函数的封装：
由于我们需要取出没有配对过的男生，所以封装一个函数，来遍历得得到第一个没配对的，返回一个索引：

  //取出第一个没有配对过的 int first_No_Marriage(vector <int> my_array){// fill the necessary code for this functionint i;for(i = 0;i<my_array.size();i++){if(my_array[i]==-1){return i;}}return -1;}

其次，我们在步骤中谈到需要比较女生列表中两个男生的喜好排名，我们封装一个函数，来得到男生1对男生2是否排在前面：

  //计算索引排名，如果index1是排在index2前面则返回true，否则返回false bool rank_check (vector <int> my_array, int index1, int index2){int i;for(i = 0;i<my_array.size();i++){if(my_array[i]==index1){return true;}else if(my_array[i]==index2){return false;}}return false;}

核心的稳定匹配算法代码如下：

void Gale_Shapley(){int man_index, woman_index;int index = 0;// 初始化为-1，表示没有匹配 for (int i= 0; i < no_of_couples; i++){match_for_men.push_back(-1);match_for_women.push_back(-1);}// Gale-Shapley Algorithm//循环取出没有配对的男生 while ( (man_index = first_No_Marriage(match_for_men)) >= 0){index = 0;//循环读取该男生的喜好列表里的女生 while(index<no_of_couples){//得到男生喜好的第index个女生 woman_index = Preference_of_men[man_index][index];//如果该女生还没匹配 ，则双方配对 if(match_for_women[woman_index]==-1){match_for_men[man_index] = woman_index;match_for_women[woman_index] = man_index;break;//如果女生已经配对了，则比较一下两个男生在女生的喜好列表中的排名，如果该男生更受这名女生喜欢，则替换该女生的配对男生 }else if(rank_check(Preference_of_women[woman_index],man_index,match_for_women[woman_index])){//踢掉原先配对的男生 match_for_men[match_for_women[woman_index] ] = -1;//重新配对这名男生 match_for_women[woman_index] = man_index;//这名男生也配对这名女生 match_for_men[man_index] = woman_index;break;//如果已经配对但是没有更受女生喜好的话，则继续探索男生列表里下一个喜欢的女生 }else{index++;}}}}

以上从每一步的注释中也说得比较明白了，相信读者不会看不清楚吧。

最后我们按照一定的格式输出男女生的喜好列表以及配对情况：

  void print_soln(){int j;std::cout << "Number of Couples:" << no_of_couples << endl;std::cout << "Preference for Men" <<endl;std::cout << "------------------"<<endl;for (int i=0;i<no_of_couples;i++){std::cout << "(" << i << "):" ;for(j=0;j<no_of_couples;j++){std::cout <<Preference_of_men[i][j]<<" ";}std::cout <<endl;}std::cout << "Preference for WoMen" <<endl;std::cout << "------------------"<<endl;for (int i=0;i<no_of_couples;i++){std::cout << "(" << i << "):" ;for(j=0;j<no_of_couples;j++){std::cout <<Preference_of_women[i][j]<<" ";}std::cout <<endl;}std::cout << "Matching  for Men" <<endl;for (int i=0;i<no_of_couples;i++){std::cout << "Man:" << i << "-> Woman:"<<match_for_men[i]<<endl ;}std::cout <<endl;std::cout << "Matching  for Wowan" <<endl;for (int i=0;i<no_of_couples;i++){std::cout << "Wowan:" << i << "-> man:"<<match_for_women[i] <<endl;}std::cout <<endl;}

文本的数据如下：

全部代码如下：

#include <iostream>
#include <vector>
#include <fstream>using namespace std;class Marriage
{// Privateint no_of_couples;vector <vector <int> > Preference_of_men;vector <vector <int> > Preference_of_women;vector <int> match_for_men;vector <int> match_for_women;//取出第一个没有配对过的  int first_No_Marriage(vector <int> my_array){// fill the necessary code for this functionint i;for(i = 0;i<my_array.size();i++){if(my_array[i]==-1){return i;}}return -1;}//计算索引排名，如果index1是排在index2前面则返回true，否则返回false bool rank_check (vector <int> my_array, int index1, int index2){int i;for(i = 0;i<my_array.size();i++){if(my_array[i]==index1){return true;}else if(my_array[i]==index2){return false;}}return false;}void Gale_Shapley(){int man_index, woman_index;int index = 0;// 初始化为-1，表示没有匹配 for (int i= 0; i < no_of_couples; i++){match_for_men.push_back(-1);match_for_women.push_back(-1);}// Gale-Shapley Algorithm//循环取出没有配对的男生 while ( (man_index = first_No_Marriage(match_for_men)) >= 0){index = 0;//循环读取该男生的喜好列表里的女生 while(index<no_of_couples){//得到男生喜好的第index个女生 woman_index = Preference_of_men[man_index][index];//如果该女生还没匹配 ，则双方配对 if(match_for_women[woman_index]==-1){match_for_men[man_index] = woman_index;match_for_women[woman_index] = man_index;break;//如果女生已经配对了，则比较一下两个男生在女生的喜好列表中的排名，如果该男生更受这名女生喜欢，则替换该女生的配对男生 }else if(rank_check(Preference_of_women[woman_index],man_index,match_for_women[woman_index])){//踢掉原先配对的男生 match_for_men[match_for_women[woman_index] ] = -1;//重新配对这名男生 match_for_women[woman_index] = man_index;//这名男生也配对这名女生 match_for_men[man_index] = woman_index;break;//如果已经配对但是没有更受女生喜好的话，则继续探索男生列表里下一个喜欢的女生 }else{index++;}}}}void read_data(){int value_just_read_from_file;int value;int i=0,j=0;vector <int> *v; ifstream input_file("input.txt");if (input_file.is_open()){input_file >> value_just_read_from_file;no_of_couples= value_just_read_from_file;for(i=0;i<no_of_couples;i++){v = new vector<int>();for(j=0;j<no_of_couples;j++){input_file >> value;//  cout<<value<<endl;v->push_back(value);}Preference_of_men.push_back(*v);}for(i=0;i<no_of_couples;i++){v = new vector<int>();for(j=0;j<no_of_couples;j++){input_file >> value;v->push_back(value);}Preference_of_women.push_back(*v);}}else{std::cout << "Input file  does not exist" << endl;}}void print_soln(){int j;std::cout << "Number of Couples:" << no_of_couples << endl;std::cout << "Preference for Men" <<endl;std::cout << "------------------"<<endl;for (int i=0;i<no_of_couples;i++){std::cout << "(" << i << "):" ;for(j=0;j<no_of_couples;j++){std::cout <<Preference_of_men[i][j]<<" ";}std::cout <<endl;}std::cout << "Preference for WoMen" <<endl;std::cout << "------------------"<<endl;for (int i=0;i<no_of_couples;i++){std::cout << "(" << i << "):" ;for(j=0;j<no_of_couples;j++){std::cout <<Preference_of_women[i][j]<<" ";}std::cout <<endl;}std::cout << "Matching  for Men" <<endl;for (int i=0;i<no_of_couples;i++){std::cout << "Man:" << i << "-> Woman:"<<match_for_men[i]<<endl ;}std::cout <<endl;std::cout << "Matching  for Wowan" <<endl;for (int i=0;i<no_of_couples;i++){std::cout << "Wowan:" << i << "-> man:"<<match_for_women[i] <<endl;}std::cout <<endl;}public:void solve_it(){read_data();Gale_Shapley();print_soln();}
};int main()
{Marriage x;x.solve_it();return 0;
}