Recherche A*
Dijkstra avec le sens de l'orientation. Au coût de chaque endroit, il ajoute une estimation du coût restant, et essaie donc d'abord les endroits qui semblent les plus proches de l'arrivée.
- temps O((V + E) log V)
- espace O(V)
- file de priorité
File de priorité : une file où passe d'abord le moins cher, pas le premier arrivé.
Autres termes de cette page
- Coût : ce que coûte un déplacement. Dans le labyrinthe, le sol coûte 1, la boue 3 et l'eau 9 ; dans le graphe, c'est le nombre sur l'arête.
- Estimation (h) : une supposition du coût restant. A* ne reste exact que si elle n'est jamais trop haute.
- Relâcher une arête : vérifier si passer par l'endroit courant donne à un voisin un coût plus bas, et le prendre si c'est le cas.
Essayez : Choisissez le champ ouvert et alternez entre Dijkstra et A* : les deux trouvent un chemin de même coût, mais A* retire bien moins de cases de la file.
Comment ça marche
A* fonctionne comme Dijkstra, mais trie la file selon f = coût déjà payé + h, où h estime le coût restant. Dans le labyrinthe, h est le nombre de déplacements jusqu'à M en ignorant murs et boue ; dans le graphe, la distance à vol d'oiseau divisée par 10. Tant que h ne surestime jamais, le chemin qu'A* a en prenant l'arrivée est le moins cher, exactement comme avec Dijkstra. Meilleure est l'estimation, moins il y a d'endroits à examiner.
Quand le choisir
A* convient quand vous cherchez une seule arrivée et savez estimer sa distance : pathfinding dans les jeux, robots, calcul d'itinéraire sur une carte. Avec h = 0, c'est exactement Dijkstra. Une estimation qui peut surestimer rend A* plus rapide, mais peut faire manquer le chemin le moins cher.