Algorithme de recherche A*
- Introduite par
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- Année
- 1968
- Type
- algorithm
- Famille
- Graph Algorithms
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'algorithme de recherche A*, développé par Peter E. Hart, Nils J. Nilsson et Bertram Raphael en 1968, est un algorithme de recherche de chemin optimal qui combine les avantages de l'algorithme de Dijkstra avec un guidage heuristique.
Il trouve efficacement le chemin le plus court en équilibrant la distance réelle depuis le départ avec la distance estimée jusqu'au but. Il utilise une fonction d'évaluation f(n) = g(n) + h(n), où g(n) est le coût réel du départ au nœud n, et h(n) est une estimation heuristique du coût restant jusqu'au but. En explorant les nœuds avec la plus faible valeur f(n), l'algorithme réduit efficacement l'espace de recherche vers le but tout en maintenant l'optimalité lorsque l'heuristique est admissible (ne surestime jamais). Cela rend A* significativement plus rapide que les méthodes de recherche non informées tout en garantissant la découverte du chemin optimal.
L’intuition derrière la méthode
A* utilise une fonction d'évaluation f(n) = g(n) + h(n), où g(n) est le coût réel du départ au nœud n, et h(n) est une estimation heuristique du coût restant jusqu'au but. En explorant les nœuds avec la plus faible valeur f(n), l'algorithme réduit efficacement l'espace de recherche vers le but tout en maintenant l'optimalité lorsque l'heuristique est admissible (ne surestime jamais). Cela rend A* significativement plus rapide que les méthodes de recherche non informées tout en garantissant la découverte du chemin optimal.
Histoire
Hart, Nilsson et Raphael ont publié A* en 1968, démontrant que l'ajout d'informations heuristiques à l'algorithme de Dijkstra pouvait améliorer considérablement l'efficacité de la recherche tout en maintenant l'optimalité. L'algorithme est devenu fondamental en intelligence artificielle et en recherche opérationnelle. Les développements ultérieurs incluent A* bidirectionnel, IDA* (approfondissement itératif) et diverses améliorations heuristiques. A* reste le choix standard pour la recherche de chemin dans les moteurs de jeux modernes et les systèmes robotiques.
Quand l’utiliser
Appliquer A* lorsque vous avez besoin de trouver des chemins optimaux dans des graphes où une bonne fonction heuristique est disponible. Il est particulièrement efficace pour la recherche de chemin dans les jeux, la robotique et la planification d'itinéraires où la recherche informée peut réduire considérablement le calcul. Utilisez-le lorsque la vitesse est importante mais que l'optimalité est requise. Pour les cas sans heuristique fiable, utilisez l'algorithme de Dijkstra à la place.
Limites et points d’attention
- L'optimalité dépend de l'admissibilité de la fonction heuristique
- Les performances se dégradent considérablement avec des heuristiques médiocres ou inadmissibles
- L'utilisation de la mémoire peut être substantielle dans de grands espaces de recherche (maintient des ensembles ouvert et fermé)
- Nécessite une connaissance explicite du domaine pour concevoir de bonnes fonctions heuristiques
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Recherche de chemin optimale lorsque l'heuristique est admissible
- Beaucoup plus rapide que Dijkstra ou la recherche en largeur lorsque de bonnes heuristiques sont disponibles
- Flexible : fonctionne avec toute fonction heuristique admissible
- Bien adapté aux problèmes de recherche de chemin à but unique
- Validation étendue dans le monde réel pour les jeux, la robotique et les systèmes de navigation
Applications
- Recherche de chemin dans les jeux vidéo : navigation NPC en temps réel dans des environnements de jeu dynamiques
- Planification de mouvement robotique : planification de chemin optimal pour des robots autonomes évitant les obstacles
- Navigation GPS : calcul d'itinéraires efficaces prenant en compte les réseaux routiers et le trafic
- Résolution de puzzles : recherche de solutions optimales dans des problèmes combinatoires comme le puzzle des 15
- Routage réseau : détermination de routes de paquets efficaces avec des heuristiques de qualité de lien
- Bioinformatique : recherche d'alignement de séquences et de prédiction de structure protéique
Comment ça marche
Comment ça marche
Créer un ensemble ouvert avec le nœud de départ, définir sa valeur g (coût depuis le départ) à zéro, et calculer sa valeur h en utilisant la fonction heuristique.
Sélectionner le nœud avec la plus faible valeur f dans l'ensemble ouvert, calculer les valeurs f de ses voisins non visités, et ajouter les voisins prometteurs à l'ensemble ouvert.
Continuer à développer les nœuds jusqu'à atteindre le but avec la plus faible valeur f, ce qui garantit le chemin optimal ; reconstruire le chemin en suivant les pointeurs parents.
Pièges courants
- Utilisation d'une heuristique inadmissible qui surestime les coûts, conduisant à des chemins sous-optimaux
- Choix d'une heuristique trop simple ou sans rapport avec le problème, réduisant l'efficacité de la recherche
- Implémentation inefficace de l'ensemble ouvert (devrait utiliser une file de priorité), entraînant une sélection lente des nœuds
Questions fréquentes
Qu'est-ce qu'une heuristique admissible et pourquoi est-elle importante ?
Une heuristique admissible ne surestime jamais le coût réel jusqu'au but. Cette propriété garantit que A* trouve le chemin optimal. Si une heuristique surestime, A* peut manquer des chemins plus courts et retourner des solutions sous-optimales.
Comment concevoir une bonne heuristique pour un problème ?
Les bonnes heuristiques sont basées sur la connaissance du domaine et la structure du problème. Pour la recherche de chemin basée sur une grille, la distance de Manhattan ou euclidienne fonctionne bien. Pour des problèmes plus complexes, envisagez de relâcher les contraintes ou d'utiliser des bases de données de motifs pour calculer des heuristiques admissibles.
Quelle est la différence entre l'algorithme A* et l'algorithme de Dijkstra ?
Les deux trouvent des chemins optimaux, mais A* utilise une heuristique pour prioriser l'exploration vers le but, ce qui le rend beaucoup plus rapide lorsqu'une bonne heuristique est disponible. Dijkstra explore uniformément dans toutes les directions et est plus sûr lorsque les heuristiques ne sont pas fiables.
A* peut-il garantir la découverte du chemin le plus court ?
Oui, A* garantit le chemin le plus court lorsque l'heuristique est admissible (ne surestime jamais le coût réel). Avec des heuristiques inadmissibles, l'optimalité n'est pas garantie.
Méthodes associées
Sources
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Ouvrir la référence DOICopié.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ISBN : 978-0-13-604259-4Copié.