Este artículo proporciona un ejemplo paso a paso de cómo el algoritmo húngaro resuelve el problema de asignación óptima en un gráfico.
La razón por la que escribo este artículo es porque me costó unos días entender cómo funciona el algoritmo húngaro en un gráfico. La versión matricial es mucho más fácil de entender, pero no proporciona la información necesaria. Toda la excelente información que encontré en la web no me proporcionó la claridad necesaria para entender intuitivamente por qué el algoritmo hace lo que hace.
Tampoco me resultó sencillo traducir las descripciones del algoritmo a un ejemplo práctico. Si bien las diversas herramientas LLM que tenemos hoy ayudaron a reformular la descripción del algoritmo de diversas maneras, todas fallaron miserablemente cuando les pedí que generaran un ejemplo práctico paso a paso. Por eso perseveré para generar un ejemplo del algoritmo húngaro haciendo su magia en un gráfico. Presento este ejemplo paso a paso aquí y la intuición que obtuve de este ejercicio, con la esperanza de que ayude a otros que intentan aprender este maravilloso algoritmo para resolver el problema de la asignación óptima.
El problema de asignación óptima es encontrar una correspondencia uno a uno entre un conjunto de nodos y otro conjunto de nodos, donde el borde entre cada par de nodos tiene un costo asociado y la correspondencia generada debe garantizar el costo total mínimo.
Este problema es generalizado. Podría consistir en asignar un conjunto de personas a un conjunto de trabajos, cada uno de los cuales exige un precio específico para un trabajo específico, y luego el problema consiste en asignar personas a los trabajos de manera que el costo total se minimice. Podría consistir en asignar un conjunto de taxis disponibles al conjunto de personas que buscan taxis, y cada taxi requiere un tiempo específico para llegar a una persona específica. El algoritmo húngaro se utiliza para resolver este problema cada vez que reservamos un Uber o un Ola.
El problema de asignación se representa mejor como una bipartito grafo, que es un grafo con dos conjuntos distintos de nodos, y los bordes nunca conectan nodos del mismo conjunto. Tomamos el ejemplo de la correspondencia de taxis, y el grafo bipartito aquí muestra las posibles conexiones entre los nodos. Los pesos de los bordes indican el tiempo (en minutos) que tarda el taxi específico en llegar a una persona específica. Si todos los nodos de un conjunto están conectados a todos los nodos del otro conjunto, el grafo se llama completo.
En este ejemplo, necesitamos asignar 4 personas a 4 taxis. Podemos aplicar la solución por fuerza bruta:
- Para la primera persona, hay cuatro posibles asignaciones de taxi, y podemos elegir cualquiera de ellas.
- Para la segunda persona quedan tres taxis y elegimos uno de los tres.
- Para la tercera persona, elegimos uno de los dos taxis que quedan.
- Para la última persona, elegimos el taxi restante.
Por lo tanto, el número total de asignaciones posibles es 4 x 3 x 2 x 1, que es 4 factorial. Luego calculamos el costo total de todas estas 4 asignaciones y elegimos la asignación que tenga el costo más bajo. Para problemas de asignación de menor tamaño, la fuerza bruta aún puede ser factible. Pero como norteel número de personas/taxis crece, el ¡norte! se vuelve bastante grande.
El otro enfoque es un algoritmo codicioso. Se elige a una persona, se le asigna el taxi con el costo mínimo, luego se elige a la siguiente persona, se le asigna uno de los taxis restantes con el costo mínimo, y así sucesivamente. En este ejemplo, la asignación de costo mínimo no es posible para la última persona porque el taxi que puede llegar a ella en el menor tiempo ya ha sido asignado a otra persona. Por lo tanto, el algoritmo elige el siguiente taxi disponible con el costo mínimo. Por lo tanto, la última persona sufre por la avaricia de todos los demás. La solución al algoritmo codicioso se puede ver en el gráfico aquí. No hay garantía de que este enfoque codicioso resulte en una asignación óptima, aunque en este ejemplo, sí da como resultado lograr el costo mínimo de 36.
El algoritmo húngaro proporciona una forma eficiente de encontrar la solución óptima. Comenzaremos con el algoritmo matricial. Podemos representar el gráfico como una matriz de adyacencia donde el peso de cada arista es una entrada de la matriz. El gráfico y su matriz de adyacencia se pueden ver aquí.
Estos son los pasos del algoritmo húngaro que opera sobre la matriz de adyacencia:
- Para cada fila de la matriz de adyacencia, encuentre y reste la entrada mínima de todas las entradas de esa fila.
- Para cada columna de la matriz de adyacencia, encuentre y reste la entrada mínima de todas las entradas de esa columna.
- Cubrir todos los ceros de la matriz con el mínimo número de líneas
a. Cuente el número de ceros en cada fila y en cada columna.
b. Dibuje líneas en la fila/columna que tenga más ceros primero, luego en la segunda fila que tenga más, y así sucesivamente.
c. Si la cantidad de líneas que se requieren para cubrir todos los ceros es menor que el número de filas/columnas de la matriz, continúe con el paso 4; de lo contrario, pase al paso 5. - Encuentre la entrada más pequeña que no esté cubierta por una línea y reste esa entrada de todas las entradas descubiertas mientras la suma a todas las entradas cubiertas dos veces (línea horizontal y vertical), vaya al paso 3
- La asignación óptima se puede generar comenzando con la fila/columna que tiene solo un cero
Los dos primeros pasos son sencillos. El tercer paso requiere tachar filas o columnas en el orden de la cantidad de ceros que tienen, de mayor a menor. Si la cantidad de filas y columnas tachadas no es igual a la cantidad de nodos que se deben emparejar, necesitamos crear ceros adicionales; esto se hace en el cuarto paso. Repita los pasos 3 y 4 hasta que se tachen suficientes filas y columnas. Entonces tendremos suficientes ceros en la matriz para una coincidencia óptima.
Los pasos del algoritmo húngaro para este ejemplo de comparación de taxis se muestran en este GIF animado.
Para aquellos a quienes les resulta difícil seguir el GIF, aquí está la imagen que muestra los pasos.
El algoritmo termina una vez que el número de filas/columnas que se han tachado es igual al número de nodos que se deben emparejar. El paso final es entonces encontrar la asignación, y esto se hace fácilmente asignando primero la arista correspondiente a una de las entradas cero, que en este ejemplo, podría ser (P1,T2) eligiendo el primer cero en la primera fila. Por lo tanto, no podemos asignar T2 a nadie más, por lo que el segundo cero en la columna T2 se puede eliminar. El único cero restante en la fila P4 dice que debe asignarse a T1, por lo que la siguiente asignación es (P4,T1). El segundo cero en la columna T1 ahora se puede eliminar, y la fila P2 entonces solo tiene un cero. La tercera asignación entonces es (P2,T3). La asignación final es por lo tanto (P3,T4). El lector puede calcular el costo total sumando todos los pesos de las aristas correspondientes a estas asignaciones, y el resultado será 36.
Este proceso de asignación es mucho más intuitivo si observamos la animación GIF, donde tenemos un subgrafo que conecta todos los nodos, y podemos crear un camino alterno donde los bordes se alternan entre coincidentes (verde) y no coincidentes (rojo).