Задача назначения, функция numpy?

Question

Поскольку assignment problem может быть поставлен в виде одной матрицы, я блуждаю, если numpy имеет функцию для решения такой матрицы. До сих пор я не нашел никого. Может быть, один из вас, ребята, знает, имеет ли функция numpy/scipy функцию решения задачи-назначения?

Редактировать: В то же время я нашел реализацию python (не numpy/scipy) на http://www.clapper.org/software/python/munkres/. Тем не менее, я полагаю, что реализация numpy/scipy может быть намного быстрее, не так ли?

Answer 1

Нет, NumPy не содержит такой функции. Комбинаторная оптимизация выходит за рамки возможностей NumPy. Возможно, это возможно сделать с одним из оптимизаторов в scipy.optimize, но я чувствую, что ограничения могут быть неправильной формы.

NetworkX, возможно, также содержит алгоритмы для проблем с назначением.

Answer 2

Существует реализация Munkres' algorithm в качестве модуля расширения python с поддержкой numpy. Я успешно использовал его на своем старом ноутбуке. Однако это не работает на моей новой машине - я предполагаю, что существует проблема с «новыми» версиями numpy (или 64-битной аркой).

Answer 3

В настоящее время существует многократная реализация алгоритма munkres в scikit-learn под sklearn/utils/linear_assignment_.py, его единственная зависимость - numpy. Я пробовал его с примерно 20x20 матрицами, и, похоже, он примерно в 4 раза быстрее, чем тот, который связан с вопросом. cProfiler показывает 2,517 секунды против 9,821 секунды за 100 итераций.

Answer 4

Я надеялся, что новая scipy.optimize.linear_sum_assignment будет быстрым, но (возможно, не удивительно) Cython library (который не имеет пип поддержки) значительно быстрее, по крайней мере, для моего случая использования:

$ 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 

I видел аналогичные результаты для размеров от 2x2 до 100x120 (на 10-40 раз быстрее).

Answer 5

Еще одна быстрая реализация, как уже намекала @Matthew: scipy.optimize, имеет функцию, называемую linear_sum_assignment. Из документов:

Используемый метод - это венгерский алгоритм, также известный как алгоритм Munkres или Kuhn-Munkres.

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