Algoritmo húngaro para resolver el problema de asignación

Enunciado del problema de asignación

Hay varias formulaciones estándar del problema de asignación (assignment problem) (todas esencialmente equivalentes). Aquí hay algunas de ellas:

• Hay $n$ trabajos y $n$ trabajadores. Cada trabajador especifica la cantidad de dinero que espera por un trabajo particular. Cada trabajador puede asignarse a solo un trabajo. El objetivo es asignar trabajos a trabajadores de forma que se minimice el costo total.

• Dada una matriz $n \times n$ $A$, la tarea es seleccionar un número de cada fila de modo que se elija exactamente un número de cada columna, y la suma de los números seleccionados se minimice.

• Dada una matriz $n \times n$ $A$, la tarea es encontrar una permutación $p$ de longitud $n$ tal que el valor $\sum A[i]\left[p[i]\right]$ se minimice.

• Consideremos un grafo bipartito completo con $n$ vértices por parte, donde a cada arista se le asigna un peso. El objetivo es encontrar un matching perfecto con el peso total mínimo.

Es importante notar que todos los escenarios de arriba son problemas “cuadrados”, lo que significa que ambas dimensiones son siempre iguales a $n$. En la práctica, a menudo se encuentran formulaciones “rectangulares” similares, donde $n$ no es igual a $m$, y la tarea es seleccionar $\min(n,m)$ elementos. Sin embargo, se puede observar que un problema “rectangular” siempre se puede transformar en un problema “cuadrado” agregando filas o columnas con valores cero o infinitos, respectivamente.

También notamos que, por analogía con la búsqueda de una solución mínima, también se puede plantear el problema de encontrar una solución máxima. Sin embargo, estos dos problemas son equivalentes entre sí: basta con multiplicar todos los pesos por $-1$.

Algoritmo húngaro

Referencia histórica

El algoritmo fue desarrollado y publicado por Harold Kuhn en 1955. El propio Kuhn le dio el nombre “húngaro” porque se basaba en el trabajo anterior de los matemáticos húngaros Dénes Kőnig y Jenő Egerváry.
En 1957, James Munkres mostró que este algoritmo corre en tiempo polinómico (estrictamente), independiente del costo.
Por lo tanto, en la literatura, este algoritmo se conoce no solo como el “húngaro”, sino también como el “algoritmo de Kuhn-Munkres” o “algoritmo de Munkres”.
Sin embargo, recientemente se descubrió en 2006 que el mismo algoritmo fue inventado un siglo antes que Kuhn por el matemático alemán Carl Gustav Jacobi. Su trabajo, About the research of the order of a system of arbitrary ordinary differential equations, que se publicó de forma póstuma en 1890, contenía, entre otros hallazgos, un algoritmo polinómico para resolver el problema de asignación. Desafortunadamente, como la publicación estaba en latín, pasó desapercibida entre los matemáticos.

También vale la pena notar que el algoritmo original de Kuhn tenía una complejidad asintótica de $\mathcal{O}(n^4)$, y solo más tarde Jack Edmonds y Richard Karp (e independientemente Tomizawa) mostraron cómo mejorarlo a una complejidad asintótica de $\mathcal{O}(n^3)$.

El algoritmo $\mathcal{O}(n^4)$

Para evitar ambigüedad, notamos de inmediato que nos ocupamos principalmente del problema de asignación en una formulación matricial (es decir, dada una matriz $A$, hay que seleccionar $n$ celdas de ella que estén en distintas filas y columnas). Indexamos los arreglos empezando en $1$, es decir, por ejemplo, una matriz $A$ tiene índices $A[1 \dots n][1 \dots n]$.

También asumiremos que todos los números de la matriz A son no negativos (si no es el caso, siempre se puede hacer la matriz no negativa sumando alguna constante a todos los números).

Llamemos potencial a dos arreglos arbitrarios de números $u[1 \ldots n]$ y $v[1 \ldots n]$, tales que se cumple la siguiente condición:

$$u[i]+v[j]\leq A[i][j],\quad i=1\dots n,\ j=1\dots n$$

(Como se puede ver, $u[i]$ corresponde a la $i$-ésima fila, y $v[j]$ corresponde a la $j$-ésima columna de la matriz).

Llamemos valor $f$ del potencial a la suma de sus elementos:

$$f=\sum_{i=1}^{n} u[i] + \sum_{j=1}^{n} v[j].$$

