目录
[隐藏]

重温稳定匹配算法(G-S算法)

稳定匹配问题是一个非常典型的算法问题,它是由Gale和Shapley共同提出的。问题是这样描述的:

1.问题发生的背景

在大学期间,很多学生会选择去找实习公司实习,那么就会有很多同学对很多公司发出实习申请。申请过程的关键是两类不同的参与者:公司(雇主)和学生(申请 人)之间的相互影响。每个申请人对公司有一个优先排序,一旦申请人来到公司,每个公司对它的申请人也构成一个优先排序。基于这些优先排序,公司对他们的某 些申请人发出录用通知书,而申请人则选择某个通知书来接受,于是人们开始进入实习工作。

好,到这里问题出现了。比如,假设你的朋友Mark接受到Microsoft的录用通知书,另一个公司Yahoo行动晚了一些,几天后它也给Mark发出 了录用通知书。而Mark更愿意去Yahoo而不是Microsoft,于是这个新的发展也可能使他取消Microsoft的录用通知。由于突然少了一个 实习生,Microsoft就会重新录用另一个学生。似乎问题越来越严重,新的问题又来了。Mark有一个朋友叫Bill,他本来已经收到了 Microsoft的录用通知书,而恰恰Yahoo是知道这个消息的。经过与Mark的交流,Bill发现Microsoft公司并不是自己希望的那样, 而Yahoo却是自己的所愿。于是Bill给Microsoft打电话取消了他的录用,并与Yahoo取得联系,Yahoo也觉的Bill是个难得的人 才,决定录用Bill,于是Yahoo就要取消一个实习生的录用申请。情况到了这个地步,已经乱成一团了,似乎完全不可控了。

于是Gale和Shapley提出了这个问题:给定一组雇主和申请人的之间的优先权,我们能否把申请人分配给雇主,以使得对每个雇主E,以及没分配为E工作的每个申请人A,至少我们下面两种情况之一成立?

  • E对他所接受的每个申请人比A更满意,或者
  • A对他目前的情况比其为雇主E更满意。

2.问题形式化

了解这个概念的本质有助于使得这个问题尽可能的清晰,公司和申请人的世界包含了某些混乱的不均匀性。每个申请人可能申请多个公司,每个公司也可能录用多个人。我们排除这些因素,得到一个这个问题的本质。n个申请人的每个人对n个公司中的每个公司提出申请,每个公司想接受单一的申请人。我们看到,这样做可以保留问题固有的基本特点,特别是我们对这个简化描述的解将被直接推广到更一般的情况。

沿着这个思路,我们提出另一个更明了的问题。n个男人和n个女人结婚,于是男人的集合是M={m1,m2,m3……,mn}和女人集合是W= {w1,w2,w3……,wn},令M×W表示所有可能的形如{m,w}的有序对的集合,一个匹配S是来自M×W的有序对的集合,并且有下述性质:每个M 的成员和每个W的成员至多出现在S的一个有序对中,一个完美的S'具有下述性质:M的每个成员和W的每个成员恰好出现在S'的一个对里。

我们在这个背景下增加优先的概念,每个男人m∈M对所有的女人排名,如果m给w的排名高于w',我们就说m喜欢w超过w'。我们把m的排序作为他的优先表,类似的,每个女人也有一个优先表。

在得到的优先表中,会存在稳定的匹配吗?看看下面的情况就知道了。

在S中存在两个对(m,w)(m',w'),他们具有m更喜欢w'而不喜欢w,w'更喜欢m而不喜欢m'。在这种情况下,我们说(m,w')是一个相对于S的不稳定因素。而我们的目标是得到一个不含有不稳定因素的婚姻集合。

那么我们怎么能得到这个稳定的集合呢?看看G-S算法的代码吧。

3.算法设计

初始所有的m∈M和w∈W都是自由的
While 存在所有的男人m是自由的且还没对每个女人都求过婚
    选择这样一个男人m
    令w是m的优先表中m还没求过婚的最高排名的女人
    If w是自由的 then
        (m,w)变成约会状态
    Else w当前与m'约会
        If w是更喜欢m'而不喜欢m then
            m保持自由
        Else w是更喜欢m而不喜欢m'
            (m,w)变成约会状态
            m'变成自由
        EndIf
    EndIf
