Il problema di assegnazione, una funzione numpy?

Question

Poiché un assignment problem può essere posto sotto forma di una singola matrice, sto vagando se numpy ha una funzione per risolvere una tale matrice. Finora non ho trovato nessuno. Forse qualcuno di voi sa se Numpy/Scipy ha una funzione di risolvere problemi di assegnazione?

Modifica: Nel frattempo ho trovato un'implementazione python (non numpy/scipy) a http://www.clapper.org/software/python/munkres/. Suppongo comunque che un'implementazione numpy/scipy possa essere molto più veloce, giusto?

Answer 1

No, NumPy non contiene tale funzione. L'ottimizzazione combinatoria è al di fuori dell'ambito di NumPy. Potrebbe essere possibile farlo con uno degli ottimizzatori in scipy.optimize ma ho la sensazione che i vincoli potrebbero non essere della forma corretta.

NetworkX probabilmente include anche algoritmi per problemi di assegnazione.

Answer 2

Esiste un'implementazione dello Munkres' algorithm come un modulo di estensione python con supporto per numpy. L'ho usato con successo sul mio vecchio portatile. Tuttavia, non funziona sulla mia nuova macchina - presumo che ci sia un problema con le "nuove" versioni numpy (o arco a 64 bit).

Answer 3

Esiste ora un'implementazione numpy dell'algoritmo munkres in scikit-learn in sklearn/utils/linear_assignment_.py la sua unica dipendenza è numpy. L'ho provato con alcune matrici di circa 20x20 e sembra essere circa 4 volte più veloce di quello collegato alla domanda. cProfiler mostra 2.517 secondi contro 9.821 secondi per 100 iterazioni.

Answer 4

Speravo che il più recente scipy.optimize.linear_sum_assignment sarebbe più veloce, ma (forse non sorprendentemente) il Cython library (che non ha il supporto pip) è significativamente più veloce, almeno per il mio caso d'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 

I ha visto risultati simili per dimensioni tra 2x2 e 100x120 (10-40x più veloce).

Answer 5

Un'altra implementazione rapida, come già suggerito da @Matthew: scipy.optimize ha una funzione chiamata linear_sum_assignment. Dalla documentazione:

Il metodo utilizzato è l'algoritmo ungherese, noto anche come algoritmo Munkres o Kuhn-Munkres.

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