Ridurre al minimo l'utilizzo della memoria di una ricerca in ampiezza

Question

Nel mio codice seguente, sto attraversando un grafico attraverso breadth first search. Il codice costruisce il grafico mentre sta attraversando. Questo è un grafico di grandi dimensioni, con un ventilatore su 12. A causa di questo, ogni volta che la profondità delle aumenta breadth first search, voglio distruggere lo strato sopra di esso in un tentativo di minimizzare l'utilizzo della memoria. Come potrei progettare un algoritmo di farlo?

string Node::bfs(Node * rootNode) {
QQueue<Cube *> q;
q.enqueue(rootNode);

while (!(q.empty())) {
    Node * currNode = q.dequeue();
    currNode->constructChildren();
    foreach (Node * child, currNode->getListOfChildren()) {
        q.enqueue(child);
    }
    if (currNode->isGoalNode()) {
        return currNode->path;
    }
}

Answer 1

Con la costante fanout e assumendo un albero-come grafico, il numero di nodi che sono stati visitati da un BFS è quasi lo stesso del numero di nodi ai margini. (Ad esempio in un albero con fanout K, ogni livello n ha K ^ n nodi, e il numero di nodi con profondità inferiore a n è anche Theta (K ^ n)).

Quindi, memorizzare la frangia già occupano un sacco di memoria. Quindi, se la memoria è un problema molto grande, una tecnica di "equivalente", come iterativo addensandosi DFS potrebbe essere molto meglio.

Ma se si vuole distruggere i nodi "visitati", quindi in qualche modo di tracciare ciò che è stato visitato (nel caso di un grafico generale; se è un albero allora non c'è problema) ha bisogno di essere concepiti. In questo caso sono necessarie maggiori informazioni sul grafico.

Modifica sul perché iterativo approfondimento DFS è meglio.

La frangia (nodi non visitati che devono essere adiacenti ai nodi visitati) in un BFS è O (K ^ n) nel formato, n essendo la profondità corrente. La frangia per la DFS è O (n) in termini di dimensioni.

iterativo approfondimento DFS ha la stessa dimensione frangia di DFS, e dà lo stesso risultato di BFS, perché "simula" BFS.

Answer 2

Larghezza-prima ricerca intrinsecamente ha esponenziale complessità spaziale . Eventuali trucchi faranno impatto solo marginale nei requisiti di memoria per i grandi grafici. È meglio usare ricerca in profondità, se si desidera trattabili complessità spaziale.