Algoritmo húngaro

Algoritmo de tiempo polinomial para el problema de asignación

El método húngaro es un algoritmo de optimización combinatoria que resuelve el problema de asignación en tiempo polinomial y que anticipó métodos primal-dual posteriores . Fue desarrollado y publicado en 1955 por Harold Kuhn , quien le dio el nombre de "método húngaro" porque el algoritmo se basaba en gran medida en los trabajos anteriores de dos matemáticos húngaros, Dénes Kőnig y Jenő Egerváry . ^{[1] [2]} Sin embargo, en 2006 se descubrió que Carl Gustav Jacobi había resuelto el problema de asignación en el siglo XIX, y la solución había sido publicada póstumamente en 1890 en latín. ^[3]

James Munkres revisó el algoritmo en 1957 y observó que es (fuertemente) polinomial . ^[4] Desde entonces, el algoritmo también se conoce como algoritmo de Kuhn-Munkres o algoritmo de asignación de Munkres . La complejidad temporal del algoritmo original era , sin embargo, Edmonds y Karp , e independientemente Tomizawa, notaron que se puede modificar para lograr un tiempo de ejecución. ^{[5] [6]} Ford y Fulkerson extendieron el método a problemas generales de flujo máximo en forma del algoritmo de Ford-Fulkerson . ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$

El problema

Ejemplo

En este sencillo ejemplo, hay tres trabajadores: Alice, Bob y Carol. Uno de ellos tiene que limpiar el baño, otro barrer los suelos y el tercero lavar las ventanas, pero cada uno de ellos exige un salario diferente por las distintas tareas. El problema consiste en encontrar la forma más económica de asignar los trabajos. El problema se puede representar en una matriz de los costes de los trabajadores que realizan los trabajos. Por ejemplo:

El método húngaro, aplicado a la tabla anterior, arrojaría el coste mínimo: 15 dólares, que se consiguen si Alice limpia el baño, Carol barre los suelos y Bob lava las ventanas. Esto se puede confirmar mediante la fuerza bruta:

(la persona no asignada lava las ventanas)

Formulación matricial

En la formulación matricial, se nos da una matriz n × n , donde el elemento en la fila i y la columna j representa el costo de asignar el trabajo j al trabajador i . Tenemos que encontrar una asignación de los trabajos a los trabajadores, de modo que cada trabajo se asigne a un trabajador y a cada trabajador se le asigne un trabajo, de modo que el costo total de la asignación sea mínimo.

Esto se puede expresar como permutar las filas de una matriz de costos C para minimizar la traza de una matriz,

${\displaystyle \min _{P}\operatorname {Tr} (PC)\;,}$

donde P es una matriz de permutación . (De manera equivalente, las columnas se pueden permutar utilizando CP ).

Si el objetivo es encontrar la asignación que produzca el costo máximo , el problema se puede resolver negando la matriz de costos C.

Formulación de grafo bipartito

El algoritmo se puede describir de manera equivalente formulando el problema utilizando un gráfico bipartito. Tenemos un gráfico bipartito completo con n vértices de trabajo ( S ) y n vértices de trabajo ( T ), y cada una de las aristas ( E ) tiene un costo . Queremos encontrar una correspondencia perfecta con un costo total mínimo. ${\displaystyle G=(S,T;E)}$ ${\displaystyle c(i,j)}$

El algoritmo en términos de grafos bipartitos

Llamemos a una función potencial si para cada . ${\displaystyle y:(S\cup T)\to \mathbb {R} }$ ${\displaystyle y(i)+y(j)\leq c(i,j)}$ ${\displaystyle i\in S,j\in T}$

El valor del potencial y es la suma del potencial sobre todos los vértices:

${\displaystyle \sum _{v\in S\cup T}y(v)}$.

El coste de cada emparejamiento perfecto es al menos el valor de cada potencial: el coste total del emparejamiento es la suma de los costes de todas las aristas; el coste de cada arista es al menos la suma de los potenciales de sus extremos; como el emparejamiento es perfecto, cada vértice es un extremo de exactamente una arista; por lo tanto, el coste total es al menos el potencial total.

El método húngaro encuentra un emparejamiento perfecto y un potencial tal que el costo del emparejamiento es igual al valor del potencial. Esto demuestra que ambos son óptimos. De hecho, el método húngaro encuentra un emparejamiento perfecto de aristas estrechas : una arista se llama estrecha para un potencial y si . Denotemos el subgrafo de aristas estrechas por . El costo de un emparejamiento perfecto en (si hay uno) es igual al valor de y . ${\displaystyle ij}$ ${\displaystyle y(i)+y(j)=c(i,j)}$ ${\displaystyle G_{y}}$ ${\displaystyle G_{y}}$

