dynamic-programming
Lösen von Grafikproblemen mithilfe der dynamischen Programmierung

Floyd-Warshall-Algorithmus

Der Algorithmus von Floyd-Warshall dient zum Finden kürzester Pfade in einem gewichteten Diagramm mit positiven oder negativen Kantengewichten. Bei einer einzelnen Ausführung des Algorithmus werden die Längen (summierten Gewichtungen) der kürzesten Pfade zwischen allen Knotenpaaren ermittelt. Mit etwas Abweichung kann er den kürzesten Weg drucken und negative Zyklen in einem Diagramm erkennen. Floyd-Warshall ist ein Algorithmus zur dynamischen Programmierung.

Schauen wir uns ein Beispiel an. Wir werden den Algorithmus von Floyd-Warshall auf diese Grafik anwenden:

Als erstes nehmen wir zwei 2D-Matrizen. Dies sind Adjazenzmatrizen . Die Größe der Matrizen wird die Gesamtanzahl der Scheitelpunkte sein. Für unser Diagramm nehmen wir 4 * 4- Matrizen. Die Distanzmatrix speichert den bisher gefundenen Mindestabstand zwischen zwei Scheitelpunkten. Wenn sich für die Kanten zuerst eine Kante zwischen uv befindet und der Abstand / das Gewicht w ist , werden wir speichern: distance[u][v] = w . Für alle Kanten, die nicht existieren, setzen wir unendlich . Die Pfadmatrix dient zum Wiederherstellen eines Pfads mit minimalem Abstand zwischen zwei Scheitelpunkten. Wenn anfangs ein Pfad zwischen u und v ist , setzen wir path[u][v] = u . Dies bedeutet, der beste Weg, um von vertex-u zu vertex-v zu gelangen, ist die Verwendung der Kante, die v mit u verbindet . Wenn es keinen Pfad zwischen zwei Scheitelpunkten gibt, setzen wir dort N , um anzuzeigen, dass jetzt kein Pfad verfügbar ist. Die zwei Tabellen für unser Diagramm sehen folgendermaßen aus:

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

Da es keine Schleife gibt, werden die Diagonalen auf N gesetzt . Und der Abstand zum Scheitelpunkt selbst ist 0 .

Um den Floyd-Warshall-Algorithmus anzuwenden, wählen wir einen mittleren Scheitelpunkt k aus . Dann werden wir für jeden Knoten i prüfen, ob wir von i nach k und dann von k nach j gehen können , wobei j ein weiterer Knoten ist, und die Kosten für den Übergang von i nach j minimieren. Wenn der aktuelle Abstand [i] [j] größer ist als der Abstand [i] [k] + Abstand [k] [j] , setzen wir den Abstand [i] [j] gleich der Summe dieser beiden Abstände . Und der Pfad [i] [j] wird auf Pfad [k] [j] gesetzt , da es besser ist, von i nach k und dann von k nach j zu gehen . Alle Scheitelpunkte werden als k ausgewählt. Wir werden drei verschachtelte Schleifen haben: für k von 1 bis 4 gehen, i von 1 bis 4 und j von 1 bis 4 gehen gehe wir überprüfen gehen:

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

Im Grunde prüfen wir also, ob wir für jedes Scheitelpaar ein kürzeres Maß erreichen, wenn wir einen anderen Scheitelpunkt durchlaufen. Die Gesamtzahl der Operationen für unser Diagramm beträgt 4 * 4 * 4 = 64 . Das bedeutet, dass wir diese Prüfung 64- mal durchführen. Schauen wir uns einige davon an:

Wenn k = 1 , i = 2 und j = 3 ist , ist der Abstand [i] [j] -2 , was nicht größer ist als der Abstand [i] [k] + Abstand [k] [j] = -2 + 0 = -2 . So bleibt es unverändert. Wenn k = 1 , i = 4 und j = 2 ist , ist der Abstand [i] [j] = unendlich , was größer ist als der Abstand [i] [k] + Abstand [k] [j] = 1 + 3 = 4 . Also setzen wir Abstand [i] [j] = 4 und wir setzen Pfad [i] [j] = Pfad [k] [j] = 1 . Das bedeutet, um von Vertex-4 zu Vertex-2 zu gelangen , ist der Pfad 4-> 1-> 2 kürzer als der vorhandene Pfad. So bevölkern wir beide Matrizen. Die Berechnung für jeden Schritt wird hier angezeigt. Nachdem Sie die erforderlichen Änderungen vorgenommen haben, werden unsere Matrizen folgendermaßen aussehen:

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

Dies ist unsere kürzeste Entfernungsmatrix. Zum Beispiel ist der kürzeste Abstand von 1 bis 4 3 und der kürzeste Abstand zwischen 4 und 3 ist 2 . Unser Pseudo-Code lautet:

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

Pfad drucken:

Um den Pfad auszudrucken, überprüfen wir die Pfadmatrix . Um den Pfad von u nach v zu drucken, beginnen wir mit Pfad [u] [v] . Wir setzen fort, v = Pfad [u] [v] zu ändern, bis wir Pfad [u] [v] = u finden und alle Werte von Pfad [u] [v] in einem Stapel schieben. Nachdem Sie u gefunden haben , drucken wir u und fangen an, Gegenstände aus dem Stapel zu werfen und zu drucken. Dies funktioniert , weil die Pfad - Matrix den Wert des Scheitelpunktes speichert , die den kürzesten Weg zu v von jedem anderen Knoten teilt. Der Pseudo-Code lautet:

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

