分配问题，一个NumPy函数？

Question

由于assignment problem可以以单个矩阵的形式提出，我想知道NumPy是否有一个函数来求解这样一个矩阵。到目前为止我还没有找到。也许你们中的一个知道NumPy/SciPy是否有一个赋值问题解决函数？

编辑：与此同时，我在http://software.clapper.org/munkres/找到了一个Python（不是NumPy/SciPy）实现。不过，我还是认为NumPy/SciPy实现会快得多，对吧？

Answer 1

我希望更新的scipy.optimize.linear_sum_assignment速度最快，但是（也许并不奇怪）更新的Cython library（它没有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

我在2x2和100x120（快10-40倍）之间看到了类似的结果。

Answer 2

现在，scikit learn中的munkres算法在sklearn/utils/linear_assignment_.py下有一个numpy实现，它唯一的依赖项是numpy。我用了一些大约20x20的矩阵，它的速度似乎是问题中链接到的矩阵的4倍。cProfiler显示100次迭代的时间是2.517秒，而不是9.821秒。

Answer 3

不，NumPy不包含这样的函数。组合优化不在NumPy的范围内。也许可以使用scipy.optimize中的一个优化器来实现这一点，但我感觉这些约束的形式可能不正确。

NetworkX可能还包括分配问题的算法。