现在的位置: 首页 > 综合 > 正文

离散数学之匈牙利算法

2018年05月11日 ⁄ 综合 ⁄ 共 341字 ⁄ 字号 评论关闭

 Given the following  graph, find the minimum cost cover in two ways .

http://hi.csdn.net/attachment/201111/18/0_13216151115Me3.gif

 

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

 

此处所说的匈牙利算法,除了最大匹配外,还基于此求带权二分图的最大权和匹配。

 

 

主要是保证利润的不变,即左侧和顶部的数值和与矩阵元素之差保持不变,同时矩阵元素在任何情况下均不为负,其余则加速每行每列均有0元素出现即可。

 

 

 

 

 

 

抱歉!评论已关闭.