稳定婚姻问题和延迟认可算法作者：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++）来遍历数组的，所以如果当 tusing 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 i) //前男友序号 t 在新男友 i 之后，则今后顺序前行可以处理 t i++; //处理下一个男士else //前男友序号 t 在新男友 i 之前，返回 t，否则会漏掉 ti = t; } else //继续处理 i 号男的“次喜欢女” man[i]++;}for (int i=0; i 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 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=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 = 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