Durante el algoritmo mantenemos un potencial y y una orientación de (denotada por ) que tiene la propiedad de que las aristas orientadas de T a S forman una coincidencia M . Inicialmente, y es 0 en todas partes, y todas las aristas están orientadas de S a T (por lo que M está vacío). En cada paso, modificamos y para que su valor aumente, o modificamos la orientación para obtener una coincidencia con más aristas. Mantenemos la invariante de que todas las aristas de M son ajustadas. Terminamos si M es una coincidencia perfecta. ${\displaystyle G_{y}}$ ${\displaystyle {\overrightarrow {G_{y}}}}$

En un paso general, sean y los vértices no cubiertos por M (por lo que consta de los vértices en S sin arista entrante y consta de los vértices en T sin arista saliente). Sea Z el conjunto de vértices alcanzables en desde mediante un camino dirigido. Esto se puede calcular mediante una búsqueda en amplitud . ${\displaystyle R_{S}\subseteq S}$ ${\displaystyle R_{T}\subseteq T}$ ${\displaystyle R_{S}}$ ${\displaystyle R_{T}}$ ${\displaystyle {\overrightarrow {G_{y}}}}$ ${\displaystyle R_{S}}$

Si no está vacío, entonces se invierte la orientación de todos los bordes a lo largo de una ruta dirigida desde hasta . Por lo tanto, el tamaño de la coincidencia correspondiente aumenta en 1. ${\displaystyle R_{T}\cap Z}$ ${\displaystyle {\overrightarrow {G_{y}}}}$ ${\displaystyle R_{S}}$ ${\displaystyle R_{T}}$

Si está vacío, entonces sea ${\displaystyle R_{T}\cap Z}$

${\displaystyle \Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}.}$

Δ está bien definido porque al menos una de esas aristas debe existir siempre que la coincidencia aún no tenga el tamaño máximo posible (ver la siguiente sección); es positivo porque no hay aristas estrechas entre y . Aumente y en Δ en los vértices de y disminuya y en Δ en los vértices de . La y resultante sigue siendo un potencial, y aunque el gráfico cambia, todavía contiene M (ver las siguientes subsecciones). Orientamos las nuevas aristas de S a T . Por la definición de Δ el conjunto Z de vértices alcanzables desde aumenta (nótese que el número de aristas estrechas no necesariamente aumenta). ${\displaystyle ij}$ ${\displaystyle Z\cap S}$ ${\displaystyle T\setminus Z}$ ${\displaystyle Z\cap S}$ ${\displaystyle Z\cap T}$ ${\displaystyle G_{y}}$ ${\displaystyle R_{S}}$

Repetimos estos pasos hasta que M sea una correspondencia perfecta, en cuyo caso se obtiene una asignación de coste mínimo. El tiempo de ejecución de esta versión del método es : M se aumenta n veces, y en una fase en la que M no cambia, hay como máximo n cambios de potencial (ya que Z aumenta cada vez). El tiempo suficiente para un cambio de potencial es . ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{2})}$

Prueba de que el algoritmo avanza

Debemos demostrar que, mientras el emparejamiento no alcance el tamaño máximo posible, el algoritmo siempre puede avanzar, es decir, aumentar el número de aristas emparejadas o ajustar al menos una arista. Basta con demostrar que se cumple al menos una de las siguientes condiciones en cada paso:

• M es el tamaño máximo posible.
• ${\displaystyle G_{y}}$Contiene una ruta de aumento.
• G contiene un camino de cola suelta : un camino desde un vértice en hasta un vértice en que consta de cualquier número (posiblemente cero) de aristas cerradas seguidas de una única arista suelta. La arista suelta final de un camino de cola suelta es, por tanto, de , lo que garantiza que Δ esté bien definido. ${\displaystyle R_{S}}$ ${\displaystyle T\setminus Z}$ ${\displaystyle Z\cap S}$

