Algoritmo húngaro

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de marzo de 2020; las comprobaciones requieren 6 ediciones .

El algoritmo húngaro es un algoritmo de optimización que resuelve el problema de asignación en tiempo polinomial (ver investigación de operaciones ). Fue desarrollado y publicado por Harold Kuhn en 1955 . El autor le dio el nombre de "Método húngaro" debido al hecho de que el algoritmo se basa en gran medida en el trabajo anterior de dos matemáticos húngaros König y Egerváry

James Mancres observó en 1957 que el algoritmo es (estrictamente) polinomial. Desde entonces, el algoritmo también se conoce como el algoritmo de Kuhn-Mankres o el algoritmo de Mankres para resolver el problema de asignación . La complejidad temporal del algoritmo original era, pero Edmonds Karp así demostraron que podía modificarse para lograr un tiempo de ejecución de. El algoritmo húngaro modificado se llama algoritmo Hopcroft-Karp. Ford y Fulkerson extendieron el método a problemas generales de transporte. En 2006, se descubrió que Jacobi había encontrado una solución del siglo XIX al problema de la asignación, que se publicó en latín en una colección póstuma de artículos de 1890. [1] [2] $O(n^{4})$ $O(n^{3})$

Ejemplo

Supongamos que hay tres empleados: Ivan, Peter y Andrey. Es necesario distribuir entre ellos la realización de tres tipos de trabajo (que llamaremos A, B, C), cada trabajador debe realizar un solo tipo de trabajo. ¿Cómo hacerlo de tal manera que se gaste la menor cantidad de dinero en los salarios de los trabajadores? Primero necesita construir una matriz de costos .

	A	B	C
Iván	10.000 rublos.	20.000 rublos.	30.000 rublos.
Pedro	30.000 rublos.	30.000 rublos.	30.000 rublos.
Andrés	30.000 rublos.	30.000 rublos.	20.000 rublos.

El algoritmo húngaro aplicado a la tabla anterior nos dará la distribución requerida: Ivan hace el trabajo A, Peter hace el trabajo B, Andrey hace el trabajo C.

Planteamiento del problema

Dada una matriz n × n no negativa , donde el elemento de la i -ésima fila y la j -ésima columna corresponde al costo de realizar el j -ésimo tipo de trabajo por parte del i -ésimo trabajador. Es necesario encontrar tal correspondencia de trabajo con los empleados para que los costos laborales sean los más bajos. Si el objetivo es encontrar el destino con el costo más alto, entonces la solución se reduce a resolver el problema recién formulado reemplazando cada costo C por la diferencia entre el costo máximo y C . [3]

Ideas principales

El algoritmo se basa en dos ideas:

si se resta el mismo número de todos los elementos de una determinada fila o columna , el costo total disminuirá en y la solución óptima no cambiará; $y$ $y$
si hay una solución de costo cero, entonces es óptima.

El algoritmo busca valores a restar de todos los elementos de cada fila y cada columna (diferentes para diferentes filas y columnas), de manera que todos los elementos de la matriz permanezcan no negativos, pero aparece una solución cero.

Definiciones

El algoritmo es más fácil de describir si el problema se formula utilizando un gráfico bipartito . Dado un grafo bipartito completo G=(S, T; E) con n vértices correspondientes a empleados ( S ) y n vértices correspondientes a tipos de trabajo ( T ); el costo de cada borde c(i, j) no es negativo. Se requiere encontrar un emparejamiento perfecto o completo con el menor costo.

Llamaremos a la función potencial si para cada . El valor potencial se define como . Es fácil ver que el costo de cualquier combinación perfecta no es menor que el valor de cualquier potencial. El método húngaro encuentra una coincidencia completa y un potencial con el mismo costo/valor, lo que demuestra que ambas cantidades son óptimas. De hecho, encuentra una combinación perfecta de aristas rígidas : se dice que una arista es rígida para el potencial si . El subgráfico de borde rígido se denotará como . El costo de una casación completa en (si existe) es igual a . $y\colon (S\cup T)\to \mathbb {R}$ $y(i)+y(j)\leq c(i,j)$ $i\en S,j\en T$ $y=\sum_{v\in S\cup T}y(v)$ $yo$ $y$ $y(i)+y(j)=c(i,j)$ ${\mathbf {G_{y))}$ ${\mathbf {G_{y))}$ $y$

Algoritmo en términos de grafos bipartitos

