稳定婚姻问题和延迟认可算法
作者：goal00001111 （高粱）
始发于goal00001111 的专栏；允许自由转载，但必须注明作者和出处
摘要：延迟认可算法（Gale-Shapley算法）是解决稳定婚姻问题的经典算法，本文用C++来实现Gale-Shapley算法。文章详细介绍了Gale-Shapley算法的原理和编码思路，给出了一个直接从原理出发的原始算法及其改进版本，并对两个版本进行了比较分析。
关键词：稳定婚姻问题 延迟认可算法 二维数组 以空间换时间
稳定婚姻问题
问题来自于一场“3分钟相亲”活动，参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流，并为她们打分，然后按照喜欢程度，对每一位女士进行排序；同样的，每位女士也要对所有男士进行打分和排序。
作为活动的组织者，当你拿到这些数据后，该如何为男，女士们配对，才能使大家皆大欢喜，组成稳定的婚姻呢？
插一句：什么样的婚姻才能称为稳定的婚姻呢？
所谓稳定的婚姻，就是指男女结婚后，双方都不会发生出轨行为。
那怎样才能做到双方都不出轨呢？
如果双方都是对方的最爱，自然不会出轨；如果有一方或双方都不是对方的最爱，则必须保证想出轨的人找不到出轨的对象。例如，男子i认为其妻子不是自己的最爱，他更爱的人是j女士，可是j女士认为自己的丈夫比男子i强，则不会选择与男子i出轨；另外有k女士很喜欢男子i，可是男子i又觉得她不如自己的现任妻子，所以也不会选择和k女士出轨。这样男子i就找不到与之出轨的对象了；同理，如果他的妻子也找不到出轨对象的话，他们的婚姻就是稳定的。
简言之，只要满足“除妻子（丈夫）外，我爱的人不爱我，爱我的人我不爱”条件，就可形成稳定的婚姻。
回到我们的问题：如何让所有参加相亲活动的男女都组成各自的“稳定婚姻”?
1962 年，美国数学家 David Gale 和 Lloyd Shapley 发明了一种寻找稳定婚姻的策略，人们称之为延迟认可算法（Gale-Shapley算法）。
先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：
① 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
② 每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。
③ 若某男士被其女友抛弃，重新变成自由男。
在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利——当然，新的追求对象比不过前女友。
这样，在算法执行期间，每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱，从一而终——每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。
本文用C++来实现Gale-Shapley算法，采用男士主动求爱，女士接受求爱的方式。
假设男女生人数均为MAX，对每位男士和女士均进行编号，用自然数0,1,2，。。。，MAX-1表示其序号（依照C++的习惯，序号从0开始）。
用二维数组liMan[MAX][MAX]来存储男士所喜欢的女士序号的排列表；同理，用二维数组libLady[MAX][MAX+1]来存储女士所喜欢的男士序号的排列表，例如v号女最喜欢i号男，则libLady[v][0] = i；若t号男比i号男更招v号女喜欢，则在数组libLady[v][]中，元素值t的下标小于元素值i的下标。
为了简化算法，增加一个“不存在”的男士（序号为MAX），作为女士最初的选择。在给二维数组libLady[MAX][MAX+1]赋初值时，对于任意一个女士v，总有libLady[v][MAX] = MAX。
为所有的男士（包括那个 “不存在”的）建立一个数组man[MAX+1]，用来存储他们追求女士的次数，i号男目前追求的女士序号为libMan[i][man[i]]。
例如，man[i]=0表示i号男尚未追求过女士，其所追求的女士序号为libMan[i][0]；man[i]=2表示i号男已经追求过两位女士，他下次追求的女士序号为libMan[i][2]（即在喜好表中排名第3位的女士）。
很明显，man[MAX+1]的每个元素初始值均为0，表示刚开始时，每位男士都去追求自己最喜欢的女士，man[i]值越大，男士对所选择的女士越不满意。
为所有的女士建立一个数组lady[MAX]，用来存储她所选择的男士序号，数组的所有元素初始值均为MAX，表示女士的当前男友为一个“不存在”的男士，他的分值比任何男士都低，以保证当有一个真正的男人追求该女士时，她会毫不犹豫的抛弃MAX，而选择该男子。
我们遍历数组man[MAX+1]，依次让每个男士去追求自己心仪的女士（当然不需要处理元素man[MAX]——那个“不存在”的男人）。例如现在正逢i号男追求v号女，若i号男不如v号女当前男友，则遭拒绝，i号男继续追求其“次喜欢女”；反之，若i号男比v号女当前男友优秀，则v抛弃前男友，选择i号男为新男友，而其前男友（设为t号男）重获自由身，可以去追求自己的“次喜欢女”了。
这里有一个地方要注意：因为我们是通过执行（i++）来遍历数组的，所以如果当t<i时，必须要让i折回到t位置（使i=t)，否则会漏掉t。
当i == MAX时，表示所有男士都找到了自己的另一半，算法结束，输出结果。
C++代码如下：
#include <iostream>
using namespace std;
const int MAX = 4;
bool ChangeFriend(const int libLady[][MAX+1], int v, int oldF, int newF);//判断是否需要换男友
int main()
{
int libMan[MAX][MAX] = {{2,1,3,0},{0,2,3,1},{2,3,1,0},{1,3,2,0}};//存储男士所喜欢的女士序号的排列表
int libLady[MAX][MAX+1] = {{0,3,1,2,MAX},{1,3,2,3,MAX},{0,2,3,1,MAX},{1,0,3,2,MAX}};//存储女士所喜欢的男士序号的排列表
int man[MAX+1] = {0};
int lady[MAX] = {MAX,MAX,MAX,MAX};
int i = 0;
while (i < MAX )
{
int v = libMan[i][man[i]]; //i号男喜欢v号女
if (i == lady[v]) //i号男就是v号女当前男友，跳过，处理下一个男士
i++;
else if (ChangeFriend(libLady, v, lady[v], i)) //若i号男比v号女当前男友优秀，则v抛弃前男友，重新选择i
{
int t = lady[v]; //存储前男友序号
man[lady[v]]++; //抛弃前男友，即前男友选择其“次喜欢女”
lady[v] = i; //选择i号男为新男友
if (t > i) //前男友序号t在新男友i之后，则今后顺序前行可以处理t
i++; //处理下一个男士
else //前男友序号t在新男友i之前，返回t，否则会漏掉t
i = t;
}
else //继续处理i号男的“次喜欢女”
man[i]++;
}
for (int i=0; i<MAX; i++)//输出每位男士追求女士的次数
cout << man[i] + 1 << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//输出每位男士的妻子的序号
cout << libMan[i][man[i]] << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//输出每位女士的丈夫的序号
cout << lady[i] << ", ";
cout << endl;
system("pause");
return 0;
}
bool ChangeFriend(const int libLady[][MAX+1], int v, int oldF, int newF)//判断是否需要换男友
{
for (int i=0; i<=MAX; i++)
{
if (libLady[v][i] == oldF)
{
oldF = i;
break;
}
}
for (int i=0; i<=MAX; i++)
{
if (libLady[v][i] == newF)
{
newF = i;
break;
}
}
return (oldF > newF);
}
在上述实现中，我设计了一个子函数bool ChangeFriend(const int libLady[][MAX+1], int v, int oldF, int newF)，用来判断女士v是否需要换男友，若男子序号newF在数组libLady[v][i]的位置比oldF靠前，则说明女士v更喜欢newF，需要换男友，否则不换。通过比较它们的下标，可以得出结论。
这个子函数的引入可以让程序完成工作，但也带来一些效率上问题，每次调用函数都要分别遍历数组libLady[v][]两次，去寻找oldF和newF的下标，这样在MAX值很大的时候，时间消耗是相当大的。
另外，由于我们是通过执行（i++）来遍历数组，每次遇到(t < i)时，都要令i折回到t，然后再执行（i++），进行了很多重复的比较，浪费了宝贵的时间。
那么，如何改进代码，解决上述两个问题？
首先解决关于子函数的问题。之所以引入子函数，是因为数组libLady[v][]存储的是女士v所喜欢的男士序号的排列表，而不是男士的分值表。如果我们创建一个二维数组libladyValue[MAX][MAX+1]，用来存储女士v所喜欢的男士的分值，即数组元素libladyValue[v][i]表示女士v给i号男打的分数，分数越高，则表示越招人喜欢。这样我们在判断女士v是否需要换男友时，就无需遍历数组，只要直接比较libladyValue[v][i]和libladyValue[v][t]的值就好了。
其次解决重复比较的问题。我们可以创建一个栈，把所有自由男的序号存储到栈中，每当有男子订婚，则将其序号出栈；每当有男子被抛弃，则将其序号入栈。这样就可以确保不会出现重复比较了。
在解决上述两个问题的时候，我都采用了“以空间换时间”的策略，小小的自夸一下，呵呵！
改进后的C++代码如下：
#include <iostream>
using namespace std;
const int MAX = 4;
int main()
{
int libMan[MAX][MAX] = {{2,1,3,0},{0,2,3,1},{2,3,1,0},{1,3,2,0}};//存储男士所喜欢的女士序号的排列表
int libLady[MAX][MAX+1] = {{0,3,1,2,MAX},{1,3,2,3,MAX},{0,2,3,1,MAX},{1,0,3,2,MAX}};//存储女士所喜欢的男士序号的排列表
int libladyValue[MAX][MAX+1] = {0};
for (int i=0; i<MAX; i++) //把女士喜好的男士序号的排列表转换为男士分值表
{
for (int j=MAX, k=0; j>=0; j--,k++)
{
libladyValue[i][libLady[i][j]] = k;
}
}
int man[MAX+1] = {0};//存储各个男士追求女士的次数
int lady[MAX] = {MAX,MAX,MAX,MAX};//序号初始值MAX表示一个“不存在”的男士，即其分值比任何男士都低
int S[MAX] = {0};//一个栈，用来存储所有自由男的序号
int top = 0;
while (top < MAX) //把所有自由男的序号存储到栈中
S[top] = top++;
top--; //top指向栈顶
while (top >= 0)//让自由男主动去追求自己喜欢的女士，直到所有的人都配对
{
int v = libMan[S[top]][man[S[top]]]; //处在栈顶（序号为S[top]）的男士喜欢v号女
if (libladyValue[v][lady[v]] < libladyValue[v][S[top]]) //若栈顶男比v号女当前男友优秀，则 v抛弃前男友，接受栈顶男
{
int t = lady[v]; //存储前男友序号
man[t]++; //抛弃前男友，即前男友选择其“次喜欢女”
lady[v] = S[top--]; //选择栈顶男为新男友，同时栈顶男出栈
if (t != MAX) //如果t号男不是那个“不存在”的男士
S[++top] = t; //t号男作为新的栈顶男
}
else //栈顶男追求下一号目标
man[S[top]]++;
}
for (int i=0; i<MAX; i++)//输出每位男士追求女士的次数
cout << man[i] + 1 << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//输出每位男士的妻子的序号
cout << libMan[i][man[i]] << ", ";
cout << endl;
for (int i=0; i<MAX; i++)//输出每位女士的丈夫的序号
cout << lady[i] << ", ";
cout << endl;
system("pause");
return 0;
}
参考文献：
（1） matrix67的博客 《[0]引言 什么是算法 如何寻找稳定的婚姻搭配》
http://www.matrix67.com/blog/archives/2976
（2） 孙 劼的博客 《稳定婚姻问题和延迟认可算法》
http://intowater.spaces.live.com/Blog/cns!1pe4f-ndtin3u1qQCckqiIWQ!949.entry