程序员
董欣欣的个人博客

二分图最大匹配的匈牙利算法

二分图最大匹配的匈牙利算法

二分图是这样一个图,它的顶点可以分类两个集合X和Y,所有的边关联在两个顶点中,恰好一个属于集合X,另一个属于集合Y。

最大匹配:图中包含边数最多的匹配称为图的最大匹配。

完美匹配:如果所有点都在匹配边上,称这个最大匹配是完美匹配。

最小覆盖: 最小覆盖要求用最少的点(X集合或Y集合的都行)让每条边都至少和其中一个点关联。可以证明:最少的点(即覆盖数)=最大匹配数

最小路径覆盖:

用尽量少的不相交简单路径覆盖有向无环图G的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个:X结点集中的i和Y结点集中的i’,如果有边i->j,则在二分图中引入边i->j’,设二分图最大匹配为m,则结果就是n-m。

最大独立集问题:

在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值.

如果图G满足二分图条件,则可以用二分图匹配来做.最大独立集点数 = N – 最大匹配数

一、匈牙利算法

设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。

v       给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

v       选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)

v       如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

最大匹配在实际中有广泛的用处,求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。

匈牙利算法是求解最大匹配的有效算法,该算法用到了增广路的定义(也称增广轨或交错轨):若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。

由增广路径的定义可以推出下述三个结论:

v       1.   P的路径长度必定为奇数,第一条边和最后一条边都不属于M。

v       2.   P经过取反操作(即非M中的边变为M中的边,原来M中的边去掉)可以得到一个更大的匹配M’。

v       3.   M为G的最大匹配当且仅当不存在相对于M的增广路径。

从而可以得到求解最大匹配的匈牙利算法:

v       (1)置M为空

v       (2)找出一条增广路径P,通过取反操作获得更大的匹配M’代替M

v       (3)重复(2)操作直到找不出增广路径为止

二、KM算法:

二分图最优匹配:对于二分图的每条边都有一个权(非负),要求一种完备匹配方案,使得所有匹配边的权和最大,记做最优完备匹配。(特殊的,当所有边的权为1时,就是最大完备匹配问题)

解二分图最优匹配问题可用穷举的方法,但穷举的效率=n!,所以我们需要更加优秀的算法。

先说一个定理:设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的一个最优匹配。

Kuhn-Munkras算法(即KM算法)流程:

v       (1)初始化可行顶标的值

v       (2)用匈牙利算法寻找完备匹配

v       (3)若未找到完备匹配则修改可行顶标的值

v       (4)重复(2)(3)直到找到相等子图的完备匹配为止

KM算法主要就是控制怎样修改可行顶标的策略使得最终可以达到一个完美匹配,首先任意设置可行顶标(如每个X节点的可行顶标设为它出发的所有弧的最大权,Y节点的可行顶标设为0),然后在相等子图中寻找增广路,找到增广路就沿着增广路增广。而如果没有找到增广路呢,那么就考虑所有现在在匈牙利树中的X节点(记为S集合),所有现在在匈牙利树中的Y节点(记为T集合),考察所有一段在S集合,一段在not T集合中的弧,取       delta = min {l(xi)+l(yj)-w(xi,yj) , | xi in S, yj   in not T}    。明显的,当我们把所有S集合中的l(xi)减少delta之后,一定会有至少一条属于(S, not T)的边进入相等子图,进而可以继续扩展匈牙利树,为了保证原来属于(S,T )的边不退出相等子图,把所有在T集合中的点的可行顶标增加delta。随后匈牙利树继续扩展,如果新加入匈牙利树的Y节点是未盖点,那么找到增广路,否则把该节点的对应的X匹配点加入匈牙利树继续尝试增广。

复杂度分析:由于在不扩大匹配的情况下每次匈牙利树做如上调整之后至少增加一个元素,因此最多执行n次就可以找到一条增广路,最多需要找n条增广路,故最多执行n^2次修改顶标的操作,而每次修改顶标需要扫描所有弧,这样修改顶标的复杂度就是O(n^2)的,总的复杂度是O(n^4)的。

对于not T的每个元素yj,定义松弛变量slack(yj) =min{l(xi)+l(yj)-w(xi,yj), | xi in S},很明显每次的delta = min{slack(yj), | yj   in not T},每次增广之后用O(n^2)的时间计算所有点的初始slack,由于生长匈牙利树的时候每条弧的顶标增量相同,因此修改每个slack需要常数时间(注意在修改顶标后和把已盖Y节点对应的X节点加入匈牙利树的时候是需要修改slack的)。这样修改所有slack值时间是O(n)的,每次增广后最多修改n次顶标,那么修改顶标的总时间降为O(n^2),n次增广的总时间复杂度降为O(n^3)。事实上这样实现之后对于大部分的数据可以比O(n^4)的算法快一倍左右。

利用二分图匹配的匈牙利算法和KM算法,我们可以求解大部分的关于二分图的问题,它们提供了求解最大匹配和最优匹配的有效算法,在具体编程时我们只要多注意优化,我们就可以得出求解这类问题的有效方法,从而可以对这类实际问题进行有效合理的解决。

未经允许不得转载:董不董 - 董欣欣的个人博客 » 二分图最大匹配的匈牙利算法
分享到: 更多 (0)

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    It’s about time sonoeme wrote about this.

    Symona2年前 (2016-10-24)回复

www.dongxinxin.cn 技术博客

联系我关于我