Si M tiene el máximo tamaño posible, por supuesto hemos terminado. De lo contrario, por el lema de Berge , debe existir un camino de aumento P con respecto a M en el grafo subyacente G . Sin embargo, este camino puede no existir en : Aunque cada arista par en P es estrecha por la definición de M , las aristas impares pueden ser flojas y, por lo tanto, estar ausentes de . Un punto final de P está en , el otro en ; wlog, supongamos que comienza en . Si cada arista en P es estrecha, entonces sigue siendo un camino de aumento en y hemos terminado. De lo contrario, sea la primera arista suelta en P . Si entonces hemos encontrado un camino de cola suelta y hemos terminado. De lo contrario, v es alcanzable desde algún otro camino Q de aristas estrechas desde un vértice en . Sea el subcamino de P que comienza en v y continúa hasta el final, y sea el camino formado al viajar a lo largo de Q hasta que se alcanza un vértice en , y luego continúa hasta el final de . Observe que es un camino de aumento en G con al menos una arista suelta menos que P . P se puede reemplazar con y este proceso de razonamiento se puede iterar (formalmente, usando inducción sobre el número de aristas sueltas) hasta que se encuentre un camino de aumento en o un camino de cola suelta en G. ${\displaystyle G_{y}}$ ${\displaystyle G_{y}}$ ${\displaystyle R_{S}}$ ${\displaystyle R_{T}}$ ${\displaystyle R_{S}}$ ${\displaystyle G_{y}}$ ${\displaystyle uv}$ ${\displaystyle v\notin Z}$ ${\displaystyle R_{S}}$ ${\displaystyle P_{v}}$ ${\displaystyle P'}$ ${\displaystyle P_{v}}$ ${\displaystyle P_{v}}$ ${\displaystyle P'}$ ${\displaystyle P'}$ ${\displaystyle G_{y}}$

Prueba de que ajustando el potencialyhojasMETROsin alterar

Para demostrar que cada arista en M permanece después de ajustar y , basta con demostrar que para una arista arbitraria en M , ambos de sus puntos finales, o ninguno de ellos, están en Z . Para este fin, sea una arista en M de T a S . Es fácil ver que si v está en Z entonces u debe estar también, ya que cada arista en M es ajustada. Ahora supongamos, hacia la contradicción, que pero . u en sí mismo no puede estar en porque es el punto final de una arista coincidente, por lo que debe haber algún camino dirigido de aristas ajustadas desde un vértice en a u . Este camino debe evitar v , ya que por suposición no está en Z , por lo que el vértice inmediatamente anterior a u en este camino es algún otro vértice . es una arista ajustada de T a S y por lo tanto está en M . Pero entonces M contiene dos aristas que comparten el vértice u , contradiciendo el hecho de que M es una coincidencia. Por lo tanto, cada arista en M tiene ambos puntos finales o ninguno de los puntos finales en Z . ${\displaystyle vu}$ ${\displaystyle u\in Z}$ ${\displaystyle v\notin Z}$ ${\displaystyle R_{S}}$ ${\displaystyle R_{S}}$ ${\displaystyle v'\in T}$ ${\displaystyle v'u}$

Prueba de queySigue siendo un potencial

Para demostrar que y sigue siendo un potencial después de ser ajustado, basta con demostrar que ninguna arista tiene su potencial total aumentado más allá de su costo. Esto ya está establecido para las aristas en M por el párrafo anterior, así que considere una arista arbitraria uv de S a T . Si se incrementa en Δ , entonces o bien , en cuyo caso se disminuye en Δ , dejando el potencial total de la arista sin cambios, o , en cuyo caso la definición de Δ garantiza que . Por lo tanto , y sigue siendo un potencial. ${\displaystyle y(u)}$ ${\displaystyle v\in Z\cap T}$ ${\displaystyle y(v)}$ ${\displaystyle v\in T\setminus Z}$ ${\displaystyle y(u)+y(v)+\Delta \leq c(u,v)}$

El algoritmo enOh(norte3) tiempo

Supongamos que hay puestos de trabajo y trabajadores ( ). Describimos cómo calcular para cada prefijo de puestos de trabajo el coste total mínimo para asignar cada uno de estos puestos de trabajo a trabajadores distintos. Específicamente, sumamos el puesto de trabajo n y actualizamos el coste total en el tiempo n , lo que da como resultado una complejidad temporal general de n . Tenga en cuenta que esto es mejor que cuando el número de puestos de trabajo es pequeño en relación con el número de trabajadores. ${\displaystyle J}$ ${\displaystyle W}$ ${\displaystyle J\leq W}$ ${\displaystyle j}$ ${\displaystyle O(jW)}$ ${\displaystyle O\left(\sum _{j=1}^{J}jW\right)=O(J^{2}W)}$ ${\displaystyle O(W^{3})}$

Añadiendo el j-ésimo trabajo enOh(jW) tiempo

Usamos la misma notación que en la sección anterior, aunque modificamos sus definiciones según sea necesario. Sea el conjunto de los primeros empleos y el conjunto de todos los trabajadores. ${\displaystyle S_{j}}$ ${\displaystyle j}$ ${\displaystyle T}$

Antes del paso n.º del algoritmo, suponemos que tenemos un emparejamiento que empareja todos los trabajos en y potenciales que satisfacen la siguiente condición: el emparejamiento es estricto con respecto a los potenciales, y los potenciales de todos los trabajadores no emparejados son cero, y los potenciales de todos los trabajadores emparejados son no positivos. Nótese que dichos potenciales certifican la optimalidad del emparejamiento. ${\displaystyle j}$ ${\displaystyle S_{j-1}\cup T}$ ${\displaystyle S_{j-1}}$ ${\displaystyle y}$

Durante el paso n, agregamos el trabajo n para formar e inicializar . En todo momento, cada vértice en será accesible desde el trabajo n en . Mientras no contenga un trabajador al que no se le haya asignado un trabajo, dejemos que ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle S_{j-1}}$ ${\displaystyle S_{j}}$ ${\displaystyle Z=\{j\}}$ ${\displaystyle Z}$ ${\displaystyle j}$ ${\displaystyle G_{y}}$ ${\displaystyle Z}$

