华为认证hcia hcip hcie云计算网络工程师在线培训
0 人在学
KM算法是一种计算机算法,功能是求完备匹配下的最大权匹配。在一张二分图中,左上角是x,右上角是y,现在每组左右连接XiYj都有wij的权利,寻求匹配使所有wij最大化。
通过对每个顶点进行标号,将求最大权值的问题转化为求完备匹配问题。设顶点的顶标为,顶点的顶标为,顶点与之间的边权为。在算法执行过程中的任何时刻,任何边缘都将永远成立。
KM算法原理
对加权完全二分图,求权重和最大匹配,称为求最佳匹配;直接穷举法:效率为n!;使用KM算法。
定理:设M是一个带权完全二分图G的一个完备匹配,给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示,第j个y顶点的可行标用ly[j]表示),如果对所有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权),且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j]成立,则M是图G的一个最佳匹配。
对于任何G和M,可行标都存在。
在二分图G和一组可行标的基础上,由满足可行标边界条件的所有边组成的生成子图,称为它的等价子图,在这个等价子图上寻找它的完备匹配,如果完备匹配存在,这个完备匹配M就是图G的一种逐次修改可行顶标的方法,即它的等价子图,在该等价子图上寻找它的完备匹配,如果完备匹配存在,那么这个算法就是图G的一种逐次修改可行顶标的方法,使之对应的等价子图上的完全匹配。
KM算法流程和实例
KM算法流程:
1.初始化可行顶标的值。
2.用匈牙利算法在等价子图中寻找完全匹配。
3.如果找不到完全匹配,修改可行顶标的值。
4.重复(2)(3)直至找到完全匹配的相等子图。
解译算法实例:
带权二分图如下:
寻找x0的增广路径,找到x0-y4,然后从x1中找到增广路径,这时就需要修改顶标,再加入一个最优的新边到等价子图:此时搜索过的路径是x1-y4-x0,而在路径上的X顶点就是S(x0)-weight(xiyj)),Y顶点为T(y4),对所有在S中的点xi及不在T中的点yj,计算d=min{(xi)+L(yj)-weight(xiyj))},S中的点的顶标减去d,T中点的顶标加上d,保持顶标仍然是可行的,然后计算d=min{(L(xi)+L(yj)-weight(xiyj))},并将S中的点的顶标减去d,T中的点在T中的顶标加上d,保持顶标的顶标加上d,就会发现顶标仍然是一个可行的,在x1中没有找到增广路径,在这个时候,就需要修改顶标,并在这个位置上找到一个最优的新边到等价子图,就是在这个位置上,在x1中找到一个点xi和不在T中的点yj,计算d=min{(L(xi)+L(yj)-weight(xiyj))},在S中的点的顶标减去d,T中的点的顶标加上d,而不在T中的点yj=min{(xi)+L(yj)-weight(
KM算法原为O(n4),n个结点找n次增广路径,在某一次找增光路径中,顶标最多需要n2次修改顶标的松弛量;
以上的所有内容就是小编对KM算法的理解了,希望能帮助到大家。
>>>>>>点击进入云计算专题