Pobieranie najkrótszej ścieżki dynamicznego wykresu

24

Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki podczas wykonywania programu. Próbuję znaleźć skuteczny algorytm do aktualizowania najkrótszych ścieżek z wierzchołka do każdego innego wierzchołka , po wstawieniu krawędzi , bez potrzeby ponownego uruchamiania algorytmu najkrótszej ścieżki na nowym wykresie. W jaki sposób mogę to zrobić? Z góry dziękuję.u evue

  • Uwaga: zmiany można wprowadzić po pierwszej iteracji algorytmu
  • Uwaga [2]: dwa węzły są podane, źródłem i cel. Muszę znaleźć najkrótszą ścieżkę między tymi węzłami. Gdy wykres jest aktualizowany, że wystarczy zaktualizować , która jest najkrótsza droga między i .t π ( s , t ) s tstπ(s,t)st
  • Uwaga [3]: Interesuje mnie tylko obudowa wstawiania krawędzi.

Formalna definicja : biorąc pod uwagę wykres . Zdefiniowania operacji aktualizacji , jak 1) wstawienie krawędzi do lub 2) aa delecji krawędzi z . Celem jest skuteczne znalezienie kosztu wszystkich par najkrótszych ścieżek po operacji aktualizacji. Przez efektywnie rozumiemy co najmniej lepsze niż wykonywanie algorytmu All-Pairs-Shortest-Path, takiego jak algorytm Bellman-Ford, po każdej operacji aktualizacji.G=(V,E)E e EeEeE


Edycja: Poniżej znajduje się uproszczona wersja problemu:

Podano wykres ważony , składający się z jednokierunkowych krawędzi i dwóch krytycznych wierzchołków i . Podany jest również zestaw kandydujących krawędzi dwukierunkowych . Muszę zbudować krawędź aby zminimalizować odległość od do .s t CG(V,E)stCs t(u,v)Cst

Rontogiannis Aristofanis
źródło
Więcej pytań wyjaśniających: czy punkty końcowe twojej ścieżki pozostają stałe za każdym razem? Czy interesuje Cię tylko przypadek wstawiania krawędzi lub dowolne zmiany na wykresie? Sądzę, że istnieją badania, które odpowiadają na twoje pytanie, ale niestety tak naprawdę nie wiem, gdzie szukać. Szybkie wyszukiwanie w Google pokazuje te slajdy, które wydają się bardzo pomocne, i ten artykuł: „najkrótsze ścieżki na dynamicznych wykresach” (mam nadzieję, że link zadziała). (u,v)
usul

Odpowiedzi:

14

Problem, który prawdopodobnie zauważyłeś, jest dość trudnym problemem. Sprawdzanie sieci doprowadzi do skomplikowanych przypadków, które prawdopodobnie nie będą potrzebne. Oto rozwiązanie - zgodnie z wymaganiami (tzn. Nie trzeba ponownie obliczać wszystkiego od zera).

w przypadku dodania krawędzi - a następnie przy użyciu już wbudowanej macierzy odległości - wykonaj następujące czynności:(u,v)

Dla każdej pary węzłów i y sprawdzenie, czy d ( ( x , u ) ) + C ( ( u , v ) ) + d ( ( V , y ) ) < d ( ( x , y ) ) - można to zrobić w O ( n 2 ), ponieważ porównujesz każdą parę węzłów.xyd((x,u))+c((u,v))+d((v,y))<d((x,y))O(n2)

W przypadku usuwania krawędzi: Biorąc pod uwagę już zbudowaną macierz odległości, możesz mieć dla każdego węzła drzewa najkrótszej ścieżki zrootowanego u . Jeśli usuniętej krawędzi e nie ma w tym drzewie, nie ma to wpływu na najkrótsze ścieżki od u do siebie - (pozostają takie same).uueu

euvπ(u,v)euv

