Algorytm Dijkstry na wielkich wykresach

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ć.

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, ...)

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.

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.

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ł.