NumPy函数中的指派问题？

Question

因为一个分配问题可以用一个单一的矩阵来表示，所以我在想NumPy有没有可以解决这种矩阵的函数。到目前为止，我还没有找到。也许你们中的某个人知道NumPy/SciPy有没有解决分配问题的函数？

编辑：在这段时间里，我找到了一种Python（不是NumPy/SciPy）的实现，地址是http://software.clapper.org/munkres/。不过我觉得NumPy/SciPy的实现可能会更快，对吧？

Answer 1

我原本希望新的 scipy.optimize.linear_sum_assignment 会更快，但（也许并不意外）Cython库（这个库不支持pip安装）在我的使用场景中明显更快：

更新：使用 munkres 版本1.1.2和 scipy 版本1.5.0 得到了以下结果：

$ 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)"
10000 loops, best of 5: 32.8 usec per loop
$ python -m timeit -s "from munkres import Munkres; import numpy as np;  np.random.seed(0); c = np.random.rand(20,30); m = Munkres()" "a = m.compute(c)"
100 loops, best of 5: 2.41 msec 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)"
5000 loops, best of 5: 51.7 usec per loop
$ python -m timeit -s "from munkres import Munkres; import numpy as np;  np.random.seed(0)" "c = np.random.rand(20,30); m = Munkres(); a = m.compute(c)"
10 loops, best of : 26 msec per loop

Answer 2

现在在scikit-learn中有一个用numpy实现的munkres算法，具体代码可以在sklearn/utils/linear_assignment_.py找到，它只依赖于numpy这个库。我用它测试了一些大约20x20的矩阵，发现它的速度大约是问题中提到的那个算法的4倍。使用cProfiler进行性能分析时，100次迭代的时间分别是2.517秒和9.821秒。

Answer 3

不，NumPy里没有这样的功能。组合优化不在NumPy的范围内。你可以试试用scipy.optimize里的某个优化工具，但我觉得可能不太符合你需要的限制条件。

NetworkX 可能也有处理分配问题的算法。