Minimizar el uso de memoria de una primera búsqueda de ancho

Question

En mi el siguiente código, estoy atravesando un gráfico a través de breadth first search. El código construye el gráfico mientras está atravesando. Este es un gráfico muy grande, con un ventilador de 12. Debido a esto, cada vez que aumenta la profundidad del breadth first search, quiero destruir la capa superior para intentar minimizar el uso de la memoria. ¿Cómo podría diseñar un algoritmo para hacerlo?

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 un fanout constante y suponiendo un gráfico arborescente, el número de nodos que ha visitado un BFS es casi el mismo que el número de nodos en el margen. (por ejemplo, en un árbol con fanout K, cada nivel n tiene nodos K ​​^ n, y el número de nodos con una profundidad menor que n también es Theta (K^n)).

Por lo tanto, almacenar la franja ya ocupará mucha memoria. Entonces, si la memoria es un problema muy grande, una técnica "equivalente", como la DFS de profundización iterativa, puede ser mucho mejor.

Pero si quieres destruir los nodos "visitados", a continuación, algunos forma de seguimiento de lo que ha sido visitada (en el caso de un gráfico en general, y si es un árbol entonces no hay problema) debe ser ideado . En ese caso, se necesita más información sobre el gráfico.

EDIT por qué la profundización iterativa DFS es mejor.

La franja (nodos no visitados que deben estar adyacentes a los nodos visitados) en una BFS es O (K^n) de tamaño, siendo n la profundidad actual. La franja de DFS tiene un tamaño O (n).

Profundización iterativa DFS tiene el mismo tamaño de franja que DFS, y da el mismo resultado que BFS, porque "simula" BFS.

Answer 2

Búsqueda en primer lugar intrínsecamente has exponential space complexity. Cualquier truco tendrá solo un impacto marginal en los requisitos de memoria para gráficos grandes. Será mejor que utilice la búsqueda de profundidad en primer lugar si desea complejidad de espacio manejable.