由于分配问题可以以单个矩阵的形式提出，我想知道 NumPy 是否具有解决这样一个矩阵的功能。到目前为止，我还没有找到。也许你们中的一个人知道 NumPy/SciPy 是否具有分配问题解决功能？
编辑：与此同时，我在http://software.clapper.org/munkres/找到了一个 Python（不是 NumPy/SciPy）实现。我仍然认为 NumPy/SciPy 实现可能会快得多，对吧？
问问题
11913 次
7 回答
16
现在在sklearn/utils/linear_assignment_.py下的 scikit-learn 中有一个 munkres 算法的 numpy 实现，它唯一的依赖是 numpy。我尝试了一些大约 20x20 的矩阵，它的速度似乎是问题中链接的矩阵的 4 倍。cProfiler 显示 2.517 秒对比 9.821 秒进行 100 次迭代。
于 2014-03-31T22:44:35.633 回答
9
我希望更新的scipy.optimize.linear_sum_assignment速度最快，但是（也许并不奇怪）Cython 库（不支持 pip）要快得多，至少对于我的用例而言：
更新：使用munkresv1.1.2 和scipyv1.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
于 2016-03-16T18:29:58.273 回答
6
不，NumPy 不包含这样的功能。组合优化超出了 NumPy 的范围。可以使用其中的一个优化器来做到这一点，scipy.optimize但我感觉约束可能不是正确的形式。
NetworkX可能还包括分配问题的算法。
于 2009-09-17T02:09:07.973 回答
5
正如@Matthew 已经暗示的那样，另一个快速实现scipy.optimize有一个名为linear_sum_assignment. 从文档：
使用的方法是匈牙利算法，也称为 Munkres 或 Kuhn-Munkres 算法。
于 2016-11-19T16:34:44.617 回答
2
Munkres 算法有一个实现作为具有 numpy 支持的 python 扩展模块。我已经在我的旧笔记本电脑上成功使用了它。但是，它在我的新机器上不起作用——我认为“新”numpy 版本（或 64 位拱门）存在问题。
于 2009-10-02T15:16:38.043 回答
2
从 2.4 版（2019-10-16 发布）开始，NetworkX 通过nx.algorithms.bipartite.minimum_weight_full_matching. 在撰写本文时，该实现scipy.optimize.linear_sum_assignment在底层使用了 SciPy，因此期望具有相同的性能特征。
于 2019-08-08T06:55:44.907 回答
0
除了在scipy.optimize.linear_sum_assignment其他一些答案中已经提到的求解器之外，SciPy（从 1.6.0 开始）还带有一个稀疏友好的求解器scipy.sparse.csgraph.min_weight_full_bipartite_matching。
In [2]: from scipy.sparse import random
In [3]: from scipy.sparse.csgraph import min_weight_full_bipartite_matching
In [4]: from scipy.optimize import linear_sum_assignment
In [15]: sparse = random(1000, 1000, density=0.01, format='csr')
In [16]: %timeit min_weight_full_bipartite_matching(sparse)
3.84 ms ± 12.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [17]: dense = sparse.toarray()
In [18]: %timeit linear_sum_assignment(dense)
18.8 ms ± 291 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
于 2021-01-01T17:57:05.213 回答