Por un lado, es fácil ver que el costo de la solución deseada $sol$ no es menor que el valor de cualquier potencial.

Por otro lado, resulta que siempre hay una solución y un potencial que convierte esta desigualdad en igualdad. El algoritmo húngaro descrito abajo será una demostración constructiva de este hecho. Por ahora, solo prestemos atención al hecho de que si cualquier solución tiene un costo igual a cualquier potencial, entonces esta solución es óptima.

Fijemos algún potencial. Llamemos a una arista $(i,j)$ rígida si $u[i]+v[j]=A[i][j].$

Recordemos una formulación alternativa del problema de asignación, usando un grafo bipartito. Denotemos con $H$ un grafo bipartito compuesto solo de aristas rígidas. El algoritmo húngaro mantendrá, para el potencial actual, el matching de máximo número de aristas $M$ del grafo $H$. En cuanto $M$ contenga $n$ aristas, entonces la solución al problema será simplemente $M$ (después de todo, será una solución cuyo costo coincide con el valor de un potencial).

Pasemos directamente a la descripción del algoritmo.

Paso 1. Al principio, se asume que el potencial es cero ($u[i]=v[i]=0$ para todo $i$), y se asume que el matching $M$ está vacío.

Paso 2. Luego, en cada paso del algoritmo, intentamos, sin cambiar el potencial, aumentar la cardinalidad del matching actual $M$ en uno (recordemos que el matching se busca en el grafo de aristas rígidas $H$). Para ello se usa el algoritmo de Kuhn usual para encontrar el matching máximo en grafos bipartitos. Recordemos el algoritmo aquí. Todas las aristas del matching $M$ se orientan en la dirección de la parte derecha a la izquierda, y todas las demás aristas del grafo $H$ se orientan en la dirección opuesta.

Recordemos (de la terminología de búsqueda de matchings) que un vértice se llama saturado si una arista del matching actual es adyacente a él. Un vértice que no es adyacente a ninguna arista del matching actual se llama no saturado. Un camino de longitud impar, en el que la primera arista no pertenece al matching, y para todas las aristas posteriores hay una pertenencia alternada al matching (pertenece/no pertenece) se llama camino aumentante. Desde todos los vértices no saturados de la parte izquierda se inicia un recorrido en profundidad o en anchura. Si, como resultado de la búsqueda, se pudo alcanzar un vértice no saturado de la parte derecha, hemos encontrado un camino aumentante de la parte izquierda a la derecha. Si incluimos las aristas impares del camino y quitamos las pares en el matching (es decir, incluimos la primera arista en el matching, excluimos la segunda, incluimos la tercera, etc.), entonces aumentaremos la cardinalidad del matching en uno.

Si no había camino aumentante, entonces el matching actual $M$ es maximal en el grafo $H$.

Paso 3. Si en el paso actual no es posible aumentar la cardinalidad del matching actual, entonces se realiza un recálculo del potencial de tal forma que, en los siguientes pasos, habrá más oportunidades de aumentar el matching.

Denotemos por $Z_1$ el conjunto de vértices de la parte izquierda que se visitaron durante el último recorrido del algoritmo de Kuhn, y por $Z_2$ el conjunto de vértices visitados de la parte derecha.

Calculemos el valor $\Delta$:

$$\Delta = \min_{i\in Z_1,\ j\notin Z_2} A[i][j]-u[i]-v[j].$$

Ahora recalculemos el potencial de esta forma:

• para todos los vértices $i\in Z_1$, hacer $u[i] \gets u[i]+\Delta$,

• para todos los vértices $j\in Z_2$, hacer $v[j] \gets v[j]-\Delta$.

Por el último lema, no pueden ocurrir más de $n$ recálculos de potencial antes de que se encuentre un camino aumentante y se aumente la cardinalidad del matching de $M$. Así, tarde o temprano, se encontrará un potencial que corresponde a un matching perfecto $M^$M∗, y $M^$ será la respuesta al problema. Si hablamos de la complejidad del algoritmo, entonces es $\mathcal{O}(n^4)$: en total debe haber a lo sumo $n$ aumentos del matching, antes de cada uno de los cuales hay no más de $n$ recálculos de potencial, cada uno de los cuales se realiza en tiempo $\mathcal{O}(n^2)$.

No daremos aquí la implementación del algoritmo $\mathcal{O}(n^4)$, ya que no resultará más corta que la implementación del de $\mathcal{O}(n^3)$, descrita abajo.

