当参加舞会的男孩和女孩按照一定的顺序排好队，位置固定之后，使用Gale-Shapley算法能够得到一个确定的稳定匹配结果。但是对这群男孩和女孩来说，稳定匹配的结果肯定不是唯一的，其实只要将计算策略从“男士优先”转换成“女士优先”，就可以得到另外一个完全不同的稳定匹配结果。同样，调整一下男孩们的位置顺序，比如让最后一个男孩排在第一的位置，让他第一个邀请女孩，则Gale-Shapley算法也可以得到一个完全不同的稳定匹配结果。 很显然，对于任意情况下的n个男孩和n个女孩来说，肯定有多个稳定匹配，那么，到底有多少个稳定匹配？稳定匹配首先必须是完美匹配，而且稳定匹配的个数小于或等于完美匹配，所以，我们可以先从理论上计算一下完美匹配的数量，估算一下问题的规模，然后再决定是否能用算法找出全部的稳定匹配。从理论上分析，只要每个人的偏爱列表都包含全部异性舞伴，那么完美匹配的个数就可以通过公式计算出来。首先，假设男孩们已经排好了队，准备按照顺序邀请女孩跳舞，在不考虑稳定匹配的情况下，每个男孩选择一个女孩之后，还没有舞伴的女孩的总数就减1，剩下的男生的可选范围就变小了。第一个男孩选择的可能情况是 ，第二个男孩可能的选择就只有 种。以此类推，可以计算出完美匹配的可能情况是M = … = n!种。如果仅仅从排列组合问题的角度考虑舞伴问题，随着男孩们的顺序变化，这个数字会成倍增加。那么男孩们有多少种顺序变化呢？n个男孩全排列，结果也是n!( )种变化，因此最终的结果应该是(n!)2。但是舞伴问题并不是单纯的排列组合问题，因为这些男孩和女孩之间通过各自的偏爱列表建立了某种联系，这使得一些组合结果实际上是没有意义的重复。举个例子说明一下，假如m在第一轮选择，他选择w作为舞伴，m'在第二轮选择，他选择w'作为舞伴。现在转换一下选择顺序，改为m'在第一轮选择，但是m'的偏爱列表中，w'排在前面，于是m'仍然选择w'作为舞伴，m也只能选择w作为舞伴，虽然选择的顺序变了，但是结果和前一次一样。 由此看来，虽然对男孩的选择顺序进行全排列有n!种可能，但是这n!种选择顺序最终得到的匹配结果都只是n!种结果的重复出现，实际的完美匹配只有n!种。接下来我们要给出的穷举算法也验证了这一点，对于3个男孩和3个女孩的情况，穷举算法得到了36（3!×3!=36）个完美匹配结果，排除掉重复结果后得到6（3×2×1=6）个结果。对于4个男孩和4个女孩的情况，穷举算法得到了576（4!×4!=576）个完美匹配结果，排除掉重复结果后得到24（4×3×2×1=24）个结果。 7.3.1 穷举所有的完美匹配 如果想知道到底有多少个稳定匹配，首先要知道有多少个完美匹配。具体的方法就是使用穷举的方法找到全部的完美匹配，然后根据条件将包含不稳定因素的完美匹配过滤掉，剩下的就是稳定匹配。遵循这个原则，我们先来研究一下穷举所有完美匹配的算法。 穷举算法的数据结构定义仍然沿用7.2.1节算法实现中使用的PARTNER定义，只是next属性用不上。穷举的方法就是每次为一个男孩选择一个舞伴，选择的方法就是从男孩的偏爱列表中找一个还没有舞伴的女孩，确定为这个男孩的舞伴，同时将男孩和女孩对应的PARTNER定义中的current属性指向对方。判断一个女孩是否已经有舞伴的方法就是判断她的current属性是否是1，如果不是1就说明这个女孩已经有舞伴了。按照男孩的顺序逐个为他们选择舞伴，当最后一个男孩也确定了舞伴之后，就得到了一个完美匹配，可以打印这个结果，用于检查是否正确。 SearchStableMatch()函数是搜索算法的核心，采用递归方式实现，每次为一个男孩选择舞伴。index参数是男孩按照顺序的编号，从0开始编号，刚好对应boys数组的下标，简化了代码实现。当index等于UNIT_COUNT（男孩的个数）时，表示已经为所有男孩找到了舞伴，如果算法没有错误，这应该就是一个完美匹配。算法的主体就是遍历index对应的男孩的偏爱列表，从列表中找到一个还没有舞伴并且也喜欢自己的女孩作为舞伴，互相设置current属性。需要注意的是，算法主体包含一个回溯处理，当某一级搜索结束后，要重置相关男孩和女孩的舞伴关系，以便后序的递归搜索能够正常进行。具体代码可看SearchStableMatch()函数的for循环主体部分。 void SearchStableMatch(int index, PARTNER *boys, PARTNER *girls) { if(index == UNIT_COUNT) { if(IsStableMatch(boys, girls)) { PrintResult(boys, girls, UNIT_COUNT); } return; } for(int i = 0; i < boys[index].pCount; i++) { int gid = boys[index].perfect[i]; if(!IsPartnerAssigned(&girls[gid]) && IsFavoritePartner(&girls[gid], index)) { boys[index].current = gid; girls[gid].current = index; SearchStableMatch(index + 1, boys, girls); boys[index].current = -1; girls[gid].current = -1; } } } 7.3.2 不稳定因素的判断算法 7.1.1节给出了完美匹配中不稳定因素的定义，当一个男孩和一个女孩同时有比他们当前舞伴更“强烈的”愿望结为舞伴的时候，他们就倾向于与各自的舞伴分开，然后结合在一起成为舞伴。不稳定因素的判断算法就是在一个完美匹配中找出图7-1所示的情况，这种情况有两个特征：首先，男孩的当前舞伴不是他的偏爱列表中排在第一位的女孩，也就是说，男孩更偏爱其他女孩胜过自己当前的舞伴；其次，男孩更偏爱的那个（或那几个女孩中的一个）女孩刚好也喜欢这个男孩胜过自己当前的舞伴。 于是，不稳定因素的判断算法就呼之欲出了，重点就是上述两个特征的识别。判断一个完美匹配是否是稳定匹配的算法流程如下。 (1) 找出这个男孩的当前舞伴在男孩的偏爱列表中的位置，如果当前舞伴排在偏爱列表的第一位，则表示这个男孩不存在不稳定因素的可能，转步骤(4)。如果当前舞伴不是男孩偏爱列表的第一位，则转到步骤(2)。 (2) 男孩的偏爱列表中如果还有排在当前舞伴之前但还没有进行判断处理的女孩，则转步骤(3)，否则转步骤(4)。 (3) 找到女孩的当前舞伴在女孩的偏爱列表中的位置和当前处理的男孩在女孩的偏爱列表中的位置，如果女孩当前舞伴的位置比当前处理的男孩的位置靠前，则表示对该女孩不存在不稳定因素，转步骤(2)。如果当前处理的男孩的位置比女孩当前舞伴的位置靠前，则表示存在不稳定因素，直接转步骤(6)。 (4) 如果对全部男孩判断完毕，转步骤(5)。否则，继续对下一个男孩进行不稳定因素判断，转步骤(1)。 (5) 结束，没有找到不稳定因素。 (6) 结束，找到不稳定因素，此完美匹配不是稳定匹配。 根据以上算法流程，我们给出判断稳定匹配的算法实现，如IsStableMatch()函数所示，非常简单，相关的注释和以上算法流程的表述都能对上，此处就不再过多解释。 bool IsStableMatch(PARTNER *boys, PARTNER *girls) { for(int i = 0; i < UNIT_COUNT; i++) { //找到男孩当前舞伴在自己的偏好列表中的位置 int gpos = GetPerfectPosition(&boys[i], boys[i].current); //在position位置之前的舞伴，男孩喜欢她们胜过current for(int k = 0; k < gpos; k++) { int gid = boys[i].perfect[k]; //找到男孩在这个女孩的偏好列表中的位置 int bpos = GetPerfectPosition(&girls[gid], i); //找到女孩的当前舞伴在这个女孩的偏好列表中的位置 int cpos = GetPerfectPosition(&girls[gid], girls[gid].current); if(bpos < cpos) { //女孩也是喜欢这个男孩胜过喜欢自己当前的舞伴，这是不稳定因素 return false; } } } return true; } 7.3.3 穷举的结果 至此，我们有了穷举法搜索全部稳定匹配结果的算法，来看看结果吧。假设有以下男孩和女孩的数据，冒号后是对应男孩和女孩的偏爱列表。 男孩 Albert： Laura，Nancy，Marcy Brad： Marcy，Nancy，Laura Chuck： Laura，Marcy，Nancy 女孩 Laura： Chuck，Albert，Brad Marcy： Albert，Chuck，Brad Nancy： Brad，Albert，Chuck 应用算法搜索后得到以下结果： Albert[1] <---> Nancy[1] Brad[0] <---> Marcy[2] Chuck[0] <---> Laura[0] Albert[2] <---> Marcy[0] Brad[1] <---> Nancy[0] Chuck[0] <---> Laura[0] Total Matchs : 6, Stable Matchs : 2 看来，有两个稳定匹配的结果，用7.2.1节给出的Gale-Shapley算法得到的只是前一个稳定匹配的结果。参考资料[6]给出了一个有意思的结论，就是稳定匹配的个数总是2的整数幂，有兴趣的读者可阅读一下该资料，看看这个结论的来龙去脉。另外，这个资料还给出了只有一种稳定匹配结果的情况，即所有的女孩的偏爱列表都完全一样的时候，无论男孩们的偏爱列表如何选择，最终都只有一种稳定匹配结果，有兴趣的读者也可以自己研究研究。