二分图最佳匹配是一个数学名词。
二分图最佳匹配详细介绍
二分图最佳匹配是一个数学名词。
二分图最佳匹配应用
如果G为加权二分图,则权值和最大的完备匹配称为最佳匹配.
求一个二分图的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法.
KM算法的基本思想是,把权值转化为可行顶标,再用匈牙利算法求出一组完备匹配,如果无法求出完备匹配,则修改可行顶标,直至找到完备匹配为止,这时的完备匹配为最佳匹配.
Kuhn－Munkras算法流程：
(1)初始化可行顶标的值
(2)用匈牙利算法寻找完备匹配
(3)若未找到完备匹配则修改可行顶标的值
(4)重复(2)(3)直到找到相等子图的完备匹配为止