El algoritmo $\mathcal{O}(n^3)$

Ahora aprendamos cómo implementar el mismo algoritmo en $\mathcal{O}(n^3)$ (para problemas rectangulares $n \times m$, $\mathcal{O}(n^2m)$).

La idea clave es considerar las filas de la matriz una por una, y no todas a la vez. Así, el algoritmo descrito arriba tomará la siguiente forma:

1. Considerar la siguiente fila de la matriz $A$.

2. Mientras no haya un camino aumentante que empiece en esta fila, recalcular el potencial.

3. En cuanto se encuentre un camino aumentante, propagar el matching a lo largo de él (incluyendo así la última arista en el matching), y reiniciar desde el paso 1 (para considerar la siguiente línea).

Para alcanzar la complejidad requerida, es necesario implementar los pasos 2-3, que se realizan para cada fila de la matriz, en tiempo $\mathcal{O}(n^2)$ (para problemas rectangulares en $\mathcal{O}(nm)$).

Para ello, recordemos dos hechos demostrados arriba:

• Con un cambio en el potencial, los vértices que eran alcanzables por el recorrido de Kuhn seguirán siendo alcanzables.

• En total, solo podían ocurrir $\mathcal{O}(n)$ recálculos del potencial antes de que se encontrara un camino aumentante.

De esto se siguen estas ideas clave que nos permiten alcanzar la complejidad requerida:

• Para comprobar la presencia de un camino aumentante, no hay necesidad de iniciar el recorrido de Kuhn otra vez después de cada recálculo de potencial. En su lugar, se puede hacer el recorrido de Kuhn en forma iterativa: después de cada recálculo del potencial, mirar las aristas rígidas agregadas y, si sus extremos izquierdos eran alcanzables, marcar sus extremos derechos como alcanzables también y continuar el recorrido desde ellos.

• Desarrollando esta idea más, podemos presentar el algoritmo de la siguiente forma: en cada paso del bucle, se recalcula el potencial. Posteriormente, se identifica una columna que se ha vuelto alcanzable (que siempre existirá ya que emergen vértices alcanzables nuevos después de cada recálculo de potencial). Si la columna no está saturada, se descubre una cadena aumentante. Por el contrario, si la columna está saturada, la fila del matching también se vuelve alcanzable.

• Para recalcular el potencial de forma rápida (más rápido que la versión naive $\mathcal{O}(n^2)$), hay que mantener mínimos auxiliares para cada una de las columnas:

  
  

  $minv[j]=\min_{i\in Z_1} A[i][j]-u[i]-v[j].$
  
  

  Es fácil ver que el valor deseado $\Delta$ se expresa en términos de ellos de la siguiente forma:

  
  

  $\Delta=\min_{j\notin Z_2} minv[j].$
  
  

  Así, encontrar $\Delta$ ahora se puede hacer en $\mathcal{O}(n)$.

  Es necesario actualizar el arreglo $minv$ cuando aparecen filas visitadas nuevas. Esto se puede hacer en $\mathcal{O}(n)$ para la fila agregada (lo que suma sobre todas las filas a $\mathcal{O}(n^2)$). También es necesario actualizar el arreglo $minv$ al recalcular el potencial, lo que también se hace en tiempo $\mathcal{O}(n)$ ($minv$ cambia solo para las columnas que aún no se han alcanzado: a saber, disminuye en $\Delta$).

Así, el algoritmo toma la siguiente forma: en el bucle externo, consideramos las filas de la matriz una por una. Cada fila se procesa en tiempo $\mathcal{O}(n^2)$, ya que solo podían ocurrir $\mathcal{O}(n)$ recálculos de potencial (cada uno en tiempo $\mathcal{O}(n)$), y el arreglo $minv$ se mantiene en tiempo $\mathcal{O}(n^2)$; el algoritmo de Kuhn funcionará en tiempo $\mathcal{O}(n^2)$ (ya que se presenta en forma de $\mathcal{O}(n)$ iteraciones, cada una de las cuales visita una columna nueva).

La complejidad resultante es $\mathcal{O}(n^3)$ o, si el problema es rectangular, $\mathcal{O}(n^2m)$.

Implementación del algoritmo húngaro

La implementación de abajo fue desarrollada por Andrey Lopatin hace varios años. Se distingue por una concisión asombrosa: todo el algoritmo consiste de 30 líneas de código.

