dynamic-programming
Risoluzione dei problemi del grafico mediante la programmazione dinamica

Algoritmo di Floyd-Warshall

L'algoritmo di Floyd-Warshall è per la ricerca di percorsi più brevi in ​​un grafico ponderato con pesi di bordo positivi o negativi. Una singola esecuzione dell'algoritmo troverà le lunghezze (pesi sommati) dei percorsi più brevi tra tutte le coppie di vertici. Con una piccola variazione, può stampare il percorso più breve e può rilevare cicli negativi in ​​un grafico. Floyd-Warshall è un algoritmo di programmazione dinamica.

Diamo un'occhiata a un esempio. Applicheremo l'algoritmo di Floyd-Warshall su questo grafico:

La prima cosa che facciamo è prendere due matrici 2D. Queste sono matrici di adiacenza . La dimensione delle matrici sarà il numero totale di vertici. Per il nostro grafico, prenderemo 4 * 4 matrici. La Distance Matrix sta per memorizzare la distanza minima trovata finora tra due vertici. All'inizio, per i bordi, se c'è un margine tra uv e la distanza / peso è w , memorizzeremo: distance[u][v] = w . Per tutti i bordi che non esistono, metteremo l' infinito . La Path Matrix serve a rigenerare il percorso di minima distanza tra due vertici. Quindi, inizialmente, se v'è un percorso tra u e v, stiamo andando a mettere path[u][v] = u . Questo significa che il modo migliore per arrivare a vertice-v da vertice-u è usare il bordo che connette v con u . Se non ci sono percorsi tra due vertici, inseriremo N indicando che non esiste alcun percorso disponibile ora. Le due tabelle per il nostro grafico saranno simili a:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  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

Poiché non vi è alcun loop, le diagonali sono impostate N. E la distanza dal vertice stesso è 0 .

Per applicare l'algoritmo di Floyd-Warshall, selezioneremo un vertice medio k . Quindi, per ogni vertice i , controlleremo se possiamo passare da i a ke poi da k a j , dove j è un altro vertice e minimizzare il costo di passare da i a j . Se la distanza attuale [i] [j] è maggiore della distanza [i] [k] + distanza [k] [j] , metteremo la distanza [i] [j] uguale alla somma di queste due distanze . E il percorso [i] [j] sarà impostato su path [k] [j] , poiché è meglio passare da i a k , e quindi da k a j . Tutti i vertici saranno selezionati come k . Avremo 3 cicli annidati: per k che va da 1 a 4, i che va da 1 a 4 e j che va da 1 a 4. Stiamo andando controllo:

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

Quindi quello che stiamo fondamentalmente controllando è, per ogni coppia di vertici, otteniamo una distanza più breve passando da un altro vertice? Il numero totale di operazioni per il nostro grafico sarà 4 * 4 * 4 = 64 . Ciò significa che stiamo andando a fare questo controllo 64 volte. Diamo un'occhiata ad alcuni di loro:

Quando k = 1 , i = 2 e j = 3 , la distanza [i] [j] è -2 , che non è maggiore della distanza [i] [k] + distanza [k] [j] = -2 + 0 = -2 . Quindi rimarrà invariato. Di nuovo, quando k = 1 , i = 4 e j = 2 , distanza [i] [j] = infinito , che è maggiore della distanza [i] [k] + distanza [k] [j] = 1 + 3 = 4 . Quindi inseriamo la distanza [i] [j] = 4 e inseriamo il percorso [i] [j] = percorso [k] [j] = 1 . Ciò significa che, per passare dal vertice-4 al vertice-2 , il percorso 4-> 1-> 2 è più corto del percorso esistente. Questo è il modo in cui popoliamo entrambe le matrici. Il calcolo per ogni passaggio è mostrato qui . Dopo aver apportato le modifiche necessarie, le nostre matrici saranno simili a:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  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

Questa è la nostra matrice di distanza più breve. Ad esempio, la distanza più breve da 1 a 4 è 3 e la distanza più breve tra 4 e 3 è 2 . Il nostro pseudo-codice sarà:

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

Stampa del percorso:

Per stampare il percorso, controlleremo la matrice Path . Per stampare il percorso da u a v , inizieremo dal percorso [u] [v] . Continueremo a cambiare v = path [u] [v] finché non troviamo path [u] [v] = u e spingere tutti i valori di path [u] [v] in uno stack. Dopo aver trovato u, noi lo stamperemo u e cominciamo popping elementi dalla pila e stamparli. Questo funziona perché la matrice del percorso memorizza il valore del vertice che condivide il percorso più breve per v da qualsiasi altro nodo. Lo pseudo-codice sarà:

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