EndWhile
输出已约会的集合S

上面输出的集合S即稳定的匹配。

算法优化

传统G-S算法整个过程分为三步:

  • Initially, make everyone take the starting status.
  • Do Work, it take a loop one send a request and another receive and handle it
  • Finally, the algorithm will terminate in condition of everyone is stable.

因此,传统的G-S算法会在至多n^2次循环后结束,显然这不是最优化的。

1.算法初步探究

是什么影响了G-S算法的效率?
优化G-S算法,也就是优化循环的次数,那么必须搞清楚是什么影响了循环的次数。在典型的men-women问题上,我们得出影响循环次数的因素是当前 free的人数,或是每进行一次循环man或woman从free到not free的人数,这个人数是0或是1,我称之为“约会效率”,即约会成功的可能性或是稳定性。 正常情况下,每进行一次循环,free man或free woman的数量减1或是不变。减1的情况下,约会的效率是最高的不单单是人数的减1,在未来的某个时候,m可能成为free,那么这一次成功的约会就为 m减少了下次求婚人的数量(因为在这个规则中没有人会向把自己甩掉的前女友去求婚),贡献度为1/n。不变的情况下,free man或free woman的人数未变,但是减少了求婚列表仍未求婚的次数,贡献度为1/n。

2.如何分析约会效率?

从上面我们了解到了“约会效率”的概念,那么到底怎么去量化一个约会效率,怎么去改变约会效率是我们进一步要做的。
首先,应该弄清什么是“约会效率”,在一个小节已经提过了,在这里再重申一遍,约会效率是每完成一次行为(循环行为)所对整个问题求解步数的贡献大小。在 整个G-S算法过程中,我们把这个问题看做是可以找到最终解的(实际情况也是如此),那么在这个求解的过程中就必须的存在一个特定的“步数”或是时间,而 每进行一次“行为”(一次循环中的求婚行为),就使我们前进一小步,逼近最终的解,那么这一小步就是这一次“行为”对整个问题的贡献。然而,一次“行为” 所走的“一小步”并不是相等的,有可能一次“行为”A走的“一小步”要大一些,给它一个权值,比如5,而另一次“行为”B走的“一小步”要小一些,比如为 1,显然“行为”A更好一些,我们总是期望一次“行为”能完成更多的事情。
因此,如何计算“约会效率”是我们优化整个算法的关键。从上面我们可以很容易的想到,整体的“约会效率”跟每一步的“约会效率”有关,那么进行一次“行 为”的“约会效率”怎么计算呢?我们知道进行一次“行为”有2种情况,变成not free的人数为0或是1,我们把它放的更普遍一些,每一次“行为”有4种情况,首先澄清几个术语,约会成功:指有一对人变成not free,约会失败:指没有人变成not free,有记忆:指对求过婚的人有记忆下次便不再求婚于他,无记忆:指对求过婚的人没有记忆下次求婚时找列表中最靠上的一个进行求婚。(有无记忆其实是 我一个多虑,但考虑到在普通的问题中确实存在,所以把这个因素也考虑在内)

本文中多次提到free和not free,free指的是单身的男女,not free是当前进入约会状态的男女。

  • 约会失败-无记忆      0%
  • 约会失败-有记忆      1/(n^2)%(n个man和n个woman形成n^2个组合,有记忆使得整体组合减1)
  • 约会成功-无记忆      ∞0%
  • 约会成功-有记忆     100%

这四种情况后面跟的是它们的“约会效率”,对于无记忆的显然会使程序陷入死循环,所以效率极低。在men-women的案例中,使用的都是2、4情况。

3.整体的效率和循环的次数

有了上面的每一步的“约会效率”,我们就可以求出整体的“约会效率”:
S=(x/n^2+y)/(x+y)*100%
n代表man或woman的人数,Number(man)==Number(woman)
x代表“约会失败-有记忆”循环的次数
y代表“约会成功-有记忆”循环的次数
我们利用两个极限,便可以求出整体“约会效率”的最大值和最小值:
1/n<=整体效率<=1
它们分别对应的循环次数为:n^2和n
循环运行的次数为C,则:
C=n/S

