dynamic-programming
Resolviendo problemas de gráficas usando programación dinámica

Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall es para encontrar rutas más cortas en un gráfico ponderado con ponderaciones de borde positivas o negativas. Una sola ejecución del algoritmo encontrará las longitudes (pesos sumados) de las rutas más cortas entre todos los pares de vértices. Con una pequeña variación, puede imprimir la ruta más corta y puede detectar ciclos negativos en un gráfico. Floyd-Warshall es un algoritmo de programación dinámica.

Veamos un ejemplo. Vamos a aplicar el algoritmo de Floyd-Warshall en este gráfico:

Lo primero que hacemos es tomar dos matrices 2D. Estas son matrices de adyacencia . El tamaño de las matrices será el número total de vértices. Para nuestra gráfica, tomaremos 4 * 4 matrices. La Matriz de distancia almacenará la distancia mínima encontrada hasta ahora entre dos vértices. Al principio, para los bordes, si hay un borde entre uv y la distancia / peso es w , almacenaremos: distance[u][v] = w . Por todos los bordes que no existen, vamos a poner el infinito . La Matriz de ruta es para regenerar la ruta de distancia mínima entre dos vértices. Entonces, inicialmente, si hay una ruta entre u y v , vamos a poner la path[u][v] = u . Esto significa que la mejor manera de llegar al vértice-v del vértice-u es usar el borde que conecta v con u . Si no hay una ruta entre dos vértices, vamos a poner N allí para indicar que no hay una ruta disponible ahora. Las dos tablas para nuestra gráfica se verán como:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Como no hay bucle, las diagonales se configuran en N. Y la distancia desde el propio vértice es 0 .

Para aplicar el algoritmo Floyd-Warshall, vamos a seleccionar un vértice medio k . Luego, para cada vértice i , vamos a verificar si podemos ir de i a k y luego k a j , donde j es otro vértice y minimizar el costo de ir de i a j . Si la distancia actual [i] [j] es mayor que la distancia [i] [k] + distancia [k] [j] , vamos a poner la distancia [i] [j] a la suma de esas dos distancias . Y la ruta [i] [j] se establecerá en la ruta [k] [j] , ya que es mejor ir de i a k , y luego k a j . Todos los vértices serán seleccionados como k . Tendremos 3 bucles anidados: para k yendo de 1 a 4, i va de 1 a 4 y j va de 1 a 4. Vamos cheque:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Entonces, lo que básicamente estamos comprobando es, para cada par de vértices, ¿obtenemos una distancia más corta al atravesar otro vértice? El número total de operaciones para nuestro gráfico será 4 * 4 * 4 = 64 . Eso significa que vamos a hacer este control 64 veces. Veamos algunos de ellos:

Cuando k = 1 , i = 2 y j = 3 , la distancia [i] [j] es -2 , que no es mayor que la distancia [i] [k] + distancia [k] [j] = -2 + 0 = -2 . Así se mantendrá sin cambios. De nuevo, cuando k = 1 , i = 4 y j = 2 , distancia [i] [j] = infinito , que es mayor que la distancia [i] [k] + distancia [k] [j] = 1 + 3 = 4 . Entonces colocamos la distancia [i] [j] = 4 , y colocamos la ruta [i] [j] = ruta [k] [j] = 1 . Lo que esto significa es que, para pasar del vértice 4 al vértice 2 , la ruta 4-> 1-> 2 es más corta que la ruta existente. Así es como poblamos ambas matrices. El cálculo para cada paso se muestra aquí . Después de hacer los cambios necesarios, nuestras matrices se verán como:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Esta es nuestra matriz de distancias más corta. Por ejemplo, la distancia más corta de 1 a 4 es 3 y la distancia más corta entre 4 a 3 es 2 . Nuestro pseudo-código será:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Imprimiendo el camino:

Para imprimir la ruta, revisaremos la matriz de ruta . Para imprimir la ruta de u a v , comenzaremos desde la ruta [u] [v] . Estableceremos seguir cambiando v = ruta [u] [v] hasta que encontremos la ruta [u] [v] = u y empujemos todos los valores de la ruta [u] [v] en una pila. Después de encontrar u, vamos a imprimir u y empiezan a saltar los elementos de la pila e imprimirlas. Esto funciona porque la matriz de ruta almacena el valor del vértice que comparte la ruta más corta a v desde cualquier otro nodo. El pseudocódigo será:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Encontrando el Ciclo del Borde Negativo:

Para saber si hay un ciclo de borde negativo, tendremos que verificar la diagonal principal de la matriz de distancia . Si algún valor en la diagonal es negativo, eso significa que hay un ciclo negativo en la gráfica.

