dynamic-programming
Lösa grafproblem med dynamisk programmering

Floyd-Warshall algoritm

Floyd-Warshalls algoritm är för att hitta kortaste vägar i en vägd graf med positiva eller negativa kantvikter. En enda exekvering av algoritmen hittar längderna (summerade vikter) för de kortaste vägarna mellan alla vertikala par. Med lite variation kan den skriva ut den kortaste vägen och kan upptäcka negativa cykler i en graf. Floyd-Warshall är en dynamisk programmeringsalgoritm.

Låt oss titta på ett exempel. Vi kommer att tillämpa Floyd-Warshalls algoritm på den här grafen:

Det första vi gör är att vi tar två 2D-matriser. Det här är adjacensmatriser . Storleken på matriserna kommer att bli det totala antalet toppningar. För vår graf tar vi 4 * 4 matriser. Distansmatrisen kommer att lagra det minsta avstånd som hittills hittats mellan två toppar. Först, för kanterna, om det finns en kant mellan uv och avståndet / vikten är w , kommer vi att lagra: distance[u][v] = w . För alla kanter som inte finns, kommer vi att sätta oändlighet . Path Matrix är avsedd för regenerering av minsta distansväg mellan två vertikaler. Så till en början, om det finns en väg mellan u och v , kommer vi att sätta path[u][v] = u . Detta betyder att det bästa sättet att komma till vertex-v från vertex-u är att använda kanten som förbinder v med u . Om det inte finns någon bana mellan två hörn, kommer vi att lägga N där som indikerar att det inte finns någon bana nu. De två tabellerna för vår graf kommer att se ut:

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

Eftersom det inte finns någon slinga ställs diagonalerna in N. Och avståndet från själva toppunktet är 0 .

Att tillämpa Floyd-Warshall algoritm, vi kommer att välja en medelväg vertex k. Sedan för varje hörn i, kommer vi att kontrollera om vi kan gå från i till k och sedan k till j, där j är en annan vertex och minimera kostnaden för att gå från i till j. Om det aktuella avståndet [i] [j] är större än avståndet [i] [k] + avståndet [k] [j] , kommer vi att sätta avståndet [i] [j] lika med summeringen av dessa två avstånd . Och vägen [i] [j] kommer att ställas in på sökväg [k] [j] , eftersom det är bättre att gå från i till k , och sedan k till j . Alla vertikaler kommer att väljas som k . Vi har tre kapslade öglor: för k går från 1 till 4, jag går från 1 till 4 och j går från 1 till 4. Vi ska kolla:

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

Så vad vi i grund och botten kontrollerar är att för varje vertikala par får vi ett kortare avstånd genom att gå igenom en annan toppunkt? Det totala antalet operationer för vår graf är 4 * 4 * 4 = 64 . Det betyder att vi kommer att göra denna kontroll 64 gånger. Låt oss titta på några av dem:

När k = 1 , i = 2 och j = 3 , är avståndet [i] [j] -2 , vilket inte är större än avståndet [i] [k] + avståndet [k] [j] = -2 + 0 = -2 . Så det kommer att förbli oförändrat. Återigen, när k = 1 , i = 4 och j = 2 , avstånd [i] [j] = oändlighet , vilket är större än avståndet [i] [k] + avstånd [k] [j] = 1 + 3 = 4 . Så vi lägger avstånd [i] [j] = 4 , och vi lägger väg [i] [j] = sökväg [k] [j] = 1 . Vad detta betyder är att gå från topp-4 till topp-2 är vägen 4-> 1-> 2 kortare än den befintliga vägen. Så här fyller vi båda matriserna. Beräkningen för varje steg visas här . Efter att vi har gjort nödvändiga ändringar ser våra matriser ut:

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

Detta är vår kortaste distansmatris. Till exempel är det kortaste avståndet från 1 till 4 3 och det kortaste avståndet mellan 4 till 3 är 2 . Vår pseudokod kommer att vara:

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

Skriva ut sökvägen:

För att skriva ut sökvägen, kontrollerar vi sökvägsmatrisen . För att skriva ut banan från u till v , börjar vi från sökväg [u] [v] . Vi kommer att ställa in att fortsätta ändra v = sökväg [u] [v] tills vi hittar sökväg [u] [v] = u och skjuter alla värden på sökväg [u] [v] i en bunt. Efter att ha hittat dig , kommer vi att skriva ut u och börja poppa objekt från bunten och skriva ut dem. Detta fungerar eftersom den bana matris lagrar värdet av vertex som delar den kortaste vägen till v från någon annan nod. Pseudokoden kommer att vara:

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

