二分图最佳匹配

如果G为加权二分图,则权值和最大的完备匹配称为最佳匹配.

求一个二分图的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法.

KM算法的基本思想是,把权值转化为可行顶标,再用匈牙利算法求出一组完备匹配,如果无法求出完备匹配,则修改可行顶标,直至找到完备匹配为止,这时的完备匹配为最佳匹配.

Kuhn－Munkras算法流程：

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

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

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

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