El algoritmo almacena en la memoria el potencial y la orientación (estableciendo la dirección) de cada borde rígido, que tiene la propiedad de que los bordes se dirigen desde para formar una coincidencia, que denotamos por . Un gráfico dirigido que consta de bordes rígidos con una orientación dada se denota por . Así, en todo momento hay tres tipos de aristas: $y\$ $T\$ $S\$ $METRO$ $\mathbf {{\overrightarrow {G}}_{y}}$

no rígido (y no perteneciente ) $METRO\$
duro pero no perteneciente $METRO\$
duro y poseído $METRO\$

Inicialmente , en todas partes es 0, y todos los bordes están dirigidos de a (por lo tanto, vacíos). En cada paso, o bien se modifica para que aumente el conjunto de vértices , definido en el siguiente párrafo, o bien se cambia la orientación para obtener un emparejamiento con mayor número de aristas; siempre es cierto que todos los bordes de son rígidos. El proceso termina si es un emparejamiento perfecto. $y\$ $S\$ $T\$ $METRO\$ $y\$ $Z\$ $METRO\$ $METRO\$

Sea en cada paso y el conjunto de vértices que no inciden en las aristas de (es decir , el conjunto de vértices de , que no incluyen ninguna arista, sino el conjunto de vértices de , de los que no sale ninguna arista). Indicar por el conjunto de vértices accesibles desde hasta (se puede encontrar mediante la búsqueda en anchura ). $R_{S}\subconjunto S$ $R_{T}\subconjunto T$ $METRO\$ $R_{S}\$ $S$ $R_{T}\$ $T$ $Z\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$

Si no está vacío, significa que hay al menos una ruta desde a . Elegimos cualquiera de estos caminos y cambiamos la orientación de todos sus bordes a la inversa. El tamaño de la coincidencia aumentará en 1. $R_{T}\cap Z$ $\mathbf {{\overrightarrow {G}}_{y}}$ $R_{S}\$ $R_{T}\$

Como prueba, notamos dos hechos obvios:

En la ruta elegida, los bordes de a se alternan con los bordes de a . Esto se deduce del gráfico bipartito. $S\$ $T\$ $T\$ $S\$
El primer vértice del camino pertenece a y el último vértice pertenece a . Por lo tanto, sus aristas primera y última se dirigen de a . $S\$ $T\$ $S\$ $T\$

Por definición , se sigue que en el camino elegido, las aristas pertenecientes y no pertenecientes se alternan, y la primera y la última aristas no pertenecen a , es decir, el camino es ascendente, de donde se sigue la afirmación que se prueba. $\mathbf {{\overrightarrow {G}}_{y}}$ $METRO\$ $METRO\$

Si está vacío, ponga . es positivo porque no hay bordes duros entre y . $R_{T}\cap Z$ $\Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$ $\Delta$ $Z\tapa S$ $T\setminus Z$

De hecho, deje que tal borde (i, j) exista. Dado que , pero , el vértice es accesible desde hasta , pero el vértice es inalcanzable. $yo\en Z$ $j\no en Z$ $i\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$

Por lo tanto, no puede contener aristas (i, j). Por lo tanto , ¿de dónde ? Como es accesible desde hasta , existe un camino desde algún vértice perteneciente a . Considere el último borde de este camino. Denotarlo (k, i). Dado que es accesible desde hasta , pero inaccesible, . Desde , . Por lo tanto, es incidente a dos aristas de : y , lo cual es imposible, ya que es una coincidencia. Contradicción. $\mathbf {{\overrightarrow {G}}_{y}}$ $(i,j)\en M$ $yo\noen R_{S}$ $i\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $i\$ $R_{S}\$ $k\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$ $k\neqj$ $(k,i)\in \mathbf {{\overrightarrow {G}}_{y}}$ $(i,k)\en M$ $i\$ $METRO\$ $(i,j)\$ $(yo, k)\$ $METRO\$

Aumentemos en los vértices desde y disminuyamos en los vértices incluidos en . El nuevo sigue siendo potencial. $y\$ $\Delta$ $Z\tapa S$ $y\$ $\Delta$ $Z\cap T$ $y\$

De hecho, para cualquier arista (i, j), , : $yo\en S$ $j\en T$

