Algorytm Dijkstry na wielkich wykresach

15

Bardzo dobrze znam Dijkstrę i mam konkretne pytanie dotyczące algorytmu. Jeśli mam ogromny wykres, na przykład 3,5 miliarda węzłów (wszystkie dane OpenStreetMap), to oczywiście nie byłbym w stanie mieć wykresu w pamięci, więc wykres jest przechowywany na dysku w bazie danych.

Dostępne są biblioteki do obliczania najkrótszych ścieżek na takich wykresach. Jak oni to robią? Mówiąc dokładniej, w jaki sposób ładują wymaganą część wykresu, aby uruchomić algorytm Dijkstry?

Pobieranie listy przyległości każdego odwiedzonego wierzchołka wymagałoby około 1500 zapytań do bazy danych na 10 000 węzłów zgodnie z moimi danymi statystycznymi, więc najwyraźniej tak nie jest. To byłoby zbyt wolne.

Jak oni to robią? Sam próbuję to wdrożyć.

dimitris93
źródło
2
Czy na pewno używają Dijkstra? Istnieje wiele innych algorytmów najkrótszej ścieżki, które mogą być lepiej dostosowane do opisywanej sytuacji.
David Richerby
1
Zajrzałeś do kodu? Skąd mamy wiedzieć? „zapytania do bazy danych” - mam nadzieję, że nie używasz DBMS do przechowywania wykresów?
Raphael
@DavidRicherby tak jestem pewien, spójrz na ten link
dimitris93
2
„Byłoby niezwykle żmudnym procesem patrzeć na czysty kod C.” Ale to jedyny sposób, aby wiedzieć, co robi kod. Więc po prostu prosisz nas o wykonanie dla Ciebie żmudnego zadania, które nie jest najlepszą reklamą dla twojego pytania ...
nudnego David Richerby
1
@Shiro Wyraźnie pytacie: „Jak oni to robią?” Jeśli tak naprawdę nie chcesz zadać pytania, musisz je ponownie sformułować.
Raphael

Odpowiedzi:

6

Dostępne są biblioteki do obliczania najkrótszych ścieżek na takich wykresach. Jak oni to robią? Mówiąc dokładniej, w jaki sposób ładują wymaganą część wykresu, aby uruchomić algorytm Dijkstry?

Możesz użyć DB, niestandardowego formatu pliku do odczytu z płyty oraz ustawienia w pamięci.

Z mojego doświadczenia wynika, że ​​korzystanie z bazy danych jest około 5 do 10 razy wolniejsze i wymaga dużo więcej pamięci niż pisanie własnego formatu pliku na podstawie „prostego” formatu listy linków.

Dobrą rzeczą jest to, że istnieje kilka platform programowych korzystających z OSM, które są open source, więc możesz zajrzeć bezpośrednio do kodu, np. Zobaczyć tutaj . W silniku routingu GraphHopper typu open source bardzo łatwo jest zmienić ustawienie mapowane w pamięci (oparte na dyskach) na ustawienie w pamięci - oba w tym samym formacie. Ustawienie „mmap” pozwala nawet na użycie urządzeń mobilnych z ograniczoną pamięcią, a ta ostatnia działa znacznie szybciej, jeśli masz niezbędną pamięć RAM, np. Na serwerze. Np. W przypadku wykresu ogólnoświatowego (> 100 milionów węzłów) potrzebujesz około 8-10 GB pamięci RAM, a także dużo więcej pamięci RAM, jeśli chcesz przyspieszyć wszystko, np. Dzięki Hierarchii Skurczów - około 5-8 GB więcej na każdy pojazd, który chcesz.

Format jest bardzo uproszczony i w zasadzie przechowuje tylko potrzebne dane z kilkoma sztuczkami, aby uczynić go kompaktowym. Przeczytaj więcej na ten temat tutaj . Oświadczenie: Jestem autorem GraphHopper.

W odniesieniu do innych odpowiedzi:

Algorytm Dijkstras, gdy ma zastosowanie, jest uważany za nieoptymalny dla tego problemu

„Normalna” Dijkstra może wykonywać bardzo rozsądne (<1s w przypadku zapytań ogólnokrajowych, takich jak przykład 3 mln węzłów) i jest optymalna w „sensie teoretycznym”, ale potrzebuje nieco dostrojenia, aby szybko uzyskać scenariusze produkcyjne. A techniki takie jak Hierachie skurczów wykorzystują dwukierunkową modyfikację i działają bardzo dobrze.

sieci drogowe są hierarchiczne i płaskie.

sieci drogowe są zhierarchizowane tylko dla samochodu i nie są płaskie (mosty, tunele, ...)

