Algoritmo húngaro

En este sencillo ejemplo, hay tres trabajadores: Alice, Bob y Carol. Uno de ellos tiene que limpiar el baño, otro barrer los pisos y el tercero lavar las ventanas, pero cada uno 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 mediante una matriz de los costos de los trabajadores que realizan las tareas. Por ejemplo:

El método húngaro, aplicado a la tabla anterior, daría el costo mínimo: $15, que se logra haciendo que Alice limpie el baño, Carol barra los pisos y Bob lave las ventanas. Esto se puede confirmar usando la fuerza bruta:

(La persona no asignada limpia las ventanas)

En la formulación matricial, se nos proporciona 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 . Debemos encontrar una asignación de los trabajos a los trabajadores, de manera que cada trabajo se asigne a un trabajador y cada trabajador a un trabajo, minimizando así el costo total de la asignación.

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 forma equivalente, las columnas se pueden permutar usando 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.

El algoritmo puede describirse de forma equivalente formulando el problema mediante un grafo bipartito. Disponemos de un grafo bipartito completo.${\displaystyle G=(S,T;E)}$con n vértices de trabajadores ( S ) y n vértices de trabajos ( T ), y las aristas ( E ) tienen cada una un costo${\displaystyle c(i,j)}$Queremos encontrar la combinación perfecta con el mínimo coste total.

Debemos demostrar que, siempre que el emparejamiento no alcance el tamaño máximo posible, el algoritmo siempre podrá progresar, 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 tiene el tamaño máximo posible.
• ${\displaystyle G_{y}}$contiene una ruta de aumento.
• G contiene un camino de cola suelta : un camino desde algún vértice en${\displaystyle R_{S}}$a un vértice en${\displaystyle T\setminus Z}$que consiste en cualquier número (posiblemente cero) de aristas estrechas seguidas de una única arista suelta. La arista suelta final de un camino de cola suelta es, por lo tanto,${\displaystyle Z\cap S}$, garantizando que Δ esté bien definido.

