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)
- utilise une file de priorité
Que veulent dire ces termes ?
- 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.
- File de priorité : une file où passe d’abord le moins cher, pas le premier arrivé.
- 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.
- dans la file
- en cours
- traité
- chemin le moins cher
- sol · 1
- boue · 3
- eau · 9
- mur
Nouveau: Départ en A1 avec un coût de 0 et une estimation de 26 jusqu’à l’arrivée. C’est le seul élément de la file.
Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.
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.