不知道细心的朋友发现问题没有,这里有一个陷阱,就是整体效率是如何得出来 的?我们只是知道整体效率的计算公式,却不知道怎么使用两个极限。这里,我做了一个假设,就是约会效率最好为1,在具体问题中,n个man和n个 woman最小的循环次数为n,最大的循环次数为n^2,我假设了当循环次数为n时,整体效率为1,即假设了一个基数n,作为约会效率对比的约会基数,效 率最高时,循环次数为n,整体效率为约会基数/n=1,而效率最低时,循环的次数为n^2,整体效率为约会基数/n^2=1/n。其实,整体效率是可以通 过数学计算得来的,只不过现在条件还不够。

上面说到了整体效率的计算过程,我们发现其实,x和y的值也是有关系的,上面我曾说过整体效率还不能通过数学计算得 出就是因为x和y的关系没有搞清楚。如果一个人总是失恋那么为了保持约会状态他肯定也总去约会。到底x和y是什么关系呢?我们设想一个场景,有ABC三名 man和abc三名woman,ABC三名man对woman的列表都为abc,也就是说ABC三名man认为a最好,b次之,c最不好。同样,abc三 名woman对man的列表都为ABC。下面是具体的情况:

  • 每个man的求婚都能成功,也就是说没有man会被女朋友甩掉。
    A先向他列表中最好的a求婚,并约会成功;接着B向他列表中最好的a求婚,但a却不好抛弃现有的男友A去和B约会,因为a认为A比B更优秀,B最终与b约会成功;同样,C最终与c约会成功。
  • 每个man都会被别的man把女朋友给抢走,除非他是最后一个求婚的人。
    C先想他列表中最好的a求婚,a会欣然接受这次求婚;然后,B开始向自己列表中最好的a求婚,a发现B要比C更好, 然后B与a约会成功,而C却失恋;随后,失恋的C发起另一轮求婚,这次他向b求婚,因为他已经向a求过婚了,而且是被a给甩掉的,显然b也会欣然接受这次 求婚的,然后C与b约会成功;现在只剩下A还是单身了,于是A向自己列表中最好的a求婚,这时a发现A要比B好,于是她又甩掉了B,并且同A约会成功;然 后单身的B开始向列表中第二位的b求婚,并且b会甩掉C跟B约会成功;然后单身的C向剩下的没有求婚的c求婚,并约会成功。
  • 这种情况比较特殊,A的列表为abc,B的为bac,C的为cab,a的为ABC,b的为BAC,c的为CAB,我们先后从ABC进行求婚,只需要进行3次便可以结束整个循环。

上面两种情况很典型。在第一种情况下,x的次数为3,y的次数为3,共进行了6次循环。第二种情况,x的次数为3,y的次数为6,第三者情况下,x的次数为0,y的次数为3。
因此,我们总结出x和y的值域,n的取值便是x和y的定义域。

  • x最小时,即“王八看绿豆”型,根本不需要盲目的求婚约会,x会是0。
  • x最大时,即“癞蛤蟆想吃天鹅肉”型,时刻保持从“最癞的一只蛤蟆”开始向“最美的一只天鹅”求婚,x最大为1+2+3+……+n-1=n(n-1)/2.
  • y最小时,即“一见钟情”型,进入约会状态后便不会再抛弃对方,y会是n。
  • y最大时,即“见异思迁”型,老是更换约会对象,y会是1+2+3+……+n=n(n+1)/2。

0<=x<=n(n-1)/2
n<=y<=n(n+1)/2
说到这里,我们可以用上面的几个公式验证一下。

4.从约会效率下手优化算法

从上面我们得出,循环的次数与x和y的值有关,而x与y又是有一定联系的,那么什么情况下才是最优的G-S算法呢? 当然是x的次数为0时的情况,那么我们怎么使得x的值尽量的小呢?很明显,我们必须知道x的大小代表着什么,X代表“约会失败-有记忆”循环的次数,那么 为什么会约会失败呢?是因为当前的约会对象不够好,那么为了减小“约会失败”的次数,我们必须让每一个woman的约会对象足够好,“足够好”的概念是预 计未来不会再有比当前约会对象更好的man来求婚了。我们定义一个新的词语叫“约会稳定性”,它指的是当前woman同当前的约会对象man约会到算法终 止时的稳定程度,“约会稳定性”越大显然算法的效率就会越高,反之则越低。我们讨论2种情况:

  • x的次数为0,y的次数为n。
  • x的次数为n*(n-1)/2,y的次数为n*(n+1)/2。

