Algoritmo di Dijkstra: consumo di memoria

Question

Ho un'implementazione dell'algoritmo di Dijkstra, basato sul codice this website. Fondamentalmente, ho un numero di nodi (diciamo 10000) e ogni nodo può avere da 1 a 3 connessioni ad altri nodi.

I nodi vengono generati in modo casuale all'interno di uno spazio 3d. Anche le connessioni vengono generate casualmente, tuttavia cerca sempre di trovare le connessioni con i vicini più vicini e aumenta lentamente il raggio di ricerca. Ad ogni connessione viene data una distanza di uno. (Dubito che ciò sia importante ma è solo uno sfondo).

In questo caso, l'algoritmo viene utilizzato per trovare il numero più breve di hop dal punto di partenza a tutti gli altri nodi. E funziona bene per 10.000 nodi. Il problema che ho è che, man mano che il numero di nodi aumenta, diciamo verso 2 milioni, uso tutta la memoria del mio computer quando provo a costruire il grafico.

Qualcuno sa di un modo alternativo di implementare l'algoritmo per ridurre l'impronta di memoria, oppure c'è un altro algoritmo là fuori che utilizza meno memoria?

Answer 1

In base al tuo commento sopra, stai rappresentando i bordi del grafico con un distance matrixlong dist[GRAPHSIZE][GRAPHSIZE]. Ciò richiederà la memoria O(n^2), che è troppo per valori elevati di n. Inoltre, non è una buona rappresentazione in termini di tempo di esecuzione quando si ha solo un piccolo numero di spigoli: ciò farà sì che l'algoritmo di Dijkstra prenda il tempo O(n^2) (dove n è il numero di nodi) quando potrebbe potenzialmente essere più veloce, a seconda del strutture dati utilizzate.

Poiché nel tuo caso hai detto che ogni nodo è connesso solo a un massimo di altri 3 nodi, non dovresti usare questa matrice: invece, per ogni nodo dovresti memorizzare un elenco dei nodi a cui è collegato. Poi, quando vuoi andare sui vicini di un nodo, devi solo scorrere questa lista.

In alcuni casi specifici non è nemmeno necessario memorizzare questo elenco perché può essere calcolato per ciascun nodo quando necessario. Ad esempio, quando il grafico è una griglia e ogni nodo è connesso ai nodi della griglia adiacenti, è facile trovare al volo i vicini di un nodo.

Answer 2

Se davvero non può permettersi di memoria, anche con minimizzazioni sul tuo rappresentazione grafica, si può sviluppare una variazione algoritmo di Dijkstra, considerando un divide et impera metodo.

L'idea è di dividere i dati in blocchi di piccole dimensioni, in modo da poter eseguire l'algoritmo di Dijkstra in ogni blocco, per ciascuno dei punti al suo interno.

Per ciascuna soluzione generata in questi blocchi secondari, considerarla come un nodo univoco per un altro blocco di dati, da cui si avvierà un'altra esecuzione di Dijkstra.

Ad esempio, considerare i seguenti punti:

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

È possibile selezionare i punti più vicini ad un dato nodo, per esempio, all'interno di due hop, e quindi utilizzare la soluzione come parte del grafico esteso, considerando la punti precedenti come un solo insieme di punti, con una distanza pari alla distanza risultante della soluzione Dijkstra.

Dire che si avvia da D:

• selezionare il closest points a D entro un determinato number of hops;
• utilizza l'algoritmo di Dijkstra sulle voci selezionate, a partire da D;
• utilizzare la soluzione come grafico con il nodo centrale D e gli ultimi nodi nei percorsi più brevi come nodi direttamente collegati a D;
• estendere il grafico, ripetendo l'algoritmo fino a quando tutti i nodi sono stati considerati.

Anche se c'è una costosa elaborazione aggiuntivaqui, devi essere in grado di sorpassare limitazione di memoria, e, se si dispone di alcune altre macchine, si può anche distribuire i processi.

Si prega di notare che questa è solo l'idea del processo, il processo che ho descritto non è necessariamente il modo migliore per farlo. Potresti trovare qualcosa di interessante alla ricerca dell'algoritmo distribuito da Dijkstra.

Answer 3

Mi piace aumentare: grafico molto. Il consumo di memoria è molto buono (l'ho usato su reti stradali con 10 milioni di nodi e 2 GB di RAM).

Esso dispone di un'implementazione Dijkstra, ma se l'obiettivo è quello di implementare e capire da soli, è comunque possibile utilizzare la loro rappresentazione grafica (suggerisco lista di adiacenza) e confrontare il risultato con loro per essere sicuri che il risultato è corretto.

Alcune persone hanno menzionato altri algoritmi. Non penso che questo giocherà un ruolo importante sull'utilizzo della memoria, ma più probabilmente nella velocità. 2M nodi, se la topologia è vicina a una rete stradale, il tempo di esecuzione sarà inferiore a un secondo da un nodo a tutti gli altri.

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