Glosario · approach
Algoritmo Húngaro
Algoritmo combinatorio que resuelve el problema de asignación (matriz de costes n×n, emparejamiento uno-a-uno de coste mínimo) en tiempo polinómico O(n³); Kuhn (1955) y Munkres (1957).
Hungarian MethodHungarian AlgorithmAlgoritmo de Kuhn-Munkres
El algoritmo húngaro (también algoritmo de Kuhn-Munkres) es el algoritmo de optimización combinatoria que resuelve el problema de asignación — emparejamiento uno-a-uno de n trabajadores/recursos con n tareas bajo una matriz de costes n×n, minimizando el coste total — en tiempo polinómico O(n³). Harold Kuhn presentó el algoritmo en su artículo de 1955 en *Naval Research Logistics Quarterly*; el nombre se le dio en honor de los teoremas de emparejamiento bipartito desarrollados a principios del siglo XX por los matemáticos húngaros Dénes König y Jenő Egerváry. James Munkres convirtió el algoritmo en 1957 en un procedimiento polinómico O(n³) completamente formal, de ahí la denominación alternativa moderna de algoritmo de Kuhn-Munkres. Funcionamiento: resta el mínimo de cada fila/columna (reducción), encuentra un emparejamiento máximo sobre las celdas de coste cero por el teorema de König-Egerváry, si no es perfecto aplica un procedimiento secuencial de cobertura para actualizar la matriz, repite hasta el emparejamiento perfecto. Óptimo garantizado, tiempo polinómico, combinatorio. Alternativas modernas más rápidas: LAP — shortest augmenting path (Jonker y Volgenant 1987, 5-20× más rápido en la práctica); algoritmo auction (Bertsekas 1988, apto para paralelización). Kuhn (1955), Munkres (1957).
Örnek
Dada una matriz de costes 5×5 donde cada técnico tiene un tiempo de viaje distinto a cada cliente, el algoritmo húngaro encuentra en segundos el emparejamiento uno-a-uno que minimiza el tiempo total; 15-30% mejor que la asignación intuitiva.