本节利用舞伴问题介绍一个Gale-Shapley算法的应用实例。舞伴问题是这样的：有 n 个男孩与 n 个女孩参加舞会，每个男孩和女孩均交给主持一个名单，写上他（她）中意的舞伴名字。无论男孩还是女孩，提交给主持人的名单都是按照偏爱程度排序的，排在前面的都是他们最中意的舞伴。试问主持人在收到名单后，是否可以将他们分成 n 对，使每个人都能和他们中意的舞伴结对跳舞？为了避免舞会上出现不和谐的情况，要求这些舞伴的关系是稳定的。 假如有两对分好的舞伴：（男孩A，女孩B）和（男孩B，女孩A），但是男孩A更偏爱女孩A，女孩A也更偏爱男孩A，同样，女孩B更偏爱男孩B，而男孩B也更偏爱女爱B。在这种情况下，这两对舞伴就倾向于分开，然后重新组合，这就是不稳定因素。很显然，这个问题需要的是一个稳定匹配的结果，适合使用Gale-Shapley算法。 7.2.1 算法实现 首先定义舞伴的数据结构，根据题意，一个舞伴至少要包含两个属性，就是每个人的偏爱舞伴列表和他（她）们当前选择的舞伴。根据Gale-Shapley算法的规则，还需要有一个属性表示下一次要向哪个偏爱舞伴提出跳舞要求。当然，这个属性并不是男生和女生同时需要的，当使用“男士优先”策略时，男生需要这个属性，当使用“女士优先”策略时，女生需要这个属性。为了使程序输出更有趣味，需要为每个角色提供一个名字。综上所述，舞伴的数据结构定义如下： typedef struct tagPartner { char *name; //名字 int next; //下一个邀请对象 int current; //当前舞伴，-1表示还没有舞伴 int pCount; //偏爱列表中舞伴个数 int perfect[UNIT_COUNT]; //偏爱列表 }PARTNER; UNIT_COUNT是男孩或女孩的数量（稳定匹配问题总是假设男孩和女孩的数量相等），pCount是偏爱列表中的舞伴个数。根据标准的“稳定婚姻问题”的要求，pCount的值应该是和UNIT_COUNT一致的，但是某些情况下（比如一些算法比赛题目的特殊要求）也会要求伙伴们提供的偏爱列表可长可短，因此我们增加了这个属性。但是有一点需要注意，如果允许舞伴的pCount小于UNIT_COUNT，则7.1.2节的证明就不适用了，需要设置相应的条件并使用更复杂的证明方法。关键是，最后不一定能得到稳定匹配的结果。这里给出的实现算法使用数组来存储参加舞会的男孩和女孩列表，因此这个数据结构中的next、current和perfect列表中存放的都是数组索引，了解这一点有助于理解算法的实现代码。 Gale-Shapley算法的实现非常简单，将7.1.2节给出算法伪代码翻译成编程语言即可。完整的算法代码如下： bool Gale_Shapley(PARTNER *boys, PARTNER *girls, int count) { int bid = FindFreePartner(boys, count); while(bid >= 0) { int gid = boys[bid].perfect[boys[bid].next]; if(girls[gid].current == -1) { boys[bid].current = gid; girls[gid].current = bid; } else { int bpid = girls[gid].current; //女孩喜欢bid胜过其当前舞伴bpid if(GetPerfectPosition(&girls[gid], bpid) > GetPerfectPosition(&girls[gid], bid)) { boys[bpid].current = -1; //当前舞伴恢复自由身 boys[bid].current = gid; //结交新舞伴 girls[gid].current = bid; } } boys[bid].next++; //无论是否配对成功，对同一个女孩只邀请一次 bid = FindFreePartner(boys, count); } return IsAllPartnerMatch(boys, count); } FindFreePartner()函数负责从男孩列表中找一个还没有舞伴、并且偏好列表中还有没有邀请过的女孩的男孩，返回男孩在列表（数组）中的索引。如果返回值等于1，表示没有符合条件的男孩了，于是主循环停止，算法就结束了。GetPerfectPosition()函数用于判断女孩喜欢一个舞伴的程度，通过返回舞伴在自己的偏爱列表中的位置来判断，位置越靠前，也就是GetPerfectPosition()函数的返回值越小，说明女孩越喜欢这个舞伴。GetPerfectPosition()函数的实现代码如下： int GetPerfectPosition(PARTNER *partner, int id) { for(int i = 0; i < partner->pCount; i++) { if(partner->perfect[i] == id) { return i; } } //返回一个非常大的值，意味着根本排不上对 return 0x7FFFFFFF; } 按照“稳定婚姻问题”的要求，这个函数应该总是能够得到ID指定的异性舞伴在partner的偏爱列表中的位置，因为每个partner的偏爱列表包含所有异性舞伴。但是当题目有特殊需求时，partner的偏爱列表可能只有部分异性舞伴。比如partner非常恨一个人，他们绝对不能成为舞伴，那么partner的偏爱列表肯定不会包含这个人。考虑到算法的通用性，GetPerfectPosition()函数默认返回一个非常大的数，返回这个数这意味着ID指定的异性舞伴在partner的偏爱列表中根本没有位置（非常恨），根据算法的规则，partner最不喜欢的异性舞伴的位置都比id指定的异性舞伴位置靠前。这也是算法一致性处理的一个技巧，GetPerfectPosition()函数当然可以设计成返回1表示ID指定的异性舞伴不在partner的偏爱列表中，但是大家想一想，算法中是不是要对这个返回值做特殊处理？原来代码中判断位置关系的一行代码处理： if(GetPerfectPosition(&girls[gid], bpid) > GetPerfectPosition(&girls[gid], bid)) 就会变得非常繁琐，让我们看看会是什么情况： if((GetPerfectPosition(&girls[gid], bpid) == -1) && (GetPerfectPosition(&girls[gid], bid) == -1)) { //当前舞伴bpid和bid都不在女孩的喜欢列表中，太糟糕了 ... } else if(GetPerfectPosition(&girls[gid], bpid) == -1) { //当前舞伴bpid不在女孩的喜欢列表中，bid有机会 ... } else if(GetPerfectPosition(&girls[gid], bid) == -1) { //bid不在女孩的喜欢列表中，当前舞伴bpid维持原状 ... } else if(GetPerfectPosition(&girls[gid], bpid) > GetPerfectPosition(&girls[gid], bid)) { //女孩喜欢bid胜过其当前舞伴bpid ... } else { //女孩喜欢当前舞伴bpid胜过bid ... } 这是我最不喜欢的代码逻辑，真的，太糟糕了。可见，这个小小的技巧为代码的逻辑处理带来了极大的好处。类似的技巧被广泛应用，在排序算法中经常使用“哨兵”位，避免每次都要判断是否比较完全部元素。面向对象技术中常用的“Dummy Object”技术，也是类似的思想。 Gale-Shapley算法原来如此简单，你是不是为沙普利能获得诺贝尔奖愤愤不平？其实不然，算法原理的简单并不等于其解决的问题也简单，本书介绍的很多算法都是如此，小算法解决大问题。 7.2.2 改进优化：空间换时间 Gale_Shapley()函数给出的算法还有点问题，主要是GetPerfectPosition()函数的策略，这个函数每次都要遍历partner的偏爱舞伴列表才能确定bid的位置，很可能导致理论上时间复杂度为O(n2)的算法在实际实现时变成O(n3)的时间复杂度。为了避免算法在多轮选择过程中频繁遍历每个partner的偏爱舞伴列表，需要对partner到底更偏爱哪个舞伴的判断策略进行改进。 改进的原则就是“以空间换时间”。简单来讲，以空间换时间的方法就是用一张事先初始化好的表存储这些位置关系，在使用个过程中，以O(1)时间复杂度的方式直接查表确定偏爱舞伴的关系。这样的表可以是线性表，也可以是哈希表这样的映射表。对于这个问题，我们选择使用二维表来存储这些位置关系。假设存在二维表priority[n][n]，我们用priority[w][m]表示m在w的偏爱列表中的位置，这个值越小，表示m在w的偏爱列表中的位置越靠前。在算法开始之前，首先初始化这个关系表： for(int w = 0; w < UNIT_COUNT; w++) { //初始化成最大值，原理同上 for(int j = 0; j < UNIT_COUNT; j++) { priority[w][j] = 0x7FFFFFFF; } //给偏爱舞伴指定位置关系 int pos = 0; for(int m = 0; m < girls[w].pCount; m++) { priority[w][girls[w].perfect[m]] = pos++; } } 最后，将对GetPerfectPosition()函数的调用替换成查表: if(priority[gid][bpid] > priority[gid][bid]) 对于一些在算法执行过程中不会发生变化的静态数据，如果算法执行过程中需要反复读取这些数据，并且读取操作存在一定时间开销的场合，比较适合使用这种“以空间换时间”的策略。用合理的方式组织这些数据，使得数据能够在O(1)时间复杂度内实现是这种策略的关键。对本问题应用“以空间换时间”的策略，需要在算法开始的准备阶段初始化好priority二维表，这需要一些额外的开销，但是相对于n2次查询节省的时间来说，这点开销是能够容忍的。 “以空间换时间”也是算法设计常用的技巧，在很多算法中都有应用。比如本书第15章介绍的快速傅里叶变换算法，经过蝶形变换后每个点的数据位置都发生了变化，需要将这些点的位置还原。可以利用一个二重循环将这些错位的数据还原，也可以利用蝶形变换的位置变换关系表，采用查表的方式将两个错位的数据交换位置，后者采用的就是“以空间换时间”的策略。