Поскольку задача присваивания может быть представлена в виде одной матрицы, мне интересно, есть ли в NumPy функция для решения такой матрицы. Пока я не нашел ни одного. Может быть, один из вас, ребята, знает, есть ли в NumPy/SciPy функция решения задач при назначении?
Изменить: Тем временем я нашел реализацию Python (не NumPy/SciPy) в http://software.clapper.org/munkres/. Тем не менее, я предполагаю, что реализация NumPy/SciPy может быть намного быстрее, верно?
Нет, NumPy не содержит такой функции. Комбинаторная оптимизация выходит за пределы области NumPy. Возможно, это возможно сделать с одним из оптимизаторов в scipy.optimize, но я чувствую, что ограничения могут быть не в правильной форме.
NetworkX, вероятно, также включает алгоритмы для проблем с назначением.
В настоящее время существует многократная реализация алгоритма munkres в scikit-learn в sklearn/utils/linear_assignment_.py его единственная зависимость - numpy. Я пробовал его с примерно 20x20 матрицами, и, похоже, он примерно в 4 раза быстрее, чем тот, который связан с вопросом. cProfiler показывает 2,517 секунды против 9,821 секунды для 100 итераций.
Я надеялся, что более новый 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 раз быстрее).
Еще одна быстрая реализация, как уже намекнул @Matthew: scipy.optimize имеет функцию под названием linear_sum_assignment. Из документов:
Используемый метод - это венгерский алгоритм, также известный как алгоритм Мункреса или Куна-Мункреса.
Существует реализация алгоритма Munkres в качестве модуля расширения python с поддержкой numpy. Я успешно использовал его на своем старом ноутбуке. Однако это не работает на моей новой машине - я предполагаю, что существует проблема с "новыми" версиями numpy (или 64-битной аркой).
Начиная с версии 2.4 (в настоящее время в бета-версии), NetworkX решает проблему с помощью nx.algorithms.bipartite.minimum_weight_full_matching. На момент написания, реализация использует SciPy scipy.optimize.linear_sum_assignment под капотом, поэтому ожидайте те же характеристики производительности.