最小成本偶匹配代碼我二部圖中尋找最大重量/最小成本匹配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