${\displaystyle \Delta :=\min\{c(j,w)-y(j)-y(w):j\in Z\cap S_{j},w\in T\setminus Z\}}$

y denotan cualquier valor en el que se alcance el mínimo. Después de ajustar los potenciales de la manera descrita en la sección anterior, ahora hay un borde estrecho de a . ${\displaystyle w_{\text{next}}}$ ${\displaystyle w}$ ${\displaystyle Z}$ ${\displaystyle w_{\text{next}}}$

• Si no hay coincidencia, entonces tenemos una ruta de aumento en el subgrafo de aristas estrechas desde hasta . Después de alternar la coincidencia a lo largo de esta ruta, ahora hemos hecho coincidir los primeros trabajos y este procedimiento finaliza. ${\displaystyle w_{\text{next}}}$ ${\displaystyle j}$ ${\displaystyle w_{\text{next}}}$ ${\displaystyle j}$
• De lo contrario, agregamos y el trabajo coincide con él . ${\displaystyle w_{\text{next}}}$ ${\displaystyle Z}$

Ajustar los potenciales lleva tiempo. El recálculo y el cambio de los potenciales también se pueden realizar a tiempo. El caso 1 puede ocurrir en la mayoría de los casos antes de que ocurra el caso 2 y el procedimiento finalice, lo que da como resultado una complejidad temporal total de . ${\displaystyle O(W)}$ ${\displaystyle \Delta }$ ${\displaystyle w_{\text{next}}}$ ${\displaystyle Z}$ ${\displaystyle O(W)}$ ${\displaystyle j-1}$ ${\displaystyle O(jW)}$

Implementación en C++

Para facilitar la implementación, el código a continuación agrega un trabajador adicional que almacena la negación de la suma de todos los cálculos realizados hasta el momento. Después de agregar el trabajo n.° y actualizar la coincidencia, el costo de la coincidencia actual es igual a la suma de todos los cálculos realizados hasta el momento, o . ${\displaystyle w_{W}}$ ${\displaystyle y(w_{W})}$ ${\displaystyle \Delta }$ ${\displaystyle j}$ ${\displaystyle \Delta }$ ${\displaystyle -y(w_{W})}$

Este código está adaptado de e-maxx::algo. ^[7]