第一种情况是算法最优时的情况,即“约会稳定性”最高时的情形。第二种情况是算法最差时的情况,即“约会稳定性”最低时,每个人匆匆的约会后,又匆匆的抛弃对方。
为了能够利用“约会稳定性”来控制算法的优略,我们需要进一步对“约会稳定性”探究。

5.如何控制“约会稳定性”

在man-woman的案例中,到底什么样的约会才算是稳定的呢?好男人配好女人,坏男人配坏女人才是比较稳定的,所以整体的“约会稳定性”最大,就意味着相同等级的man去跟相同等级的woman约会。下面分几点进行阐述:

  • 每个man都有一个对所有woman的优先列表,这些列表肯定的存在一定的差异,这些差异形成了我们想要的数据——共识率A。共识率指示了man 对所有woman整体偏好的差异程度,比如m1的列表为w1,w2,m2的列表为w1,w2,就说m1和m2对woman有一个共识,如果m2的列表为 w2,w1,就说m1和m2对woman没有一个共识。同样的,woman也有一个这样的对man的共识率B。
  • 根据A判断出所有的man是否有一个可信的共识(这个比率的设定因人而异,通常要大于60%才能说有一个可信的共识),然后计算出men对 women的平均排名A(有点像一个班的男生对自己班女生进行排名一样,这个排名是大家达成的共识),共识率越高,那么这个平均排名就越可信,反之,则不 可取。同样的,women对men也有一个平均排名B。
  • 上面我们得出了平均排名A和平均排名B,我们又称AB为“稳定方向”,那么沿着“稳定方向”上的约会将是最稳定的,得出的“整体约会稳定性”会最 高。因此,沿着这个“稳定方向”,依次选取free的man去向他列表中第一个为求过婚的woman求婚,得出的效率将是最优的。当然,这个“约会稳定 性”也不是绝对的,可能一个人的优先列表与他人的完全不同,但有一点,在每一次循环时,我们总是选择最优秀的man去向他认为最优秀的woman求婚。

因此,我们得到一个优化的G-S算法。下面是优化的伪代码:

初始所有的m∈M和w∈W都是自由的
if(M和W的共识率达到一定要求)
    按照M和W对彼此的优先列表对M和W进行排序,形成“稳定方向”
While 存在所有的男人m是自由的且还没对每个女人都求过婚
    选择这样一个男人m
    令w是m的优先表中m还没求过婚的最高排名的女人
    If w是自由的 then
        (m,w)变成约会状态
    Else w当前与m'约会
        If w是更喜欢m'而不喜欢m then
            m保持自由
        Else w是更喜欢m而不喜欢m'
            (m,w)变成约会状态
            m'变成自由
        EndIf
    EndIf
EndWhile
输出已约会的集合S

上面的代码中加粗的代码是优化后的部分,我们发现整个过程跟传统的G-S算法是一样的,只不过在进行匹配之前进行了一些预处理工作。
具体优化后的性能如何呢?且看下回分解。

-----------------------------------

“约会稳定性”和“稳定方向”

上一篇最后,我们大致明确了如何去优化G-S算法,其中提到了“约会稳定性”和“稳定方向”的概念,如果还不是太明白请看优化G-S匹配算法(1)之兵马未动粮草先行为了提高“约会稳定性”我们计算得出“稳定方向”,然后沿着“稳定方向”去一一匹配,便会得出比较优化的结果。但是,“稳定方向”的计算也不是一个轻巧的过程,本篇主要介绍如何去计算“稳定方向”这个过程,同时也希望大家提出更好的方案。

共识率和平均排名

我们知道,“稳定方向”是一个men对所有women的一个平均排名,有点想一个班里所有的男生讨论得出的自己班里班花排行一样,在G-S问题中,“稳定方向”的得出是从每一个man的优先列表中计算得出的,同样的women对men也有这样一个平均排名。

