KM算法原理+证明

ustbfym 2020-04-26


title: KM算法原理+证明
date: 2020-04-26
categories: ["算法"]
summary: "以匈牙利算法为基础,改善后用于求解带权二分图的求最佳匹配问题。百度百科中有KM算法的介绍,当中有证明过程:[百度KM算法]"
author: White Song
tags: ["二分图"]
cover: https://img.yilon.top/blog/czsh9.png
blog: https://blog.yilon.top


介绍

匈牙利算法为基础,改善后用于求解带权二分图的求最佳匹配问题

百度百科中有KM算法的介绍,当中有证明过程:百度KM算法

最大权匹配

带权二分图的边权重和最大匹配,如下图所示,最大和为102

KM算法原理+证明

最佳匹配

带权二分图的边权重和最大完备匹配,如下图所示

KM算法原理+证明

显然,最佳匹配和最大权匹配并不一致,但如果把剩下的边补上,并且设置权重为零,那么二者可以统一起来

KM算法原理+证明

KM算法

下面讲的KM算法是用来求最佳匹配,而非最大权匹配。

KM算法是一种计算机算法,功能是求完备匹配下的最大权匹配。

如果不存在完备匹配,那么算法会求最大匹配,如果最大匹配有多种,那么结果是最大匹配中权重和最大的。

在一个二分图内,左顶点为X,右顶点为Y,现对于每组左右连接XiYj有权,求最大匹配,并且使得该匹配中所有的和是最大。

该算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的问题转化为求完备匹配的问题的。

设顶点的顶标为的顶标为,顶点的顶标为,顶点与之间的边权为,在算法执行过程中,对于图中的任意一条边,始终成立。

相等子图

G当中每一条边有左右两个顶标,*相等子图*就是那些顶标和等于边权重的边构成的子图,如下图绿色加粗线构成相等子图

KM算法原理+证明

KM算法的正确性基于以下的定理:

定理:若二分图中,,并且存在某个相等子图有完备匹配,那么这个完备匹配就是二分图的最大权匹配。

证明:因为这个完备匹配存在于相等子图中,因此,这个匹配所有边都满足:,同时由于完备匹配包含所有的顶点,因此这个属于相等子图的完备匹配的总权重等于所有顶标的和。

如果这个二分图存在另外一个完备匹配,如果它不完全属于相等子图,即存在某条边,那么该匹配的权重和就小于所有顶标的和,即小于上述属于相等子图的完备匹配的权重和。

算法过程

首先选择顶点数较少的为X部,初始时对X部的每一个顶点设置顶标,顶标的值为该点关联的最大边的权值,Y部的顶点顶标为0。

KM算法原理+证明

对于X部中的每个顶点,在相等子图中利用匈牙利算法找一条增广路径,如果没有找到,则修改顶标,扩大相等子图,继续找增广路径。当每个点都找到增广路径时,此时意味着每个点都在匹配中,即找到了二分图的完备匹配。该完备匹配是最大权重的完备匹配,即为二分图的最佳匹配。

匈牙利算法对左边第一个顶点,在相等子图中进行增广路径搜索,找到路径1-C后进行匹配增广操作,如下图所示

KM算法原理+证明

回答第一个问题,需要理解如何在保持相等子图原来的边符合相等子图要求的同时,让新加的边也满足相等子图的要求。

那么在增广路径搜索时,我们知道,如果下面这些紫色边任意一条加入相等子图后,都可以在相等子图中使用匈牙利算法找到一条增广路径2-A(or 2-B or 2-C-1-A):

KM算法原理+证明

KM算法选择上述三条紫色边中,顶标和与边权重差值最小的边1-A或者2-A,以该最小差值为d

这里有一个问题就是为什么最小那个?首先比这更小了就不能扩大相等子图了,但是如果大了,就不能保证KM算法原理+证明总是成立了。比如上图选择了2-B边的差值2,那么修改顶标值后,1-A有KM算法原理+证明

KM算法中需要修改的顶标,是那些在匈牙利算法增广路径搜索时,产生一棵交错树,为了保证KM算法原理+证明总是成立,交错树上所有的顶标都要参与修改。

比如在如上第二个顶点搜索增广路径时,产生如下图所示的橙色顶标集合{1,2,C}:

KM算法原理+证明