si , , entonces c(i, j)-y(i)-y(j) no cambia porque ni y(i) ni y(j) $yo\no en Z$ $j\no en Z$
si , , entonces c(i, j)-y(i)-y(j) no cambia, porque y(i) aumenta en , y y(j) disminuye en la misma cantidad $yo\en Z$ $j\en Z$ $\Delta$
si , , la diferencia c(i, j)-y(i)-y(j) aumenta en , por lo tanto, permanece no negativa $yo\no en Z$ $j\en Z$ $\Delta$
si , , la diferencia c(i, j)-y(i)-y(j) disminuye en , pero sigue siendo no negativa, porque es la más pequeña de tales diferencias. $yo\en Z$ $j\no en Z$ $\Delta$ $\Delta$

El gráfico cambia, pero, a pesar de ello, contiene . $\mathbf {{\overrightarrow {G}}_{y}}$ $METRO\$

En efecto, para excluir de alguna arista (i, j), , , es necesario hacerlo no rígido, es decir, aumentar la diferencia c(i, j)-y(i)-y(j) . Como hemos visto, la diferencia aumenta solo si , , en otras palabras, es inalcanzable desde , pero es alcanzable. Pero en este caso, la arista (j, i) no puede pertenecer a , por lo tanto, la arista no pertenece a . $\mathbf {{\overrightarrow {G}}_{y}}$ $yo\en S$ $j\en T$ $yo\no en Z$ $j\en Z$ $i$ $R_{S}$ $j$ $\mathbf {{\overrightarrow {G}}_{y}}$ $METRO$

Oriente los nuevos bordes de a . Por definición , el conjunto de vértices alcanzables desde aumentará (y el número de aristas rígidas no necesariamente aumentará). $S\$ $T\$ $\Delta$ $Z\$ $R_{S}$

Para probar esta afirmación, primero demostramos que ningún vértice desaparece de Z. Sea . Entonces hay un camino desde algún vértice que pertenece a V a V. Todos los vértices en este camino son accesibles desde , es decir, pertenecen a Z. Cada borde en este camino es incidente a dos vértices desde Z. Como vimos arriba, para tales aristas la diferencia c(i, j )-y(i)-y(j) no cambia. Esto significa que todos los bordes de la ruta permanecerán rígidos y V seguirá siendo accesible desde . Ahora demostremos que se agrega al menos un vértice a Z. Considere el borde en el que se alcanza el mínimo . Para esta arista, la diferencia c(i, j)-y(i)-y(j) será cero, por lo tanto, se volverá rígida y estará dirigida de S a T, es decir, de i a j. Dado que , j también será accesible desde , es decir, se agregará a Z. $V\en Z$ $R_{S}$ $R_{S}$ $R_{S}$ $\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$ $yo\en Z$ $R_{S}$

Repetimos estos pasos hasta que quede un maridaje perfecto; en este caso, da la asignación con el costo más bajo. El tiempo de ejecución de esta versión del algoritmo es : se rellena una vez, y en la etapa en que no cambia, no puede haber más cambios potenciales (ya que aumenta cada vez). El tiempo requerido para cambiar el potencial es . $METRO\$ $O(n^{4})$ $METRO\$ $norte\$ $METRO\$ $norte\$ $Z\$ $O(n^{2})$

Interpretación matricial

Para trabajadores y trabajos, dada una matriz n × n que especifica el costo de cada trabajo para cada trabajador. Encuentre el costo mínimo de hacer un trabajo tal que cada trabajador haga exactamente un trabajo y cada trabajo lo haga exactamente un trabajador. $norte$

En lo que sigue, por asignación entendemos la correspondencia entre trabajadores y puestos de trabajo, que tiene coste cero después de haber realizado transformaciones que afectan sólo al coste total de los puestos de trabajo.

En primer lugar, escribamos el problema en forma matricial:

{\begin{bmatriz}a1&a2&a3&a4\\b1&b2&b3&b4\\c1&c2&c3&c4\\d1&d2&d3&d4\end{bmatriz))

donde a, b, c, d son trabajadores que deben realizar los trabajos 1, 2, 3, 4. Los coeficientes a1, a2, a3, a4 denotan el costo de realizar los trabajos 1, 2, 3, 4 por el empleado "a", respectivamente. Otros símbolos tienen un significado similar. La matriz es cuadrada, por lo que cada trabajador solo puede realizar un trabajo.

Paso 1