La implementación encuentra una solución para la matriz rectangular $A[1\dots n][1\dots m]$, donde $n\leq m$. La matriz es 1-based por conveniencia y brevedad del código: esta implementación introduce una fila cero ficticia y una columna cero, lo que nos permite escribir muchos ciclos de forma general, sin comprobaciones adicionales.

Los arreglos $u[0 \ldots n]$ y $v[0 \ldots m]$ guardan el potencial. Inicialmente, se ponen en cero, lo cual es consistente con una matriz de cero filas (Nótese que para esta implementación no es importante si la matriz $A$ contiene o no números negativos).

El arreglo $p[0 \ldots m]$ contiene un matching: para cada columna $j = 1 \ldots m$, guarda el número $p[j]$ de la fila seleccionada (o $0$ si aún no se ha seleccionado nada). Por conveniencia de la implementación, se asume que $p[0]$ es igual al número de la fila actual.

El arreglo $minv[1 \ldots m]$ contiene, para cada columna $j$, los mínimos auxiliares necesarios para un recálculo rápido del potencial, como se describió arriba.

El arreglo $way[1 \ldots m]$ contiene información sobre dónde se alcanzan estos mínimos para que luego podamos reconstruir el camino aumentante. Nótese que, para reconstruir el camino, basta con guardar solo valores de columna, ya que los números de fila se pueden tomar del matching (es decir, del arreglo $p$). Así, $way[j]$, para cada columna $j$, contiene el número de la columna anterior en el camino (o $0$ si no hay ninguna).

El algoritmo mismo es un bucle externo a través de las filas de la matriz, dentro del cual se considera la $i$-ésima fila de la matriz. El primer bucle do-while corre hasta que se encuentra una columna libre $j0$. Cada iteración del bucle marca como visitada una columna nueva con el número $j0$ (calculado en la última iteración; e inicialmente igual a cero, es decir, empezamos desde una columna ficticia), así como una fila nueva $i0$ adyacente a ella en el matching (es decir, $p[j0]$; e inicialmente cuando $j0=0$ se toma la $i$-ésima fila). Debido a la aparición de una fila visitada nueva $i0$, hay que recalcular el arreglo $minv$ y $\Delta$ en consecuencia. Si $\Delta$ se actualiza, entonces la columna $j1$ se vuelve el mínimo que se ha alcanzado (nótese que con tal implementación $\Delta$ podría resultar igual a cero, lo que significa que el potencial no se puede cambiar en el paso actual: ya hay una columna alcanzable nueva). Después de eso, se recalculan el potencial y el arreglo $minv$. Al final del bucle “do-while”, encontramos un camino aumentante que termina en una columna $j0$ que se puede “desenrollar” usando el arreglo de ancestros $way$.

La constante INF es “infinito”, es decir, algún número, obviamente mayor que todos los números posibles de la matriz de entrada $A$.

vector<int> u (n+1), v (m+1), p (m+1), way (m+1);
for (int i=1; i<=n; ++i) {
    p[0] = i;
    int j0 = 0;
    vector<int> minv (m+1, INF);
    vector<bool> used (m+1, false);
    do {
        used[j0] = true;
        int i0 = p[j0],  delta = INF,  j1;
        for (int j=1; j<=m; ++j)
            if (!used[j]) {
                int cur = A[i0][j]-u[i0]-v[j];
                if (cur < minv[j])
                    minv[j] = cur,  way[j] = j0;
                if (minv[j] < delta)
                    delta = minv[j],  j1 = j;
            }
        for (int j=0; j<=m; ++j)
            if (used[j])
                u[p[j]] += delta,  v[j] -= delta;
            else
                minv[j] -= delta;
        j0 = j1;
    } while (p[j0] != 0);
    do {
        int j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
    } while (j0);
}

Para restaurar la respuesta en una forma más familiar, es decir, encontrar para cada fila $i = 1 \ldots n$ el número $ans[i]$ de la columna seleccionada en ella, se puede hacer de la siguiente forma:

vector<int> ans (n+1);
for (int j=1; j<=m; ++j)
    ans[p[j]] = j;