修改顶标后产生如下图所示的结果:

KM算法原理+证明

在该相等子图上以顶点2为开始点,搜索增广路径2-A(or 2-C-1-A),进行增广操作:

KM算法原理+证明

同样对左边第三个点:

KM算法原理+证明

另外一个问题是为什么修改橙色顶标而不去修改顶标A(找到最小差对应的边的右边顶标)?修改顶标A的值为-1,那么边1-A也可以加入相等子图了。问题就在于能不能保证总是成立,如下图所示结果,修改顶标A,边3-A就不满足该条件了。除非在修改顶标A的同时,增加顶标3的值,但是需要修改的顶标集合需要额外的搜索算法,而修改橙色顶标所需要的交错树在增广路径搜索时可以一并产生。

KM算法原理+证明

C++代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3;
const int INF = 0x3f3f3f3f;
 
int wx[maxn], wy[maxn];//每个点的顶标值(需要根据二分图处理出来)
int cx[maxn], cy[maxn];//每个点所匹配的点
int visx[maxn], visy[maxn];//每个点是否加入增广路
int cntx=maxn, cnty=maxn;//分别是X和Y的点数
//int Map[maxn][maxn] = { {3,INF,100},{2,1,3 },{INF,INF,5} };//二分图边的权值
int Map[maxn][maxn] = { {3,0,100},{2,1,3 },{0,0,5} };//二分图边的权值
int minz;//边权和顶标最小的差值
 
bool dfs(int u)//进入DFS的都是X部的点
{
	visx[u] = 1;//标记进入增广路
	for (int v = 0; v < cnty; v++)
	{
		if (!visy[v] && Map[u][v] != INF)//如果Y部的点还没进入增广路,并且存在路径
		{
			int t = wx[u] + wy[v] - Map[u][v];
			if (t == 0)//t为0说明是相等子图
			{
				visy[v] = 1;//加入增广路
							//如果Y部的点还未进行匹配
							//或者已经进行了匹配,但是可以从v点原来匹配的cy[v]找到一条增广路
							//因为visy[v] = 1;因此从if (!visy[v] && Map[u][v] != INF) 中可以看出下一个找到的cy[v]-v‘连接肯定不在已经匹配的边集合M中
							//因为当v‘=v时if不满足!visy[v]=true
							//这保证了所找到的路径是属于M和不属于M的边交替出现
							//这时,下面递归的cx[u] = v; 和cy[v] =u 就可以对路径上的边取反,达到增广的效果
							//这是DFS的算法
							//那就可以进行匹配
				if (cy[v] == -1 || dfs(cy[v]))
				{
					cx[u] = v;
					cy[v] = u;//进行匹配
					return true;
				}
			}
			else if (t > 0)//此处t一定是大于0,因为顶标之和一定>=边权
			{
				minz = min(minz, t);//边权和顶标最小的差值
			}
		}
	}
	return false;
}
 
int KM()
{
	memset(cx, -1, sizeof(cx));
	memset(cy, -1, sizeof(cy));
	memset(wx, 0, sizeof(wx));//wx的顶标为该点连接的边的最大权值
	memset(wy, 0, sizeof(wy));//wy的顶标为0
	for (int i = 0; i < cntx; i++)//预处理出顶标值
	{
		for (int j = 0; j < cnty; j++)
		{
			if (Map[i][j] == INF) {
				continue;
			}
			wx[i] = max(wx[i], Map[i][j]);
		}
	}
	for (int i = 0; i < cntx; i++)//枚举X部的点
	{
		while (1)
		{
			minz = INF;
			memset(visx, 0, sizeof(visx));
			memset(visy, 0, sizeof(visy));
			if (dfs(i))break;//已经匹配正确
 
							 //还未匹配,将X部的顶标减去minz,Y部的顶标加上minz
			for (int j = 0; j < cntx; j++)
				if (visx[j])wx[j] -= minz;
			for (int j = 0; j < cnty; j++)
				if (visy[j])wy[j] += minz;
		}
	}
 
	int ans = 0;//二分图最优匹配权值
	for (int i = 0; i < cntx; i++)
		if (cx[i] != -1)ans += Map[i][cx[i]];
	return ans;
}
int n, k;
int main()
{
	int result = KM();
	return 0;
}