代入問題は単一の行列の形で提起できるので、NumPy にそのような行列を解く機能があるかどうか疑問に思っています。これまでのところ、私は何も見つけていません。NumPy/SciPy に代入問題解決機能があるかどうか知っている人がいるでしょうか?
編集:その間、 http: //software.clapper.org/munkres/ で Python (NumPy/SciPy ではない) の実装を見つけました。それでも、NumPy/SciPy の実装ははるかに高速になると思いますよね?
質問する
11913 次
7 に答える
16
sklearn/utils/linear_assignment_.pyの下の scikit-learn には、munkres アルゴリズムの numpy 実装があり、唯一の依存関係は numpy です。約20x20の行列で試してみましたが、質問にリンクされているものよりも約4倍速いようです。cProfiler は、100 回の反復で 2.517 秒と 9.821 秒を示しています。
于 2014-03-31T22:44:35.633 に答える
6
いいえ、NumPy にはそのような関数は含まれていません。組み合わせ最適化は、NumPy の範囲外です。オプティマイザの 1 つを使用して実行できる可能性がありますがscipy.optimize、制約が正しい形式ではない可能性があると感じています。
NetworkXには、割り当て問題のアルゴリズムも含まれている可能性があります。
于 2009-09-17T02:09:07.973 に答える
5
@Matthew によってすでに示唆されているように、さらに別の高速な実装:scipy.optimizeと呼ばれる関数がありますlinear_sum_assignment。ドキュメントから：
使用される方法は、Munkres または Kuhn-Munkres アルゴリズムとも呼ばれるハンガリー語アルゴリズムです。
于 2016-11-19T16:34:44.617 に答える
2
numpyをサポートするPython拡張モジュールとしてMunkresのアルゴリズムの実装があります。私は古いラップトップでそれをうまく使用しました。ただし、新しいマシンでは機能しません。「新しい」numpyバージョン（または64ビットアーチ）に問題があると思います。
于 2009-10-02T15:16:38.043 に答える
0
他のいくつかの回答で既に言及されているソルバーに加えてscipy.optimize.linear_sum_assignment、SciPy (1.6.0 現在) にはスパース性に適したソルバーも付属していscipy.sparse.csgraph.min_weight_full_bipartite_matchingます。
In [2]: from scipy.sparse import random
In [3]: from scipy.sparse.csgraph import min_weight_full_bipartite_matching
In [4]: from scipy.optimize import linear_sum_assignment
In [15]: sparse = random(1000, 1000, density=0.01, format='csr')
In [16]: %timeit min_weight_full_bipartite_matching(sparse)
3.84 ms ± 12.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [17]: dense = sparse.toarray()
In [18]: %timeit linear_sum_assignment(dense)
18.8 ms ± 291 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
于 2021-01-01T17:57:05.213 に答える