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 costos. 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.
- Repita hasta que todos los ceros estén encuadrados 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.
