Wstęp W zobaczyliśmy, jak rozwiązać problem najkrótszej ścieżki dla wszystkich par, używając . Zbadaliśmy również kilka sposobów na poprawę wydajności algorytmu, używając paralelizmu i wektoryzacji. poprzednim poście algorytmu Floyda-Warshalla Jednakże, jeśli pomyślimy o wynikach algorytmu Floyda-Warshalla, szybko zauważymy interesujący moment – znamy odległości (wartości najkrótszych ścieżek) między wierzchołkami w grafie, ale nie znamy „tras”, tzn. nie wiemy, jakie wierzchołki przyczyniają się do każdej najkrótszej ścieżki i nie możemy odtworzyć tych „tras” na podstawie posiadanych wyników. W tym poście zapraszam do dołączenia do mnie i rozszerzenia algorytmu Floyda-Warshalla. Tym razem upewnimy się, że możemy obliczyć odległość i odbudować „trasę”. Trochę znanej teorii… Zanim zagłębimy się w kod i testy porównawcze, przypomnijmy sobie teorię działania algorytmu Floyda-Warshalla. Oto opis tekstowy algorytmu: Zaczynamy od przedstawienia grafu ( ) o rozmiarze jako macierzy ( ) o rozmiarze , gdzie każda komórka zawiera wagę krawędzi od wierzchołka do wierzchołka (patrz Rysunek 1). W przypadkach, gdy nie ma krawędzi między wierzchołkami, komórka jest ustawiana na specjalną wartość (pokazaną jako ciemne komórki na Rysunku 1). G N W N x N W[i,j] i j NO_EDGE Od tej chwili mówimy – zawiera odległość między wierzchołkami oraz . W[i,j] i j Następnie bierzemy wierzchołek i przechodzimy przez wszystkie pary wierzchołków sprawdzając czy odległość jest mniejsza niż aktualnie znana odległość między i . k W[i,j] i ⭢ k ⭢ j i j Najmniejsza wartość jest przechowywana w , a krok nr 3 jest powtarzany dla następnego aż wszystkie wierzchołki zostaną użyte jako . W[i,j] k G k Oto pseudo-kod: algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm Po wykonaniu tej operacji każda komórka macierzy będzie zawierała odległość najkrótszej ścieżki między wierzchołkami i lub wartość , jeśli nie ma między nimi ścieżki. W[i,j] W i j NO_EDGE Jak wspomniałem na początku – posiadanie tylko tych informacji uniemożliwia rekonstrukcję tras między tymi wierzchołkami. Więc… co powinniśmy zrobić, aby móc zrekonstruować te trasy? Cóż... może to zabrzmieć oczywiste, ale... musimy zebrać więcej danych! … Trochę tej samej teorii, ale z innej perspektywy Istotą algorytmu Floyda-Warshalla jest przedział o znanej odległości z odległością potencjalnie nowej ścieżki z do przez wierzchołek pośredni . W[i,j] i j k Przywiązuję tak dużą wagę do tego szczegółu, ponieważ jest on kluczem do tego, jak możemy zachować informacje o trasie. Weźmy poprzedni graf 5 wierzchołków (patrz Rysunek 2) i wykonajmy na nim algorytm Floyda-Warshalla. Początkowo znamy wszystkie krawędzie grafu, co daje nam następujące ścieżki: , , , , i . 0 ⭢ 1 :2 0 ⭢ 4 :10 1 ⭢ 3 :1 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 Do zapisywania ścieżek używam formatu „od” ⭢ „do” :”odległość” z . poprzedniego posta - Uwaga autora Wiemy również, że nie ma krawędzi prowadzących do wierzchołka , więc wykonywanie algorytmu dla nie ma sensu. Oczywiste jest również, że istnieje pojedyncza krawędź ( ) prowadząca od wierzchołka do wierzchołka , co również sprawia, że wykonywanie wszystkich ( jest tutaj „z”) jest całkowicie bezsensowne, a ponieważ wierzchołek ma krawędzie z i , nie ma również sensu wykonywanie algorytmów dla dowolnego , które nie jest lub ( jest tutaj „do”). 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 j 2 4 j Dlatego naszym pierwszym krokiem będzie wykonanie algorytmu dla , i . k = 1 i = 0 j = 2,4 Krok Ścieżka Komentarz 1 0 ⭢ 1 ⭢ 2 Znaleziono ścieżkę. Odległość = 3 (nie było nic) 2 0 ⭢ 1 ⭢ 4 Znaleziono ścieżkę. Odległość = 8 (było 10). Znaleźliśmy dwie ścieżki: nową ścieżkę ( ) i skrót ( ). Obie przechodzą przez wierzchołek Jeśli nie zapiszemy tej informacji (faktu, że dotarliśmy do i przez ) gdzieś teraz, zostanie ona utracona na zawsze (a to jest całkowite przeciwieństwo tego, czego chcemy). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 2 4 1 Co więc powinniśmy zrobić? Zaktualizujemy macierz nowymi wartościami (patrz Rysunek 3a) i zapiszemy wartość ( ) w komórkach i nowej macierzy o takim samym rozmiarze jak macierz ale zainicjowanej wartościami (patrz Rysunek 3b). W k k = 1 R[0,2] R[0,4] R W NO_EDGE Na razie nie skupiajmy się na tym, czym dokładnie jest macierz Po prostu kontynuujmy i wykonajmy algorytm dla następnego . R k = 2 Tutaj wykonamy tę samą analizę (aby zrozumieć, jakie kombinacje mają sens wykonać), jaką przeprowadziliśmy dla ale tym razem użyjemy macierzy zamiast wykresu Przyjrzyjmy się macierzy , szczególnie w kolumnie nr 2 i wierszu nr 2 (Rysunek 4). k = 1, W G W Tutaj widać, że istnieją dwie ścieżki do wierzchołka z wierzchołka i z wierzchołka (kolumna nr 2) oraz dwie ścieżki z wierzchołka do wierzchołka i do wierzchołka (wiersz nr 2). Wiedząc o tym, ma sens wykonanie algorytmu tylko dla kombinacji , i . 2 0 1 2 3 4 k = 2 i = 0,1 j = 3,4 Krok Ścieżka Komentarz 1 0 ⭢ 2 ⭢ 3 Znaleziono ścieżkę. Odległość = 4 (było nic) 2 0 ⭢ 2 ⭢ 4 Znaleziono ścieżkę. Odległość = 6 (było 8) 3 1 ⭢ 2 ⭢ 3 Znaleziono ścieżkę. Odległość = 2 (nie było nic) 4 1 ⭢ 2 ⭢ 4 Znaleziono ścieżkę. Odległość = 4 (było 6) Jak już zrobiliśmy wcześniej, aktualizujemy komórki , , , o nowe odległości, a komórki , , i o (patrz Rysunek 5). W[0,3] W[0,4] W[1,3] W[1,4] R[0,3] R[0,4] R[1,3] R[1,4] k = 2 Pozostało tylko do przetworzenia (ponieważ nie ma krawędzi prowadzących z wierzchołka do żadnego innego wierzchołka na grafie). k = 3 4 Przyjrzyjmy się ponownie macierzy (rysunek 6). W Zgodnie z macierzą istnieją trzy ścieżki do wierzchołka z wierzchołków , i (kolumna nr 3), a istnieje jedna ścieżka z wierzchołka do wierzchołka (wiersz nr 3). Dlatego mamy następujące ścieżki do przetworzenia: W 3 0 1 2 3 4 Krok Ścieżka Komentarz 1 0 ⭢ 3 ⭢ 4 Znaleziono ścieżkę. Odległość = 5 (było 6) 2 1 ⭢ 3 ⭢ 4 Znaleziono ścieżkę. Odległość = 3 (było 4) 3 2 ⭢ 3 ⭢ 4 Znaleziono ścieżkę. Odległość = 2 (było 3) Była to ostatnia iteracja algorytmu. Pozostało jedynie zaktualizować komórki , , nowymi odległościami i ustawić komórki , , na . W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] 3 Oto co otrzymaliśmy na końcu algorytmu (Rysunek 7). Jak wiemy z , macierz zawiera teraz wszystkie pary najkrótszych ścieżek w grafie Ale co jest przechowywane w macierzy ? poprzedniego wpisu W G R Powrót Za każdym razem, gdy znaleźliśmy nową najkrótszą ścieżkę, aktualizowaliśmy odpowiadającą jej komórkę macierzy bieżącą wartością . Podczas gdy na początku ta czynność może wydawać się tajemnicza, ma ona bardzo proste znaczenie – przechowywaliśmy wierzchołek, z którego dotarliśmy do wierzchołka docelowego: (tutaj docieramy do bezpośrednio z ). R k i ⭢ k ⭢ j j k Ten moment jest kluczowy. Ponieważ znajomość wierzchołka, z którego przyszliśmy, pozwala nam na odbudowanie trasy poprzez cofanie się (jak homar) od wierzchołka („do”) do wierzchołka („od”). j i Poniżej znajduje się opis tekstowy algorytmu przebudowującego trasę z do : i j Przygotuj pustą tablicę dynamiczną X Zacznij od odczytania wartości z komórki . z R[i,j] Jeśli jest , to trasa z do została znaleziona i możemy przejść do kroku nr 7. z NO_EDGE i j Dodaj na początku tablicy dynamicznej z X Odczytaj wartość komórki do . R[i,z] z Powtarzaj kroki 3, 4 i 5, aż zostanie osiągnięty warunek wyjścia podany w punkcie 3. Dodaj do X. i Dodaj do j X Teraz dynamiczna tablica zawiera trasę z do . X i j Należy pamiętać, że powyższy algorytm działa tylko dla istniejących ścieżek. Nie jest on również idealny z punktu widzenia wydajności i z pewnością można go zoptymalizować. Jednak w zakresie tego posta jest on szczegółowo opisany w taki sposób, aby ułatwić jego zrozumienie i odtworzenie na kartce papieru. - Uwaga autora W pseudokodzie wygląda to jeszcze prościej: algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm Wypróbujmy to na naszym grafie i odbudujmy trasę od wierzchołka do wierzchołka (patrz rysunek 8). G 0 4 Oto opis tekstowy powyższej ilustracji: Zaczynamy od odczytania wartości z , co daje wynik Zgodnie z algorytmem oznacza to, że trasa prowadzi do wierzchołka z wierzchołka (zaznaczonego na NIEBIESKO). R[0,4] 3 4 3 Ponieważ wartość nie jest równa , kontynuujemy i odczytujemy wartość co daje wynik (zaznaczony na ZIELONO). R[0,4] NO_EDGE R[0,3] 2 Ponownie, ponieważ wartość nie jest , kontynuujemy i odczytujemy wartość co daje wynik (zaznaczony na CZERWONO). R[0,3] NO_EDGE R[0,2] 1 Na koniec odczytujemy wartość , co skutkuje wartością , co oznacza, że nie ma więcej wierzchołków poza i , które przyczyniają się do trasy. Dlatego wynikowa trasa to: , co jeśli spojrzysz na graf, rzeczywiście odpowiada najkrótszej ścieżce od wierzchołka do wierzchołka . R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 Zamyślony czytelnik mógłby zapytać: Jak możemy mieć pewność, że wszystkie dane odczytane z macierzy należą do tej samej ścieżki? R - Czytelnik myślący To bardzo dobre pytanie. Jesteśmy pewni, ponieważ aktualizujemy macierz nową wartością, gdy aktualizujemy wartość najkrótszej ścieżki w macierzy Tak więc ostatecznie każdy wiersz macierzy zawiera dane związane z najkrótszymi ścieżkami. Nic więcej, nic mniej. R W R Teraz, gdy skończyliśmy teorię, czas na wdrożenie. Implementacja w C# W , oprócz zaimplementowania oryginalnej wersji algorytmu Floyda-Warshalla, zintegrowaliśmy także różne optymalizacje: obsługę grafów rzadkich, paralelizmu i wektoryzacji, a na końcu wszystko to połączyliśmy. poprzednim poście Nie ma powodu, aby powtarzać to wszystko dzisiaj. Chciałbym jednak pokazać, jak zintegrować zapamiętywanie tras z oryginalnymi i wektorowymi (z obsługą grafów rozrzedzonych) wersjami algorytmu. Integracja z oryginalnym algorytmem Może trudno w to uwierzyć, ale aby zintegrować zapamiętywanie trasy z oryginalną wersją algorytmu, wystarczy: Rozszerz sygnaturę funkcji, aby uwzględnić macierz jako oddzielny parametr – . R int[] routes Zapisz k w za każdym razem, gdy najkrótsza ścieżka zostanie zmieniona (linie: 2 i 14). routes To wszystko. Tylko półtora wiersza kodu: public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } Integracja z algorytmem wektorowym Integracja z wersją wektorową (obsługującą rzadkie grafy) wymaga nieco więcej wysiłku, jednak kroki koncepcyjne są takie same: Rozszerz sygnaturę funkcji, aby uwzględnić macierz jako oddzielny parametr – . R int[] routes W każdej iteracji zainicjuj nowy wektor wartości (linia: 6). k Zapisz wektor wartości do za każdym razem, gdy zmieni się najkrótsza ścieżka (wiersze: 31-32). k routes Zaktualizuj niewektorowaną część algorytmu w taki sam sposób, w jaki zaktualizowaliśmy oryginalny algorytm (linia: 41). public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } Małe przypomnienie – operacja zwraca nowy wektor, w którym wartości są równe mniejszej z dwóch odpowiadających sobie wartości wektorów wejściowych, tj. jeśli wartość wektora jest równa , operacja wybiera wartość z , w przeciwnym razie wybiera wartość z . Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - Uwaga autora Benchmarking Zbieranie informacji o trasie wydaje się wystarczająco rozsądne, ponieważ… cóż, czemu nie? Zwłaszcza, gdy tak łatwo jest zintegrować je z istniejącymi algorytmami. Zobaczmy jednak, jak praktyczne jest ich domyślne zintegrowanie. Oto dwa zestawy testów porównawczych: z i bez (oba wykonują oryginalne i wektorowe wersje algorytmu). Wszystkie testy porównawcze zostały wykonane przez v0.13.1 (.NET 6.0.4 x64) na komputerze wyposażonym w procesor Intel Core i5-6200U CPU 2.30GHz (Skylake) i działającym w systemie Windows 10. BenchmarkDotNet Wszystkie eksperymenty przeprowadzono na predefiniowanym zestawie grafów użytym w : 300, 600, 1200, 2400 i 4800 wierzchołków. poprzednim poście Kod źródłowy i wykresy eksperymentalne są dostępne w repozytorium na GitHub. Wykresy eksperymentalne można znaleźć w katalogu . pliku Data/Sparse-Graphs.zip Wszystkie testy porównawcze w tym poście są zaimplementowane w APSP02.cs . Poniżej znajdują się wyniki testów porównawczych, w których metody i odpowiadają oryginalnej wersji algorytmu, a metody i odpowiadają wektoryzowanej (z obsługą grafów rzadkich) wersji algorytmu. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes Metoda Rozmiar Średnia (ms) Błąd (ms) Odchylenie standardowe (ms) Linia bazowa 300 40.233 0,0572 0,0477 Linia bazowa z trasami 300 40.349 0,1284 0,1201 SpartialVectorOptimisations 300 4.472 0,0168 0,0140 Częściowe optymalizacje wektorowe z trasami 300 4.517 0,0218 0,0193 Linia bazowa 600 324.637 5.6161 4.6897 Linia bazowa z trasami 600 321.173 1,4339 1.2711 SpartialVectorOptimisations 600 32.133 0,2151 0,1679 Częściowe optymalizacje wektorowe z trasami 600 34.646 0,1286 0,1073 Linia bazowa 1200 2,656.024 6.9640 5.8153 Linia bazowa z trasami 1200 2,657.883 8.8814 7.4164 SpartialVectorOptimisations 1200 361.435 2,5877 2.2940 Częściowe optymalizacje wektorowe z trasami 1200 381.625 3,6975 3.2777 Linia bazowa 2400 21 059,519 38.2291 33.8891 Linia bazowa z trasami 2400 20 954,852 56.4719 50.0609 SpartialVectorOptimisations 2400 3,029.488 12.1528 11.3677 Częściowe optymalizacje wektorowe z trasami 2400 3,079.006 8.6125 7.1918 Linia bazowa 4800 164,869.803 547.6675 427.5828 Linia bazowa z trasami 4800 184,305.980 210.9535 164.6986 SpartialVectorOptimisations 4800 21,882.379 200.2820 177.5448 Częściowe optymalizacje wektorowe z trasami 4800 21,004.612 79.8752 70.8073 Wyniki testów porównawczych nie są proste do zinterpretowania. Jeśli przyjrzysz się bliżej, znajdziesz kombinację, gdy zbieranie tras faktycznie przyspieszyło działanie algorytmu lub nie miało żadnego znaczącego wpływu. Wygląda to bardzo myląco (i jeśli tak jest – zdecydowanie radzę posłuchać tego z i , aby lepiej zrozumieć, jakie trudne rzeczy mogą wpływać na pomiary). Moim zdaniem „mylące” zachowanie jest spowodowane przez świetną wydajność pamięci podręcznej procesora (ponieważ wykresy nie są wystarczająco duże, aby nasycić pamięci podręczne). Częściowo teoria ta opiera się na „ ” próbce, gdzie możemy zobaczyć znaczną degradację na największym wykresie. Jednak jej nie zweryfikowałem. programu Denisem Bakhvalovem Andriejem Akinshinem pogrubionej Ogólnie rzecz biorąc, testy pokazują, że jeśli nie mamy do czynienia ze scenariuszami wymagającymi ekstremalnie wysokiej wydajności i ogromnymi wykresami, to nie ma problemu z domyślnym zintegrowaniem zapamiętywania tras z obydwoma algorytmami (należy jednak pamiętać, że spowoduje to podwojenie zużycia pamięci, ponieważ będziemy musieli przydzielić dwie macierze i zamiast jednej). W R Pozostało jedynie zaimplementowanie algorytmu przebudowy trasy. Implementacja algorytmu przebudowy trasy Implementacja algorytmów przebudowy tras w języku C# jest prosta i niemal całkowicie odzwierciedla wcześniej zaprezentowany pseudokod (do reprezentacji tablicy dynamicznej używamy ): LinkedList<T> public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; } Powyższy algorytm nie jest doskonały i zdecydowanie można go ulepszyć. Najprostszym ulepszeniem, jakie możemy wprowadzić, jest wstępne przydzielenie tablicy o rozmiarze i wypełnienie jej w odwrotnej kolejności: sz public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); } Chociaż ta „optymalizacja” zmniejsza liczbę alokacji do jednej, niekoniecznie sprawia, że algorytm jest „szybszy” lub „alokuje mniej pamięci” niż poprzedni. Chodzi o to, że jeśli potrzebujemy trasy uporządkowanej od do , zawsze będziemy musieli „odwrócić” dane pobierane z macierzy i nie ma sposobu, aby tego uniknąć. i j R Jeśli jednak możemy przedstawić dane w odwrotnej kolejności, możemy wykorzystać LINQ i uniknąć niepotrzebnych alokacji: public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; } Istnieje wiele wariantów tego, jak ten kod może zostać „zmieniony” lub „ulepszony”. Ważne jest, aby pamiętać, że każda „zmiana” ma swoje wady pod względem pamięci lub cykli procesora. Eksperymentuj swobodnie! Możliwości są niemal nieograniczone! Implementacje wszystkich algorytmów trasowania można znaleźć w pliku na platformie GitHub Routes.cs . Wniosek W tym poście zagłębiliśmy się w teorię algorytmu Floyda-Warshalla i rozszerzyliśmy ją o możliwość zapamiętywania najkrótszych ścieżek „tras”. Następnie zaktualizowaliśmy implementacje C# (oryginalne i wektorowe) z . Na koniec zaimplementowaliśmy kilka wersji algorytmu, aby przebudować „trasy”. poprzedniego posta Wiele powtórzyliśmy, ale jednocześnie mam nadzieję, że znalazłeś coś nowego i interesującego w tym. To nie koniec problemu najkrótszych ścieżek dla wszystkich par. To dopiero początek. Mam nadzieję, że lektura przypadła Ci do gustu. Do zobaczenia następnym razem!
