私は二部グラフで最大の重量/最小コストマッチングを求めるPythonコードを探しています。私はNetworkXで一般的なケースの最大重量マッチングコードを使用してきましたが、それは私の必要性には遅すぎます。これは、一般的なアルゴリズムが遅いという事実と、NetworkXのソリューションが完全にPythonで実装されていることの両方が原因と考えられます。理想的には、私はいくつかのC/C++コードをラップする二部的なマッチング問題のためのPythonコードを探したいと思いますが、今はNetworkXの実装より速いものが役に立ちます。最大重量/最小コストPythonでの2者一致コード
さらにいくつかの調査の後、私は（http://pypi.python.org/pypi/pyLAPJV/0.3とhttp://pypi.python.org/pypi/hungarian）特に参考に二つのモジュールを見つけました。どちらもPythonバインディングを使用してC++で実装されたアルゴリズムであり、NetworkXマッチングの実装よりもはるかに高速に動作します。しかし、pyLAPJVの実装は、私のニーズにとってはあまりにも揺らめくようで、同じ重み付きエッジを適切に処理できません。ハンガリーのモジュール（おそらくpyLAPJVアルゴリズムよりも遅いですが）は、私が現在扱っているデータサイズでNetworkXの実装より約3桁高速です。 kunigamiが提案したコードをもう一度見てみましょう。私は、Shedskinをかなり簡単に実行して、合理的に速い実装を行うことができると信じています。
これはあなたが探しているものですが、それはホップクロフト・カープ二部グラフマッチングアルゴリズムのPython実装であれば、あまりにもわかりません。もしそうでなければ、おそらくあなたのための良い出発地になるかもしれません。
リンクNicoをありがとう。しかし、最大のマッチング問題は、最大のマッチング問題よりも問題があります。それは関与する頂点の最大数を見つけることに関係していますが、勘は重要ではありません。 – nomad
はあなたにもMunkresまたはクーン-Munkresアルゴリズムとして知られ、ハンガリーのアルゴリズムのscipyのダウンロードの実装を試してみましたか？
あなたが心の中で、特定の擬似コードをお持ちですか？あなたはPythonの入出力の例を提供できますか？ – kevpie
類似した質問http://stackoverflow.com/questions/4075669/hungarian-algorithm-in-python – Ante
@Kevpie私はほぼすべてのインターフェイスを開いています。最大の重み問題は、それ自体がよく定義されています（たとえば、Wikipedia http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs）。私はそれを再定義するスペースを無駄にしたくありませんでした。入力はグラフでも重み行列でも、出力は二部頂点間のマッチングです。 – nomad