2.1 基本概念二分图:如果图 G=(V,E)是一个无向图,如
果顶点 V 可分割为两个互不相交的子集(X,Y),并且图中的每条边(i,j)所关联的两个顶点 i和 j 分别属于这两个不同的顶点集(i∈X,j∈Y),则称图 G 为一个二分图。比如:x1 y1
我们每个同学可以根据自己的兴趣,给选择课题一个满意度,比如共五个等级,5 代表最喜欢,4 次之,依次类推。这样我们可以把同学与课题抽象成一个带权的二分图匹配,权就是同学对这个课题的满意度,通过最大权二分图匹配算
x2
x3
y2
y3
匹配:二分图 G=(V,E)中边集 E 的子集,其中的在 M 中的任意两边都没有公共顶点。交错路径:增广路,若 M 是二分图 G=(V,E)的
一个匹配,设从图 G 中的一个顶点到另一个顶点存在一条道路,这条道路是由属于 M 的边和不属于 M 的边交替出现组成的,则称这条道路为交错路或称增广路。如果交错路的头尾两个顶点不属于 M 则称这条增广路为可增广道路。
x1 y1
图的最大权匹配。
y3错路径存在,那么,就说明该匹配加入到最大匹配 M 中,如果交错路径找不到,可以用某种方法对顶标进行调整。调整的方法是:根据最后一次
不成功的寻找交错路的 DFS,取所有 i 被访问到而 j 没被访问到的边(i,j)的 lx[i]+ly[j]-w[i]
最优匹配:有二分图 G=(X,Y,E)其中|X|=|Y|=匹配数,E 中每条边(Xi,Yj)有权 Wij>=0,若能找到一个匹配 M(|M|=匹配数),满足所有匹配的边权和最大(或最小),则称 M 为 G 的一个最优匹配(
或称最大权匹配’)。完备匹配:对于二分图 G=(X,Y,E),M 是 G 中的一个匹配,如果 G 中每个顶点都是 M 中的一个匹配顶点,则称 M 为 G 的完备匹配(或称完全匹配%完美匹配)。
下面是我的伪代码:FindPathFrom uu is visited
for v in adj[u]
if v is not visited and lx[u]+lv[v]=w{u,v}v is visitedif v is matched and
FindPathFrom v is truev is matched ureturn truereturn false
Kuhn_Munkras:for u in Xlx[u]=max{w{u,v} | v is in Y}for v in Yly[v]=0
for u in Xwhile truefor each vertex uif FindPathFrom u is truebreakelse
find the d=min{ lx[i]+l[j]-w{i,j} } that i is in X and j is in Yfor each i is visitedlx[i] = lx[i]-dfor each j is visitedly[j] = ly[j]+d
在导出子图的边对应的 lx[i]+ly[j]-w[i][j]的最小值,在 find 过程中,若某条边不在导出子图中就用它对相应的 slack 值进行更新。然后求d 只要用 O(N),而不是原来的 O(N2)的时间找到
slack 中的最小值就可以了。
3 应用:KM 算法能够很好地应用在课题选择系统中,解决题目与学生最优匹配的问题。假设我们有 n
个同学选了课题 x1,x2,...,xn,并且有 m 个课题y1,y2,...,ym,第 i 个同学对第 j 门课题的感兴趣程度可以用 w[i][j]这个二维矩阵来表示。匹配可以用 match[m]记录,表示第 j 课题的匹配学生是 match[j]。这样,等主要程序运行完毕后,存储在 match 数组里的数据就是匹配的内容。输出
所有 match[i]的内容就表示第 i 个课题被第match[i]个同学选取。这里需要考虑一个问题,就是 m 与 n 值,如果 m=n 那么肯定可以得到一个匹配,但是 mn 则需要考虑一些问题,需要建一些虚顶点,用权 0 来标记顶点与虚顶点之间的权。所以可以
用 0 初始化所有 w 数组。可以据一个简单的例子:假设我们有三个同学 x1,x2,x3,三个课题 y1,y2,y3。每个同学最多可以选两个课题,各个同学的对兴趣程度在图中已标出。这样它的最大权匹配为 x1~y2,x2~y3,x3~y1
x1 y1
该算法的时间复杂度是 O(n4),尽管这样,它在实际应用中还是能够比较快的完成任务。如果对时间要求比较高,还句话说数据量非常庞大,本算法还可以优化成 O(n3),这样,时间量会减少比较大。
具体做法是用 slack[j]表示右边的点 j 的所有不