dynamic-programming
Rozwiązywanie problemów z grafem za pomocą programowania dynamicznego

Algorytm Floyda-Warshalla

Algorytm Floyda-Warshalla służy do znajdowania najkrótszych ścieżek na wykresie ważonym z dodatnimi lub ujemnymi wagami krawędzi. Pojedyncze wykonanie algorytmu znajdzie długości (zsumowane wagi) najkrótszych ścieżek między wszystkimi parami wierzchołków. Przy niewielkiej zmienności może wydrukować najkrótszą ścieżkę i wykryć cykle ujemne na wykresie. Floyd-Warshall to algorytm programowania dynamicznego.

Spójrzmy na przykład. Na tym wykresie zastosujemy algorytm Floyda-Warshalla:

Po pierwsze, bierzemy dwie matryce 2D. Są to macierze przylegania . Rozmiar macierzy będzie całkowitą liczbą wierzchołków. Do naszego wykresu weźmiemy macierze 4 * 4 . Macierz odległości będzie przechowywać minimalną odległość znalezioną do tej pory między dwoma wierzchołkami. Na początku, dla krawędzi, jeśli istnieje krawędź między UV a odległość / waga wynosi w , będziemy przechowywać: distance[u][v] = w . Dla wszystkich krawędzi, które nie istnieją, wprowadzimy nieskończoność . Matryca ścieżek służy do regeneracji ścieżki minimalnej odległości między dwoma wierzchołkami. Tak więc początkowo, jeśli istnieje ścieżka między u i v , wstawimy path[u][v] = u . Oznacza to, że najlepszym sposobem, aby przyjść do wierzchołka-v od wierzchołka-u jest użycie krawędzi łączącej V z u. Jeśli między dwoma wierzchołkami nie ma ścieżki, umieścimy tam N , wskazując, że nie ma obecnie dostępnej ścieżki. Dwie tabele dla naszego wykresu będą wyglądały następująco:

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

Ponieważ nie ma pętli, przekątne są ustawione na N. Odległość od samego wierzchołka wynosi 0 .

Aby zastosować algorytm Floyda-Warshalla, wybierzemy środkowy wierzchołek k . Następnie dla każdego wierzchołka i sprawdzimy, czy możemy przejść od i do k, a następnie od k do j , gdzie j jest innym wierzchołkiem i zminimalizujemy koszty przejścia od i do j . Jeśli bieżąca odległość [i] [j] jest większa niż odległość [i] [k] + odległość [k] [j] , ustawimy odległość [i] [j] równą sumie tych dwóch odległości . Ścieżka [i] [j] zostanie ustawiona na ścieżkę [k] [j] , ponieważ lepiej jest przejść od i do k , a następnie od k do j . Wszystkie wierzchołki zostaną wybrane jako k . Musimy 3 zagnieżdżone pętle: k trwającego od 1 do 4, i począwszy od 1 do 4 i j trwającego od 1 do 4. Jedziemy czek:

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

Więc w zasadzie sprawdzamy, czy dla każdej pary wierzchołków uzyskujemy krótszy dystans, przechodząc przez inny wierzchołek? Całkowita liczba operacji dla naszego wykresu wyniesie 4 * 4 * 4 = 64 . Oznacza to, że sprawdzimy to 64 razy. Spójrzmy na kilka z nich:

Gdy k = 1 , i = 2 i j = 3 , odległość [i] [j] wynosi -2 , co nie jest większe niż odległość [i] [k] + odległość [k] [j] = -2 + 0 = -2 . Więc pozostanie niezmieniony. Ponownie, gdy k = 1 , i = 4 i j = 2 , odległość [i] [j] = nieskończoność , która jest większa niż odległość [i] [k] + odległość [k] [j] = 1 + 3 = 4 . Więc umieszczamy odległość [i] [j] = 4 i umieszczamy ścieżkę [i] [j] = ścieżka [k] [j] = 1 . Oznacza to, że aby przejść z wierzchołka-4 do wierzchołka-2 , ścieżka 4-> 1-> 2 jest krótsza niż istniejąca ścieżka. W ten sposób wypełniamy obie macierze. Obliczenia dla każdego kroku pokazano tutaj . Po wprowadzeniu niezbędnych zmian nasze matryce będą wyglądały następująco:

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

To nasza najkrótsza macierz odległości. Na przykład najkrótsza odległość od 1 do 4 wynosi 3, a najkrótsza odległość od 4 do 3 wynosi 2 . Nasz pseudo-kod będzie:

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

Drukowanie ścieżki:

Aby wydrukować ścieżkę, sprawdzimy macierz Ścieżki . Aby wydrukować ścieżkę od u do v , zaczniemy od ścieżki [u] [v] . Ustawimy zmienianie v = ścieżka [u] [v], dopóki nie znajdziemy ścieżki [u] [v] = u i nie wypchniemy wszystkich wartości ścieżki [u] [v] na stos. Po znalezieniu u, będziemy drukować u i zacząć popping elementy ze stosu i wydrukować je. Działa to, ponieważ macierz ścieżek przechowuje wartość wierzchołka, który dzieli najkrótszą ścieżkę do v z dowolnego innego węzła. Pseudo-kod będzie:

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