Complejidad:

La complejidad del algoritmo Floyd-Warshall es O (V³) y la complejidad del espacio es: O (V²) .

Cubierta de vértice mínimo

La cubierta mínima de vértices es un problema de gráficos clásico. Digamos que en una ciudad tenemos algunas carreteras que conectan algunos puntos. Representemos los caminos usando bordes y los puntos usando nodos. Tomemos dos gráficos de ejemplo:

Queremos poner vigilantes en algunos puntos. Un vigilante puede proteger todos los caminos conectados al punto. El problema es, ¿cuál es el número mínimo de vigilantes necesarios para cubrir todas las carreteras? Si colocamos vigilantes en los nodos A , B , H , I y J , podemos cubrir todas las carreteras.

Esta es nuestra solución óptima. Necesitamos al menos 5 vigilantes para vigilar toda la ciudad. ¿Cómo determinar esto?

Al principio, debemos entender que este es un problema NP-difícil , es decir, el problema no tiene una solución de tiempo polinómico. Pero si el gráfico era un árbol , eso significa que si tenía nodos (n-1) donde n es el número de bordes y no hay un ciclo en el gráfico, podemos resolverlo mediante la programación dinámica.

Para construir una solución de DP, debemos seguir dos estrategias:

1. Si no hay un vigilante en un nodo, todos los nodos conectados a él deben tener un vigilante, o todas las carreteras no estarán cubiertas. Si u y v están conectados y u no tiene ningún vigilante, entonces v debe tener un vigilante.
2. Si hay un vigilante en un nodo, un nodo diferente conectado a él puede o no tener un vigilante. Eso significa que no es necesario tener un vigilante, pero puede ser beneficioso. Si u y v están conectados y u tiene un vigilante, verificaremos y encontraremos cuál es beneficioso para nosotros al:
   • Poniendo vigilante en v .
   • No poner vigilante en v .

Definamos una función recursiva con el estado que es el nodo actual en el que estamos y si tiene un vigilante o no. Aquí:

F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.

La función devolverá el número de vigilantes en los nodos restantes.

Tomemos un árbol de ejemplo:

Podemos decir fácilmente que si no ponemos al vigilante en el nodo A , tendremos que poner vigilantes en el nodo B , C y D. Podemos deducir:

F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0

Nos devuelve el número de vigilantes necesarios si no colocamos al vigilante en el nodo A. Agregamos 0 al final porque no configuramos ningún vigilante en nuestro nodo actual.

Ahora F(A,1) significa que configuramos a watchman en el nodo A. Para eso, podemos establecer vigilantes en todos los nodos conectados o no. Tomaremos el que nos proporcione el número mínimo de vigilantes.

F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1

Verificamos estableciendo y no configurando al vigilante en cada nodo y tomando el valor óptimo.

Una cosa que debemos tener cuidado es que, una vez que vamos al nodo secundario, nunca volveremos a mirar el nodo principal. Del ejemplo anterior, fuimos a B desde A , entonces el padre [B] = A. Así que no volveremos a la A de la B.

Para determinar el caso base, podemos notar que, si desde un nodo, no podemos ir a ningún otro nodo nuevo, devolveremos 1 si hay un vigilante en nuestro nodo actual, 0 si no hay un vigilante en nuestro actual nodo.

Es mejor tener una lista de adyacencia para nuestro árbol. Deja que la lista se denote por borde . Tendremos una matriz dp [n] [2] , donde n denota el número de nodos para almacenar los valores calculados e inicializarlos con -1 . También tendremos una matriz principal [n] para denotar la relación principal y secundaria entre nodos. Nuestro pseudo-código se verá así:

Procedure f(u, isGuarded):
if edge[u].size is equal to 0                    //node doesn't have any new edge
    Return isGuarded
else if dp[u][isGuarded] is not equal to -1      //already calculated
    Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
    v := edge[u][i]
    if v is not equal to parent[u]               //not a parent
        parent[v] := u
        if isGuarded equals to 0                 //not guarded, must set a watchman
            sum := sum + f(v,1)
        else                                     //guarded, check both
            sum := sum + min(f(v,1), f(v,0)
        end if
    end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]

Si denotamos el nodo A como raíz, llamaremos la función por: min(f(A,1), f(A,0)) . Eso significa que también verificaremos si es óptimo establecer a watchman en el nodo raíz o no. Esta es nuestra solución de DP. Este problema también se puede resolver utilizando el algoritmo de coincidencia máxima o max-flow.