Hitta negativ kantcykel:

För att ta reda på om det finns en negativ kantcykel måste vi kontrollera huvuddiagonalen för distansmatris . Om något värde på diagonalen är negativt betyder det att det finns en negativ cykel i diagrammet.

Komplexitet:

Komplexiteten hos Floyd-Warshall-algoritmen är O (V³) och rymdkomplexiteten är: O (V²) .

Minsta toppmantel

Minimum Vertex Cover är ett klassiskt grafproblem. Låt oss säga, i en stad har vi några vägar som förbinder några punkter. Låt oss representera vägarna med kanter och punkter som använder noder. Låt oss ta två exempelgrafer:

Vi vill ställa vaktmästare på vissa punkter. En vaktmästare kan skydda alla vägar som är anslutna till punkten. Problemet är, vad är det minsta antalet vakthavare som behövs för att täcka alla vägar? Om vi ställer vakthavare vid nod A , B , H , I och J , kan vi täcka alla vägar.

Detta är vår optimala lösning. Vi behöver minst fem vaktmän för att skydda hela staden. Hur bestämmer jag detta?

Först måste vi förstå att detta är ett NP-hårt problem, dvs. problemet har ingen polynomisk tidslösning. Men om diagrammet var ett träd , betyder det att om det hade (n-1) noder där n är antalet kanter och det inte finns någon cykel i diagrammet, kan vi lösa det med dynamisk programmering.

För att konstruera en DP-lösning måste vi följa två strategier:

1. Om det inte finns någon vaktmästare i en nod, måste alla noder som är anslutna till den ha en vaktmästare, annars kommer alla vägar inte att täckas. Om u och v är anslutna och du inte har någon vaktare, måste v ha en vaktmästare.
2. Om det finns en vaktmästare i en nod, kan en annan nod kopplad till den kanske eller inte ha en vaktmästare. Det betyder att det inte är nödvändigt att ha en vaktmästare, men det kan vara fördelaktigt. Om u och v är anslutna och u har en vaktmästare, ska vi kontrollera och hitta vilken som är till nytta för oss genom att:
   • Ställer in vakten i v .
   • Sätter inte vakten i v .

Låt oss definiera en rekursiv funktion där staten är den nuvarande nod vi befinner oss i och om den har en vaktmästare eller inte. Här:

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.

Funktionen returnerar antalet vaktmästare i återstående noder.

Låt oss ta ett exempelträd:

Vi kan lätt säga att om vi inte sätter vakten på nod- A , måste vi sätta vakterna på nod- B , C och D. Vi kan härleda:

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

Det ger oss antalet bevakare som behövs om vi inte sätter vakten i nod- A . Vi har lagt till 0 i slutet eftersom vi inte satt någon vaktmästare i vår nuvarande nod.

Nu betyder F(A,1) , vi sätter vakten i nod- A . För det kan vi antingen ställa vaktmästare i alla anslutna noder eller så gör vi det inte. Vi tar den som ger oss ett minimumantal bevakare.

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

Vi kontrollerar genom att ställa in och inte ställa vaktmästare på varje nod och ta det optimala värdet.

En sak som vi måste vara försiktiga med är att när vi går till barnnoden så ser vi aldrig tillbaka till föräldernoden. Från exemplet ovan gick vi till B från A , så förälder [B] = A. Så vi kommer inte tillbaka till A från B.

För att fastställa basfall kan vi märka att om vi från en nod inte kan gå till någon annan ny nod, kommer vi tillbaka 1 om det finns en vaktmästare i vår nuvarande nod, 0 om det inte finns någon vaktmästare i vår nuvarande nod nod.

Det är bättre att ha en adjacenslista för vårt träd. Låt listan betecknas efter kant . Vi har en matris dp [n] [2] , där n anger antalet noder för att lagra de beräknade värdena och initialisera det med -1 . Vi har också en förälder [n] -grupp för att beteckna förälder- och barnförhållandet mellan noder. Vår pseudokod kommer att se ut:

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]

Om vi betecknar nod- A som root, kallar vi funktionen med: min(f(A,1), f(A,0)) . Det betyder att vi också ska kontrollera om det är optimalt att ställa in vaktmannen i rotnoden eller inte. Detta är vår DP-lösning. Detta problem kan också lösas med hjälp av maximal matchande algoritm eller max-flow.