Recherche A*
L'algorithme de Dijkstra trouve le plus court chemin vers une cible, mais il cherche dans toutes les directions à la fois, même à l'opposé de la cible. La recherche A* ajoute une seule connaissance, une estimation de la distance qui reste jusqu'à la cible, et soudain la recherche file droit vers elle.
L'idée
Quand vous cherchez un itinéraire sur une carte, vous n'explorez pas les routes qui s'éloignent de votre destination avec autant de soin que celles qui s'en rapprochent. La recherche A* fait de même. Chaque nœud reçoit un score : la distance depuis le départ jusqu'ici, g, plus une estimation de la distance restante, h. La recherche repart toujours du nœud au plus petit score, donc les nœuds situés vers la cible passent en premier.
Pas à pas
Donnez au départ la distance 0 et placez-le dans une file avec le score h(départ). Répétez : prenez le nœud au plus petit score et rendez sa distance définitive. Si c'est la cible, arrêtez : en remontant les nœuds retenus, on obtient le chemin. Sinon, pour chaque voisin qui n'est pas définitif, calculez sa distance en passant par ce nœud. Si elle est plus courte que sa distance jusqu'ici, abaissez-la, retenez ce nœud comme chemin pour y arriver, et donnez au voisin comme score sa nouvelle distance plus son estimation. Quand deux scores sont égaux, prendre d'abord le nœud à la plus petite estimation atteint généralement la cible plus tôt.
Un exemple
Prenons un départ A et une cible D. A–B mesure 2 et B–D 2, tandis que A–C mesure 1 et C–D 5. Les estimations en ligne droite jusqu'à D sont 3 depuis A, 2 depuis B et 3 depuis C. A commence avec le score 0 + 3 = 3. Prendre A donne à B le score 2 + 2 = 4 et à C le score 1 + 3 = 4. En cas d'égalité, A* prend B, le nœud à la plus petite estimation, et B donne à D le score 4 + 0 = 4. D a maintenant le plus petit score avec la plus petite estimation, il est donc pris : le plus court chemin est A → B → D, de longueur 4, et C, qui mène dans la mauvaise direction, n'est jamais rendu définitif. L'algorithme de Dijkstra aurait rendu C définitif en premier, car c'est le nœud le plus proche de A.
Une bonne estimation
L'estimation ne doit jamais être plus longue que la vraie distance jusqu'à la cible ; une telle estimation est dite admissible, et avec elle A* trouve toujours un plus court chemin. La ligne droite est admissible, car aucun trajet n'est plus court qu'une ligne droite. Si en plus l'estimation ne baisse jamais de plus que la longueur d'une arête d'un nœud au suivant, elle est consistante, et aucun nœud définitif n'a jamais besoin d'être réexaminé. Plus l'estimation est proche de la réalité, moins A* a besoin de nœuds. Une estimation de 0 est admissible mais inutile : A* devient alors l'algorithme de Dijkstra. Une estimation trop grande rend A* plus rapide mais peut manquer le plus court chemin.
Histoire et usages
Peter Hart, Nils Nilsson et Bertram Raphael, du Stanford Research Institute, ont publié A* en 1968, alors qu'ils travaillaient sur Shakey, l'un des premiers robots mobiles. Leurs versions précédentes s'appelaient A1 et A2 ; l'étoile désignait la version dont ils ont prouvé l'optimalité. Aujourd'hui, A* fait contourner des obstacles aux personnages de jeux vidéo, planifie des itinéraires et des mouvements de robots, et résout des casse-tête comme le 15-puzzle (taquin), où l'estimation additionne la distance de chaque pièce à sa place.
À vous d'essayer
Ouvrez l'application et appuyez sur Étape. Les nombres sur les arêtes sont leurs longueurs, qui correspondent ici à la longueur de leur tracé, et la ligne pointillée montre l'estimation en ligne droite jusqu'à la cible. La file sous le graphe liste les nœuds par score, du plus petit au plus grand. Quand la cible est définitive, la ligne d'état compare le nombre de nœuds rendus définitifs par A* à celui qu'il aurait fallu à l'algorithme de Dijkstra. Essayez une cible dans un coin éloigné d'un grand graphe pour voir la plus grande différence.
Questions fréquemment posées
Que signifie l'étoile dans A* ?
Hart, Nilsson et Raphael ont d'abord décrit des algorithmes qu'ils appelaient A1 et A2. A* (« A étoile ») était la version dont ils ont prouvé qu'elle trouve un plus court chemin en développant le moins de nœuds parmi les algorithmes comparables utilisant la même estimation, quand l'estimation est consistante.
Quelle est la complexité en temps de A* ?
Dans le pire cas, avec une estimation inutile, A* fait le même travail que l'algorithme de Dijkstra : O((V + E) log V) avec un tas binaire. Avec une bonne estimation, il ne rend définitive qu'une fraction des nœuds, c'est pourquoi il est rapide en pratique.
Qu'est-ce qu'une bonne heuristique pour A* ?
Elle doit être rapide à calculer, ne jamais surestimer la vraie distance et en être aussi proche que possible. Sur une grille où l'on ne peut se déplacer que vers le haut, le bas, la gauche et la droite, la distance de Manhattan est un choix courant ; sur une carte, la distance à vol d'oiseau.
Et si l'heuristique surestime ?
A* peut alors renvoyer un chemin qui n'est pas le plus court, car il peut finir avant d'examiner le meilleur trajet. Certains programmes le font exprès (A* pondéré) pour échanger un peu de qualité de chemin contre beaucoup de vitesse.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer la recherche A*