El costo del matching se puede tomar simplemente como el potencial de la columna cero (tomado con el signo opuesto). En efecto, como se puede ver del código, $-v[0]$ contiene la suma de todos los valores de $\Delta$, es decir, el cambio total en el potencial. Aunque varios valores de $u[i]$ y $v[j]$ podrían cambiar a la vez, el cambio total en el potencial es exactamente igual a $\Delta$, ya que hasta que no hay un camino aumentante, el número de filas alcanzables es exactamente uno más que el número de las columnas alcanzables (solo la fila actual $i$ no tiene un “par” en forma de una columna visitada):

int cost = -v[0];

Conexión con el algoritmo de caminos más cortos sucesivos

El algoritmo húngaro se puede ver como el algoritmo de caminos más cortos sucesivos (Successive Shortest Path Algorithm), adaptado para el problema de asignación. Sin entrar en los detalles, demos una intuición respecto de la conexión entre ellos.

El algoritmo de caminos sucesivos usa una versión modificada del algoritmo de Johnson como técnica de reponderación. Esta se divide en cuatro pasos:

• Usar el algoritmo de Bellman-Ford, empezando desde el sumidero $s$ y, para cada nodo, encontrar el peso mínimo $h(v)$ de un camino de $s$ a $v$.

Para cada paso del algoritmo principal:

• Reponderar las aristas del grafo original de esta forma: $w(u,v) \gets w(u,v)+h(u)-h(v)$.
• Usar el algoritmo de Dijkstra para encontrar el subgrafo de caminos más cortos de la red original.
• Actualizar los potenciales para la siguiente iteración.

Dada esta descripción, podemos observar que hay una analogía fuerte entre $h(v)$ y los potenciales: se puede comprobar que son iguales salvo un desplazamiento constante. Además, se puede mostrar que, después de reponderar, el conjunto de todas las aristas de peso cero representa el subgrafo de caminos más cortos donde el algoritmo principal intenta aumentar el flujo. Esto también ocurre en el algoritmo húngaro: creamos un subgrafo hecho de aristas rígidas (aquellas para las que la cantidad $A[i][j]-u[i]-v[j]$ es cero), e intentamos aumentar el tamaño del matching.

En el paso 4, todos los $h(v)$ se actualizan: cada vez que modificamos la red de flujo, debemos garantizar que las distancias desde la fuente son correctas (de lo contrario, en la siguiente iteración, el algoritmo de Dijkstra podría fallar). Esto suena como la actualización realizada sobre los potenciales, pero en este caso, no se incrementan de forma igual.

Para profundizar la comprensión de los potenciales, consultar este artículo .

Ejemplos de tareas

Aquí hay unos pocos ejemplos relacionados con el problema de asignación, desde tareas muy triviales hasta menos obvias:

• Dado un grafo bipartito, se requiere encontrar en él el matching máximo con el peso mínimo (es decir, en primer lugar se maximiza el tamaño del matching, y en segundo lugar se minimiza su costo).
  Para resolverlo, simplemente construimos un problema de asignación, poniendo el número “infinito” en lugar de las aristas que faltan. Después de eso, resolvemos el problema con el algoritmo húngaro, y quitamos las aristas de peso infinito de la respuesta (podrían entrar en la respuesta si el problema no tiene una solución en forma de matching perfecto).

• Dado un grafo bipartito, se requiere encontrar en él el matching máximo con el peso máximo.
  La solución es otra vez obvia: todos los pesos deben multiplicarse por menos uno.

• La tarea de detectar objetos en movimiento en imágenes: se tomaron dos imágenes, como resultado de lo cual se obtuvieron dos conjuntos de coordenadas. Se requiere correlacionar los objetos de la primera y la segunda imagen, es decir, determinar para cada punto de la segunda imagen a qué punto de la primera imagen correspondía. En este caso, se requiere minimizar la suma de distancias entre los puntos comparados (es decir, buscamos una solución en la que los objetos han tomado el camino más corto en total).
  Para resolverlo, simplemente construimos y resolvemos un problema de asignación, donde los pesos de las aristas son las distancias euclidianas entre puntos.

• La tarea de detectar objetos en movimiento por localizadores: hay dos localizadores que no pueden determinar la posición de un objeto en el espacio, sino solo su dirección. Ambos localizadores (ubicados en puntos distintos) recibieron información en forma de $n$ de tales direcciones. Se requiere determinar la posición de los objetos, es decir, determinar las posiciones esperadas de los objetos y sus pares correspondientes de direcciones de tal forma que se minimice la suma de distancias de los objetos a los rayos de dirección.
  Solución: otra vez, simplemente construimos y resolvemos el problema de asignación, donde los vértices de la parte izquierda son las $n$ direcciones del primer localizador, los vértices de la parte derecha son las $n$ direcciones del segundo localizador, y los pesos de las aristas son las distancias entre los rayos correspondientes.

