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

Question

我正在寻找用于在二分图中进行最大权重/最小成本匹配的Python代码。我一直在使用NetworkX中的通用最大权重匹配代码，但发现它对我来说太慢了。这可能是因为通用算法本身就比较慢，而且NetworkX的解决方案完全是用Python实现的。理想情况下，我希望找到一些针对二分匹配问题的Python代码，它能调用一些C/C++的代码，但现在，只要比NetworkX的实现快的任何东西都对我有帮助。

Answer 1

当你提到“最小成本匹配”时，我理解你是指在所有最大匹配中，找到成本最低的匹配。

从版本2.4（发布于2019年10月17日）开始，NetworkX专门处理这种二分图的情况，使用的是nx.algorithms.bipartite.minimum_weight_full_matching。

在背后，它依赖于scipy.optimize.linear_sum_assignment。从版本1.6.0开始，SciPy还提供了scipy.sparse.csgraph.min_weight_full_bipartite_matching，这个功能是为稀疏输入设计的，能够在处理稀疏图时提高性能。

Answer 2

你有没有试过使用scipy库里的匈牙利算法实现呢？这个算法也叫做Munkres算法或者Kuhn-Munkres算法。

scipy.optimize.linear_sum_assignment

Answer 3

经过进一步的调查，我发现以下两个模块特别有用：http://pypi.python.org/pypi/pyLAPJV/0.3 和 http://pypi.python.org/pypi/hungarian。这两个模块都是用C++写的算法，并且有Python的接口，所以可以在Python中使用，运行速度比NetworkX的匹配实现快很多。不过，pyLAPJV这个模块对我来说有点不稳定，处理相同权重的边时效果不好。而hungarian模块（虽然据说比pyLAPJV慢）在我目前处理的数据规模上，速度比NetworkX快了大约三个数量级。我还打算再看看kunigami推荐的代码，因为我觉得可以通过Shedskin比较容易地运行，从而实现一个相对较快的版本。