Reducimos los elementos línea por línea. Encontramos el más pequeño de los elementos de la primera fila (a1, a2, a3, a4), y lo restamos de todos los elementos de la primera fila. En este caso, al menos uno de los elementos de la primera fila se pondrá a cero. Hacemos lo mismo para todas las demás líneas. Ahora cada fila de la matriz tiene al menos un cero. A veces los ceros ya son suficientes para encontrar el destino. En la tabla se muestra un ejemplo. Los ceros rojos indican trabajos asignados.

0	a2'	0	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

Con una gran cantidad de ceros, para encontrar el destino (costo cero), puede usar un algoritmo para encontrar la coincidencia máxima de gráficos bipartitos, por ejemplo, el algoritmo Hopcroft-Karp . Además, si al menos una columna no tiene elementos nulos, la asignación no es posible.

Paso 2

A menudo no hay asignación en el primer paso, como en el siguiente caso:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

La tarea 1 puede ser realizada de manera eficiente (a costo cero) tanto por el trabajador a como por el trabajador c, pero la tarea 3 no puede ser realizada de manera eficiente por nadie.

En tales casos, repetimos el paso 1 para las columnas y verificamos nuevamente si la asignación es posible.

Paso 3

En muchos casos, lograremos el resultado deseado después del paso 2. Pero a veces no es así, por ejemplo:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	0	d4'

Si el trabajador d está haciendo el trabajo 2, no hay nadie para hacer el trabajo 3 y viceversa.

En tales casos, seguimos el procedimiento que se describe a continuación.

Primero, utilizando cualquier algoritmo para encontrar la coincidencia máxima en un gráfico bipartito, asignamos tantos trabajos como sea posible a aquellos trabajadores que pueden realizarlos a un costo cero. En la tabla se muestra un ejemplo, los trabajos asignados están resaltados en rojo.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	0	d4'

Tenga en cuenta todas las líneas sin asignaciones (línea 1). Tenga en cuenta todas las columnas con ceros en estas filas (columna 1). Tenga en cuenta todas las filas con ceros "rojos" en estas columnas (línea 3). Seguimos hasta que ya no se marquen nuevas filas y columnas.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0
0	c2'	c3'	c4'	×
d1'	0	0	d4'

Ahora dibujamos líneas a través de todas las columnas marcadas y filas sin marcar .

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0
0	c2'	c3'	c4'	×
d1'	0	0	d4'

Todas estas acciones perseguían un único objetivo: dibujar el menor número de líneas (verticales y horizontales) para cubrir todos los ceros. Puede usar cualquier otro método en lugar del descrito.

Paso 4

De los elementos de la matriz que no están cubiertos por líneas (en este caso, estos son a2', a3', a4', c2', c3', c4'), encuentre el más pequeño. Réstelo de todas las filas sin marcar y agréguelo a todas las intersecciones de filas y columnas marcadas. Entonces, por ejemplo, si el elemento más pequeño de la lista es a2', obtenemos

×
0	0	a3'-a2'	a4'-a2'	×
b1'+a2'	b2'	b3'	0
0	c2'-a2'	c3'-a2'	c4'-2'	×
d1'+a2'	0	0	d4'

Repita el procedimiento (pasos 1-4) hasta que la cita sea posible.

Bibliografía

R. E. Burkard, M. Dell'Amico, S. Martello: Problemas de asignación . SIAM, Filadelfia (PA.) 2009. ISBN 978-0-89871-663-4
Harold W. Kuhn, "El método húngaro para el problema de la asignación", Naval Research Logistics Quarterly , 2 :83-97, 1955. Publicación original de Kuhn.
Harold W. Kuhn, "Variantes del método húngaro para problemas de asignación", Naval Research Logistics Quarterly , 3 : 253-258, 1956.
J. Munkres, "Algoritmos para los problemas de asignación y transporte", Revista de la Sociedad de Matemáticas Industriales y Aplicadas , 5 (1): 32-38, marzo de 1957.
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, Italia, 1995.
R. Ahuja, T. Magnanti, J. Orlin, Flujos de red, Prentice Hall, 1993.

Notas

↑ Jacobi C. De investigando ordine systematis aequationum differenceum vulgarium cujuscunque, CGJ Jacobi's gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. - 1890.
↑ (enlace no disponible) politechnique.fr Archivado el 29 de enero de 2020 en Wayback Machine .
↑ Copia archivada (enlace no disponible) . Consultado el 11 de febrero de 2010. Archivado desde el original el 19 de julio de 2011. (indefinido)