最小成本偶匹配代码我二部图中寻找最大重量/最小成本匹配Python代码。我一直在使用NetworkX中的一般情况下最大权重匹配代码，但是我发现它对我的需求来说太慢了。这可能是由于一般算法速度较慢以及NetworkX解决方案完全用Python实现的事实。理想情况下，我希望找到一些用于包装某些C/C++代码的二分匹配问题的Python代码，但现在，比NetworkX实现更快的任何操作都会有所帮助。最大重量/ Python中
经过一些进一步的调查，我发现下面的两个模块特别有用（http://pypi.python.org/pypi/pyLAPJV/0.3和http://pypi.python.org/pypi/hungarian）。它们都是使用Python绑定在C++中实现的算法，运行速度比NetworkX匹配实施要快得多。但是，pyLAPJV的实现似乎对我的需求来说有点过于浮躁，并没有很好地处理相同加权的边缘。匈牙利模块（虽然据推测比pyLAPJV算法慢）在我目前处理的数据量上比NetworkX实现快大约3个数量级。我还会再看一下kunigami提出的代码，因为我相信它可以通过Shedskin运行，相当容易实现合理的快速实现。
不太清楚，如果这是你在找什么，但它是一个Python实现Hopcroft - 卡普二分图匹配算法。如果不是，它可能会成为你的一个好去处。
感谢您的链接尼科。然而，最大匹配问题比最大权重匹配问题更为严重;它关心的是找到参与顶点的最大数量，肠线不采用权重isnto帐户。 – nomad 2010-12-13 15:09:09
你试过SciPy的实施匈牙利算法的，也被称为的Munkres或库恩的Munkres算法？
您是否有任何特定的伪代码？你能提供一个python输入/输出的例子吗？ – kevpie 2010-12-13 07:20:11
类似问题http://stackoverflow.com/questions/4075669/hungarian-algorithm-in-python – Ante 2010-12-13 14:51:54
@Kevpie我接受几乎任何接口。最大重量的问题是，它本身良好定义（维基百科例如http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs），所以我不想浪费空间重新定义。输入将是一个图或甚至只是一个权重矩阵，输出将是两部分顶点之间的匹配。 – nomad 2010-12-13 15:19:09