Kuhn-Munkres algorithm 库恩-曼克莱斯算法

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

Kuhn-Munkras算法流程:

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

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

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

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

References

Kuhn-Munkres算法
匹配问题: 匈牙利算法 、最优指派、相等子图、库恩—曼克莱斯 (Kuhn-Munkres) 算法

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据