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

客服QQ:3315713922

匈牙利算法

作者:匿名     来源: 云计算点击数:1131发布时间: 2021-10-21 15:08:04

标签: 虚拟化匈牙利算法实现

  匈牙利算法是一种种时间内解决任务分配问题的组合优化算法,推进了后来的原始对偶方法。美国数学家哈罗德·库恩于1965年提出该算法。这种算法之所以被称为匈牙利算法,是因为它的大部分是基于匈牙利数学家之前的DénesKnig和Jeng被创建的。

  基本概念

  二分图:二分图又称二部图。简单地说,如果可将图中点分成两组,并使所有边都跨越群组的边界,则此为二分图。精确地说:将图的顶点分成两个不相交的U和V,使每个边分别连接U、V中的顶点。这个图是一个二分图,如果存在这样的划分。一个等价的二分图定义是:不包含"包含奇数条边的环"的图。构建子图:子图包含了原图的所有顶点。

  匹配:通俗地说:匹配是边的集合,其中任何两条边都没有共同顶点.定义:对于给定的二分图G,在G的子图M中,M的边集合{E}中的任意两条边不依赖于同一顶点,则称M为匹配。

  最大匹配:在图的所有匹配中,包含最多边的匹配称为最大匹配。

  完全匹配:如果图G的一个匹配M,那么G的每一个顶点都与匹配M中的一条边相关联,那么M就是完美匹配;完备匹配必须是最大匹配.  

 

  如图:Fig.1是一个二分图,把它改成Fig.2,更直观一些;Fig.3-红色部分,表示最大匹配;Fig.4表示完全匹配。

  最大匹配求解的匈牙利算法

  求得最大匹配最直接暴力的方法是:找出全部匹配,然后保留边最多的.此方法的复杂性是边数目呈指数级函数.匈牙利算法更有效。

  增广路径:如果P是图G中一条连接两个未匹配点的路径,而P属于匹配M的边,而不属于M的边(即匹配边和不匹配边)在P上交替出现,则称P为相对于M的增广路径.  

 

  如上所示,Fig.5红色为匹配,Fig.6为增广路径相对匹配。

  根据增广路径的定义,可以得出三个结论:

  l 其路径长度一定是奇数,且第一边和最后一边均不属于M;

  l 通过取反运算,可得到较大匹配M1;

  l 最大匹配M是G,只有当没有相对于M的增广路径时。

  匈牙利算法:通过增广路径获得最大匹配,其结构如下:

  1.放置M是空的;

  2.求一条增广路径P,通过取反运算得到较大匹配M1;

  3.反复执行第2步,直到没有找到增广路径。

  匈牙利算法的实现  

  增广路径的寻径有两种,一种是深搜索,一种是宽搜索。如上所示,蓝色线是第一次匹配子图,现在是x1查找增广路径,如果是DFS深度搜索:首先:x1找到y0,发现y0已经被x0匹配,于是深入到x0,为x0找新的匹配点,发现x0可以匹配y2,让x0与y2匹配,然后让x1与y0匹配,得到第二次匹配子图.现在,从x2出发,搜寻增广路径,x2找到y0匹配,但发现y0已经被x1匹配了,于是就深入到x1,去为x1找新的匹配节点,结果发现x1没有其他的匹配节点,于是匹配失败,x2接着找y1,发现y1可以匹配,于是就找到了新的增广路径,将x2-y1加入匹配中。

  匈牙利算法的实现原理就是这样的了,只要理解了这个实现原理,代码就很容易敲出来。

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

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