Algoritmo húngaro

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.

Siendo este problema similar a un problema de acoplamiento en un grafico, cumple el criterio de König de cobertura nodal de peso mínimo. Por lo tanto, el objetivo es encontrar un elemento por fila y columna en la tabla de modo que la suma de los costos sea mínima. Si partimos de un problema de maximización, será necesario invertir los costes para volver a un problema de minimización.

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

Restamos de cada línea el elemento más pequeño de la línea. Cuanto más restamos de cada columna, menor es el elemento de la columna.
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.

  1. Rodeamos uno de los ceros de esta línea (arbitrariamente el que está más a la izquierda).
  2. Todos los ceros de la misma fila y columna que la seleccionada están tachados.
  3. 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:

  1. Marcamos cualquier línea que no contenga ningún cero enmarcado.
  2. Cualquier columna con un cero tachado se marca en una fila marcada.
  3. Marcamos cualquier fila que tenga un cero enmarcado en una columna marcada.
  4. 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.

  1. Restamos de todas las casillas de esta tabla el elemento más pequeño de la misma.
  2. 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.

Algoritmo húngaro Algoritmo de Kühn Problemas de asignación de métodos húngaros Criterio de König