/*** Solución a https://open.kattis.com/problems/cordonbleu usando húngaro* algoritmo.*/#include <certificado> #include <flujo de datos> #include <límites> #include <vector> utilizando el espacio de nombres std ;  /*** Establece a = min(a, b)* @return verdadero si b < a*/plantilla < clase T > bool ckmin ( T & a , const T & b ) { devolver b < a ? a = b , 1 : 0 ; }                     /*** Dados J empleos y W trabajadores (J <= W), calcula el costo mínimo para asignar cada uno* prefijo de puestos de trabajo para trabajadores distintos.** @tparam T un tipo lo suficientemente grande para representar números enteros del orden de J **máximo(|C|)* @param C una matriz de dimensiones JxW tal que C[j][w] = costo para asignar el j-ésimo* trabajo con el trabajador (posiblemente negativo)** @return un vector de longitud J, con la entrada j-ésima igual al costo mínimo* para asignar los primeros (j+1) trabajos a trabajadores distintos*/plantilla < class T > vector < T > húngaro ( const vector < vector < T >> & C ) {        const int J = ( int ) tamaño ( C ), W = ( int ) tamaño ( C [ 0 ]);        afirmar ( J <= W );   // job[w] = trabajo asignado al trabajador w-ésimo, o -1 si no hay trabajo asignado // nota: se agregó un trabajador W-th para mayor comodidad vector < int > trabajo ( W + 1 , -1 );     vector < T > ys ( J ), yt ( W + 1 ); // potenciales      // -yt[W] será igual a la suma de todos los deltas vector < T > respuestas ;  const T inf = límites numéricos < T >:: max ();     para ( int j_cur = 0 ; j_cur < J ; ++ j_cur ) { // asignar el j_cur-ésimo trabajo           int w_cur = W ;    trabajo [ w_cur ] = j_cur ;   // Costo mínimo reducido sobre los bordes de Z al trabajador w vector < T > min_to ( W + 1 , inf );     vector < int > prv ( W + 1 , -1 ); // trabajador anterior en ruta alterna      vector < bool > in_Z ( W + 1 ); // si el trabajador está en Z     while ( job [ w_cur ] != -1 ) { // se ejecuta como máximo j_cur + 1 veces      en_Z [ w_cur ] = verdadero ;   constante int j = trabajo [ w_cur ];     T delta = inf ;    int w_siguiente ;  para ( int w = 0 ; w < W ; ++ w ) {          si ( ! en_Z [ w ]) {   si ( ckmin ( min_to [ w ], C [ j ][ w ] - ys [ j ] - yt [ w ]))       prv [ w ] = w_cur ;   si ( ckmin ( delta , min_to [ w ])) w_next = w ;      } } // delta siempre será no negativo, // excepto posiblemente durante la primera vez que se ejecuta este bucle // si alguna entrada de C[j_cur] es negativa para ( int w = 0 ; w <= W ; ++ w ) {          si ( en_Z [ w ]) ys [ trabajo [ w ]] += delta , yt [ w ] -= delta ;        de lo contrario min_to [ w ] -= delta ;    } w_cur = w_siguiente ;   } // Actualizar asignaciones a lo largo de una ruta alterna para ( int w ; w_cur != W ; w_cur = w ) trabajo [ w_cur ] = trabajo [ w = prv [ w_cur ]];              respuestas .push_back ( -yt [ W ] ) ; } devolver respuestas ; }/*** Comprobación de cordura: https://en.wikipedia.org/wiki/Hungarian_algorithm/Hungarian_algorithm#Example* Primer trabajo (5):* baño limpio: Bob -> 5*Primer + segundo empleo (9):* baño limpio: Bob -> 5* barrer pisos: Alice -> 4*Primer + segundo + tercer trabajo (15):* baño limpio: Alice -> 8* barrer pisos: Carol -> 4* lavar ventanas: Bob -> 3*/void comprobación de cordura_húngara () {   vector < vector < int >> costos {{ 8 , 5 , 9 }, { 4 , 2 , 4 }, { 7 , 3 , 8 }};          afirmar (( húngaro ( costos ) == vector < int > { 5 , 9 , 15 }));     cerr << "Verificación de cordura aprobada. \n " ;  }// resuelve https://open.kattis.com/problems/cordonbleuvacío cordon_bleu () {   entero N , M ;   cin >> N >> M ;     vector < par < int , int >> B ( N ), C ( M );    vector < par < int , int >> botellas ( N ), mensajeros ( M );    para ( auto & b : botellas ) cin >> b . primero >> b . segundo ;          para ( auto & c : mensajeros ) cin >> c . primero >> c . segundo ;          par < int , int > resto ;   cin >> resto.primero >> resto.segundo ;​​​​     vector < vector < int >> costos ( N , vector < int > ( N + M - 1 ));       auto dist = [ & ]( par < int , int > x , par < int , int > y ) {          devuelve abs ( x . primero - y . primero ) + abs ( x . segundo - y . segundo );        }; para ( int b = 0 ; b < N ; ++ b ) {          para ( int c = 0 ; c < M ; ++ c ) { // mensajero -> botella -> restaurante           costos [ b ][ c ] =  dist ( mensajeros [ c ], botellas [ b ]) + dist ( botellas [ b ], resto );     } para ( int _ = 0 ; _ < N - 1 ; ++ _ ) { // restaurante -> botella -> restaurante             costos [ b ][ _ + M ] = 2 * dist ( botellas [ b ], resto );        } } cout << húngaro ( costos ). back () << " \n " ;    }int principal () {   comprobación de cordura húngaro (); cordón_bleu ();}

Conexión a caminos sucesivos más cortos

El algoritmo húngaro puede verse como equivalente al algoritmo de ruta más corta sucesiva para el flujo de costo mínimo, ^{[8] [9]} donde la técnica de reponderación del algoritmo de Johnson se utiliza para encontrar las rutas más cortas. La implementación de la sección anterior se reescribe a continuación de tal manera que se enfatice esta conexión; se puede verificar que los potenciales para los trabajadores son iguales a los potenciales de la solución anterior hasta un desplazamiento constante. Cuando el gráfico es escaso (solo se permiten pares de trabajo y trabajador), es posible optimizar este algoritmo para que se ejecute en el tiempo utilizando un montón de Fibonacci para determinar en lugar de iterar sobre todos los trabajadores para encontrar el que tiene la distancia mínima (al que se alude aquí ). ${\displaystyle h}$ ${\displaystyle 0\dots W-1}$ ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle O(JM+J^{2}\log W)}$ ${\displaystyle w_{\text{next}}}$ ${\displaystyle W}$

