分配问题,一个numpy函数？

Question

由于赋值问题可以以单个矩阵的形式提出,如果numpy具有解决这种矩阵的函数,我就会徘徊.到目前为止,我没有找到.也许你们其中一个人知道numpy/scipy是否有一个赋值问题解决函数？

编辑:同时我在http://www.clapper.org/software/python/munkres/找到了一个python(不是numpy/scipy)实现.我仍然认为numpy/scipy实现可能会快得多,对吧？

Answer 1

现在scleit-learn中的munkres算法实现了numpy实现,在sklearn/utils/linear_assignment_.py下它唯一的依赖是numpy.我尝试使用大约20x20的矩阵,它似乎是问题中链接速度的4倍.对于100次迭代,cProfiler显示2.517秒对9.821秒.

Answer 2

我希望新版本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

我看到大小在2x2和100x120之间的类似结果(快10-40倍).

Answer 3

不，NumPy 不包含这样的功能。组合优化超出了 NumPy 的范围。可以使用其中的一个优化器来做到这一点，scipy.optimize但我觉得约束可能不是正确的形式。

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

Answer 4

@Matthew已经暗示了另一个快速实现，它scipy.optimize具有一个名为的函数linear_sum_assignment。从文档：

使用的方法是匈牙利算法，也称为Munkres或Kuhn-Munkres算法。

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