Différence entre largeur d 'abord la recherche et l'approfondissement itératives

Question

Je comprends BFS et DFS, mais pour la vie de moi ne peut pas comprendre la différence entre itérative et l'approfondissement de BFS. Apparemment, l'approfondissement itératives a la même utilisation de la mémoire DFS, mais je suis incapable de voir comment cela est possible, car il ne cesse en expansion comme BFS. Si quelqu'un peut clarifier ce serait génial.

arbre au travail sur le cas échéant:

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

D'après ce que je comprends itérative l'approfondissement ne DFS à la profondeur 1 ne puis DFS jusqu'à une profondeur de 2 ... jusqu'à la profondeur n, et ainsi de suite jusqu'à ce qu'il ne trouve pas plus de niveaux

par exemple, je pense que l'arbre serait lu

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

Je crois que le fait à peu près un DFS séparés avec limite de profondeur pour chaque niveau et jeter la mémoire.

Answer 2

De ma compréhension de l'algorithme, IDDFS (itérative l'approfondissement de la recherche en profondeur d'abord) est tout simplement une recherche en profondeur d'abord effectué plusieurs fois, en approfondissant le niveau des noeuds recherché à chaque itération. Par conséquent, les exigences de mémoire sont les mêmes que la recherche en profondeur d'abord parce que l'itération de profondeur maximale est juste la pleine recherche en profondeur d'abord.

Par conséquent, pour l'exemple de l'arbre que vous avez donné, la première itération visiterait noeud A, la deuxième itération visiterait noeuds A, B et C, et la troisième itération visiterait tous les nœuds de l'arbre.

La raison pour laquelle il est mis en œuvre comme cela est que, si la recherche a une contrainte de temps, alors l'algorithme aura au moins une idée de ce qu'est un noeud « bon score » est si elle atteint le délai avant de faire un plein traversal de l'arbre.

Ceci est différent d'une largeur d'abord parce que la recherche à chaque itération, les noeuds sont visités comme ils le seraient dans une recherche en profondeur d'abord, pas comme dans une recherche en largeur. En règle générale, les algorithmes IDDFS emmagasineraient probablement le noeud « meilleur score » trouve de chaque itération.

Answer 3

l'utilisation de la mémoire est le nombre maximum de noeuds enregistre en tout point. pas le nombre de nœuds visités.

à tout moment IDFS a besoin de stocker uniquement les noeuds dans la branche est expanding.only A et C, si nous élargissons C (dans votre par exemple). BFS doit enregistrer tous les nœuds de la profondeur, il est à la recherche. pour voir l'effet prendre un arbre avec facteur de ramification 8 au lieu de 2. de chercher à une profondeur de 3, BFS a besoin de stocker un 64 noeuds massifs. IDFS n'a besoin que 3.

Answer 4

Dans chaque itération de itératives-Approfondir Recherche, nous avons une limite et on traverse le graphique en utilisant l'approche DFS, cependant, pour chaque étape de chaque itération, nous avons juste besoin de garder une trace de seulement nœuds à l'intérieur du chemin depuis la racine à d profondeur. C'est la sauvegarde en mémoire.

Par exemple, regardez la dernière ligne de l'image ci-dessous. Si nous avons utilisé BFS, nous avons dû garder une trace de tous les nœuds jusqu'à la profondeur 2. Mais parce que nous utilisons DFS, nous ne devons garder tous en mémoire car soit certains noeuds sont déjà visités afin que nous ne sommes pas besoin d'eux, ou non encore visité donc nous allons ajouter plus tard. Nous venons tout juste garder notre chemin vers la racine (le chemin gris).

L'image est de l'intelligence artificielle livre par Peter Norvig et Stuart Russel