Si M tiene el tamaño máximo posible, por supuesto hemos terminado. De lo contrario, según 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${\displaystyle G_{y}}$: Aunque cada arista par en P es ajustada por definición de M , las aristas impares pueden ser sueltas y, por lo tanto, estar ausentes de${\displaystyle G_{y}}$. Un extremo de P está en${\displaystyle R_{S}}$, el otro en${\displaystyle R_{T}}$; wlog, supongamos que comienza en${\displaystyle R_{S}}$. Si cada arista en P es estrecha, entonces sigue siendo un camino de aumento en${\displaystyle G_{y}}$y hemos terminado. De lo contrario, deja${\displaystyle uv}$sea ​​el primer borde suelto en P. Si${\displaystyle v\notin Z}$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${\displaystyle R_{S}}$. Dejar${\displaystyle P_{v}}$Sea el subcamino de P que comienza en v y continúa hasta el final, y sea${\displaystyle P'}$sea ​​el camino formado al viajar a lo largo de Q hasta un vértice en${\displaystyle P_{v}}$se llega y luego continúa hasta el final de${\displaystyle P_{v}}$. Observe que${\displaystyle P'}$es un camino de aumento en G con al menos una arista suelta menos que P. P puede ser reemplazado por${\displaystyle P'}$y este proceso de razonamiento se iteró (formalmente, usando inducción sobre el número de aristas sueltas) hasta que se encontró un camino de aumento en${\displaystyle G_{y}}$o se encuentra una ruta de cola suelta en G.

Para demostrar que cada arista en M permanece después de ajustar y , basta con demostrar que para una arista arbitraria en M , o bien ambos de sus extremos, o ninguno de ellos, están en Z. Para ello, sea${\displaystyle vu}$Sea v una arista en M desde T hasta S. Es fácil ver que si v está en Z , entonces u también debe estarlo, ya que toda arista en M es estrecha. Ahora supongamos, para contradicción, que${\displaystyle u\in Z}$pero${\displaystyle v\notin Z}$. u mismo no puede estar en${\displaystyle R_{S}}$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${\displaystyle R_{S}}$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.${\displaystyle v'\in T}$.${\displaystyle v'u}$es una arista estrecha de T a S y por lo tanto está en M. Pero entonces M contiene dos aristas que comparten el vértice u , lo que contradice el hecho de que M es un emparejamiento. Por lo tanto , cada arista en M tiene ambos extremos o ninguno de los extremos en Z.

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

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

Antes de la${\displaystyle j}$En el paso n del algoritmo, asumimos que tenemos una coincidencia en${\displaystyle S_{j-1}\cup T}$que coincide con todos los trabajos en${\displaystyle S_{j-1}}$y potenciales${\displaystyle y}$que cumplen la siguiente condición: el emparejamiento es preciso con respecto a los potenciales, los potenciales de todos los trabajadores no emparejados son cero y los potenciales de todos los trabajadores emparejados son no positivos. Cabe destacar que dichos potenciales certifican la optimalidad del emparejamiento.

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

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

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

• Si${\displaystyle w_{\text{next}}}$es no coincidente, entonces tenemos un camino de aumento en el subgrafo de aristas ajustadas de${\displaystyle j}$a${\displaystyle w_{\text{next}}}$. Después de alternar la coincidencia a lo largo de este camino, ahora hemos hecho coincidir el primero${\displaystyle j}$trabajos, y este procedimiento finaliza.
• De lo contrario, añadimos${\displaystyle w_{\text{next}}}$y el trabajo que coincidía con ello${\displaystyle Z}$.

Ajustar los potenciales requiere${\displaystyle O(W)}$tiempo. Recalcular${\displaystyle \Delta }$y${\displaystyle w_{\text{next}}}$después de cambiar los potenciales y${\displaystyle Z}$también se puede hacer en${\displaystyle O(W)}$tiempo. El caso 1 puede ocurrir como máximo${\displaystyle j-1}$tiempos antes de que ocurra el caso 2 y finalice el procedimiento, lo que da como resultado la complejidad temporal general de${\displaystyle O(jW)}$.

Para facilitar la implementación, el siguiente código agrega un trabajador adicional.${\displaystyle w_{W}}$de tal manera que${\displaystyle y(w_{W})}$almacena la negación de la suma de todos${\displaystyle \Delta }$calculado hasta ahora. Después del${\displaystyle j}$Cuando se agrega el trabajo y se actualiza la coincidencia, el costo de la coincidencia actual es igual a la suma de todos los${\displaystyle \Delta }$calculado hasta ahora, o${\displaystyle -y(w_{W})}$.

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

/** * Solución a https://open.kattis.com/problems/cordonbleu usando el algoritmo húngaro. */ import std ;using std :: integral ; using std :: istream ; using std :: numeric_limits ; using std :: pair ; using std :: stringstream ; using std :: string_view ; using std :: vector ;constexpr string_view SAMPLE_INPUT = R " ( 2 2 1 0 0 -1 -1 1 2 -1 0 0 ) " ;/** * @brief Realiza el algoritmo húngaro. * * Dados J trabajos y W trabajadores (J <= W), calcula el costo mínimo para asignar cada * prefijo de trabajos a trabajadores distintos. * * @tparam T un tipo lo suficientemente grande como para representar enteros del orden de J * * max(|C|) * @param C una matriz de dimensiones JxW tal que C[j][w] = costo para asignar el j-ésimo * trabajo al w-ésimo trabajador (posiblemente negativo) * * @return un vector de longitud J, con la j-ésima entrada igual al costo mínimo * para asignar los primeros j + 1 trabajos a trabajadores distintos */ template < integral T > vector < T > hungarian ( const vector < vector < T >>& C ) { auto lessThan = [] < integral T > ( T & a , const T & b ) -> bool { return b < a ? a = b , true : false ; } const int J = static_cast < int > ( C . size ()); const int W = static_cast < int > ( C [ 0 ]. size ()); contract_assert ( J <= W ); // job[w] = trabajo asignado al trabajador w, o -1 si no se ha asignado ningún trabajo // nota: se añadió un trabajador W por conveniencia vector < int > job ( W + 1 , -1 ); vector < T > ys ( J ); vector < T > yt ( W + 1 ); // potenciales // -yt[W] será igual a la suma de todos los deltas vector < T > answers ; const T inf = numeric_limits < T >::max (); para ( int jCur = 0 ; jCur < J ; ++ jCur ) { // asignar el trabajo jCur-ésimo int wCur = W ; trabajo [ wCur ] = jCur ; // costo reducido mínimo sobre aristas desde Z al trabajador w vector <T> minTo ( W + 1 , inf ); vector <int> prev ( W + 1 , -1 ); // trabajador anterior en ruta alterna vector <bool> inZ ( W + 1 ); // si el trabajador está en Z mientras ( trabajo [ wCur ] != -1 ) { // se ejecuta como máximo jCur + 1 veces inZ [ wCur ] = true ; const int j = trabajo [ wCur ] ; T delta = inf ; int wNext ; for ( int w = 0 ; w < W ; ++ w ) { if ( ! inZ [ w ]) { if ( ckmin ( minTo [ w ], C [ j ][ w ] - ys [ j ] - yt [ w ])) { prev [ w ] = wCur ; } if ( ckmin ( delta , minTo [ w ])) { wNext = w ; } } } // delta siempre será no negativo, // excepto posiblemente durante la primera vez que se ejecuta este bucle // si alguna entrada de C[jCur] es negativa for ( int w= 0 ; w <= W ; ++ w ) { if ( inZ [ w ]) { ys [ job [ w ]] += delta ; yt [ w ] -= delta ; } else { minTo [ w ] -= delta ; } } wCur = wNext ; } // actualizar asignaciones a lo largo de una ruta alterna para ( int w ; wCur != W ; wCur = w ) { job [ wCur ] = job [ w = prev [ wCur ]]; } answers . push_back ( - yt [ W ]); } return answers ; }/** * @brief resuelve https://open.kattis.com/problems/cordonbleu */ int cordonBleu ( istream & is ) { int N ; int M ; is >> N >> M ; vector < pair < ​​int , int >> B ( N ); vector < pair < ​​int , int >> C ( M ); vector < pair < ​​int , int >> bottle ( N ); vector < pair < ​​int , int >> couriers ( M ); for ( auto & [ a , b ] : bottle ) { is >> a >> b ; } for ( auto & [ c , d ] : couriers ) { is >> a >> d ; } pair < ​​int , int > rest ; std :: cin >> rest . first >> rest . second ; vector < vector < int >> costs ( N , vector < int > ( N + M - 1 )); auto dist = [ & ]( const pair < ​​int , int >& x , const pair < ​​int , int >& y ) -> int { return std :: abs ( x . first - y .primero ) +std :: abs ( x.second - y.second ); } ; for ( int b = 0 ; b < N ; ++ b ) { for ( int c = 0 ; c < M ; ++ c ) { // costo del mensajero -> botella -> restaurante [ b ][ c ] = dist ( couriers [ c ], bottle [ b ]) + dist ( bottle [ b ], rest ); } for ( int c = 0 ; c < N - 1 ; ++ c ) { // costo del restaurante -> botella -> restaurante [ b ][ c + M ] = 2 * dist ( bottle [ b ], rest ); } } return hungarian ( costs ) .back (); }/** * @brief Punto de entrada al programa. * * @return El código de retorno del programa. */ int main () { stringstream sampleInput1 ( SAMPLE_INPUT );std :: println ( stderr , "{}" , cordonBleu ( sampleInput1 )); // 5 std :: println ( "{}" , cordonBleu ( std :: cin )); } // https://godbolt.org/z/Wen35833G

Para cada fila, se resta su elemento mínimo a todos los demás elementos 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 resulta en al menos un cero en cada fila. Por lo tanto, un algoritmo voraz ingenuo 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 mínimos. Por lo tanto, en algún momento este algoritmo ingenuo debería ser descartado.

En ocasiones, puede ocurrir que la matriz en esta etapa no se pueda utilizar para la asignación, como sucede con la matriz que se muestra a continuación.

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

En la mayoría de los casos esto dará el resultado, pero si aún así no es posible, entonces debemos continuar.

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

Para cada fila, intente asignar un cero arbitrario. Las tareas asignadas se representan colocando un asterisco seguido de un cero. Tenga en cuenta que las asignaciones no pueden estar en la misma fila ni en la misma 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.
• Los ceros de la fila 3 y la fila 4 no se pueden asignar 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 para las filas y columnas.

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

Encuentra un cero no cubierto y márcalo con una prima (con el símbolo de prima ). Si no encuentras ningún cero de este tipo, es decir, si todos los ceros están cubiertos, pasa 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, vaya a "Encuentre un cero no cubierto y conviértalo en prima".
  • Aquí, el segundo cero de la fila 1 queda al descubierto. Como hay otro cero marcado con un asterisco 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.

• De lo contrario, el cero no cubierto no tiene asignado ningún cero en su fila. Creamos un camino a partir del cero realizando los siguientes pasos:
  1. Subpaso 1: Encuentra un cero marcado con un asterisco en la columna correspondiente. Si lo encuentras, ve al subpaso 2; de lo contrario, detente.
  2. Subpaso 2: Encuentra un cero inicial en la fila correspondiente (siempre debe haber uno). Ve al subpaso 1.

El cero de la fila 3 queda al descubierto. Añadimos al camino el primer cero de la fila 1, luego el segundo cero de la fila 1, y con eso terminamos.

• (De lo contrario, la rama continuó) Para todos los ceros encontrados durante el camino, ceros con asterisco y ceros sin asterisco.
  • Como la ruta comienza y termina con un cero inicial al intercambiar ceros con asterisco, hemos asignado un cero más.

• (De lo contrario, la rama continúa) Desprima todos los ceros primados y descubra todas las líneas.
• Repita los pasos anteriores (continúe el bucle hasta que se llegue a "saltar al paso 5" mencionado anteriormente).
  • Cubrimos las columnas 1, 2 y 3. El segundo cero de la fila 2 queda al descubierto, por lo que cubrimos la fila 2 y descubrimos la columna 2:

Ahora todos los ceros 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 el número mínimo de líneas para cubrir todos los ceros. Otros métodos también funcionan.

Si el número de ceros marcados con asterisco es n (o en el caso general${\displaystyle min(n,m)}$(donde n es el número de personas y m es el número de puestos de trabajo), el algoritmo finaliza. Consulte la subsección «Resultados» a continuación para obtener información sobre cómo interpretarlos.

De lo contrario, encuentre el valor más bajo sin cubrir. Réstelo a cada elemento sin cubrir y súmelo a cada elemento cubierto por dos líneas. Vuelva al paso 4.

Esto equivale a restar un número a 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.

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

Según el 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 del emparejamiento máximo ^{[ 13 ]} ). Por lo tanto, cuando se requieren n líneas, la asignación de costo mínimo se puede encontrar considerando solo los ceros en la matriz.

Tenga en cuenta que no todos estos satisfacen la${\displaystyle O(n^{3})}$complejidad temporal, incluso si afirman lo contrario. Algunos pueden contener errores, implementan el más lento.${\displaystyle O(n^{4})}$algoritmo, u otras ineficiencias. En el peor de los casos, un ejemplo de código enlazado desde Wikipedia podría modificarse posteriormente para incluir código malicioso. Es necesario verificar y realizar pruebas de rendimiento al utilizar ejemplos de código de autores desconocidos.

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