优先列表,在G-S问题中指一个人对所有异性的排名。比如,男人m喜欢女人w1胜过w2,则在m的优先列表中w1的位置比w2更靠前。
平均排名,指的是men对women达成的一种优先共识,即大体上所有的man都认为woman的排名应该是这样的。

我们知道“稳定方向”代表着大多数人的意见,也就是说“稳定方向”是大多数人形成的一个共识,既然有共识,那么必然 的存在着意见的不同。当我们给出一个优先列表A,设A为标准的平均排名,只是假设其实不存在标准的平均排名。那么如果大多数人大体同意A,也就是说能达成 共识,如果大多数人不同意A,也就是说不能达成共识。于是,对A质量的评价就取决与人们对它达成共识的程度,我们称之为共识率。共识率的大小决定了人们意 见的统一与分散,在G-S问题中,men对women的共识率决定了men对women排名的相近和不同。

共识率的作用非常大,如果共识率较低,说明平均排名没有说服力,不能代表大部分人的意见,因此对算法提高的效率产生的积极影响也小,反之,对算法效率的提供帮助越大。如果共识率非常低以至于趋近于0,则优化后的算法跟传统的算法没有区别。

因此,我们应先计算出平均排名,再计算优先列表相对平均排名的共识率,以说明平均排名的结果是否可信,可信度为多少。

平均排名的计算

平均排名的计算是对一组优先列表的计算产生的,n个man对应n个优先列表,那么如何从这么多的优先列表中计算出平均排名呢?
我采用了一种方法,叫做逆序数逐步求精法

逆序数,指一个数列相对于标准数列的逆序的总和。
比如,2314的逆序数为2(相对于1234)。
我们很容易知道,有n个数,那么该数列最大的逆序数Nmax=n(n-1)/2。

比如有man A、B、C、D。他们对woman的优先列表分别为:
A:{a,b,c,d}
B:{d,c,a,b}
C:{c,d,b,a}
D:{d,a,c,b}
我们假设A的优先列表与平均排名相同,则A、B、C、D的优先列表对于平均排名的逆序数为0,5,5,4,逆序数越大,说明它们与平均排名差别越 大,dcba与平均排名abcd的差别最大,dcba的逆序数为6,所以根据贪心原则,当每一个优先列表的逆序数最小时,总逆序数最小,也就说明各个优先 列表间差别最小,即达成一个共识。

因此,设所有优先列表逆序数的和为R,优先列表i的逆序数为Vi,则R=∑Vi(0<=i<=n)。当R达到最小时,当前假设的平均排名最接近标准的平均排名,我们取它作为平均排名来作为“稳定方向”,并技术该“稳定方向”的共识率。

怎么个逐步求精呢?以上面的ABCD为例:

1.假设平均排名

我们首先假设A的优先列表为平均排名。则ABCD的优先列表相对于平均排名的逆序数为0,5,5,4。
A:{a,b,c,d}    0
B:{d,c,a,b}    5
C:{c,d,b,a}    5
D:{d,a,c,b}    4
从BCD优先列表的逆序数上我们可以看出它们与平均排名相差甚远,因为最大的逆序数为6,它们已经非常接近最大逆序数了。但是,我们发现BCD优先列表的逆序数却很相似。

2.计算平均逆序数修正假设

为了更进一步逼近标准平均排名,我们找出最接近平均逆序数的那个优先列表,并假设它为平均排名。
逆序数和R=0+5+5+4=14,平均逆序数r=14/4=3.5,D优先列表的逆序数最接近,因此设D的优先列表为平均排名,下面是以D优先列表为平均排名计算出的逆序数:
A:{a,b,c,d}    4
B:{d,c,a,b}    1
C:{c,d,b,a}    3
D:{d,a,c,b}    0
R=8,r=2,比起上一步显然D比A的优先列表作为平均排名更合适。
然后回到1,直到满足3退出得到平均排名。

3.终止逐步求精,得到平均排名

