下载安卓APP箭头
箭头给我发消息

客服QQ:3315713922

KM算法

作者:匿名     来源: 云计算点击数:848发布时间: 2021-10-21 15:00:13

标签: 虚拟化算法KM算法

  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算法的理解了,希望能帮助到大家。

    >>>>>>点击进入计算专题

赞(7)
踩(0)
分享到:
华为认证网络工程师 HCIE直播课视频教程