Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » 

KM算法

KM算法是求一个二分图在完备匹配下的最大权匹配的算法,该算法是通过给每一个顶点标号将求最大匹配问题转化为求完备匹配的问题。
KM算法是在匈牙利算法基础上实现的,如果还未了解匈牙利算法及二分图相关概念,请先看匈牙利算法这篇文章。

算法原理

上次的二分图G=(X,Y)中,顶点之间要么有边要么没边,可以通过匈牙利算法求出此时的最大匹配。
现在考虑二分图G中的边有非负的权值,求一种完备匹配方案,使得边权之和最大。

把原来没有边的顶点对看成有权值为0的边相连,于是完备匹配一定存在,通过匈牙利算法求出的最大匹配必定是完备匹配,但这个求到的匹配不一定是权值最大的。
KM算法就是通过给图的顶点添加适当的标号,然后对标号满足一定条件的顶点使用匈牙利算法,最终求出最大的匹配。

把顶点x映射到一个非负整数,这个非负整数就叫顶点的标号,记二分图的标号为l,具体的,为了实现的方便,记左边的顶点标号为lx[i],右边顶点标号为ly[j]。
如果对于任意边(i,j),均有lx[i]+ly[j]>=map[i][j](标号之和大于等于边权重),则称G的这个标号为可行顶点标号。
注意到,可行顶点标号总是存在的,比如下面的平凡标号(实际上算法初始化也是用的平凡标号):

lx[i] = max(map[i][j]) for j in Y, for i in X; ly[j] = 0 for j in Y

即左边顶点标号为其所连接的边的最大权值,右边顶点的标号为0,如下图所示,这显然满足可行标号的要求。

km图片

给定标号l的二分图G中,以所有满足lx[i]+ly[j]==map[i][j]的边组成边集的生成子图称为G在l下的相等子图Gl。
如上图中,红色边对应的生成子图即为相等子图。

KM算法的正确性由以下定理保证
定理:二分图G有可行顶点标号l,若G在l下的相等子图Gl有完备匹配M’,则M’是G的最大权完备匹配。
由于相等子图Gl是G的生成子图,Gl与G有相同的顶点,故Gl的完备匹配也是G的完备匹配。

w(M’) = sum(w(e)) for e in M’ = sum(l(v)) for v in V

另一方面,对任意的G的完备匹配M,根据可行顶点标号定义有

w(M) = sum(w(e)) for e in M <= sum(l(v)) for v in V

于是w(M’)>=w(M),即M’是G的最大权完备匹配

由定理可知,要求G的最大权完备匹配,可在相等子图中运用匈牙利算法求完备匹配。但相等子图中如果没有完备匹配怎么办?此时KM算法给出一个修改顶点标号的方法,使得相等子图原有边不变的情况下,逐步加入新的边到相等子图中,直到相等子图中有完备匹配出现为止。

先给出交错树的概念,匈牙利算法再寻找增广路时,从左边某个顶点x出发,沿着所有的交错路寻找增广路,找完备匹配失败时,遍历过程中访问过的节点会形成一棵交错树。交错树根节点为初始节点x,第二层节点全是Y中的节点,第三层节点全是X中的节点,因为没有增广路,所以叶子节点全是X的节点。

现在可以根据交错树进行修改顶点标号:
假设在当前顶点标号下匈牙利算法没有找到完备匹配,记交错树中X的顶点集为S,树中Y的顶点集为T,令

d = min(lx[i] + ly[j] – map[i][j]) for i in S, for j in Y\T

然后对每个顶点修改标号如下:

lx[i] += d for i in S; ly[i] -= d for i in T

即交错树中X的标号增加d,交错树中Y的标号较少d ,其余顶点标号不变。

修改顶点标号后,我们观察相等子图可能发生的变化:

  1. 两端都在交错树中的边(i,j),lx[i]增加了d,ly[j]减少了d,lx[i]+ly[j]不变。它原来属于相等子图,现在仍属于相等子图。
  2. 两端都不在交错树中的边(i,j),lx[i]和ly[j]都不变,lx[i]+ly[j]也不变。它原来属于(不属于)相等子图的话,现在仍属于(不属于);
  3. X端不在交错树,Y端在交错树的边(i,j),lx[i]不变,ly[j]减少了d。它原来不属于相等子图,现在更不属于相等子图。
  4. X端在交错树,Y端不在交错树的边(i,j),lx[i]增加了d,ly[j]不变,lx[i]+ly[j]增加了α。它原来不属于相等子图,现在可能属于相等子图。