Karussell
źródło
Mam jeszcze jedno pytanie. Jak znaleźć NodeIDnajbliższy węzeł z latitude/longitude? Jest to wymagane do obliczenia najkrótszej ścieżki A-> B. Musimy również pamiętać, że A i B mogą nie istnieć jako węzły, ponieważ nie każdy metr kwadratowy zawiera węzeł. Musimy więc znaleźć 2 najbliższe NodeID A i B.
dimitris93
Odbywa się to w LocationIndexTree, który jest rodzajem kwadratu skutecznie przechowującego NodeID w komórce, która ma na przykład dla GraphHopper promień ~ 500m. Jeśli nic nie zostanie znalezione, powiększy promień do pewnego stopnia. W teorii brzmi to prosto, ale jest bardzo złożone, ponieważ możesz mieć krawędzie przecinające ten obszar, musisz być wydajny podczas tworzenia i wysyłania zapytań i wiele więcej.
Karussell
Czy drzewa KD nie są bardziej wydajne podczas wyszukiwania najbliższego sąsiada? Dlaczego wybrałeś QuadTrees zamiast KD-Trees? W tej chwili wdrażam KD-Trees dla mojego silnika routingu. Zacząłem wdrażać QuadTrees, ale przestałem, ponieważ doszedłem do wniosku, że KD-Trees to to samo, ale łatwiejsze do kodowania i szybsze zapytania do najbliższego sąsiada. Czy się mylę ?
dimitris93
Podczas korzystania z czworokątów nie ma potrzeby jawnego przechowywania obwiedni, co daje przewagę pamięci, co było bardziej krytyczne dla mojego przypadku użycia (również uważam, że kwadraty są łatwiejsze;)). Szybkość zapytania nie stanowi problemu. W rzeczywistości ktoś studiował takie próby i przewyższał wszelkie inne wdrożenia, w tym. Drzewa KD, ale zakładam, że wszystko zależy od konkretnej implementacji ...
Karussell
Jeśli spojrzysz na stronę 9 tego pliku pdf ze Stanford, wyszukiwanie najbliższego sąsiada w KD-Trees nie wymaga wcale znajomości obwiedni. Inną rzeczą jest to, że ponieważ znamy wszystkie punkty wcześniej, możemy stworzyć zrównoważone drzewo o wysokości kłody. Czy nadal masz pewność, że drzewa czworokątne mają jakąkolwiek przewagę nad drzewami KD?
dimitris93
2

Nie musisz umieszczać wszystkich krawędzi sąsiadujących w kolejce priorytetowej. „Połóż” na algorytmie Dijkstry i nadaj mu tylko najkrótszy wierzchołek, v, incydent na wierzchołku, powiedzmy w, ściągnięty ze stosu. Następnie, gdy v zostanie wyciągnięte z kolejki, powiesz „ups”, popełniłem błąd i powinienem dać ci ten wierzchołek, który jest najbliższy wierzchołkowi w. Łatwo zauważyć, że w ten sposób będziesz mieć właściwe rozwiązanie, a rozmiar kolejki zostanie znacznie zredukowany do jednego wierzchołka zdarzenia zamiast do wielu. Musisz jednak śledzić przypadki, aby zawsze podawać najbliższy wierzchołek - gdy jest to wymagane. Jeden z komentarzy twierdził, że sieci dróg są płaskie, co jest niepoprawne. W rzeczywistości badania wykazały, że są one wysoce niepłaskie. Pomyśl o wszystkich autostradach przechodzących przez mosty przez miasto, co powoduje wiele niepłaszczyzn.

użytkownik49040
źródło
0

