Approfondissement itératif vs profondeur-première recherche
https://stackoverflow.com/questions/7395992
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je continue à lire sur l'approfondissement itératif , mais je ne comprends pas comment il diffère de profondeur-première recherche . .
J'ai compris que la première fois la première recherche continue d'aller plus loin et plus profonde.
Dans l'approfondissement itératif, vous établissez une valeur d'un niveau, s'il n'y a pas de solution à ce niveau, vous incrémentez cette valeur et recommencez à partir de zéro (la racine).
Je veux dire que vous continueriez à incrémenter et à incrémenter, aller plus loin jusqu'à ce que vous trouviez une solution.Je vois cela comme la même chose!Je vais descendre la même branche, car si je recommence à partir de zéro, je descendrais dans la même branche qu'avant.
La solution
Dans une première recherche de profondeur, vous commencez à un nœud dans le graphique et explorez en permanence plus profondément dans le graphique pendant que vous pouvez trouver de nouveaux nœuds que vous n'avez pas encore atteint (ou avant de trouver la solution). À tout moment, le DFS est sorti des mouvements, elle recule jusqu'au dernier point où elle pourrait faire un choix différent, puis explore à partir de là. Cela peut être un problème grave si votre graphique est extrêmement volumineux et il n'y a qu'une solution, car vous risquez de vous retrouver dans l'ensemble du graphique sur un chemin DFS uniquement pour trouver la solution après avoir examiné chaque nœud. Pire, si le graphique est infini (votre graphique est peut-être constitué de tous les numéros, par exemple), la recherche peut ne pas se terminer. De plus, une fois que vous avez trouvé le nœud que vous recherchez, vous n'avez peut-être pas le chemin optimal de celui-ci (vous auriez pu boucler sur le graphique à la recherche de la solution, même s'il était juste à côté du noeud de démarrage!)
Une solution potentielle à ce problème serait de limiter la profondeur de tout chemin pris par le DFS. Par exemple, nous pourrions faire une recherche DFS, mais arrêtez la recherche si nous prenons une voie de longueur supérieure à 5. Cela garantit que nous n'explorons jamais de nœud de distance supérieure à cinq du nœud de départ, ce qui signifie que nous n'explorons jamais Infiniment ou (à moins que le graphique soit extrêmement dense), nous ne recherchons pas le graphique entier. Cependant, cela signifie que nous ne trouvions peut-être pas le nœud que nous recherchons, car nous n'explorons pas nécessairement l'ensemble du graphique.
L'idée de l'approfondissement itératif est d'utiliser cette deuxième approche, mais de continuer à augmenter la profondeur à chaque niveau. En d'autres termes, nous pourrions essayer d'explorer avec tous les chemins de la longueur, puis tous les chemins de la longueur deux, puis la longueur trois, etc. jusqu'à ce que nous retrouvions le nœud en question. Cela signifie que nous ne finons jamais par explorer le long des chemins morts infinis, car la longueur de chaque chemin est plafonnée par une certaine longueur à chaque étape. Cela signifie également que nous trouvons le chemin le plus court possible sur le nœud de destination, car si nous n'avions pas trouvé le nœud à la profondeur d, mais l'avons trouvé à la profondeur D + 1, il ne peut y avoir de chemin de longueur D (ou nous l'aurait pris), le chemin de la longueur D + 1 est vraiment optimal.
La raison pour laquelle cela est différent d'un DFS est qu'il ne fonctionne jamais dans le cas où il prend un chemin extrêmement long et détourné autour du graphique sans jamais terminer. Les longueurs des chemins sont toujours coiffées, nous ne finissons donc jamais par explorer des branches inutiles.
La raison pour laquelle cela est différent de BFS est que dans un BFS, vous devez conserver tous les nœuds de franges en mémoire à la fois. Cela prend la mémoire O (b d ), où B est le facteur de ramification. Comparez ceci à l'utilisation de la mémoire O (d) de l'approfondissement itératif (pour maintenir l'état pour chacun des nœuds D dans le chemin actuel). Bien sûr, BFS n'explore jamais le même chemin de plusieurs fois, tandis que l'approfondissement itératif peut explorer n'importe quel chemin à plusieurs reprises, car elle augmente la limite de profondeur. Cependant, les deux ont la même heure d'exécution. BFS se termine dans O (b d ) après avoir examiné tous les nœuds O (b d ) à la distance d. Utilisations d'approfondissement itératif O (b d ) temps par niveau, qui résume jusqu'à O (b d ) dans l'ensemble, mais avec un facteur constant plus élevé.
bref:
- DFS n'est pas garanti de trouver un chemin optimal; L'approfondissement itératif est.
- DFS peut explorer le graphique entier avant de trouver le nœud cible; L'approfondissement itératif ne fait que cela si la distance entre le nœud de début et de fin est le maximum dans le graphique.
- bfs et approfondissement itératif fonctionnent à la fois dans O (B d ), mais l'approfondissement itératif a un facteur constant plus élevé.
- bfs utilise la mémoire O (b d ), tandis que l'approfondissement itératif utilise uniquement O (D).
J'espère que cela vous aidera!
Autres conseils
Il y a une page décente sur Wikipedia à ce sujet.
L'idée de base que je pense que vous avez manquée est que l'approfondissement itératif est principalement un Heuristic .Lorsqu'une solution est susceptible d'être trouvée près de l'approfondissement itératif racine, on le trouvera relativement rapide, tandis que la profondeur de la profondeur-première-recherche peut faire une décision "incorrecte" et passer beaucoup de temps sur une branche profonde infructueuse.
(Ceci est particulièrement important lorsque l'arbre de recherche peut être infini. Dans ce cas, ils sont encore moins équivalents car les DFS peuvent rester coincés pour toujours pendant que BFS ou l'approfondissement itératif ne consistait pas à trouver la réponse un jourS'il existe)
Il suffit d'ajouter à ce qui est déjà ici, mais voici quelques vidéos du laboratoire d'AI en mouvement de l'Université de Denver montrant les différences.
Vous pouvez voir dans leurs exemples d'approfondissement itératif gagne lorsque l'objectif est peu profond (profondeur de la solution 3, profondeur d'arborescence) et la solution est à droite, mais DFS gagne, peu importe si la solution est dans la dernière rangée.
Je suis entré dans cette lecture sur la programmation des échecs, le prochain vers moi réfléchissait à Search de quiescence Vérifiez que si vous voulez en savoir plus sur les stratégies de recherche pour la programmation d'AI.
