Algoritmo húngaro
También llamado algoritmo de Kühn, el algoritmo húngaro o método húngaro resuelve problemas de asignación del tipo tabla de costes. Considere un número de máquinas y tantas tareas. Cada máquina realiza una tarea a un costo determinado. El objetivo es determinar la máquina en la que se ejecutará cada tarea, en paralelo.
Tomemos un ejemplo simple para mostrar el proceso del algoritmo. Deje que 5 máquinas (fila) y 5 tareas (columna) den la siguiente tabla de costos:
17 | 15 | 9 | 5 | 12 |
16 | 16 | 10 | 5 | 10 |
12 | 15 | 14 | 11 | 5 |
4 | 8 | 14 | 17 | 13 |
13 | 9 | 8 | 12 | 17 |
Paso 1 algoritmo húngaro: reducción de la tabla inicial
12 | 9 | 4 | 0 | 7 |
11 | 10 | 5 | 0 | 5 |
7 | 9 | 9 | 6 | 0 |
0 | 3 | 10 | 13 | 9 |
5 | 0 | 0 | 4 | 9 |
Esta estandarización de los costos de las máquinas y las tareas hace posible tener al menos un cero por fila y por columna.
Algoritmo húngaro, paso 2: encuentre una solución viable
Buscamos la línea con la menor cantidad de ceros no cruzados. En caso de empate, tomaremos la línea más alta.
- Rodeamos uno de los ceros de esta línea (arbitrariamente el que está más a la izquierda).
- Todos los ceros de la misma fila y columna que la seleccionada están tachados.
- Comenzamos de nuevo hasta que todos los ceros estén encasillados o tachados.
Si hemos enmarcado un cero por fila y por columna, tenemos una solución óptima. De lo contrario, vamos al paso 3.
12 | 9 | 4 | 0 | 7 |
11 | 10 | 5 | -0- | 5 |
7 | 9 | 9 | 6 | 0 |
0 | 3 | 10 | 13 | 9 |
5 | 0 | -0- | 4 | 9 |
Paso 3 algoritmo húngaro: creación de los pivotes
La subtabla permite por sustracción tener una configuración que permita encontrar una solución óptima. La construcción de los pivotes se realiza de la siguiente manera:
- Marcamos cualquier línea que no contenga ningún cero enmarcado.
- Cualquier columna con un cero tachado se marca en una fila marcada.
- Marcamos cualquier fila que tenga un cero enmarcado en una columna marcada.
- Repita 2 y 3 hasta que no haya más cambios.
Luego se dibuja una línea en cualquier línea no marcada y en cualquier columna marcada. En nuestro ejemplo, las filas 1 y 2 están marcadas, así como la columna 4. Los elementos marcados con doble marca están marcados con una estrella.
12 | 9 | 4 | -0- | 7 |
11 | 10 | 5 | -0- | 5 |
-7- | -9- | -9- | *-6-* | -0- |
-0- | -3- | -10- | *-13-* | -9- |
-5- | -0- | -0- | *-4-* | -9- |
Paso 4 algoritmo húngaro: modificación de la tabla
Las celdas no cruzadas por una línea constituyen una tabla parcial.
- Restamos de todas las casillas de esta tabla el elemento más pequeño de la misma.
- Este elemento se suma a todas las casillas de la tabla tachadas en ambas direcciones (acompañadas de una estrella).
Los pasos 2 a 4 se repiten hasta que se obtiene un resultado óptimo. En nuestro ejemplo, obtenemos un resultado óptimo después de la primera iteración.
8 | 5 | 0 | 0 | 3 |
7 | 6 | 1 | 0 | 1 |
7 | 9 | 9 | 10 | 0 |
0 | 3 | 10 | 17 | 9 |
5 | 0 | 0 | 8 | 9 |
La asignación mínima se calcula a partir de la tabla inicial: 9 + 5 + 5 + 4 + 9 = 32.
La siguiente figura muestra los cambios en el gráfico bipartito con el algoritmo húngaro.
ES 
FR 
EN