Muchos problemas que inicialmente parecen combinatoriales pueden ser resueltos de manera eficiente si son modelados de manera inteligente. A continuación se presenta un problema que inicialmente parece ser exponencial, pero que puede ser modelado como un problema de flujo máximo para obtener una solución polinomial.
El problema es el siguiente: dada una grilla de n filas y m columnas donde ciertas posiciones están bloqueadas, ¿Es posible cubrir la grilla utilizando dominós? Tomemos por ejemplo la siguiente grilla, donde las posiciones en naranjo estan bloqueadas. ¿Puedes cubrir todas las posiciones no bloqueadas utilizando los dominós? Prueba arrastrando los dominós de la derecha sobre la grilla para cubrirla.
No pareciera ser posible cubrir la grilla anterior. Sin embargo, demostrar esto no es trivial. Como se dijo al comienzo, la estrategia que seguiremos será modelar el problema como un problema de flujo máximo en un grafo.
La modelación es como sigue: cada celda de la grilla representa un nodo. Los nodos que están en una diagonal par (fila + columna es divisible por 2) se conectan con la fuente, mientras que los nodos que están en una diagonal impar se conectan con el sumidero. Además, dos nodos se conectan entre ellos si y solo si representan celdas adyacentes en la grilla, y la dirección de la arista va desde el nodo asociado a una diagonal par hacia el nodo asociado a una diagonal impar. La capacidad de cada arista es 1 y los nodos asociados a celdas bloqueadas no tienen aristas. Luego, el tablero puede ser cubierto con dominós si y solo si el flujo máximo desde la fuente al sumidero es igual a la mitad de las celdas no bloqueadas.
La siguiente visualización muestra la modelación descrita anteriormente. A la izquierda se encuentra la grilla, mientras que a la derecha se encuentra el grafo que deriva de ella. Para simplificar el grafo, se asume que las aristas van de izquierda a derecha, y la capacidad de cada arista es 1. Al mover el cursor sobre una celda de la grilla se hace resaltar el nodo correspondiente en el grafo. Además, se puede hacer doble click sobre las celdas para bloquearlas/desbloquearlas. Por último, al colocar un dominó se representa el flujo en el grafo resaltando las aristas correspondientes con color morado (por ejemplo, al colocar un dominó vertical sobre las celdas 2 y 7, se resalta el camino fuente-2-7-sumidero).
Consideremos las celdas que estan en una diagonal par. Lo primero es notar estos nodos tienen una única arista de entrada, la que se conecta a la fuente con una capacidad igual a 1. Esto hace respetar la restricción de que cada una de estas celdas es ocupada por a lo más un dominó, puesto que no puede pasar más que una unidad de flujo por ese nodo. Luego ese flujo pasa por uno de los nodos asociados a una diagonal impar para luego irse al sumidero.
Ahora consideremos los nodos asociados a una diagonal impar. Análogo a lo anterior, estos nodos tiene solo una arista de salida, la que se conecta al sumidero con una capacidad igual a 1. Esto restringe a que estas celdas también sean ocupadas por a lo más un nodo.
Falta verificar que el flujo representa una configuración válida de dominós y que no se está colocando un dominó "partido en 2" ocupando celdas no adyacentes. Esta restricción se respeta por el hecho de que solo nodos asociados a celdas adyacentes están conectados en el grafo.
Por último, falta justificar cómo se determina que el tablero completo puede ser cubierto. Esto es simple: cada unidad de flujo desde la fuente al sumidero representa un dominó, lo que cubre dos celdas. Por lo tanto, para cubrir todas las celdas se necesita que el flujo máximo sea igual a la mitad del número de celdas.
La siguiente visualización muestra la instancia del problema que atacamos al comienzo junto con su modelación como grafo. ¿Es posible mediante inspección del grafo determinar que la grilla no puede ser cubierta? Intenta rellenar la grilla y observa que sucede con el flujo en el grafo.
La respuesta es que al sumidero solo llegan 9 aristas (cada una con capacidad 1), por lo que el flujo máximo es menor o igual a 9. Sin embargo, hay 20 celdas no bloqueadas, por lo que necesitaríamos que el flujo máximo sea 10 para poder cubrir la grilla. Esto implica que la grilla no puede ser cubierta.
Sin embargo, esta simple inspección del grafo no funciona en todos los casos. Tomemos por ejemplo la siguiente instancia:
El test anterior entrega que la grilla sí puede ser cubierta, pero esto es falso. Necesitamos un método más sofisticado para determinar el valor del flujo máximo.
A diferencia de los algoritmos basados en el método de Ford y Fulkerson, los algoritmos basados en push/relabel no mantienen siempre un flujo válido por el grafo. En cambio, estos algoritmos no respetan la "conservación" del fluido, es decir, los nodos pueden recibir más fluido que el que sale de ellos - pueden tener un exceso de flujo. Al igual que los algoritmos basados en Ford y Fulkerson, los algoritmos basados en push/relabel trabajan sobre el grafo de capacidades residuales, es decir, al enviar c unidades de flujo desde u hasta v, se agregan c unidades de capacidad a la arista que va desde v hasta u.
La intuición detrás de los métodos de push/relabel se pueden entender en términos de fluidos. Las aristas representan cañerías entre los vertices. Por el otro lado, los vertices representan un estanque de fluido arbitrariamente grande, el cual guarda el exceso de flujo del vertice. Cada vertice (estanque) se ubica a una determinada altura, la cual va aumentando a lo largo del algoritmo.
La altura de los vértices determina como el flujo se mueve por la red: solo se 'empuja' fluido cuesta abajo, es decir, desde vértices más altos a vértices más bajos. Esta operación se llama push. El flujo puede ir cuesta arriba, pero las operaciones del algoritmo solo empujan el flujo cuesta abajo. El vértice fuente tiene una altura fija en N (el número de nodos de la red), mientras que todos los otros vértices parten con altura 0.
Inicialmente el algoritmo envía todo el fluido posible desde las cañerías que salen de la fuente. Ese fluido se acumula en los vertices a donde llegan esas cañerías y eventualmente se continua empujando cuesta abajo hacia el sumidero. Si un vertice intermedio contiene fluido en su estanque pero solo se conecta con vertices con altura superior, entonces la altura de ese vertice debe ser aumentada. Esta operacion se llama relabel, y consiste en aumentar la altura de un vértice a una unidad más que la altura del más bajo de sus vecinos hacia el que se puede empujar fluido.
Eventualmente todo el fluido que podía llegar al sumidero ha llegado a él. Para hacer que el flujo sea 'legal' y se respete que todo el fluido que entra a un nodo también salga de él, lo que sucede es que los vertices intermedios del grafo siguen aumentando su altura hasta que eventualmente se ubican por sobre la fuente. Una vez llegado a ese punto, el exceso de flujo que quedaba en los estanques empieza a fluir de vuelta hacia la fuente. La respuesta final del algoritmo (osea, el flujo máximo) es igual al exceso de flujo en el sumidero al finalizar.
Ya entregada la intuición detras de los algoritmos de push/relabel se procede a entregar el pseudocódigo. Algunos comentarios sobre la notación:
Algunos detalles sobre la visualización:
Esta operación toma vértices \(u\) y \(v\), y es válida solo cuando \(u\) tiene exceso de flujo, \((u,v).c\) es mayor a 0 y \(u.h = u.v+1\). Su acción es mover todo el flujo posible desde \(u\) hacia \(v\).
En el ejemplo se hace push desde el nodo 3 al 2.
Esta operación toma un vértice \(u\), y es válida solo cuando todos los vértices \(v\) tales que \((u,v)>0\) tienen \(v.h \geq u.h\). Su acción es mover el nodo a una altura una unidad mayor que el más bajo de sus vecinos.
En el ejemplo se hace relabel del nodo 3.
Esta operación se aplica solamente al comienzo del algoritmo. Lo que hace es empujar todo el flujo posible desde la fuente hacia sus vecinos y setear la altura de cada vértice a la distancia entre el vértice y el sumidero.
Este es el loop principal del algoritmo.
El ejemplo muestra la ejecución completa del algoritmo sobre un grafo cualquiera.
Volvamos a la última instancia del problema de los dominós:
Claramente no es posible cubrir la grilla de dominós en esta instancia del problema. Sin embargo, analizando el grafo resultante no es fácil determinar esto. Ejecutemos el algoritmo de Push/Relabel sobre el grafo y veamos que sucede:
Podemos ver que el flujo máximo es 3, pero necesitamos un flujo de 4 para cubrir las 4 celdas libres de la grilla. Por lo tanto, esta instancia es imposible de resolver. La solución encontrada por push/relabel es:
Se presentó un problema que inicialmente parecía requerir backtracking para resolverse, y se explicó la modelación del problema como un problema de flujo máximo. Además, se presentó un algoritmo eficiente para resolver el problema de flujo máximo: dependiendo de las estructuras de datos utilizadas (no exploradas acá), el algoritmo puede funcionar en \(O(V^3)\), lo que es considerablemente mejor que el algoritmo de Ford y Fulkerson plano (el cual es exponencial).
Para más detalles sobre el tiempo de ejecución del algoritmo y su correctitud, sugerimos leer 'Introduction to Algorithms' de Cormen et. al.