Minimiser l'utilisation de la mémoire d'une largeur d'abord rechercher

Question

Dans mon code suivant, je traverse un graphique à travers breadth first search. Le code construit le graphique pendant qu'il traverse. Ceci est un très grand graphique, avec un ventilateur sur 12. Pour cette raison, chaque fois que la profondeur du breadth first search augmente, je veux détruire le calque au-dessus afin de minimiser l'utilisation de la mémoire. Comment pourrais-je concevoir un algorithme pour le faire?

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

Avec une ventilation constante et en supposant un graphe arborescent, le nombre de nœuds visités par un BFS est presque le même que le nombre de nœuds sur la frange. (Par exemple dans un arbre avec une fanout K, chaque niveau n a K^n nœuds, et le nombre de nœuds de profondeur inférieure à n est également Theta (K^n)).

Par conséquent, stocker la frange prendra déjà beaucoup de mémoire. Donc, si la mémoire est un très gros problème, une technique "équivalente" comme l'approfondissement itératif DFS peut être bien meilleure. Mais si vous voulez détruire les nœuds "visités", alors un moyen de suivre ce qui a été visité (dans le cas d'un graphique général, si est un arbre alors il n'y a pas de problème) doit être imaginé . Dans ce cas, plus d'informations sur le graphique sont nécessaires.

EDIT explique pourquoi l'approfondissement itératif DFS est meilleur.

La frange (nœuds non visités qui doivent être adjacents aux nœuds visités) dans un BFS est de taille O (K^n), n étant la profondeur actuelle. La frange pour DFS est de taille O (n).

Approfondissement itératif DFS a la même taille de frange que DFS et donne le même résultat que BFS, car il "simule" BFS.

Answer 2

Largeur-première recherche par nature has exponential space complexity. Toutes les astuces ne feront que des impacts marginaux dans les exigences de mémoire pour les grands graphiques. Il vaut mieux utiliser la recherche en profondeur si vous voulez une complexité de l'espace.