Pobieranie najkrótszej ścieżki dynamicznego wykresu

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 $v$$u$$e$

• 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 $s$$t$$\pi(s,t)$$s$$t$
• 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 $e$$E$$e$$E$

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 $G(V,E)$$s$$t$$C$s $(u,v) \in C$$s$$t$

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.$x$$y$$d((x,u)) + c((u,v)) + d((v,y)) < d((x,y))$$O(n^2)$

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).$u$$u$$e$$u$

$e$$u$$v$$\pi(u,v)$$e$$u$$v$

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ę

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(n^2(\log n +\log^2 (1+m/n))$$O(1)$$O(n\log n)$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.

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