Suche nach einem negativen Kantenzyklus:

Um herauszufinden, ob es einen negativen Flankenzyklus gibt, müssen wir die Hauptdiagonale der Distanzmatrix überprüfen. Wenn ein Wert auf der Diagonale negativ ist, bedeutet dies, dass der Graph einen negativen Zyklus aufweist.

Komplexität:

Die Komplexität des Floyd-Warshall-Algorithmus ist O (V³) und die Raumkomplexität ist: O (V²) .

Minimum Vertex Cover

Minimum Vertex Cover ist ein klassisches Diagrammproblem. Sagen wir, in einer Stadt gibt es einige Straßen, die einige Punkte miteinander verbinden. Lassen Sie uns die Straßen mit Kanten und die Punkte mit Knoten darstellen. Nehmen wir zwei Beispielgraphen:

Wir wollen Wächter auf einige Punkte setzen. Ein Wächter kann alle mit dem Punkt verbundenen Straßen überwachen. Das Problem ist, wie viele Wächter müssen mindestens alle Straßen befahren? Wenn wir Wächter an Knoten A , B , H , I und J einstellen, können wir alle Straßen abdecken.

Dies ist unsere optimale Lösung. Wir brauchen mindestens 5 Wächter, um die ganze Stadt zu bewachen. Wie kann ich das feststellen?

Zunächst müssen wir verstehen, dass es sich um ein NP-hartes Problem handelt, dh das Problem hat keine polynomiale Zeitlösung. Wenn der Graph jedoch ein Baum ist, bedeutet dies, wenn er (n-1) Knoten hat, wobei n die Anzahl der Kanten ist und der Graph keinen Zyklus enthält, können wir ihn mit dynamischer Programmierung lösen.

Um eine DP-Lösung zu erstellen, müssen wir zwei Strategien verfolgen:

1. Wenn sich in einem Knoten kein Wächter befindet, müssen alle damit verbundenen Knoten über einen Wächter verfügen, oder alle Straßen werden nicht abgedeckt. Wenn u und v verbunden sind und u hat keine Wächter, dann muss v einen Wächter haben.
2. Befindet sich in einem Knoten ein Wächter, kann ein anderer Knoten einen Wächter haben oder nicht. Das heißt, es ist nicht notwendig, einen Wächter zu haben, aber es kann von Vorteil sein. Wenn u und v verbunden sind und u einen Wächter, werden wir überprüfen und durch die auf ist von Vorteil für uns:
   • Wächter in v .
   • Wächter nicht in v .

Definieren Sie eine rekursive Funktion, wobei state der aktuelle Knoten ist, in dem wir sich befinden, und ob es einen Watchman hat oder nicht. 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.

Die Funktion gibt die Anzahl der Watchman in den verbleibenden Knoten zurück.

Nehmen wir einen Beispielbaum:

Wir können leicht sagen, wenn wir Wächter nicht auf Knoten A setzen , müssen wir Wächter auf Knoten B , C und D setzen . Wir können ableiten:

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

Es gibt uns die Anzahl der Wächter zurück, die benötigt werden, wenn wir den Wächter nicht in Knoten A setzen . Wir haben am Ende 0 hinzugefügt, weil wir in unserem aktuellen Knoten keinen Wächter festgelegt haben.

Nun bedeutet F(A,1) , dass wir Wächter in Knoten- A setzen . Dafür können wir entweder Watchmen in allen verbundenen Knoten einstellen oder nicht. Wir nehmen den, der uns mit einer minimalen Anzahl von Wächtern versorgt.

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

Wir prüfen, indem Sie den Watchman an jedem Knoten einstellen und nicht einstellen und den optimalen Wert annehmen.

Eine Sache, die wir vorsichtig sein müssen: Sobald wir zum untergeordneten Knoten gehen, werden wir nie wieder auf den übergeordneten Knoten zurückblicken. Aus dem obigen Beispiel gingen wir von A nach B , also übergeordnet [B] = A. Wir werden also nicht von B nach A zurückgehen.

Um den Basisfall zu bestimmen, können wir feststellen, dass wir von einem Knoten zu keinem anderen neuen Knoten gelangen können. Wir geben 1 zurück, wenn sich in unserem aktuellen Knoten ein Wächter befindet, und 0, wenn sich in unserem aktuellen Knoten kein Wächter befindet Knoten.

Es ist besser, eine Nachbarschaftsliste für unseren Baum zu haben. Die Liste soll mit Rand bezeichnet werden. Wir haben ein Array dp [n] [2] , wobei n die Anzahl der Knoten angibt, die die berechneten Werte speichern und mit -1 initialisieren. Wir haben auch ein übergeordnetes [n] -Array, um die übergeordnete und untergeordnete Beziehung zwischen Knoten zu bezeichnen. Unser Pseudo-Code wird folgendermaßen aussehen:

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]

Wenn wir Knoten- A als root bezeichnen, rufen wir die Funktion mit: min(f(A,1), f(A,0)) . Das heißt, wir prüfen auch, ob es optimal ist, Watchman im Wurzelknoten zu setzen oder nicht. Dies ist unsere DP-Lösung. Dieses Problem kann auch mit dem Maximum Matching-Algorithmus oder Max-Flow gelöst werden.