jeśli chcesz mieć lepsze wyniki niż to, spójrz na:

  1. Demetrescu, Camil i Giuseppe F. Italiano. „Nowe podejście do dynamicznej wszystkich par najkrótszych ścieżek”. Journal of the ACM (JACM) 51.6 (2004): 968-992. (można znaleźć za darmo od Google)

  2. lub spójrz na tę ładnie napisaną ankietę

AJed
źródło
17

Problem, o który prosisz, to dobrze znane problemy algorytmiczne. W rzeczywistości wciąż jest otwarte, jak trudny jest ten problem. Powinieneś także wiedzieć, że istnieją różne wcielenia tego problemu. W przeciwieństwie do tego, o co prosisz, zwykle zwracane są tylko odległości, podczas gdy pytasz o rzeczywiste najkrótsze ścieżki. Zauważ, że ścieżki te mogą być już bardzo długie. Dynamiczne algorytmy graficzne rozróżniają tylko usuwanie krawędzi (algorytmy malejące dg), tylko wstawianie krawędzi (przyrostowe algorytmy dg) oraz wstawianie i usuwanie krawędzi (w pełni dynamiczne algorytmy dg). Dlatego interesują Cię algorytmy przyrostowe .

O(n2(logn+log2(1+m/n))O(1)O(nlogn)krawędzi, możesz po prostu przeliczyć od zera za pomocą stosów Dijkstry i Fibonacciego i uzyskać taki sam czas działania, jak w algorytmie Thorupa. Więc jeśli twoje wykresy nie są zbyt gęste, polecam użycie Dijkstra.

Nie znam żadnego lepszego algorytmu przyrostowego . Ale powinieneś przeszukać sieć, jeśli istnieją nowsze wyniki dla tego specjalistycznego problemu.

A.Schulz
źródło
(s,t)
@RondogiannisAristophanes w rzeczywistości to, co dotychczas zaproponowano, jest jakoś najlepsze. Spójrz na ten artykuł, który twierdzi, że: „przyrostowe i malejące problemy z najkrótszymi ścieżkami z jednego źródła, dla ważonych grafów skierowanych lub niekierowanych, są w silnym sensie co najmniej tak trudne, jak statyczne wszystkie pary najkrótszych ścieżek problem." (szczerze mówiąc, przeczytałem tylko wprowadzenie) - odniesienie: „Problemy z dynamicznymi najkrótszymi ścieżkami”, Roditty & Zwick - ale czy mógłbyś nam powiedzieć, jaki dokładnie masz problem? jaki konkretny scenariusz? co do tej pory nie zrobiłeś? - może pomożemy ci lepiej.
AJed
@RondogiannisAristophanes im lepsza wydajność, tym trudniej jest ją wdrożyć (w większości przypadków), a czasami w praktycznych zastosowaniach nie potrzebujesz aż tak dużej poprawy wydajności.
AJed
@AJed Zredagowałem swój post, aby uwzględnić uproszczony opis problemu.
Rontogiannis Aristofanis,
5

Uważam, że algorytm AD * może ci pomóc.

http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf

Po otrzymaniu zaktualizowanych informacji dotyczących podstawowego wykresu algorytm przyrostowo naprawia poprzednie rozwiązanie. Rezultatem jest podejście łączące zalety planistów w dowolnym czasie i przyrostowych, aby zapewnić skuteczne rozwiązania złożonych, dynamicznych problemów wyszukiwania

Najważniejsze informacje o AD *: „W każdej chwili”, co oznacza, że ​​może bardzo szybko zapewnić „nieoptymalne rozwiązanie”, choć może nie być najlepsze. Jednak mając wystarczająco dużo czasu, zwróci optymalne rozwiązanie. Ponadto można ograniczyć nieoptymalne rozwiązanie, aby nie było gorsze niż optymalne rozwiązanie przez jakąś stałą zdefiniowaną przez użytkownika. Daje to możliwość wykorzystania tego w scenariuszu planowania w czasie rzeczywistym, w którym posiadanie dobrego rozwiązania (gdzie teoretycznie „dobre” jest ograniczone) jest lepsze niż brak rozwiązania.

http://www.cs.cmu.edu/~maxim/software.html

zwycięzca
źródło