由d的取值知,修改标号后,至少增加了一条新边到相等子图中(即使min成立的那对(i,j))。

现在的KM算法已经可以找到最大权的完备匹配了。
分析其复杂度为,寻找O(n)次增广路,每次寻找增广路最多需要O(n)次遍历,因没有完备匹配而修改标号时需要O(n^2)枚举所有满足的(i,j),于是最终复杂度为O(n^4)。
一个优化是对Y顶点引入松弛函数slack,slack[j]保存跟当前节点j相连的节点i的lx[i]+ly[j]-map[i][j]的最小值,于是求d是只需O(n)枚举不在交错树中的Y顶点的最小slack值即可。
松弛值可以在匈牙利算法检查相等子树边失败时进行更新,同时在修改标号后也要更新,具体参考代码实现。

上面讲的都是求最大权的完备匹配,如果要求最小权完备匹配,只需在调用km算法前把所有权值都取反,然后再调用km算法,然后把km算法得到的结果再取反即为最小权值。

代码实现

具体实现代码如下

const int mx = 101, oo = 2100000000;	//二分图最大顶点数
int n;								//二分图中左右两边顶点的个数
int map[mx][mx], lx[mx], ly[mx];	//二分图,左边点的定标值,右边点的定标值
int match[mx], slack[mx];			//右边点匹配的结果,右边点的松弛值
bool vsx[mx], vsy[mx];				//找增光轨过程中使用过(交错树中)的左边、右边的点

//寻找在相等子树中以左边点x为起点的增广轨
bool find (int x)
{
	vsx[x] = 1;				//标记为交错树中的点
	for (int i = 0; i < n; i++)
	{
		if (vsy[i])	continue;	//已经使用过
		int t = lx[x] + ly[i] - map[x][i];	
		if (!t)			//相等子树中的边,加入增广轨中
		{
			vsy[i] = 1;		//标记为已使用过
			//尚未匹配 || 已经匹配但从其出发仍然可以找到增广轨
			if (match[i]==-1 || find(match[i]))	
			{
				match[i] = x;	return 1;		//标记匹配值,返回成功
			}
		}
		else
			if (slack[i] > t)	slack[i] = t;	//更新松弛值
	}
	return 0;
}

int km ()
{
	//求最小权匹配时把边权值作转化(最大权不用转化)
	/*for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			map[i][j] = -map[i][j];*/

	//初始化顶标值,左边为连接各边的最大值,右边为0
	for (int i = 0; i < n; i++)
	{
		lx[i] = -oo, ly[i] = 0;
		for (int j = 0; j < n; j++)
			if (map[i][j] > lx[i])		lx[i] = map[i][j];
	}
	
	memset(match, -1, sizeof(match));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)	slack[j] = oo;		//初始化松弛值
		while (1)
		{
			memset(vsx, 0, sizeof(vsx));
			memset(vsy, 0, sizeof(vsy));
			if (find(i))	break;		//找到增广轨
			int d = oo;				//未找到增广轨,修改定标值
			for (int j = 0; j < n; j++)
				if (!vsy[j] && slack[j] < d)	
					d = slack[j];		//右边未在交错树中且松弛值最小的值
			for (int j = 0; j < n; j++)
			{
				if (vsx[j])	lx[j] -= d;	//左边交错树中的点的定标值减少d
				if (vsy[j])	ly[j] += d; //右边交错树中的点的定标值增加d
				else		slack[j] -= d; //右边非交错树中的点的松弛值减少d
			}
		}
	}
	int sum = 0;	//计算最大权值
	for (int i = 0; i < n ;i++)	sum += map[match[i]][i];

	//求最小权时把结果转化回去,并把原图还原(最大权不用)
	/*sum = -sum;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)	
			map[i][j] = -map[i][j];*/

	return sum;
}

上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论