El problema de asignación, ¿una función numpy?

Dado que un problema de asignación puede plantearse en la forma de una sola matriz, estoy vagando si el número tiene una función para resolver dicha matriz. Hasta ahora no he encontrado ninguno. Tal vez alguno de ustedes sepa si numpy / scipy tiene una función de resolución de problemas de asignación?

Edición: Mientras tanto, he encontrado una implementación de python (no numpy / scipy) en http://www.clapper.org/software/python/munkres/ . Aún así, supongo que una implementación numpy / scipy podría ser mucho más rápida, ¿verdad?

Related of "El problema de asignación, ¿una función numpy?"

No, NumPy no contiene tal función. La optimización combinatoria está fuera del scope de NumPy. Puede ser posible hacerlo con uno de los optimizadores en scipy.optimize pero tengo la sensación de que las restricciones pueden no ser de la forma correcta.

NetworkX probablemente también incluye algoritmos para problemas de asignación.

Ahora hay una implementación numpy del algoritmo munkres en scikit-learn bajo sklearn / utils / linear_assignment_.py su única dependencia es numpy. Lo probé con algunas matrices de aproximadamente 20×20, y parece ser aproximadamente 4 veces más rápido que el que está vinculado en la pregunta. cProfiler muestra 2.517 segundos frente a 9.821 segundos para 100 iteraciones.

Esperaba que el nuevo scipy.optimize.linear_sum_assignment fuera más rápido, pero (quizás no sorprendentemente) la biblioteca de Cython (que no tiene soporte para pip) sea significativamente más rápida, al menos para mi caso de uso:

 $ 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 

Vi resultados similares para tamaños entre 2×2 y 100×120 (10-40x más rápido).

Otra implementación rápida, como ya insinuó @Matthew: scipy.optimize tiene una función llamada linear_sum_assignment . De los documentos:

El método utilizado es el algoritmo húngaro, también conocido como el algoritmo Munkres o Kuhn-Munkres.

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

Hay una implementación del algoritmo de Munkres como un módulo de extensión de python que tiene soporte numpy. Lo he usado con éxito en mi vieja computadora portátil. Sin embargo, no funciona en mi nueva máquina. Supongo que hay un problema con las “nuevas” versiones numpy (o arco de 64 bits).