代入問題、NumPy 関数?

Question

以来 割り当て問題 は単一の行列の形で提示できますが、NumPy にそのような行列を解く機能があるかどうか疑問に思っています。今のところ何も見つかりませんでした。もしかしたら、NumPy/SciPy に代入問題解決機能があるかどうか知っている人がいるかもしれません。

編集： その間、私は Python (NumPy/SciPy ではない) 実装を次の場所で見つけました。 http://software.clapper.org/munkres/. 。それでも、NumPy/SciPy 実装のほうがはるかに高速になる可能性があると思いますよね?

Answer 1

いいえ、numpyのはそのような機能が含まれていません。組合せ最適化は、numpyのの範囲外です。 scipy.optimizeにおけるオプティマイザの一つでそれを行うことは可能かもしれないが、私は制約が右のフォームのではないかもしれないという気持ちを持っています。

NetworkX にもおそらく割り当ての問題のためのアルゴリズムが含まれます。

Answer 2

scikit-learn には、munkres アルゴリズムの numpy 実装が追加されました。 sklearn/utils/linear_assignment_.py 唯一の依存関係は numpy です。約20x20の行列で試してみましたが、質問でリンクされているものよりも約4倍高速であるようです。cProfiler は、100 回の反復で 2.517 秒対 9.821 秒を示します。

Answer 3

私は新しいscipy.optimize.linear_sum_assignmentが最速になることを期待していたが（おそらく驚くことではないが） Cythonライブラリー（PIPをサポートしていません）のは、少なくとも私のユースケースのために、大幅に高速化されます：

$ python -m timeit -s 'from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0); c = np.random.rand(20,30)' 'a,b = linear_sum_assignment(c)'
100 loops, best of 3: 3.43 msec per loop
$ python -m timeit -s 'from munkres import munkres; import numpy as np;  np.random.seed(0); c = np.random.rand(20,30)' 'a = munkres(c)'
10000 loops, best of 3: 139 usec per loop
$ python -m timeit -s 'from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0);' 'c = np.random.rand(20,30); a,b = linear_sum_assignment(c)'
100 loops, best of 3: 3.01 msec per loop
$ python -m timeit -s 'from munkres import munkres; import numpy as np; np.random.seed(0)' 'c = np.random.rand(20,30); a = munkres(c)'
10000 loops, best of 3: 127 usec per loop

私は2×2および100x120（10-40x速い）間のサイズの同様の結果を見ます。

Answer 4

さらに別の高速な実装では、既に@Matthewによって示唆：scipy.optimizeはlinear_sum_assignmentと呼ばれる機能があります。ドキュメントから：

  

使用方法もMunkres又はキューン - Munkresアルゴリズムとして知られているハンガリーのアルゴリズムである。

ます。https：//ドキュメント。 scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.htmlする

Answer 5

はPython拡張モジュールとして Munkres'アルゴリズムするの実装がありますnumpyのをサポートしています。私は私の古いノートパソコン上で正常にそれを使用しました。しかし、それは私の新しいマシン上の作業はしません - 私は「新しい」numpyのバージョン（または64ビットのアーチ）に問題があると仮定します。

。

Answer 6

（現在はベータ版）バージョン2.4のように、

は、NetworkXはnx.algorithms.bipartite.minimum_weight_full_matching介して問題を解決します。執筆の時点では、実装は、ボンネットの下にscipyのダウンロードのscipy.optimize.linear_sum_assignmentを使用するため、同じ性能特性を期待しています。