plantilla < class T > vector < T > húngaro ( const vector < vector < T >> & C ) {        const int J = ( int ) tamaño ( C ), W = ( int ) tamaño ( C [ 0 ]);        afirmar ( J <= W );   // job[w] = trabajo asignado al trabajador w-ésimo, o -1 si no hay trabajo asignado // nota: se agregó un trabajador W-th para mayor comodidad vector < int > trabajo ( W + 1 , -1 );     vector < T > h ( W ); // Potenciales de Johnson   vector < T > respuestas ;  T ans_cur = 0 ;    const T inf = límites numéricos < T >:: max ();     // Asignar el trabajo j_cur-ésimo usando Dijkstra con potenciales para ( int j_cur = 0 ; j_cur < J ; ++ j_cur ) {          int w_cur = W ; // trabajador no visitado con distancia mínima     trabajo [ w_cur ] = j_cur ;   vector < T > dist ( W + 1 , inf ); // Distancias reducidas por Johnson      dist [ W ] = 0 ;   vector < bool > vis ( W + 1 ); // si ya se ha visitado     vector < int > prv ( W + 1 , -1 ); // trabajador anterior en la ruta más corta      mientras ( job [ w_cur ] != -1 ) { // Paso de Dijkstra: extraer el mínimo de trabajadores del montón      T mínima_distancia = inf ;    vis [ w_cur ] = verdadero ;   int w_next = -1 ; // próximo trabajador no visitado con distancia mínima     // considere extender la ruta más corta por w_cur -> job[w_cur] -> w para ( int w = 0 ; w < W ; ++ w ) {          si ( ! vis [ w ]) {   // suma de pesos de aristas reducidas w_cur -> job[w_cur] -> w T borde = C [ trabajo [ w_cur ]][ w ] - h [ w ];      si ( w_cur != W ) {     borde -= C [ trabajo [ w_cur ]][ w_cur ] - h [ w_cur ];     assert ( edge >= 0 ); // consecuencia de los potenciales de Johnson    } si ( ckmin ( dist [ w ], dist [ w_cur ] + borde )) prv [ w ] = w_cur ;        si ( ckmin ( min_dist , dist [ w ])) w_next = w ;      } } w_cur = w_siguiente ;   } para ( int w = 0 ; w < W ; ++ w ) { // actualizar potenciales           ckmin ( dist [ w ], dist [ w_cur ]);  h [ w ] += dist [ w ];   } ans_cur += h [ w_cur ];   para ( int w ; w_cur != W ; w_cur = w ) trabajo [ w_cur ] = trabajo [ w = prv [ w_cur ]];              respuestas .push_back ( ans_cur ) ; } devolver respuestas ; }

Interpretación de matrices

Esta variante del algoritmo sigue la formulación dada por Flood ^[10] y descrita más explícitamente por Munkres, quien demostró que funciona en el tiempo. ^[4] En lugar de realizar un seguimiento de los potenciales de los vértices, el algoritmo opera solo sobre una matriz: ${\displaystyle {\mathcal {O}}(n^{4})}$

${\displaystyle a_{ij}:=c(i,j)-y(i)-y(j)}$

donde es la matriz de costos original y son los potenciales de la interpretación gráfica. Cambiar los potenciales corresponde a sumar o restar filas o columnas de esta matriz. El algoritmo comienza con . Por lo tanto, se puede considerar que se toma la matriz de costos original y se la modifica. ${\displaystyle c(i,j)}$ ${\displaystyle y(i),y(j)}$ ${\displaystyle a_{ij}=c(i,j)}$

Dados n trabajadores y tareas, el problema se escribe en forma de una matriz de costos n × n

donde a, b, c y d son trabajadores que tienen que realizar las tareas 1, 2, 3 y 4. a ₁ , a ₂ , a ₃ y a ₄ denotan las penalizaciones en las que incurre cuando el trabajador "a" realiza las tareas 1, 2, 3 y 4 respectivamente.

El problema es equivalente a asignar a cada trabajador una tarea única de modo que la penalización total se minimice. Tenga en cuenta que cada tarea solo puede ser realizada por un trabajador.

Paso 1

En cada fila, se resta el elemento mínimo de cada elemento de esa fila. Esto hace que todos los elementos tengan valores no negativos. Por lo tanto, una asignación con una penalización total de 0 es, por definición, una asignación mínima.

Esto también genera al menos un cero en cada fila. Por lo tanto, un algoritmo ingenuo y codicioso puede intentar asignar a todos los trabajadores una tarea con una penalización de cero. Esto se ilustra a continuación.

Los ceros de arriba serían las tareas asignadas.

En el peor de los casos, hay n combinaciones para probar, ya que pueden aparecer varios ceros seguidos si varios elementos son el mínimo. Por lo tanto, en algún momento, este algoritmo ingenuo debería ser cortocircuitado.

Paso 2

A veces puede resultar que la matriz en esta etapa no se pueda utilizar para realizar asignaciones, como es el caso de la matriz siguiente.

Para superar esto, repetimos el procedimiento anterior para todas las columnas (es decir, el elemento mínimo en cada columna se resta de todos los elementos en esa columna ) y luego verificamos si es posible una asignación con penalización 0.

En la mayoría de las situaciones esto dará el resultado, pero si aún no es posible entonces debemos seguir adelante.

Paso 3

Todos los ceros de la matriz deben cubrirse marcando la menor cantidad posible de filas y/o columnas. Los pasos 3 y 4 son una forma de lograrlo.

Para cada fila, intenta asignar un cero arbitrario. Las tareas asignadas se representan marcando con un cero. Ten en cuenta que las tareas no pueden estar en la misma fila o columna.

• Asignamos el primer cero de la Fila 1. El segundo cero de la Fila 1 no se puede asignar.
• Asignamos el primer cero de la Fila 2. El segundo cero de la Fila 2 no se puede asignar.
• No se pueden asignar ceros en las filas 3 y 4, porque están en la misma columna que el cero asignado en la fila 1.

Podríamos terminar con otra tarea si elegimos otro orden de filas y columnas.

Paso 4

Cubra todas las columnas que contengan un cero (marcado con asterisco).

Busque un cero no cubierto y agréguele un valor de prima (márquelo con un símbolo de prima ). Si no se puede encontrar dicho cero, es decir, si todos los ceros están cubiertos, salte al paso 5.

• Si el cero está en la misma fila que un cero con asterisco, cubra la fila correspondiente y descubra la columna del cero con asterisco.
• Luego, GOTO "Encuentra un cero no cubierto y prepáralo".
  • Aquí se descubre el segundo cero de la fila 1. Como hay otro cero marcado con una estrella en la fila 1, cubrimos la fila 1 y descubrimos la columna 1.
  • Luego se descubre el segundo cero de la fila 2. Cubrimos la fila 2 y descubrimos la columna 2.

• En caso contrario el cero no cubierto no tiene ningún cero asignado en su fila. Creamos un recorrido a partir del cero realizando los siguientes pasos:
  1. Paso secundario 1: Busque un cero marcado con asterisco en la columna correspondiente. Si hay uno, vaya al paso secundario 2; de lo contrario, deténgase.
  2. Paso secundario 2: Busque un cero primo en la fila correspondiente (siempre debe haber uno). Vaya al paso secundario 1.

Se descubre el cero de la fila 3. Añadimos al recorrido el primer cero de la fila 1, luego el segundo cero de la fila 1 y ya está.

• (Continúa la rama Else) Para todos los ceros encontrados durante la ruta, ceros con asterisco y ceros sin asterisco.
  • Como la ruta comienza y termina con un cero primado, al intercambiar los ceros con asterisco, hemos asignado un cero más.

• (Continúa la rama Else) Desprime todos los ceros primos y descubre todas las líneas.
• Repita los pasos anteriores (continúe haciendo el bucle hasta llegar al punto "saltar al paso 5" mencionado anteriormente).
  • Cubrimos las columnas 1, 2 y 3. El segundo cero de la fila 2 está descubierto, por lo que cubrimos la fila 2 y descubrimos la columna 2:

Todos los ceros ahora están cubiertos con un número mínimo de filas y columnas.

La descripción detallada mencionada anteriormente es solo una forma de dibujar la cantidad mínima de líneas para cubrir todos los 0. Otros métodos también funcionan.

Paso 5

Si la cantidad de ceros marcados con asterisco es n (o en el caso general , donde n es la cantidad de personas y m es la cantidad de empleos), el algoritmo finaliza. Consulte la subsección de Resultados a continuación para saber cómo interpretar los resultados. ${\displaystyle min(n,m)}$

De lo contrario, busque el valor más bajo que no esté cubierto. Reste este valor de cada elemento sin marcar y agréguelo a cada elemento cubierto por dos líneas. Vuelva al paso 4.

Esto equivale a restar un número de todas las filas que no están cubiertas y sumar el mismo número a todas las columnas que sí lo están. Estas operaciones no modifican las asignaciones óptimas.

Resultado

Si se sigue esta versión específica del algoritmo, los ceros marcados con asterisco forman la asignación mínima.

Del teorema de König ^[11] , el número mínimo de líneas (cobertura mínima de vértices ^[12] ) será n (el tamaño de la correspondencia máxima ^[13] ). Por lo tanto, cuando se requieren n líneas, la asignación de costo mínimo se puede encontrar observando solo los ceros en la matriz.

Bibliografía

• RE Burkard, M. Dell'Amico, S. Martello: Problemas de asignación (reimpresión revisada). SIAM, Filadelfia (PA.) 2012. ISBN  978-1-61197-222-1
• M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
• R. Ahuja , T. Magnanti , J. Orlin , "Flujos de red", Prentice Hall, 1993.
• S. Martello, "Jeno Egerváry: desde los orígenes del algoritmo húngaro hasta la comunicación por satélite". Revista Central Europea de Investigación Operativa 18, 47–58, 2010

Referencias

1. Harold W. Kuhn, "El método húngaro para el problema de asignación", Naval Research Logistics Quarterly , 2 : 83–97, 1955. Publicación original de Kuhn.
2. Harold W. Kuhn, "Variantes del método húngaro para problemas de asignación", Naval Research Logistics Quarterly , 3 : 253–258, 1956.
3. "Presentación". Archivado desde el original el 16 de octubre de 2015.
4. 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.
5. Edmonds, Jack; Karp, Richard M. (1 de abril de 1972). "Mejoras teóricas en la eficiencia algorítmica para problemas de flujo de red". Revista de la ACM . 19 (2): 248–264. doi : 10.1145/321694.321699 . S2CID  6375478.
6. Tomizawa, N. (1971). "Sobre algunas técnicas útiles para la solución de problemas de redes de transporte". Redes . 1 (2): 173–194. doi :10.1002/net.3230010206. ISSN  1097-0037.
7. "Algoritmo húngaro para resolver el problema de asignación". e-maxx::algo . 23 de agosto de 2012 . Consultado el 13 de mayo de 2023 .
8. Jacob Kogler (20 de diciembre de 2022). «Flujo de mínimo coste: algoritmo de ruta más corta sucesiva». Algoritmos para la programación competitiva . Consultado el 14 de mayo de 2023 .
9. "Resolución de problemas de asignación mediante flujo de costos mínimos". Algoritmos para programación competitiva . 17 de julio de 2022 . Consultado el 14 de mayo de 2023 .
10. Flood, Merrill M. (1956). "El problema del viajante de comercio". Investigación de operaciones . 4 (1): 61–75. doi :10.1287/opre.4.1.61. ISSN  0030-364X.
11. Teorema de König (teoría de grafos) Teorema de König
12. Cobertura de vértice Cobertura de vértice mínima
13. Coincidencia (teoría de grafos) coincidencia

Enlaces externos

• Bruff, Derek, El problema de la asignación y el método húngaro (formalismo matricial).
• Mordecai J. Golin, Coincidencia bipartita y el método húngaro (formalismo bígrafo), Notas del curso, Universidad de Ciencia y Tecnología de Hong Kong .
• Algoritmo de coincidencia máxima húngaro (ambos formalismos), en el sitio web Brilliant.
• RA Pilgrim, Algoritmo de asignación de Munkres. Modificado para matrices rectangulares , Notas del curso, Universidad Estatal de Murray .
• Mike Dawes , El problema de asignación óptima , Notas del curso, Universidad de Western Ontario .
• Sobre el método húngaro de Kuhn: un tributo desde Hungría, András Frank , Grupo de Investigación Egervary, Pazmany P. setany 1/C, H1117, Budapest, Hungría.
• Conferencia: Fundamentos de la investigación de operaciones - Problema de asignación - Algoritmo húngaro, Prof. G. Srinivasan, Departamento de Estudios de Gestión, IIT Madrás.
• Extensión: Análisis de sensibilidad de asignación (con complejidad temporal O(n^4)), Liu, Shell.
• Resuelve cualquier problema de tarea en línea, proporciona una explicación paso a paso del algoritmo húngaro.

Implementaciones

Tenga en cuenta que no todos ellos satisfacen la complejidad temporal, aunque así lo afirmen. Algunos pueden contener errores, implementar el algoritmo más lento o tener otras ineficiencias. En el peor de los casos, un ejemplo de código vinculado desde Wikipedia podría modificarse posteriormente para incluir código de explotación. La verificación y la evaluación comparativa son necesarias cuando se utilizan ejemplos de código de autores desconocidos. ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{4})}$

