dynamic-programming
Grafische problemen oplossen met dynamische programmering

Floyd-Warshall-algoritme

Het algoritme van Floyd-Warshall is voor het vinden van de kortste paden in een gewogen grafiek met positieve of negatieve randgewichten. Een enkele uitvoering van het algoritme vindt de lengtes (opgetelde gewichten) van de kortste paden tussen alle paar hoekpunten. Met een beetje variatie kan het het kortste pad afdrukken en negatieve cycli in een grafiek detecteren. Floyd-Warshall is een algoritme voor dynamisch programmeren.

Laten we een voorbeeld bekijken. We gaan het algoritme van Floyd-Warshall op deze grafiek toepassen:

Het eerste wat we doen is, nemen we twee 2D-matrices. Dit zijn aangrenzende matrices . De grootte van de matrices wordt het totale aantal hoekpunten. Voor onze grafiek nemen we 4 * 4 matrices. De afstandsmatrix gaat de minimaal gevonden afstand tussen twee hoekpunten opslaan. Voor de randen, als er een rand is tussen uv en de afstand / gewicht is w , slaan we op: distance[u][v] = w . Voor alle randen die niet bestaan, gaan we oneindig . De padmatrix is voor het regenereren van het minimale afstandpad tussen twee hoekpunten. Dus als er een pad is tussen u en v , gaan we path[u][v] = u . Dit betekent dat de beste manier om van vertex-u naar vertex-v te komen, is door de rand te gebruiken die v met u verbindt. Als er geen pad tussen twee hoekpunten is, gaan we N daar plaatsen om aan te geven dat er nu geen pad beschikbaar is. De twee tabellen voor onze grafiek zien er als volgt uit:

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

Omdat er geen lus is, zijn de diagonalen ingesteld op N. En de afstand vanaf het hoekpunt zelf is 0 .

Om het Floyd-Warshall-algoritme toe te passen, gaan we een middelpunt selecteren k . Vervolgens gaan we voor elk hoekpunt i controleren of we van i naar k en vervolgens van k naar j kunnen gaan , waarbij j een ander hoekpunt is en de kosten minimaliseren om van i naar j te gaan . Als de huidige afstand [i] [j] groter is dan afstand [i] [k] + afstand [k] [j] , gaan we afstand [i] [j] gelijk stellen aan de som van die twee afstanden . En het pad [i] [j] wordt ingesteld op pad [k] [j] , omdat het beter is om van i naar k te gaan en vervolgens van k naar j . Alle hoekpunten worden geselecteerd als k . We hebben 3 geneste lussen: voor k van 1 tot 4, ik van 1 tot 4 en j van 1 tot 4. We gaan het volgende controleren:

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

Dus wat we eigenlijk controleren, is dat we voor elk paar hoekpunten een kortere afstand krijgen door door een ander hoekpunt te gaan? Het totale aantal bewerkingen voor onze grafiek is 4 * 4 * 4 = 64 . Dat betekent dat we deze controle 64 keer gaan uitvoeren. Laten we er een paar bekijken:

Wanneer k = 1 , i = 2 en j = 3 , is afstand [i] [j] -2 , wat niet groter is dan afstand [i] [k] + afstand [k] [j] = -2 + 0 = -2 . Het blijft dus ongewijzigd. Nogmaals, wanneer k = 1 , i = 4 en j = 2 , afstand [i] [j] = oneindig , wat groter is dan afstand [i] [k] + afstand [k] [j] = 1 + 3 = 4 . Dus zetten we afstand [i] [j] = 4 , en we zetten pad [i] [j] = pad [k] [j] = 1 . Wat dit betekent is dat om van vertex-4 naar vertex-2 te gaan , het pad 4-> 1-> 2 korter is dan het bestaande pad. Dit is hoe we beide matrices vullen. De berekening voor elke stap wordt hier weergegeven. Na het aanbrengen van de nodige wijzigingen zien onze matrices eruit:

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

Dit is onze kortste afstandsmatrix. De kortste afstand van 1 tot 4 is bijvoorbeeld 3 en de kortste afstand tussen 4 en 3 is 2 . Onze pseudo-code zal zijn:

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

Het pad afdrukken:

Om het pad af te drukken, controleren we de padmatrix . Om het pad van u naar v af te drukken, beginnen we vanaf pad [u] [v] . We zullen instellen dat v = pad [u] [v] blijft veranderen totdat we pad [u] [v] = u vinden en alle waarden van pad [u] [v] in een stapel pushen. Na het vinden van u, zullen wij u af te drukken en start popping items uit de stapel en afdrukken. Dit werkt omdat het pad matrix slaat de waarde van het hoekpunt waarvan deelt de kortste weg naar v van een ander knooppunt. De pseudo-code zal zijn:

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