Individuazione del ciclo del bordo negativo:

Per scoprire se c'è un ciclo di bordo negativo, dovremo controllare la diagonale principale della matrice delle distanze . Se qualsiasi valore sulla diagonale è negativo, significa che c'è un ciclo negativo nel grafico.

Complessità:

La complessità dell'algoritmo di Floyd-Warshall è O (V³) e la complessità spaziale è: O (V²) .

Copertura Vertex minima

La copertura verticale di vertice è un classico problema grafico. Diciamo che in una città abbiamo alcune strade che collegano alcuni punti. Rappresentiamo le strade usando i bordi e i punti usando i nodi. Prendiamo due grafici di esempio:

Vogliamo impostare i guardiani su alcuni punti. Un guardiano può sorvegliare tutte le strade collegate al punto. Il problema è: qual è il numero minimo di sentinelle necessario per coprire tutte le strade? Se impostiamo sentinelle sul nodo A , B , H , I e J , possiamo coprire tutte le strade.

Questa è la nostra soluzione ottimale. Abbiamo bisogno di almeno 5 guardiani per proteggere l'intera città. Come determinare questo?

In un primo momento, dobbiamo capire che questo è un problema NP-difficile , ovvero che il problema non ha una soluzione temporale polinomiale. Ma se il grafico fosse un albero , significa che se aveva n-1 nodi dove n è il numero di spigoli e non ci sono cicli nel grafico, possiamo risolverlo usando la programmazione dinamica.

Per costruire una soluzione DP, dobbiamo seguire due strategie:

1. Se non ci sono guardiani in un nodo, tutti i nodi ad esso collegati devono avere un guardiano, o tutte le strade non saranno coperte. Se U e V sono connesse e u non ha alcun sentinella, poi v deve avere una sentinella.
2. Se c'è un guardiano in un nodo, un diverso nodo ad esso collegato può avere o meno un guardiano. Ciò significa che non è necessario avere un guardiano, ma può essere utile. Se U e V sono collegati e la u ha un guardiano, controlleremo e troviamo che da è vantaggioso per noi da:
   • Impostazione del guardiano in v .
   • Non impostare guardiano in v .

Definiamo una funzione ricorsiva con stato essendo il nodo corrente in cui ci troviamo e se ha o meno un guardiano. Qui:

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 funzione restituirà il numero di watchman nei restanti nodi.

Prendiamo un albero di esempio:

Possiamo facilmente dire che se non mettiamo watchman sul nodo A , dovremo mettere watchmen sul nodo B , C e D. Possiamo dedurre:

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

Ci restituisce il numero di sentinelle necessarie se non mettiamo watchman nel nodo A. Abbiamo aggiunto 0 alla fine perché non abbiamo impostato alcun watchman nel nostro nodo corrente.

Ora F(A,1) significa, impostiamo watchman nel nodo A. Per questo, possiamo impostare watchmen in tutti i nodi connessi o no. Prenderemo quello che ci fornisce il numero minimo di guardiani.

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

Controlliamo impostando e non impostando watchman su ciascun nodo e prendendo il valore ottimale.

Una cosa dobbiamo stare attenti che, una volta che andiamo al nodo figlio, non guarderemo mai al nodo genitore. Dall'esempio sopra, siamo passati a B da A , quindi genitore [B] = A. Quindi non torneremo ad A da B.

Per determinare il caso base, possiamo notare che, se da un nodo, non possiamo passare a nessun altro nuovo nodo, restituiremo 1 se c'è un guardiano nel nostro nodo corrente, 0 se non ci sono guardiani nel nostro attuale nodo.

È meglio avere una lista di adiacenza per il nostro albero. Lascia che la lista sia denotata dal bordo . Avremo un array dp [n] [2] , dove n indica il numero di nodi per memorizzare i valori calcolati e inizializzarlo con -1 . Avremo anche una matrice genitore [n] per indicare la relazione genitore e figlio tra i nodi. Il nostro pseudo-codice sarà simile a:

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]

Se denotiamo il nodo A come root, chiameremo la funzione per: min(f(A,1), f(A,0)) . Ciò significa che controlleremo anche se è ottimale impostare watchman nel nodo radice o meno. Questa è la nostra soluzione DP. Questo problema può anche essere risolto utilizzando l'algoritmo di corrispondenza massimo o il flusso massimo.