Algorytm Dijkstras, gdy ma zastosowanie, jest uważany za nieoptymalny dla tego problemu, chociaż bardziej wydajne warianty można uznać za „podobne”. istnieją różne uproszczenia. sieci drogowe są hierarchiczne i płaskie . oto podstawowe podejścia. obszar ten jest ogólnie znany jako „planowanie trasy w sieciach drogowych”.

  • strukturę wykresu można „skompilować” na podstawie danych listy sąsiadów. takie podejście w bibliotece, którą cytujesz , SpatiaLite. te struktury wykresów są przechowywane w skompresowanym formacie binarnym, w którym lokalizacje wykresu są reprezentowane przez liczby całkowite kodowane binarnie itp., więc reprezentacja wykresu i manipulacja zajmuje znacznie mniej miejsca niż przechowywanie wszystkich nazw dróg itp .; wygląda na to, że algorytm SpatiaLite nie jest „online” i działa całkowicie w pamięci.

  • istnieją równoległe / rozproszone algorytmy. patrz np. skalowalny wykres GPU Traversal / Merrill, Garland, Grimshaw.

  • pytanie wykorzystuje terminologię klient-serwer, tj. „zapytania”. algorytmy nie uruchamiają się przez „odpytywanie” bazy danych w sensie klient-serwer. języki zapytań wyższego poziomu, takie jak SQL, są interfejsem do bazy danych i mogą być używane do przesyłania żądania obliczenia minimalnych tras, ale nie są używane przez algorytm wewnętrznie. ogólnie algorytm działa „w bazie danych”, tj. całkowicie „po stronie serwera”. dlatego pisanie algorytmu najkrótszej ścieżki w zapytaniach do bazy danych jest wykonalne w małych sieciach, ale nie w średnich / dużych.

  • istnieje inne podejście, w którym szacunki w niewielkich procentach mogą być dopuszczalne. podstawową ideą jest utrzymanie indeksu odległości między węzłami. patrz np. Szybkie i dokładne oszacowanie najkrótszych ścieżek na dużych wykresach / Gubiczew, Bedathur, Seufert, Weikum

  • ta (235p!) praca doktorska jest szczególnie przydatna. Planowanie trasy w sieciach drogowych / Schultes

  • niektóre algorytmy wykorzystują wiele z tych pomysłów, a inne są wysoce zestrojone i zastrzeżone oraz ograniczają konkurencyjne tajemnice handlowe. np. Google. na ten temat mogą znajdować się mylące media. np . prosty, elegancki algorytm, który umożliwia korzystanie z Google Maps, który twierdzi / sugeruje, że Google używa algorytmu Dijkstras bez żadnego cytowania.

vzn
źródło
1
Mapy Google z pewnością zostały uaktualnione do czegoś lepszego niż Dijskstra. Każdy w połowie kompetentny programista używałby A * do map drogowych, ale podczas mojej poprzedniej pracy dowiedzieliśmy się, że silnik Google może przebudować 2500 km tras przez punkt trasy w <100 ms. To jest zbyt szybkie jak na A *, więc jest prawdopodobne, że używają czegoś takiego jak ArcFlags.
MSalters
Odpowiedź Karussella podważa to zdanie wstępne „Algorytm Dijkstrasa, gdy ma zastosowanie, jest uważany za nieoptymalny dla tego problemu”, co, jak się nie spodziewało, będzie kontrowersyjne. istnieje bardzo silne poparcie dla twierdzenia w tezie Schultesa (wcześnie), która jest również bardzo obszernym / ostatnim badaniem tego obszaru, a także wyjaśnia „przybliżenia” hierarchiczne i planarne. niestety wydaje się, że w otwartej literaturze na temat wyszukiwania pobieżnego nie ma wskazań na temat rzeczywistych algorytmów Google.
vzn
-2

W przypadku bardzo dużych zestawów danych, aby uzyskać tak szybkie wyniki, najlepiej jest użyć struktury danych znajdowania związku z kompresją ścieżki. Jeśli jednak chcesz użyć i zoptymalizować algorytm Djikstry, sprowadza się to do tego, jakie informacje ma każdy węzeł na wykresie. Najprawdopodobniej nie musisz wykonywać wszystkich 1500 zapytań.

Rozważmy na przykład następujący przykład. Powiedzmy, że próbuję znaleźć stopnie separacji między dowolnymi 2 aktorami (liczba Bacona) i chcę znaleźć ścieżkę o najmniejszej wadze (ścieżka z wykorzystaniem najnowszych filmów). Powiedzmy, że mam funkcję o nazwie shortestPath(actor A, actor B);. Rozważ następujący scenariusz.

Jeśli aktor A działa od 1970 r., A aktor B działa od 2000 r., To biorąc pod uwagę te informacje, logiczniej byłoby znaleźć ścieżkę zaczynającą się od pierwszego filmu aktora B, a następnie przemierzając drogę do aktora A. w przeciwieństwie do powtarzania każdego filmu, w którym występował Aktor A.

Zatem głównym punktem jest to, że optymalizacja algorytmu Djikstry naprawdę zależy od tego, jaki jest twój zestaw danych. Musisz podać więcej informacji na temat tego, co pociąga za sobą Twój zestaw danych, aby pomóc Ci zoptymalizować algorytm.

EDYCJA: Powiedzmy, że próbujesz znaleźć najkrótszą drogę między 2 miastami w tym samym kraju, a jeśli ten kraj jest dłuższy niż szerszy, na przykład Argentyna, możesz wykonać zapytania w oparciu o długość i szerokość geograficzną krajów Granic. Następnie możesz zacząć przechodzić w pionie (przy użyciu długości geograficznej), a nie w poziomie. Oczywiście musiałaby być obsługiwana wyjątek, ale masz ogólny pomysł.

Jonathan
źródło
1
Jak korzystać z Union-Find w Dijkstra?
Raphael
Dane to dane przestrzenne, szerokość i długość geograficzna. Myślałem, że to jasne.
dimitris93