• Cubrir un grafo dirigido acíclico con caminos: dado un grafo dirigido acíclico, se requiere encontrar el menor número de caminos (si hay empate, con el menor peso total) de modo que cada vértice del grafo yazca en exactamente un camino.
  La solución es construir el grafo bipartito correspondiente a partir del grafo dado y encontrar el matching máximo de peso mínimo en él. Véase un artículo separado para más detalles.

• Libro para colorear un árbol. Dado un árbol en el que cada vértice, excepto las hojas, tiene exactamente $k-1$ hijos. Se requiere elegir para cada vértice uno de los $k$ colores disponibles de modo que no haya dos vértices adyacentes con el mismo color. Además, para cada vértice y cada color se conoce el costo de pintar este vértice con este color, y se requiere minimizar el costo total.
  Para resolver este problema, usamos programación dinámica. A saber, aprendamos a calcular el valor $d[v][c]$, donde $v$ es el número de vértice, $c$ es el número de color, y el valor $d[v][c]$ mismo es el costo mínimo necesario para colorear todos los vértices del subárbol enraizado en $v$, y el vértice $v$ mismo con color $c$. Para calcular tal valor $d[v][c]$, es necesario distribuir los $k-1$ colores restantes entre los hijos del vértice $v$, y para ello es necesario construir y resolver el problema de asignación (en el que los vértices de la parte izquierda son colores, los vértices de la parte derecha son hijos, y los pesos de las aristas son los valores correspondientes de $d$).
  Así, cada valor $d[v][c]$ se calcula usando la solución del problema de asignación, lo que al final da la asintótica $\mathcal{O}(nk^4)$.

• Si, en el problema de asignación, los pesos no están en las aristas, sino en los vértices, y solo en los vértices de la misma parte, entonces no es necesario usar el algoritmo húngaro: solo hay que ordenar los vértices por peso y ejecutar el algoritmo de Kuhn usual (para más detalles, véase un artículo separado ).

• Consideremos el siguiente caso especial. Sea que a cada vértice de la parte izquierda se le asigna algún número $\alpha[i]$, y a cada vértice de la parte derecha $\beta[j]$. Sea el peso de cualquier arista $(i,j)$ igual a $\alpha[i]\cdot \beta[j]$ (los números $\alpha[i]$ y $\beta[j]$ son conocidos). Resolver el problema de asignación.
  Para resolverlo sin el algoritmo húngaro, primero consideramos el caso cuando ambas partes tienen dos vértices. En este caso, como se puede ver fácilmente, es mejor conectar los vértices en el orden inverso: conectar el vértice con el menor $\alpha[i]$ al vértice con el mayor $\beta[j]$. Esta regla se puede generalizar fácilmente a un número arbitrario de vértices: hay que ordenar los vértices de la primera parte en orden creciente de los valores $\alpha[i]$, la segunda parte en orden decreciente de los valores $\beta[j]$, y conectar los vértices en pares en ese orden. Así, obtenemos una solución con complejidad $\mathcal{O}(n\log n)$.

• El problema de los potenciales. Dada una matriz $A[1 \ldots n][1 \ldots m]$, se requiere encontrar dos arreglos $u[1 \ldots n]$ y $v[1 \ldots m]$ tales que, para cualquier $i$ y $j$, $u[i] + v[j] \leq a[i][j]$ y la suma de elementos de los arreglos $u$ y $v$ sea máxima.
  Conociendo el algoritmo húngaro, la solución a este problema no será difícil: el algoritmo húngaro justamente encuentra tal potencial $u, v$ que satisface la condición del problema. Por otro lado, sin conocimiento del algoritmo húngaro, parece casi imposible resolver tal problema.

Literatura

• Ravindra Ahuja, Thomas Magnanti, James Orlin. Network Flows [1993] 

• Harold Kuhn. The Hungarian Method for the Assignment Problem [1955] 

• James Munkres. Algorithms for Assignment and Transportation Problems [1957] 

Problemas de práctica

• UVA - Crime Wave - The Sequel 

• UVA - Warehouse 

• SGU - Beloved Sons 

• UVA - The Great Wall Game 

• UVA - Jogging Trails