• Versiones de Lua y Python del código de RA Pilgrim (que afirman tener una complejidad temporal de O ( n 3 ) {\displaystyle O(n^{3})})
• Implementación de Julia
• Implementación de C que afirma tener una complejidad temporal de O ( n 3 ) {\displaystyle O(n^{3})}
• Implementación de Java que afirma tener una complejidad temporal de O ( n 3 ) {\displaystyle O(n^{3})}
• Implementación de Python
• Implementación de Ruby con pruebas unitarias
• Implementación de C# que afirma tener una complejidad temporal de O ( n 3 ) {\displaystyle O(n^{3})}
• Implementación de D con pruebas unitarias (puerto de una versión de Java que afirma O ( n 3 ) {\displaystyle O(n^{3})} ) Archivado el 30 de diciembre de 2019 en Wayback Machine.
• Implementación interactiva en línea
• Implementaciones seriales y paralelas.
• Matlab y C Archivado el 3 de mayo de 2008 en Wayback Machine.
• Implementación de Perl
• Implementación en C++
• Implementación de C++ que afirma tener una complejidad temporal de O ( n 3 ) {\displaystyle O(n^{3})} (licencia de código abierto estilo BSD)
• Implementación de MATLAB
• Implementación en C
• Implementación de JavaScript con pruebas unitarias (versión de Java que afirma tener una complejidad temporal de O ( n 3 ) {\displaystyle O(n^{3})})
• El paquete Clue R propone una implementación, solve_LSAP
• Implementación de Node.js en GitHub
• Implementación de Python en el paquete scipy