La différence entre la Largeur de la Recherche, et l'approfondissement Itératif
Je comprends BFS, et DFS, mais pour la vie de moi ne peut pas comprendre la différence entre l'approfondissement itératif et BFS. Apparemment, l'approfondissement Itératif a la même utilisation de la mémoire comme DFS, mais je suis incapable de voir comment cela est possible, comme il ne cesse de l'expansion comme BFS.
Si quelqu'un peut préciser ce serait génial.
arbre de travail, si cela est nécessaire:
A
/\
B C
/ /\
D E F
OriginalL'auteur theraven | 2010-06-08
Vous devez vous connecter pour publier un commentaire.
Ce que je comprends de l'approfondissement itératif ne DFS jusqu'à une profondeur de 1 alors à DFS jusqu'à une profondeur de 2 ... jusqu'à une profondeur n , et ainsi de suite jusqu'à ce qu'il ne trouve pas plus de niveaux
par exemple je pense que l'arbre serait de lire
Je crois que c'est assez bien fait un DFS distincts avec limite de profondeur pour chaque niveau et de jeter la mémoire.
Je suis en train de penser en termes d'un appel récursif à la mise en œuvre avec la lecture là où vous obtenez en fait la valeur et la visite étant whats en haut de la pile.
Ouais, je comprends ce que vous êtes en ce sens, mais je pense que la "visite" est le terme qui est généralement utilisé pour signifier quand vous obtenez en fait la valeur (ou de faire une sorte d'opération sur le nœud).
Que font les gens habituellement utiliser pour se référer à ce que j'ai marqué comme lu? et est-il une alternative populaire à l'aide visité pour obtenir la valeur(juste le son de mal pour moi)?
OriginalL'auteur Roman A. Taycher
À partir de ma compréhension de l'algorithme, IDDFS (itératif de l'approfondissement du depth-first search) est tout simplement une profondeur de recherche est exécutée plusieurs fois, d'approfondir les nœuds du niveau recherché à chaque itération. Par conséquent, les besoins en mémoire sont les mêmes que la profondeur de recherche est parce que la profondeur maximale d'itération est juste la pleine profondeur de la première recherche.
Donc, pour l'exemple de l'arbre que vous avez donné, la première itération de visiter Un nœud, la deuxième itération de visiter les nœuds A, B, et C, et la troisième itération de visiter tous les nœuds de l'arbre.
La raison pour laquelle il est mis en œuvre comme il en est ainsi que, si la recherche a une contrainte de temps, alors l'algorithme va au moins avoir une idée de ce qu'est un "bon score" nœud est si elle atteint la limite de temps avant de faire la traversée de l'arbre.
Ceci est différent de celui d'une ampleur-première de la recherche, parce qu'à chaque itération, les nœuds sont visités juste comme ils le seraient en profondeur d'abord de recherche, pas comme dans une vaste recherche d'abord. Généralement, IDDFS algorithmes serait probablement stocker le "meilleur score" nœud trouvé de chaque itération.
Morrison IDDFS n'aurait pas de meilleure idée que de BFS ce qu'est un "bon score" nœud est, la mémoire avantage est le seul avantage.
Vous vous êtes trompé. L'approfondissement itératif a une meilleure idée que BFS sur lequel les nœuds score ainsi que ses évalué les nœuds sur des passes précédentes. IDDFS pouvez utiliser cette information pour rechercher le plus marquant les noeuds.
Morrison, Vous parlez de la formation d'une heuristique ou fonction d'évaluation sur la première profondes recherches pour prendre de meilleures décisions à l'aide de l'élagage ou l'heuristique de recherche techniques. BFS peuvent également être exécutées à plusieurs reprises, avec un début de coupure à former une heuristique, dans lequel cas, il pourrait prendre les mêmes raccourcis. IDDFS vous demandant de faire le travail répété (peu importe si vous l'utilisez pour le train) est donc pas un avantage.
Ah, je vois. Je pensais IDDFS toujours utilisé une heuristique. Mais IDDFS n'est pas nécessairement l'utilisation d'une heuristique. Et même si IDDFS a une heuristique, elle n'offre aucun avantage sur BFS avec la même heuristique, sauf en termes de mémoire. Vous avez raison, mon erreur.
OriginalL'auteur Steven Oxley
l'utilisation de la mémoire est le nombre maximum de noeuds, il enregistre à tout moment. pas le nombre de nœuds visités.
à tout moment RI a besoin de stocker uniquement les nœuds dans la direction qu'il est en expansion.seul l'Un et C si nous élargissons C (dans votre message.g). BFS devez enregistrer tous les nœuds de la profondeur de la recherche. pour voir l'effet prendre un arbre avec un facteur de branchement 8 au lieu de 2. à la recherche d'une profondeur de 3, la SECTION a besoin de stocker une énorme 64 nœuds. RI a besoin de seulement 3.
OriginalL'auteur Aruna Herath
À chaque itération de Itératif de l'Approfondissement de la Recherche, nous avons une limite et nous traversons le graphique à l'aide de la DFS approche, cependant, pour chaque étape de chaque itération, nous avons juste besoin de garder une trace de seuls les nœuds à l'intérieur du chemin de la racine à la profondeur d. C'est l'enregistrement dans la 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'à une profondeur de 2. Mais parce que nous sommes l'aide de DFS, nous n'avons pas besoin de les maintenir tous en mémoire, depuis certains nœuds sont déjà visité donc nous n'avons pas besoin d'eux, ou pas visité encore si nous allons l'ajouter plus tard. Nous continuons notre chemin vers la racine (le gris).
L'image est d'une Intelligence Artificielle livre de Peter Norvig et Stuart Russel
OriginalL'auteur Iman Mirzadeh