作業問題，一個numpy函數？

Question

由於assignment problem可以以單個矩陣的形式提出，如果numpy具有解決這種矩陣的函數，我就會遊蕩。到目前爲止，我沒有發現。也許你們中的一個人知道numpy/scipy是否具有分配問題解決功能？

編輯：在此期間，我發現了一個python（非numpy/scipy）實現在http://www.clapper.org/software/python/munkres/。不過，我認爲一個numpy/scipy實現可能會快得多，對吧？

Answer 1

不，NumPy不包含這樣的功能。組合優化不在NumPy的範圍內。有可能用scipy.optimize中的優化器之一來完成，但我有一種感覺，這種約束可能不是正確的形式。

NetworkX可能還包括分配問題的算法。

Answer 2

Munkres' algorithm作爲具有numpy支持的python擴展模塊的實現。我已經在我的舊筆記本電腦上成功使用了它。但是，它不適用於我的新機器 - 我認爲「新」numpy版本（或64位拱）存在問題。

Answer 3

現在在scikit-learn下有一個nunky實現的munkres算法，其sklearn/utils/linear_assignment_.py其唯一的依賴是numpy。我用一些大約20x20的矩陣進行了試驗，似乎是問題中相關問題的4倍。 cProfiler在100次迭代中顯示2.517秒比9.821秒。

Answer 4

我希望在新的scipy.optimize.linear_sum_assignment將是最快的，但（這也許並不奇怪）的Cython library（不具備畫中畫功能的支持）顯著更快，至少在我的使用情況：

$ 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 

我在2x2和100x120之間看到類似的結果（快10-40倍）。

Answer 5

另一個快速實現，正如@Matthew暗示的那樣：scipy.optimize有一個叫做linear_sum_assignment的函數。從文檔：

使用的方法是匈牙利算法，也被稱爲Munkres或Kuhn-Munkres算法。

https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html