Algoritmo húngaro

Carta Común · N.º 311438

El algoritmo húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo O ( n 3 ) {\displaystyle O(n^{3}\,)} . La primera versión conocida del método húngaro, fue inventado y publicado por Harold W. Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres. El algoritmo desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de otros dos matemáticos húngaros: Dénes Kőnig y Jenő Egerváry. La gran ventaja del método de Kuhn es que es fuertemente polinómico (ver Complejidad computacional para más detalles). El algoritmo húngaro construye una solución del problema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco…

Leer en Wikipedia