Kuhn-Munkres算法(二分图最大权匹配)
- 格式:doc
- 大小:55.50 KB
- 文档页数:11
Kuhn-Munkres算法(二分图最大权匹配)
二分图如果是没有权值的,求最大匹配。则是用匈牙利算法求最大匹配。如果带了权值,求最大或者最小权匹配,则必须用KM算法。
其实最大和最小权匹配都是一样的问题。只要会求最大匹配,如果要求最小权匹配,则将权值取相反数,再把结果取相反数,那么最小权匹配就求出来了。
KM算法及其难理解。。。看了几天还无头绪。
先拿上一直采用的KM算法模板,按照吉林大学的模板写的。试试了好多次感觉都没有出错。
/******************************************************
二分图最佳匹配(kuhn munkras 算法 O(m*m*n)).
邻接矩阵形式。返回最佳匹配值,传入二分图大小m,n
邻接矩阵 mat ,表示权,match1,match2返回一个最佳匹配,为匹配顶点的match值为-1,
一定注意m<=n,否则循环无法终止,最小权匹配可将全职取相反数。
初始化: for(i=0;i for(j=0;j 对于存在的边:mat[i][j]=val;//注意不能负值 ********************************************************/ #include { int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN]; int p,q,i,j,k,ret=0; for(i=0;i { l1[i]=-inf; for(j=0;j l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i]; if(l1[i]==-inf) return -1; } for(i=0;i l2[i]=0; _clr(match1); _clr(match2); for(i=0;i { _clr(t); p=0;q=0; for(s[0]=i;p<=q&&match1[i]<0;p++) { for(k=s[p],j=0;j if(l1[k]+l2[j]==mat[k][j]&&t[j]<0) { s[++q]=match2[j]; t[j]=k; if(s[q]<0) { for(p=j;p>=0;j=p) { match2[j]=k=t[j]; p=match1[k]; match1[k]=j; } } } } } if(match1[i]<0) { i--; p=inf; for(k=0;k<=q;k++) { for(j=0;j { if(t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j] } } for(j=0;j l2[j]+=t[j]<0?0:p; for(k=0;k<=q;k++) l1[s[k]]-=p; } } for(i=0;i ret+=mat[i][match1[i]]; return ret; } 下面是从网上的博客摘抄的一些零散的总结。。。。。 [二分图带权匹配与最佳匹配] 什么是二分图的带权匹配?二分图的带权匹配就是求出一个匹配集合,使得集合中边的权值之和最大或最小。而二分图的最佳匹配则一定为完备匹配,在此基础上,才要求匹配的边权值之和最大或最小。二分图的带权匹配与最佳匹配不等价,也不互相包含。 这两个的关系比较悬乎。我的理解就是带权匹配是不考虑是不是完备,只求最大或最小权匹配。而最佳匹配则必须在完备匹配的基础上找最大或最小权匹配。 这两个还是结合具体题目比较好理解些。 KM算法是求最大权完备匹配,如果要求最小权完备匹配怎么办?方法很简单,只需将所有的边权值取其相反数,求最大权完备匹配,匹配的值再取相反数即可。 KM算法的运行要求是必须存在一个完备匹配,如果求一个最大权匹配(不一定完备)该如何办?依然很简单,把不存在的边权值赋为0。 KM算法求得的最大权匹配是边权值和最大,如果我想要边权之积最大,又怎样转化?还是不难办到,每条边权取自然对数,然后求最大和权匹配,求得的结果a再算出e^a就是最大积匹配。至于精度问题则没有更好的办法了。 二分图最优匹配:对于二分图的每条边都有一个权(非负),要求一种完备匹配方案,使得所有匹配边的权和最大,记做最优完备匹配。(特殊的,当所有边的权为1时,就是最大完备匹配问题) 定义设G= 在上述定义中,若|V2|=|V1|,则完备匹配即为完美匹配,若|V1|<|V2|,则完备匹配为G中最大匹配。 KM算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点X i的顶标为A[i],顶点Y i的顶标为B[i],顶点X i与Y j之间的边权为w[i,j]。在算法执行过程中的任一时刻,对于任一条边(i,j), A[i]+B[j]>=w[i,j]始终成立,初始A[i]为与xi相连的边的最大边权,B[j]=0。KM算法的正确性基于以下定理: