Algorytm Dijkstry: zużycie pamięci

Question

Mam implementację algorytmu Dijkstry opartą na kodzie pod numerem this website. Zasadniczo mam liczbę węzłów (powiedzmy 10000), a każdy węzeł może mieć od 1 do 3 połączeń z innymi węzłami.

Węzły są generowane losowo w przestrzeni 3d. Połączenia są generowane losowo, jednak zawsze najpierw szukają połączeń z najbliższymi sąsiadami i powoli zwiększają zasięg wyszukiwania. Każde połączenie ma odległość równą jeden. (Wątpię, żeby to wszystko miało znaczenie, ale to tylko tło).

W tym przypadku algorytm jest używany do znajdowania najkrótszej liczby przeskoków od punktu początkowego do wszystkich innych węzłów. I działa dobrze na 10 000 węzłów. Problem w tym, że wraz ze wzrostem liczby węzłów, powiedzmy do 2 milionów, wykorzystuję pamięć wszystkich moich komputerów podczas próby zbudowania wykresu.

Czy ktoś wie o alternatywnym sposobie implementacji algorytmu w celu zmniejszenia śladu pamięci, czy istnieje inny algorytm wykorzystujący mniej pamięci?

Answer 1

Zgodnie z powyższym komentarzem reprezentujesz krawędzie wykresu za pomocą distance matrixlong dist[GRAPHSIZE][GRAPHSIZE]. Zajmie to pamięć O(n^2), która jest zbyt duża dla dużych wartości n. Nie jest to również dobra reprezentacja pod względem czasu wykonania, gdy masz tylko niewielką liczbę krawędzi: spowoduje to, że algorytm Dijkstry przyjmie czas O(n^2) (gdzie n jest liczbą węzłów), kiedy może potencjalnie być szybszy, w zależności od używane struktury danych.

Ponieważ w twoim przypadku powiedziałeś, że każdy węzeł jest podłączony tylko do 3 innych węzłów, nie powinieneś używać tej macierzy: Zamiast tego, dla każdego węzła powinieneś przechowywać listę węzłów, z którymi jest połączony. Następnie, gdy chcesz przejść przez sąsiadów węzła, musisz po prostu powtórzyć tę listę.

W niektórych szczególnych przypadkach nie trzeba nawet przechowywać tej listy, ponieważ w razie potrzeby można ją obliczyć dla każdego węzła. Na przykład, gdy wykres jest siatką, a każdy węzeł jest połączony z sąsiednimi węzłami sieci, łatwo jest znaleźć sąsiadów węzła w locie.

Answer 2

Jeśli naprawdę nie może sobie pozwolić na pamięć, nawet z minimalizacji dla zmniejszenia o swojej reprezentacji grafów, można opracować odmianę algorytmu Dijkstry, rozważa dziel i rządź metody.

Pomysł polega na podzieleniu danych na drobne fragmenty, dzięki czemu będziesz mógł wykonać algorytm Dijkstry w każdym kawałku, dla każdego z punktów w nim.

Dla każdego rozwiązania wygenerowanego w tych mniejszych porcjach, należy traktować go jako unikalny węzeł do innej porcji danych, z której rozpocznie się kolejne wykonanie Dijkstra.

Na przykład, rozważmy punkty poniżej:

.B  .C 
        .E 
.A   .D 
     .F     .G 

Można wybrać najbliższe punkty do danego węzła, powiedzmy, w ciągu dwóch chmielu, a następnie użyć roztworu jako część wykresu rozszerzonego, biorąc pod uwagę poprzednie punkty to tylko jeden zestaw punktów, z odległością równą wynikowi odległości rozwiązania Dijkstra.

Say zacząć od D:

• wybrać closest points do D obrębie danego number of hops;
• użyj algorytmu Dijkstry dla wybranych wpisów, zaczynając od D;
• użyj rozwiązania jako wykres z węzłem centralnym D i ostatnimi węzłami na najkrótszych ścieżkach jako węzły bezpośrednio połączone z D;
• przedłużyć wykres, powtarzając algorytm, aż wszystkie węzły zostaną rozpatrzone.

Chociaż istnieje kosztowne dodatkowe przetwarzanie tutaj, byłbyś w stanie przewyższać ograniczenie pamięci, a jeśli masz jakieś inne maszyny, można nawet rozpowszechniać procesy.

Proszę pamiętać, że to tylko idea procesu, proces, który opisałem, niekoniecznie jest najlepszym sposobem na zrobienie tego. Możesz znaleźć coś interesującego szukając rozproszonego algorytmu Dijkstry.

Answer 3

Bardzo lubię boost :: graph. Zużycie pamięci jest bardzo przyzwoite (użyłem go w sieci drogowej z 10 milionami węzłów i 2GB pamięci RAM).

Ma implementację Dijkstry, ale jeśli celem jest samodzielne zaimplementowanie i zrozumienie, możesz nadal używać reprezentacji wykresu (sugeruję listę przyległości) i porównywać wyniki z ich wynikami, aby mieć pewność, że wynik jest poprawny.

Niektórzy wspominali o innych algorytmach. Nie sądzę, że będzie to odgrywać dużą rolę w wykorzystaniu pamięci, ale raczej w szybkości. 2M węzłów, jeśli topologia jest zbliżona do sieci ulicznej, czas działania będzie krótszy niż sekunda od jednego węzła do wszystkich innych.

http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/index.html