Python中的最大权重/最小成本Bipartite匹配代码

Question

我在二分图中搜索最大权重/最小成本匹配的Python代码.我一直在使用NetworkX中的一般情况最大权重匹配代码,但我发现它对我的需求来说太慢了.这可能是由于通用算法速度较慢以及NetworkX解决方案完全用Python实现的事实.理想情况下,我想为包含一些C/C++代码的二分匹配问题找到一些Python代码,但是现在,任何比NetworkX实现更快的东西都会有所帮助.

Answer 1

您是否尝试过匈牙利算法的 scipy 实现，也称为 Munkres 或 Kuhn-Munkres 算法？

scipy.optimize.linear_sum_assignment

Answer 2

经过一番进一步调查后,我发现以下两个模块特别有用(http://pypi.python.org/pypi/pyLAPJV/0.3和 http://pypi.python.org/pypi/hungarian).它们都是用C++实现的Python绑定算法,运行速度比NetworkX匹配实现快得多.然而,pyLAPJV实现似乎对我的需求有点过于复杂,并且不能很好地正确处理相同加权的边缘.匈牙利模块(虽然据称比pyLAPJV算法慢)比我目前正在处理的数据大小上的NetworkX实现快了大约3个数量级.我还要再看一下kunigami建议的代码,因为我相信它可以通过Shedskin很容易地运行,以实现相当快的实现.