IDA-Star Iterative deepening A*

Thèmes abordés

IDA Approfondissement Itératif A, graphe, algorithme, F-score, fonction heuristique

Résumé du document

L'approfondissement itératif A* (IDA*) est un algorithme de parcours des graphes et de recherche du chemin le plus court entre un noeud de départ et un noeud objectif dans un graphe.

Extraits

[...]  Développé par Richard E. Korf en 1985 comme une amélioration de l'algorithme IDA* utilise une variante de la recherche itérative en profondeur avec l'intégration d'une fonction heuristique pour évaluer les coûts.  IDA* réduit l'utilisation de la mémoire par rapport à grâce à sa nature de recherche en profondeur, tout en se concentrant sur les nœuds les plus prometteurs plutôt que sur une exploration exhaustive à la même profondeur.  Contrairement à IDA* n'utilise pas de programmation dynamique, ce qui entraîne l'exploration répétée des nœuds F-score F-score est une fonction heuristique utilisée pour estimer le coût d'atteindre l'état final à partir d'un état donné. [...]

[...] En économisant l'espace mémoire et en garantissant des solutions optimales, même avec des ressources limitées, IDA* offre une approche efficace pour résoudre des problèmes complexes de manière pragmatique et équilibrée. Son adaptation aux contraintes de mémoire en fait un choix précieux pour des applications où l'efficacité des ressources est une priorité Reference Reference https://en.wikipedia.org/wiki/Iterative_deepening_A* https://www.youtube.com/watch?v=Krh2PlkbN28&t=471s . [...]

[...] Explorer ses enfants. • 4 > Seuil et 5 > Seuil. Ainsi, cette itération est terminée et les valeurs élaguées sont 4 et Exemple d'application Itération • Dans les valeurs élaguées, la plus petite est 4. Donc, le seuil (threshold) = Exemple d'application Itération • Dans les valeurs élaguées, la plus petite est 5. Donc, le seuil (threshold) = Exemple d'application Itération • Dans les valeurs élaguées, la plus petite est 6. Donc, le seuil (threshold) = Exemple d'application Itération • Dans les valeurs élaguées, la plus petite est 7. [...]

[...] Et stockez-le dans la liste des nœuds visités. Étape 5 : Chemin vers le but Si le nœud Goal est trouvé, renvoyez le chemin du nœud de départ au nœud Goal. Étape 6 : Mettre à jour le seuil Si le nœud Objectif n'est pas trouvé, répétez à partir de l'étape 2 en modifiant le seuil avec la valeur d'élagage minimale de la liste des nœuds visités. Et continuez jusqu'à ce que vous atteigniez le nœud objectif Exemple d'application Exemple d'application Itération • Nœud racine en tant que nœud actuel, c'est-à-dire 2 • Seuil = valeur du nœud actuel = 2). [...]

[...] Donc, le seuil (threshold) = 8. La solution est 2 - 5 - 6 - 8 - Les Avantages de IDA* Avantages de IDA*  Gestion efficace de la mémoire : IDA* optimise l'utilisation de la mémoire en stockant uniquement les données requises pour la recherche en cours, consommant ainsi moins de ressources que l'algorithme A*.  Complétude garantie : Il trouvera toujours la solution optimale à condition qu'elle existe et si une heuristique est fournie elle doit être admissible Les inconvénients de IDA* Les inconvénients de IDA*  Ne garde pas la trace des nœuds visités et explore donc à nouveau les nœuds déjà explorés. [...]