1和2给出了计算过程,但是缺少一个终止的条件,就是我们需要记录上一次平均排名的逆序数和R1和这一步的逆序数和 R2,然后取R1和R2中值较小的一个作为平均排名,如果R1和R2相同,则有两种方法:一种是取优先列表逆序数方差小的一个,一种是取共识率更高的一 个。共识率的计算在接下来会介绍。
在2中,我们以D的优先列表作为平均排名计算的结果已经给出,然后再选B的优先列表作为平均排名,计算出R=8,r=2。那么到底B和D的优先列表那个更 接近标准优先列表呢?按照方差小优先的方法,B的优先列表更接近标准优先列表,于是我们得出了“稳定方向”为B的优先列表,接着就是共识率的计算。

共识率的计算

我们设所有优先列表相对平均排名的共识率为Q,每一个优先列表相对于平均排名的共识率为q,则有:
Q=∑qi/n
以abcd为基准,则dcba的逆序数为6,abcd的逆序数为0,dcab的逆序数为5,因为逆序数表示的是位置先后的差异度,abcd全排列得到6种 组合(ab/ac/ad/bc/bd/cd组合内无先后顺序),则在dcba种也可以找到这6种组合,那么如果abcd6种组合中的一个在dcba中的顺 序不同时,逆序数加1(比如abcd中ab组合a在前b在后,而在dcba中ab组合a在后b在前),所以逆序数又可以看做是每一对组合的顺序差异。那 么,对于q有:
q=(Nmax-r)/Nmax
Nmax是我们前面提到的最大逆序数。Nmax=n(n-1)/2
这样我们便求出了每个优先列表对于平均排名的共识率,继而得出所有优先列表对于平均排名的共识率。
Q=(1-R/(Nmax*n))*100%

在“平均排名的计算”一节中的第3步,有这么一种情况,就是我们计算出以B和D优先列表作为平均排名它们的逆序数和R都等于8,而共识率Q又与R有关,所以从共识率上我们看不出B和D那个的优先列表作为平均排名更好些,所以我们采用方差最小优先法。

“强”平均排名

通过上面的介绍,相信大家都了解了求“稳定方向”的整个过程,但是我们求出来的平均排名有一个问题,上面求出来的平均排名我称之为“弱”平均排名,为什么呢?
细心的朋友发现不管ABCD的优先列表如何,我们求出的平均排名肯定是ABCD的优先列表中的一个,这显然不符合实际问题,如果man的数量庞大,有可能 这里的“弱”平均排名==“强”平均排名,所以“强”平均排名更接近与标准的平均排名。怎么化解这个弊端呢?就是通过引入全排列,并计算它们相对于当前假 设的平均排名的逆序数,比如ABCDEF的优先列表的逆序数为0,1,2,13,12,12则R=40,r=6.67显然,没有ABCDEF的优先列表中 没有一个符合要求,则需要引入其它的假设的平均排名,进而求出“强”平均排名。

引入“强”平均排名后,因为在获取符合要求的假设平均排名时需要计算每一个全排列的逆序数并获取最接近平均逆序数的 一个作为假设的新的平均排名,所以问题的求解规模会很大,而且对于小规模问题我们可以使用传统的G-S算法,对于大规模问题,如果使用“强”平均排名由于 问题规模较大(man的人数n较大,则n个全排列的逆序数的计算和比较会很消耗资源),求解“强”平均排名的过程会消耗非常大的资源,甚至远不如不优化, 而且随着问题规模的增大,“弱”平均排名也趋近于“强”平均排名,所以,在理论上,存在这么一个误区,而在实际问题中,如果采用“强”平均排名就得不偿失 了。这里就不再做详细分析,有兴趣的朋友可以研究一下。

形成“稳定方向”伪代码

int[] preO=第一个woman的优先列表
int[] nowO=preO
int[] preR=preO的逆序数数列
int[] nowR=preR
int preRN=preR的总和,nowRN=0
while(true){
    选择最接近平均逆序数r的优先列表B,并nowO=B
    nowR=nowO的逆序数数列
    nowRN=nowR逆序数和
    if(nowRN>preRN)    break;
    else if(nowR==preR){
        if(方差(nowR)<方差(preR)){
            preO=nowO
            preR=nowR
            preRN=nowRN
        }
        else
            break;
    }
    else{
        preO=nowO
        preR=nowR
        preRN=nowRN
    }
}
preO作为平均排名,preR作为逆序数数列,preRN作为逆序数和
Q=(1-preRN/(Nmax*n))*100%
返回preO作为“稳定方向”,Q作为共识率