El algoritmo húngaro
Suponga que es dueño de una empresa y tiene cuatro empleados para elegir para completar tres trabajos que necesita. La siguiente tabla muestra el costo de cada trabajo para cada empleado.
 |
Esta tabla también se llama matriz , que es una matriz de elementos en filas y columnas.
Desea asignar a los empleados a trabajos de tal manera que se minimice el costo total. Este es un ejemplo de un problema de asignación que podemos resolver con el algoritmo húngaro. El algoritmo húngaro se utiliza para encontrar el costo mínimo al asignar personas a actividades según el costo, y cada actividad debe asignarse a una persona diferente.
Algoritmo de Redes Sociales: Qué Es, Definición y Ejemplos
Pasos del algoritmo húngaro
Para usar el algoritmo húngaro, primero organizamos las actividades y las personas en una matriz con filas como personas, columnas como actividad y entradas como costos. Una vez que hemos hecho esto, nos aseguramos de que el número de filas sea igual al número de columnas agregando columnas ficticias o filas con entradas iguales al mayor costo en toda la matriz.
Una vez que tenemos nuestra matriz cuadrada, los pasos del algoritmo son los siguientes:
- Restar mínimos de fila: reste la entrada más pequeña en cada fila de cada entrada en esa fila.
- Restar mínimos de columna: reste la entrada más pequeña en cada columna de cada entrada en esa columna.
- Cubra todos los ceros con el número mínimo de líneas: use el menor número de líneas posible, dibuje líneas sobre filas y columnas para cubrir todos los ceros en la matriz. Si el número de líneas es igual al número de filas en su matriz cuadrada, deténgase aquí. De lo contrario, vaya al paso 4.
- Cree ceros adicionales: busque el elemento más pequeño, llámelo c , que no está cubierto por una línea. Reste c de todos los elementos descubiertos en la matriz y agréguelo a cualquier elemento que esté cubierto dos veces. Vuelve al paso 3.
Una vez que pueda detener el algoritmo, elija un conjunto de ceros de modo que cada fila y columna solo tenga un cero seleccionado. Ahora elimine las filas o columnas ficticias que agregó. Los ceros en la matriz final corresponden a la asignación ideal en la matriz original. ¡Pongamos esto en acción para hacerlo más comprensible!
Aplicación del algoritmo húngaro
Primero, queremos convertir nuestra matriz en una matriz cuadrada agregando una columna ficticia con entradas iguales a 518 (la entrada más alta en la matriz).
 |
Ahora tenemos una matriz cuadrada de 4 por 4, por lo que podemos iniciar el algoritmo.
El primer paso es restar los mínimos de fila, por lo que vamos fila por fila y restamos la entrada más pequeña en cada fila de las entradas de esa fila.
 |
Problemas y soluciones de seguridad de redes inalámbricas
Ahora restamos los mínimos de columna. Vamos columna por columna y restamos la entrada más pequeña en cada columna de las entradas de esa columna.
 |
¡Vamos al tercer paso! Queremos cubrir todos los ceros en la matriz usando el número mínimo de líneas. Note que podemos hacer esto usando tres líneas.
 |
Debido a que 3 obviamente no es igual a 4, como en el número de filas en la matriz cuadrada, pasamos al paso 4. En este paso, identificamos el elemento descubierto más pequeño en la matriz como 10, y lo restamos del descubierto elementos y agréguelo a cualquier elemento que esté cubierto por dos líneas.
 |
¡Regrese al paso 3! Nuevamente, determinamos el número de líneas necesarias para cubrir todos los ceros.
 |
Esta vez necesitamos un mínimo de cuatro líneas para cubrir todos los ceros, y cuatro es igual al número de filas o columnas de nuestra matriz, así que podemos detenernos.
Una vez que podemos detenernos así, elegimos un conjunto de ceros en la matriz para que cada fila y columna solo tenga un cero seleccionado. Luego sacamos la columna ficticia.
 |
Los ceros en la matriz resultante corresponden a las entradas en la matriz original que resultarán en la asignación ideal para minimizar su costo.
 |
El costo mínimo es 421 + 407 + 411 = $ 1,239, y sucede cuando asigna el trabajo 1 al empleado 2, el trabajo 2 al empleado 3 y el trabajo 3 al empleado 4. Parece que el empleado 1 no tiene suerte, pero al menos usted Sepa cómo asignar los trabajos para minimizar su costo.
Resumen de la lección
El algoritmo húngaro se utiliza para encontrar el costo mínimo en problemas de asignación que implican asignar personas a actividades. Para usar este algoritmo, comenzamos organizando nuestros datos en una matriz con personas como filas y actividades como columnas. Si no es una matriz cuadrada, la convertimos en una agregando filas / columnas ficticias con entradas iguales al costo más alto en la matriz. Entonces, los pasos del algoritmo húngaro son los siguientes:
- Reste los mínimos de fila.
- Reste los mínimos de la columna.
- Cubra todos los ceros con el número mínimo de líneas. Si el número de líneas es igual al número de filas o columnas en su matriz, deténgase aquí. De lo contrario, vaya al paso 4.
- Cree ceros adicionales encontrando el elemento más pequeño, llámelo c , que no está cubierto por una línea. Reste c de todos los elementos descubiertos en la matriz y agréguelo a cualquier elemento que esté cubierto por dos líneas. Vuelve al paso 3.
Una vez que pueda detener el algoritmo, elija un conjunto de ceros para que solo haya uno seleccionado en cada fila y columna, luego elimine las filas y columnas ficticias. Los ceros seleccionados corresponden a la asignación ideal en la matriz original. Una vez que se acostumbre al proceso, el algoritmo húngaro es pan comido, así que siga practicando.
Explora más sobre este tema
Selecciona un tema y sigue aprendiendo...
