算法, Kuhn"/>
二分图匹配,Hangarian算法, Kuhn
一. 看到的比较好的文章:
图论总结(一)二分图最大匹配_LinHunYoR的博客-CSDN博客_二分图最大匹配://brc2/the-algorithm-workshop//
匈牙利算法(Kuhn-Munkres)算法_17420的博客-CSDN博客_munkres算法
二、二分图最优匹配:
匹配:在二分图G的一个子图M中, M的边集{E}中的任意两条边都不交汇于同一个结点,则称M是一个匹配
最优匹配:M的边数最多(边无权重, Hangarian 算法), 或者是边的权重(costs)和最小(Kuhn-Munkres算法)
三、一些开源实现:
3.1 Munkres-cpp: ://github/saebyn/munkres-cpp简介:1)基于c++的带权(cost)的二分图匹配,希望权重的和最小, inplace改变costs matrix的值;2)没有办法表示不相连的顶点, 效率上稍微低一些;
正常输出:0的地方表示匹配的位置
solve的时间:50x50的矩阵大概在10ms左右:
更多推荐
二分图匹配,Hangarian算法, Kuhn
发布评论