Algoritmo húngaro

El método húngaro es un algoritmo de optimización combinatoria que resuelve el problema de asignación en tiempo polinómico y que anticipó los 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 basó en gran medida en los trabajos anteriores de dos matemáticos húngaros, Dénes Kőnig y Jenő Egerváry. Sin embargo, en 2006 se descubrió que Carl Gustav Jacobi había resuelto el problema de la asignación en el siglo XIX y la solución se publicó póstumamente en 1890 en latín.

James Munkres revisó el algoritmo en 1957 y observó que es (fuerte) polinomio. Desde entonces el algoritmo ha sido conocido también como el algoritmo Kuhn-Munkres o algoritmo de asignación de Munkres. La complejidad del tiempo del algoritmo original fue ${\displaystyle O(n^{4}}$, sin embargo Edmonds y Karp, e independientemente Tomizawa, notó que puede ser modificado para lograr un ${\displaystyle O(n^{3}}$ correr el tiempo. Uno de los más populares ${\displaystyle O(n^{3}}$ variantes es el algoritmo Jonker-Volgenant. Ford y Fulkerson ampliaron el método a los problemas de flujo máximo general en forma del algoritmo Ford-Fulkerson.

El problema

Ejemplo

En este ejemplo sencillo, hay tres trabajadores: Alice, Bob y Dora. 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 es encontrar la forma más económica de asignar los puestos de trabajo. El problema se puede representar en una matriz de costos de los trabajadores que realizan los trabajos. Por ejemplo:

Tareas Trabajador	Limpio baño	Sweep pisos	Lavado ventanas
Alice	$8	$4	$7
Bob	$5	2 dólares	$3
Dora	$9	$4	$8

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

Limpio Sweep	Alice	Bob	Dora
Alice	—	17 dólares	16 dólares
Bob	18 dólares	—	18 dólares
Dora	15 dólares	16 dólares	—

(la persona no firmada lava las ventanas)

Formulación matricial

En la formulación matricial, se nos da una matriz n×n no negativa, donde el elemento en la i-ésima fila y < La columna i>j-ésima representa el costo de asignar el trabajo j-ésimo al trabajador i-ésimo. Tenemos que encontrar una asignación de 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 el rastro de una matriz,

${\displaystyle \min ¿Por qué?$

donde P es una matriz de permutación. (De manera 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.

Formulación de gráfico bipartito

El algoritmo puede describirse equivalentemente formulando el problema utilizando un gráfico bipartito. Tenemos un gráfico bipartito completo ${\displaystyle G=(S,T;E)}$ con n vértices obrerosS) y n vertices de trabajo (T), y los bordes (E) cada uno tiene un costo no negativo ${\displaystyle c(i,j)}$. Queremos encontrar una combinación perfecta con un coste total mínimo.

El algoritmo en términos de gráficos bipartitos

Llamemos a una función ${\displaystyle y:(S\cup T)\to \mathbb {R}$ a potencial si ${\displaystyle y(i)+y(j)\leq c(i,j)}$ para cada uno ${\displaystyle i\in S,j\in T}$. El valor del potencial Sí. es la suma del potencial sobre todos los vértices: ${\displaystyle \sum _{v\in S\cup T}y(v)}$.

El costo de cada coincidencia perfecta es al menos el valor de cada potencial: el costo total de la coincidencia es la suma de los costos de todas las aristas; el coste de cada arista es al menos la suma de los potenciales de sus puntos finales; dado que la coincidencia es perfecta, cada vértice es un punto final de exactamente una arista; por tanto, el costo total es al menos el potencial total.

El método húngaro encuentra una combinación perfecta y un potencial de tal manera que el costo de emparejación equivale al valor potencial. Esto demuestra que ambos son óptimos. De hecho, el método húngaro encuentra una combinación perfecta de bordes apretados: un borde ${\displaystyle ij}$ se llama apretado para un potencial Sí. si ${\displaystyle y(i)+y(j)=c(i,j)}$. Denotamos el subgrafo de apretado bordes por ${\displaystyle G_{y}$. El costo de una combinación perfecta en ${\displaystyle G_{y}$ (si hay uno) iguala el valor Sí..

Durante el algoritmo mantenemos un potencial Sí. y una orientación ${\displaystyle G_{y}$ (denominado por ${\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\\\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft}\\\\\\\\\\\\fnMicrosoft {\fnMicro {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fnMicroG {\fnMicroG\\\\\\\\\\\\\\\\\\\\fnMicrosoft {\fnMicro {G_{y}}}$) que tiene la propiedad que los bordes orientados desde T a S forma una coincidencia M. Inicialmente, Sí. es 0 en todas partes, y todos los bordes están orientados desde S a T (so M está vacío). En cada paso, o modificamos Sí. para que su valor aumente o modifique la orientación para obtener una coincidencia con más bordes. Mantenemos el invariante que todos los bordes de M están apretados. Hemos terminado si M es una combinación perfecta.

En un paso general, ${\displaystyle R_{S}\subseteq S.$ y ${\displaystyle R_{T}\subseteq T}$ ser los vértices no cubiertos por M (so ${\displaystyle R_{S}$ consiste en los vértices en S sin borde entrante y ${\displaystyle R_{T}$ consiste en los vértices en T sin borde saliente). Vamos. Z ser el conjunto de vértices alcanzable en ${\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\\\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft}\\\\\\\\\\\\fnMicrosoft {\fnMicro {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fnMicroG {\fnMicroG\\\\\\\\\\\\\\\\\\\\fnMicrosoft {\fnMicro {G_{y}}}$ desde ${\displaystyle R_{S}$ por un camino dirigido. Esto puede ser computado por la primera búsqueda.

Si ${\displaystyle R_{T}\cap Z.$ es no vacío, luego revierte la orientación de todos los bordes a lo largo de un camino dirigido en ${\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\\\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\fnMicrosoft}\\\\\\\\\\\\fnMicrosoft {\fnMicro {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fnMicroG {\fnMicroG\\\\\\\\\\\\\\\\\\\\fnMicrosoft {\fnMicro {G_{y}}}$ desde ${\displaystyle R_{S}$ a ${\displaystyle R_{T}$. Así el tamaño del correspondiente aumento de emparejamiento por 1.

Si ${\displaystyle R_{T}\cap Z.$ está vacía, entonces deja

${\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 uno de estos bordes ${\displaystyle ij}$ debe existir siempre que el emparejamiento no sea de tamaño máximo posible (ver la siguiente sección); es positivo porque no hay bordes ajustados entre ${\displaystyle Z\cap S}$ y ${\displaystyle T\setminus Z}$. Aumento Sí. por Δ sobre los vértices ${\displaystyle Z\cap S}$ y disminución Sí. por Δ sobre los vértices ${\displaystyle Z\cap T}$. El resultado Sí. es todavía un potencial, y aunque el gráfico ${\displaystyle G_{y}$ cambios, todavía contiene M (ver las subsecciones siguientes). Orientamos los nuevos bordes de S a T. Por definición Δ el conjunto Z de vértices alcanzables desde ${\displaystyle R_{S}$ aumentos (nota que el número de bordes ajustados no aumenta necesariamente).

Repito estos pasos hasta M es una combinación perfecta, en cuyo caso da una asignación de coste mínimo. El tiempo de funcionamiento de esta versión del método es ${\displaystyle O(n^{4}}$: M se aumenta n tiempos, y en una fase donde M es inmutable, hay n cambios potenciales (desde Z aumenta cada vez). El tiempo suficiente para un cambio potencial es ${\displaystyle O(n^{2}}$.

Prueba de que el algoritmo avanza

Debemos demostrar que mientras la coincidencia no sea del tamaño máximo posible, el algoritmo siempre puede progresar, es decir, aumentar el número de bordes coincidentes o apretar al menos un borde. Es suficiente demostrar que al menos uno de los siguientes se cumple en cada paso:

• M es de tamaño máximo posible.
• ${\displaystyle G_{y}$ contiene un camino de aumento.
• G contiene a camino suelto: un camino de 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 bordes apretados seguido por un solo borde suelto. El borde holgado de un camino suelto es por lo tanto desde ${\displaystyle Z\cap S}$, garantizando que Δ está bien definido.

Si M es de tamaño máximo posible, por supuesto terminamos. De lo contrario, por la lema de Berge, debe existir un camino de aumento P con respecto a M en el gráfico subyacente G. Sin embargo, este camino no puede existir en ${\displaystyle G_{y}$: Aunque cada borde numerado en P se ajusta por la definición de M, los bordes numerados impares pueden ser sueltos y así ausentes ${\displaystyle G_{y}$. Un punto final P está dentro. ${\displaystyle R_{S}$, el otro en ${\displaystyle R_{T}$; w.l.o.g., supongamos que comienza en ${\displaystyle R_{S}$. Si cada borde en P es fuerte, entonces sigue siendo un camino de aumento en ${\displaystyle G_{y}$ y hemos terminado. De lo contrario, déjalo ${\displaystyle uv}$ ser el primer borde suelto en P. Si ${\displaystyle v\notin Z}$ entonces hemos encontrado un camino suelto y hemos terminado. De lo contrario, v es accesible desde otro camino Q de bordes apretados de un vértice en ${\displaystyle R_{S}$. Vamos. ${\displaystyle P_{v}$ ser el subte de P empezar a v y continuar hasta el final, y dejar ${\displaystyle P'}$ ser el camino formado por viajar Q hasta un vértice en ${\displaystyle P_{v}$ se alcanza, 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 un borde suelto menos que P. P puede ser reemplazado por ${\displaystyle P'}$ y este proceso de razonamiento se iteró (anteriormente, utilizando la inducción en el número de bordes sueltos) hasta un camino de aumento en ${\displaystyle G_{y}$ o un camino suelto en G se encuentra.

Prueba de que ajustar el potencial y deja M sin cambios

Para mostrar que cada borde en M restos después del ajuste Sí., basta demostrar que para un borde arbitrario en M, ambos de sus puntos finales, o ninguno de ellos, están en Z. A este fin ${\displaystyle vu}$ ser un borde en M desde T a S. Es fácil ver que si v está dentro. Z entonces u debe ser también, ya que cada borde en M está apretado. Ahora supongamos, hacia la contradicción, que ${\displaystyle u\in Z}$ pero ${\displaystyle v\notin Z}$. u no puede ser ${\displaystyle R_{S}$ porque es el punto final de un borde emparejado, por lo que debe haber algún camino dirigido de bordes estrechos de un vértice en ${\displaystyle R_{S}$ a u. Este camino debe evitar v, ya que es por supuesto que no Z, así que el vértice inmediatamente anterior u en este camino es otro vértice ${\displaystyle v'\in T}$. ${\displaystyle v'u}$ es un borde apretado T a S y así está M. Pero entonces M contiene dos bordes que comparten el vertex u, contradiciendo el hecho de que M es una coincidencia. Así cada borde en M tiene ambos puntos finales o no punto final en Z.

Demostración de que y sigue siendo un potencial

Para mostrar eso Sí. sigue siendo un potencial después de ser ajustado, basta demostrar que ningún borde tiene su potencial total aumentado más allá de su costo. Esto ya está establecido para los bordes en M por el párrafo anterior, así que considere un borde arbitrario uv desde S a T. Si ${\displaystyle y(u)}$ ha aumentado Δ, entonces ${\displaystyle v\in Z\cap T}$, en cuyo caso ${\displaystyle y(v)}$ disminución en Δ, dejando sin cambios el potencial total del borde ${\displaystyle v\in T\setminus Z}$, en cuyo caso la definición Δ garantías ${\displaystyle y(u)+y(v)+\Delta \leq c(u,v)}$. Así Sí. sigue siendo un potencial.

El algoritmo en tiempo O(n3)

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

Agregar el trabajo j-ésimo en tiempo O(jW)

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

Antes ${\displaystyle j}$el paso del algoritmo, suponemos que tenemos una coincidencia ${\displaystyle S_{j-1}\cup T}$ que coincide con todos los trabajos en ${\displaystyle S_{j-1}$ y potenciales ${\displaystyle y}$ Satisfacer la siguiente condición: el emparejamiento es estricto con respecto a los potenciales, y los potenciales de todos los trabajadores inigualables son cero, y los potenciales de todos los trabajadores emparejados no son positivos. Tenga en cuenta que tales potenciales certifican la optimización de la coincidencia.

Durante el ${\displaystyle j}$a paso, añadimos el ${\displaystyle j}$de trabajo ${\displaystyle S_{j-1}$ para formar ${\displaystyle S_{j}$ y inicialización ${\displaystyle Z=\{j\}$. En todo momento, cada vértice en ${\displaystyle Z}$ será accesible desde el ${\displaystyle j}$trabajo en ${\displaystyle G_{y}$. Mientras tanto ${\displaystyle Z}$ no contiene un trabajador que no ha sido asignado un trabajo,

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

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

• Si ${\displaystyle w_{\text{next}}$ es inigualable, entonces tenemos un camino de aumento en el subgrafo de bordes apretados de ${\displaystyle j}$ a ${\displaystyle w_{\text{next}}$. Después de revolver la coincidencia a lo largo de este camino, ahora hemos coincidido con el primero ${\displaystyle j}$ empleos, y este procedimiento termina.
• De lo contrario, agregamos ${\displaystyle w_{\text{next}}$ y el trabajo coincide con él ${\displaystyle Z}$.

Ajuste de los potenciales requiere ${\displaystyle O(W)}$ tiempo. Recomputación ${\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. Caso 1 puede ocurrir en la mayoría ${\displaystyle j-1}$ tiempos antes del caso 2 ocurre y el procedimiento termina, dando lugar a la complejidad general del tiempo ${\displaystyle O(jW)}$.

Implementación en C++

Para mayor comodidad en la implementación, el siguiente código añade un trabajador adicional ${\displaystyle w_{W}$ tales que ${\displaystyle y(w_{W}}$ almacena la negación de la suma de todos ${\displaystyle \Delta }$ hasta ahora. Después de la ${\displaystyle j}$a trabajo se añade y el emparejado actualizado, el costo de la actual emparejamiento equivale a la suma de todos ${\displaystyle \Delta }$ hasta ahora, o ${\displaystyle -y(w_{W}}$.

Este código está adaptado de e-maxx:: algo.

* * Solución a https://open.kattis.com/problems/cordonbleu usando húngaro * algoritmo. */#include Identificador#include ■iostream#include > >#include Identificadorutilizando namespace std;* * Sets a = min(a, b) * @return true if b */plantilla c)clase T■ bool ckmin()T "a, const T "b) {} Regreso b c) a ? a = b, 1 : 0; }* * Dado J puestos de trabajo y trabajadores W (J <= W), calcula el costo mínimo para asignar cada uno * prefijo de empleos a trabajadores distintos. * * @tparam T un tipo lo suficientemente grande para representar enteros en el orden de J * * max(Sobreviviente) * @param C una matriz de dimensiones JxW tal que C[j][w] = costo para asignar j-th * trabajo para el trabajador (posiblemente negativo) * * @return a vector of length J, with the j-th entry equaling the minimum cost * asignar los primeros (j+1) empleos a trabajadores distintos */plantilla c)clase T■ vectorc)T■ hungría()const vectorc)vectorc)T" "C) {} const int J = ()int)tamaño()C), W = ()int)tamaño()C[0]); afirmación()J . W); // trabajo[w] = trabajo asignado a w-th worker, o -1 si no se asigna trabajo // nota: un trabajador W-th fue añadido para conveniencia vectorc)int■ trabajo()W + 1, -1); vectorc)T■ Ys()J), Y...()W + 1); // potenciales // -yt[W] igualará la suma de todos los deltas vectorc)T■ respuestas; const T inf = numeric_limitsc)T- No.max(); para ()int J_cur = 0; J_cur c) J; ++J_cur) {} // asigne j_cur-th job int w_cur = W; trabajo[w_cur] = J_cur; // min reducido costo sobre bordes de Z a trabajador w vectorc)T■ min_to()W + 1, inf); vectorc)int■ prv()W + 1, -1); // trabajador anterior en camino alternado vectorc)bool■ in_Z()W + 1); // si el trabajador está en Z mientras ()trabajo[w_cur] ! -1) {} // carreras en la mayoría j_cur + 1 veces in_Z[w_cur] = verdadero; const int j = trabajo[w_cur]; T delta = inf; int w_next; para ()int w = 0; w c) W; ++w) {} si ()!in_Z[w]) {} si ()ckmin()min_to[w] C[j[ ]w] - Ys[j] - Y...[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 este bucle corre // si las entradas de C[j_cur] son negativas para ()int w = 0; w . W; ++w) {} si ()in_Z[w]) Ys[trabajo[w]] += delta, Y...[w] -= delta; más min_to[w] -= delta; } w_cur = w_next; } // Actualización de asignaciones a lo largo del camino alternado para ()int w; w_cur ! W; w_cur = w) trabajo[w_cur] = trabajo[w = prv[w_cur]] respuestas.push_back()-Y...[W]); } Regreso respuestas;}* * Sanity check: https://en.wikipedia.org/wiki/Hungarian_algorithm#Example * Primer trabajo (5): * baño limpio: Bob... 5 * Primer + segundo empleo (9): * baño limpio: Bob... 5 * pisos de barrido: Alice - título 4 * Primer + segundo + tercer empleo (15): * baño limpio: Alice - título 8 * pisos de barrido: Dora - título 4 * ventanas de lavado: Bob... 3 */vacío sanity_check_hungarian() {} vectorc)vectorc)int" Gastos{} {}8, 5, 9} {}4, 2, 4} {}7, 3, 8} afirmación(()hungría()Gastos) == vectorc)int■{}5, 9, 15})); cerradura c) c) "Pasó el cheque de Sanidad.\n";}// resolves https://open.kattis.com/problems/cordonbleuvacío cordon_bleu() {} int N, M; cinc " N " M; vectorc)parc)int, int" B()N), C()M); vectorc)parc)int, int" botellas()N), correos()M); para ()auto "b : botellas) cinc " b.primero " b.segundo; para ()auto "c : correos) cinc " c.primero " c.segundo; parc)int, int■ Descansa; cinc " Descansa.primero " Descansa.segundo; vectorc)vectorc)int" Gastos()N, vectorc)int■()N + M - 1)); auto No. = ["]parc)int, int■ x, parc)int, int■ Sí.) {} Regreso abdominales()x.primero - Sí..primero) + abdominales()x.segundo - Sí..segundo); }; para ()int b = 0; b c) N; ++b) {} para ()int c = 0; c c) M; ++c) {} // courier - collar de botellas restaurante Gastos[b[ ]c] = No.()correos[c] botellas[b]) + No.()botellas[b] Descansa); } para ()int ¿Qué? = 0; ¿Qué? c) N - 1; ++¿Qué?) {} // restaurante - collar de botellas restaurante Gastos[b[ ]¿Qué? + M] = 2 * No.()botellas[b] Descansa); } } cout c) c) hungría()Gastos).atrás() c) c) "\n";}int principal() {} sanity_check_hungarian(); cordon_bleu();}

Conexión a caminos más cortos sucesivos

El algoritmo húngaro se puede ver equivalente al algoritmo de trayectoria más corto sucesivo para el flujo mínimo de costes, donde la técnica de repeso del algoritmo de Johnson se utiliza para encontrar los caminos más cortos. La aplicación de la sección anterior se reescribe a continuación de manera que se haga hincapié en ello conexión; se puede comprobar que los potenciales ${\displaystyle h}$ para los trabajadores ${\displaystyle 0\dots W-1}$ son iguales a los potenciales ${\displaystyle y}$ desde la solución anterior hasta un offset constante. Cuando el gráfico es escaso (hay solamente ${\displaystyle M}$ trabajo permitido, pares de trabajadores), es posible para optimizar este algoritmo ${\displaystyle O(JM+J^{2}\log W)}$ tiempo utilizando un montón de Fibonacci para determinar ${\displaystyle w_{\text{next}}$ en lugar de iterating sobre todo ${\displaystyle W.$ trabajadores para encontrar el que tiene una distancia mínima (incluido hasta aquí).

plantilla c)clase T■ vectorc)T■ hungría()const vectorc)vectorc)T" "C) {} const int J = ()int)tamaño()C), W = ()int)tamaño()C[0]); afirmación()J . W); // trabajo[w] = trabajo asignado a w-th worker, o -1 si no se asigna trabajo // nota: un trabajador W-th fue añadido para conveniencia vectorc)int■ trabajo()W + 1, -1); vectorc)T■ h()W); // Johnson potenciales vectorc)T■ respuestas; T ans_cur = 0; const T inf = numeric_limitsc)T- No.max(); // asignar j_cur-th trabajo utilizando Dijkstra con potenciales para ()int J_cur = 0; J_cur c) J; ++J_cur) {} int w_cur = W; // trabajador no visto con la distancia mínima trabajo[w_cur] = J_cur; vectorc)T■ No.()W + 1, inf); // Distancias reducidas por Johnson No.[W] = 0; vectorc)bool■ vis()W + 1); // si se ha visitado vectorc)int■ prv()W + 1, -1); // trabajador anterior en el camino más corto mientras ()trabajo[w_cur] ! -1) {} // Dijkstra paso: pop min worker from heap T min_dist = inf; vis[w_cur] = verdadero; int w_next = -1; // siguiente trabajador no previsto con distancia mínima // Considerar la posibilidad de extender el camino más corto por w_cur - título[w_cur] w para ()int w = 0; w c) W; ++w) {} si ()!vis[w]) {} // suma de pesos de borde reducido w_cur - empleo de confianza[w_cur] - título w T borde = C[trabajo[w_cur]w] - h[w]; si ()w_cur ! W) {} borde -= C[trabajo[w_cur]w_cur] - h[w_cur]; afirmación()borde >= 0); // consecuencia de los potenciales de Johnson } si ()ckmin()No.[w] No.[w_cur] + borde) prv[w] = w_cur; si ()ckmin()min_dist, No.[w]) w_next = w; } } w_cur = w_next; } para ()int w = 0; w c) W; ++w) {} // potenciales de actualización ckmin()No.[w] No.[w_cur]); h[w] += No.[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); } Regreso respuestas;}

Interpretación de la matriz

Esta variante del algoritmo sigue la formulación dada por Flood, y posteriormente descrita más explícitamente por Munkres, que demostró que se ejecuta en ${\displaystyle {\mathcal}(n^{4})}$ tiempo. En lugar de mantener el seguimiento de los potenciales de los vértices, el algoritmo opera sólo en una matriz:

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

Donde ${\displaystyle c(i,j)}$ es la matriz de coste original y ${\displaystyle y(i),y(j)}$ son los potenciales de la interpretación gráfica. Cambiar los potenciales corresponde a añadir o restar de filas o columnas de esta matriz. El algoritmo comienza con ${\displaystyle a_{ij}=c(i,j)}$. Como tal, se puede ver como tomar la matriz de coste original y modificarla.

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

a1	a2	a3	a4
b1	b2	b3	b4
c1	c2	c3	c4
d1	d2	d3	d4

donde a, b, cy d son trabajadores que tienen que realizar las tareas 1, 2, 3 y 4. a₁, a₂, a ₃, y a₄ denotan las sanciones incurridas cuando el trabajador "a" Realiza las tareas 1, 2, 3 y 4 respectivamente.

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

Paso 1

Para cada fila, su elemento mínimo se resta de cada elemento en 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 conduce a al menos un cero en cada fila. Como tal, 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.

0	a2	a3	a4
b1	b2	b3	0
c1	0	c3	c4
d1	d2	0	d4

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 en una fila si varios elementos son el mínimo. Entonces, en algún momento, este ingenuo algoritmo debería sufrir un cortocircuito.

Paso 2

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

0	a2	0	a4
b1	0	b3	0
0	c2	c3	c4
0	d2	d3	d4

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 una asignación con penalización 0 es posible.

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

Paso 3

Todos los ceros en la matriz deben cubrirse marcando la menor cantidad de filas y/o columnas posible. Los pasos 3 y 4 forman una una manera de lograr esto.

Para cada fila, intente asignar un cero arbitrario. Las tareas asignadas se representan con un asterisco cero. Tenga 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 puede ser asignado.
• Asignamos el primer cero de la fila 2. El segundo cero de la fila 2 no puede ser asignado.
• Cero en la fila 3 y la fila 4 no se puede 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 de las filas y columnas.

0*	a2	0	a4
b1	0*	b3	0
0	c2	c3	c4
0	d2	d3	d4

Paso 4

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

×	×
0*	a2	0	a4
b1	0*	b3	0
0	c2	c3	c4
0	d2	d3	d4

Encuentra un cero no cubierto y prima (márcalo con un símbolo primo). Si no se puede encontrar ese cero, lo que significa que todos los ceros están cubiertos, salte al paso 5.

• Si el cero está en la misma fila que un cero estrellado, cubre la fila correspondiente, y descubre la columna del cero estrellado.
• Entonces, GOTO "Encontrar un cero no cubierto y prepararlo."
  • Aquí, el segundo cero de la fila 1 es descubierto. Porque hay otro cero protagonizado en la fila 1, cubremos la fila 1 y descubrimos la columna 1.
  • Entonces, el segundo cero de la fila 2 es descubierto. Cubrimos la fila 2 y descubrimos la columna 2.

	×
0*	a2	0 '	a4	×
b1	0*	b3	0
0	c2	c3	c4
0	d2	d3	d4

0*	a2	0 '	a4	×
b1	0*	b3	0 '	×
0	c2	c3	c4
0	d2	d3	d4

• Si el cero no cubierto no tiene cero asignado en su fila. Realizamos un camino desde el cero realizando los siguientes pasos:
  1. Substep 1: Encuentra un cero protagonizado en la columna correspondiente. Si hay uno, ve al Substrato 2, detente.
  2. Substep 2: Encuentra un cero primo en la fila correspondiente (siempre debe haber uno). Vaya al SubPaso 1.

El cero de la fila 3 está descubierto. Agregamos a la ruta el primer cero de la Fila 1, luego el segundo cero de la Fila 1, y listo.

0*	a2	0 '	a4	×
b1	0*	b3	0 '	×
0 '	c2	c3	c4
0	d2	d3	d4

• (Sucursal de Else) Para todos los ceros encontrados durante el camino, los ceros estrellados y los ceros estrellados.
  • A medida que el camino comienza y termina por un cero primo cuando intercambiamos ceros protagonizados, hemos asignado un cero más.

0	a2	0*	a4
b1	0*	b3	0
0*	c2	c3	c4
0	d2	d3	d4

• (Sucursal de Else) Unprime todos los ceros primos y descubrir todas las líneas.
• Repita los pasos anteriores (continue bucle hasta que se llegue el "skip to step 5").
  • Cubrimos las columnas 1, 2 y 3. El segundo cero en la fila 2 es descubierto, así que cubrimos la fila 2 y descubrimos la columna 2:

×		×
0	a2	0*	a4
b1	0*	b3	0 '	×
0*	c2	c3	c4
0	d2	d3	d4

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

La descripción detallada antes mencionada es sólo una forma de dibujar el número mínimo de líneas para cubrir todos los ceros. Otros métodos también funcionan.

Paso 5

Si el número de ceros estrellados 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 trabajos), el algoritmo termina. Vea la subsección de resultados a continuación sobre cómo interpretar los resultados.

De lo contrario, encuentre el valor descubierto más bajo. Resta esto de cada elemento sin marcar y agrégalo 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í están cubiertas. Estas operaciones no cambian las asignaciones óptimas.

Resultado

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

Según el teorema de Kőnig, el número mínimo de líneas (cobertura mínima de vértices) será n (el tamaño de coincidencia máxima). Por lo tanto, cuando se requieren n líneas, la asignación de costo mínimo se puede encontrar mirando solo los ceros en la matriz.