阅读:0       作者:解学武

Gale-Shapley算法解决舞伴问题过程详解(C++实现)

舞伴问题是这样的:有 n 个男孩与 n 个女孩参加舞会,每个男孩和女孩均交给主持一个名单,写上他(她)中意的舞伴名字。无论男孩还是女孩,提交给主持人的名单都是按照偏爱程度排序的,排在前面的都是他们最中意的舞伴。试问主持人在收到名单后,是否可以将他们分成 n 对,使每个人都能和他们中意的舞伴结对跳舞?为了避免舞会上出现不和谐的情况,要求这些舞伴的关系是稳定的。

假如有两对分好的舞伴:(男孩 A,女孩 B)和(男孩 B,女孩 A),但是男孩A更偏爱女孩 A,女孩 A 也更偏爱男孩 A,同样,女孩 B 更偏爱男孩 B,而男孩 B 也更偏爱女爱 B。在这种情况下,这两对舞伴就倾向于分开,然后重新组合,这就是不稳定因素。很显然,这个问题需要的是一个稳定匹配的结果,适合使用 Gale-Shapley 算法

算法实现

首先定义舞伴的数据结构,根据题意,一个舞伴至少要包含两个属性,就是每个人的偏爱舞伴列表和他(她)们当前选择的舞伴。根据 Gale-Shapley 算法的规则,还需要有一个属性表示下一次要向哪个偏爱舞伴提出跳舞要求。当然,这个属性并不是男生和女生同时需要的,当使用“男士优先”策略时,男生需要这个属性,当使用“女士优先”策略时,女生需要这个属性。为了使程序输出更有趣味,需要为每个角色提供一个名字。

综上所述,舞伴的数据结构定义如下:
typedef struct tagPartner {
    char *name; //名宇
    int next; //下一个邀请对象
    int current; //当前舞伴,-1表示还没有舞伴
    int pcount; //偏爱列表中舞伴个数
    int perfect[UNIT_C0UNT]; //偏爱列表
}PARTNER;
UNIT_COUNT 是男孩或女孩的数量(稳定匹配问题总是假设男孩和女孩的数虽相等),pcount 是偏爱列表中的舞伴个数。根据标准的“稳定婚姻问题”的要求,pcount 的值应该是和 UNIT_COUNT —致的,但是某些情况下(比如一些算法比赛题目的特殊要求)也会要求伙伴们提供的偏爱列表可长可短,因此我们增加了这个属性。

这里给出的实现算法使用数组来存储参加舞会的男孩和女孩列表,因此这个数据结构中的 next、current 和 perfect 列表中存放的都是数组索引,了解这一点有助于理解算法的实现代码。

Gale-Shapley 算法的实现非常简单,完整的算法代码如下:
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 IsAllPantnerMatch(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
    ...
}
这是我最不喜欢的代码逻辑,真的,太糟糕了。可见,这个小小的技巧为代码的逻辑处理带来了极大的好处。类似的技巧被广泛应用,在排序算法中经常使用“哨兵”位,避免每次都要判断是否比较完全部元素。面向对象技术中常用的“DuramyObject”技术,也是类似的思想。

Gale-Shapley 算法原来如此简单,你是不是为沙普利能获得诺贝尔奖愤愤不平?其实不然,算法原理的简单并不等于其解决的问题也简单,小算法解决大问题。

改进优化:空间换时间

Gale_Shapley() 函数给出的算法还有点问题,主要是 GetPerfectPosition() 函数的策略,这个函数每次都要遍历 partner 的偏爱舞伴列表才能确定 bid 的位罝,很可能导致理论上时间复杂度为的算法在实际实现时变成的时间复杂度。为了避免算法在多轮选择过程中频繁遍历每个 partner 的偏爱舞伴列表,需要对 partner 到底更偏爱哪个舞伴的判断策略进行改进。

改进的原则就是“以空间换时间”。简单来讲,以空间换时间的方法就是用一张事先初始化好的表存储这些位罝关系,在使用个过程中,以 O(1) 时间复杂度的方式直接查表确定偏爱舞伴的关系。这样的表可以是线性表,也可以是哈希表这样的映射表。

对于这个问题,我们选择使用二维表来存储这些位置关系。假设存在二维表 priority[n][n],我们用 priority[w][m] 表示在 w 的偏爱列表中的位置,这个值越小,表示 m 在 w 的偏爱列表中的位置越靠前。在算法开始之前,首先初始化这个关系表:
for(int w = 0; w < unit_count; w++)
{
    //初始化成最大值,原理同上
    for(int j = 0; j < UNIT_COUNT; j++)
    {
        priority= 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 次查询节省的时间来说,这点开销是能够容忍的。