Negatieve randcyclus vinden:

Om erachter te komen of er een negatieve randcyclus is, moeten we de hoofddiagonaal van de afstandsmatrix controleren . Als een waarde op de diagonaal negatief is, betekent dit dat er een negatieve cyclus in de grafiek is.

complexiteit:

De complexiteit van het Floyd-Warshall-algoritme is O (V³) en de complexiteit van de ruimte is: O (V²) .

Minimale hoekpuntdekking

Minimale Vertex Cover is een klassiek grafiekprobleem. Laten we zeggen, in een stad hebben we een paar wegen die een paar punten verbinden. Laten we de wegen weergeven met randen en de punten met knooppunten. Laten we twee voorbeeldgrafieken nemen:

We willen wachters op sommige punten zetten. Een wachter kan alle wegen bewaken die met het punt zijn verbonden. Het probleem is, wat is het minimale aantal wachters dat nodig is om alle wegen te bedekken? Als we wachters op knooppunt A , B , H , I en J zetten , kunnen we alle wegen bedekken.

Dit is onze optimale oplossing. We hebben minstens 5 wachters nodig om de hele stad te bewaken. Hoe dit te bepalen?

In het begin moeten we begrijpen dat dit een NP-moeilijk probleem is, dat wil zeggen dat het probleem geen polynomiale tijdoplossing heeft. Maar als de grafiek een boom was , betekent dit dat als het (n-1) knooppunten had waarbij n het aantal randen is en er geen cyclus in de grafiek is, we het kunnen oplossen met behulp van dynamische programmering.

Om een DP-oplossing te bouwen, moeten we twee strategieën volgen:

1. Als er geen bewaker in een knooppunt is, moeten alle knooppunten die ermee zijn verbonden een bewaker hebben, anders worden niet alle wegen bedekt. Als u en v verbonden zijn en u heeft geen bewaker, dan moet v een bewaker hebben.
2. Als er een bewaker in een knoop is, kan een andere knoop die erop is aangesloten wel of geen bewaker hebben. Dat betekent dat het niet nodig is om een wachter te hebben, maar het kan nuttig zijn. Als u en v verbonden zijn en u heeft een bewaker, zullen we controleren en vinden welke op ons voordelig is door:
   • Wachter instellen in v .
   • Wachter niet instellen in v .

Laten we een recursieve functie definiëren met status als het huidige knooppunt waarin we ons bevinden en of het een bewaker heeft of niet. Hier:

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.

De functie retourneert het aantal bewaker in resterende knooppunten.

Laten we een voorbeeldboom nemen:

We kunnen gemakkelijk zeggen dat als we geen wachter op knooppunt A zetten , we wachters op knooppunt B , C en D moeten zetten . We kunnen afleiden:

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

Het geeft ons het aantal benodigde wachters als we de wacht niet in knoop A zetten . We hebben aan het einde 0 toegevoegd omdat we geen bewaker in onze huidige node hebben geplaatst.

Nu betekent F(A,1) dat we de wachter in knooppunt A zetten . Daarvoor kunnen we wachters instellen op alle verbonden knooppunten of niet. We nemen degene die ons een minimum aantal wachters geeft.

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

We controleren door wachter op elk knooppunt in te stellen en niet in te stellen en de optimale waarde te nemen.

Eén ding waar we voorzichtig mee moeten zijn, is dat we, als we eenmaal naar het onderliggende knooppunt gaan, nooit meer terugkijken naar het bovenliggende knooppunt. Uit het bovenstaande voorbeeld zijn we van A naar B gegaan, dus ouder [B] = A. Dus we gaan niet terug naar A vanaf B.

Om het basisscenario te bepalen, kunnen we opmerken dat als we vanuit een knooppunt niet naar een ander nieuw knooppunt kunnen gaan, we 1 retourneren als er een bewaker is in onze huidige knoop, 0 als er geen bewaker is in onze huidige knooppunt.

Het is beter om een aangrenzende lijst voor onze boom te hebben. Laat de lijst met rand worden aangegeven. We hebben een array dp [n] [2] , waarbij n het aantal knooppunten aangeeft om de berekende waarden op te slaan en te initialiseren met -1 . We hebben ook een ouder [n] array om de ouder- en kindrelatie tussen knooppunten aan te geven. Onze pseudo-code ziet eruit als:

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]

Als we knooppunt- A als root aanduiden, zullen we de functie aanroepen door: min(f(A,1), f(A,0)) . Dat betekent dat we ook zullen controleren of het optimaal is om watchman in het root-knooppunt te zetten of niet. Dit is onze DP-oplossing. Dit probleem kan ook worden opgelost met behulp van het maximale matching-algoritme of max-flow.