Znajdowanie cyklu ujemnej krawędzi:

Aby dowiedzieć się, czy istnieje ujemny cykl zbocza, musimy sprawdzić główną przekątną macierzy odległości . Jeśli jakakolwiek wartość na przekątnej jest ujemna, oznacza to, że na wykresie występuje cykl ujemny.

Złożoność:

Złożoność algorytmu Floyda-Warshalla wynosi O (V³), a złożoność przestrzeni to: O (V²) .

Minimalna pokrywa wierzchołków

Minimalna pokrywa wierzchołków jest klasycznym problemem graficznym. Powiedzmy, że w mieście mamy kilka dróg łączących kilka punktów. Przedstawmy drogi za pomocą krawędzi, a punkty za pomocą węzłów. Weźmy dwa przykładowe wykresy:

Chcemy ustawić strażników w niektórych punktach. Stróż może strzec wszystkich dróg połączonych z punktem. Problem polega na tym, jaka jest minimalna liczba stróżów potrzebnych do pokonania wszystkich dróg? Jeśli ustawimy strażników na węzłach A , B , H , I i J , możemy pokonać wszystkie drogi.

To jest nasze optymalne rozwiązanie. Potrzebujemy co najmniej 5 stróżów, którzy będą strzec całego miasta. Jak to ustalić?

Na początku musimy zrozumieć, że jest to problem trudny dla NP , tzn. Że problem nie ma rozwiązania czasu wielomianowego. Ale jeśli wykres był drzewem , to znaczy, że miał (n-1) węzły, gdzie n jest liczbą krawędzi i na wykresie nie ma cyklu, możemy go rozwiązać za pomocą programowania dynamicznego.

Aby zbudować rozwiązanie DP, musimy przestrzegać dwóch strategii:

1. Jeśli w węźle nie ma stróża, wszystkie połączone z nim węzły muszą mieć stróża, w przeciwnym razie wszystkie drogi nie zostaną pokryte. Jeśli u i v są podłączone u nie ma żadnego stróża, a następnie v musi mieć stróża.
2. Jeśli w węźle jest stróż, inny podłączony do niego węzeł może mieć stróża, ale nie musi. Oznacza to, że nie trzeba mieć stróża, ale może to być korzystne. Jeśli U i V są podłączone i ma u stróża, będziemy sprawdzić i dowiedzieć się, jakie on jest korzystna dla nas:
   • Ustawienie stróża w w .
   • Nie ustawianie stróża w w .

Zdefiniujmy funkcję rekurencyjną, której stan jest bieżącym węzłem, w którym się znajdujemy i czy ma on stróża, czy nie. Tutaj:

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.

Funkcja zwróci liczbę stróża w pozostałych węzłach.

Weźmy przykładowe drzewo:

Możemy z łatwością powiedzieć, że jeśli nie umieścimy stróża w węźle A , będziemy musieli postawić stróża w węźle B , C i D. Możemy wywnioskować:

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

Zwraca nam liczbę potrzebnych stróżów, jeśli nie umieścimy stróża w węźle A. Na końcu dodaliśmy 0, ponieważ nie ustawiliśmy żadnego stróża w naszym bieżącym węźle.

Teraz F(A,1) oznacza, że ustawiamy stróża w węźle A. W tym celu możemy ustawić strażników we wszystkich połączonych węzłach lub nie. Weźmiemy ten, który zapewnia nam minimalną liczbę strażników.

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

Sprawdzamy, ustawiając i nie ustawiając stróża na każdym węźle i przyjmując optymalną wartość.

Jedną rzeczą, na którą musimy uważać, jest to, że kiedy przejdziemy do węzła potomnego, nigdy nie spojrzymy wstecz na węzeł macierzysty. Z powyższego przykładu poszliśmy do B z A , więc rodzic [B] = A. Więc nie wrócimy do A z B.

Aby określić przypadek podstawowy, możemy zauważyć, że jeśli z węzła nie możemy przejść do żadnego innego nowego węzła, zwrócimy 1, jeśli w naszym bieżącym węźle jest stróż, 0, jeśli w naszym bieżącym nie ma stróża węzeł.

Lepiej mieć listę sąsiedztwa dla naszego drzewa. Niech lista będzie oznaczona krawędzią . Będziemy mieć tablicę dp [n] [2] , gdzie n oznacza liczbę węzłów do przechowywania obliczonych wartości i inicjalizacji jej za pomocą -1 . Będziemy także mieli tablicę nadrzędną [n], aby wskazać relację nadrzędną i podrzędną między węzłami. Nasz pseudo-kod będzie wyglądał następująco:

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]

Jeśli oznaczymy węzeł- A jako root, wywołamy funkcję przez: min(f(A,1), f(A,0)) . Oznacza to, że sprawdzimy również, czy optymalne jest ustawienie stróża w węźle głównym, czy nie. To jest nasze rozwiązanie DP. Ten problem można również rozwiązać za pomocą algorytmu maksymalnego dopasowania lub maksymalnego przepływu.