我在二分图中搜索最大权重/最小成本匹配的Python代码 . 我一直在使用NetworkX中的一般情况最大权重匹配代码，但我发现它对我的需求来说太慢了 . 这可能是由于通用算法速度较慢以及NetworkX解决方案完全用Python实现的事实 . 理想情况下，我想为包含一些C / C代码的二分匹配问题找到一些Python代码，但是现在，比NetworkX实现更快的任何东西都会有所帮助 .
经过一番进一步调查后，我发现以下两个模块特别有用（http://pypi.python.org/pypi/pyLAPJV/0.3和http://pypi.python.org/pypi/hungarian） . 它们都是使用Python绑定在C中实现的算法，并且运行速度比NetworkX匹配实现快得多 . 然而，pyLAPJV实现似乎对我的需求有点过于复杂，并且目前还没有处理过 . 我还要再看一下kunigami建议的代码，因为我相信它可以通过Shedskin很容易地运行，以实现相当快的实现 .
您是否尝试过使用匈牙利算法的scipy实现，也称为Munkres或Kuhn-Munkres算法？
scipy.optimize.linear_sum_assignment
不太确定这是否是您正在寻找的，但它是Hopcroft-Karp二分图匹配算法的python实现 . 如果没有，它可能是一个很好的起点 .
Hopcroft-Karp Bipartite Matching
最小权重二分匹配可以通过匈牙利算法（wikipedia）来解决 . 维基百科中的链接链接到python实现 . 不过，我比你提到的代码快了.2458665 .
4 回答
经过一番进一步调查后，我发现以下两个模块特别有用（http://pypi.python.org/pypi/pyLAPJV/0.3和http://pypi.python.org/pypi/hungarian） . 它们都是使用Python绑定在C中实现的算法，并且运行速度比NetworkX匹配实现快得多 . 然而，pyLAPJV实现似乎对我的需求有点过于复杂，并且目前还没有处理过 . 我还要再看一下kunigami建议的代码，因为我相信它可以通过Shedskin很容易地运行，以实现相当快的实现 .
您是否尝试过使用匈牙利算法的scipy实现，也称为Munkres或Kuhn-Munkres算法？
scipy.optimize.linear_sum_assignment
不太确定这是否是您正在寻找的，但它是Hopcroft-Karp二分图匹配算法的python实现 . 如果没有，它可能是一个很好的起点 .
Hopcroft-Karp Bipartite Matching
最小权重二分匹配可以通过匈牙利算法（wikipedia）来解决 . 维基百科中的链接链接到python实现 . 不过，我比你提到的代码快了.2458665 .