Teoretyczne informatyka shortest-path

6

Czym różnią się najnowocześniejsze algorytmy wyszukiwania ścieżek do zmiany wykresów (D *, D * -Lite, LPA * itd.)?

W ostatnich latach opracowano wiele algorytmów wyszukiwania ścieżek, które potrafią obliczyć najlepszą ścieżkę w odpowiedzi na zmiany wykresu znacznie szybciej niż A * - czym one są i czym się różnią? Czy są w różnych sytuacjach, czy też niektóre są przestarzałe? Oto te, które do tej pory udało mi się …

96 ds.algorithms shortest-path

1

Znalezienie najkrótszej ścieżki w obecności cykli ujemnych

Biorąc pod uwagę ukierunkowany wykres cykliczny, na którym ciężar każdej krawędzi może być ujemny, koncepcja „najkrótszej ścieżki” ma sens tylko wtedy, gdy nie ma żadnych cykli ujemnych, iw takim przypadku można zastosować algorytm Bellmana-Forda. Jestem jednak zainteresowany znalezieniem najkrótszej ścieżki między dwoma wierzchołkami, która nie wymaga cyklizacji (tj. Pod warunkiem, …

13 ds.algorithms graph-algorithms shortest-path

3

Podgraf zawierający wszystkie węzły i krawędzie, które są częścią prostych ścieżek st o ograniczonej długości na niekierowanym wykresie

Całkiem podobne do mojego wcześniejszego pytania . Tym razem jednak wykres nie jest przekierowany. Dany Nieukierunkowane wykres solGG bez wielu krawędzie lub pętli Źródło wierzchołek sss , Docelowy wierzchołek ttt , Maksymalna długość ścieżki lll , Szukam sol′G′G' - podgraf solGG który zawiera dowolny wierzchołek i dowolną krawędź w solGG …

12 ds.algorithms graph-algorithms shortest-path

1

Identyfikacja bezużytecznych krawędzi dla najkrótszej ścieżki

Rozważmy wykres (problem ma sens zarówno dla wykresów skierowanych, jak i niekierowanych). Nazwij macierzą odległości : to najkrótsza odległość ścieżki od wierzchołka do wierzchołka w dla pewnej stałej funkcji agregacji (na przykład lub ).M G G M G [ i , j ] i j G + maxsolGGM.solMGM_GsolGGM.sol[ i , …

11 ds.algorithms reference-request graph-algorithms shortest-path

2

Klasy wykresów, dla których można obliczyć średnicę w czasie liniowym

Przypomnijmy, średnica grafu oznacza długość najdłuższego najkrótszej ścieżce G . Biorąc pod uwagę wykres, oczywisty algorytm obliczania diam ( G ) rozwiązuje problem wszystkich par najkrótszej ścieżki (APSP) i zwraca długość najdłuższej znalezionej ścieżki.solGGsolGGśrednica ( G )diam(G)\text{diam}(G) Wiadomo, że problem APSP można rozwiązać w optymalnym czasie dla kilku klas grafów. …

11 graph-theory graph-algorithms shortest-path

3

Problem najkrótszej odległości z długością jako funkcją czasu

Motywacja Pewnego dnia podróżowałem po mieście środkami transportu publicznego i stworzyłem interesujący problem graficzny, modelujący problem znalezienia najkrótszego połączenia między dwoma miejscami. Wszyscy znamy klasyczny „problem najkrótszej ścieżki”: biorąc pod uwagę ukierunkowany wykres o długości krawędzi i dwóch wierzchołkach , znalezienie najkrótszej ścieżki pomiędzy i (to znaczy ścieżka minimalizację całkowitej …

10 graph-algorithms shortest-path

Pytania otagowane jako shortest-path