Visualiseur Algorithme A*

Pseudocode

A* est Dijkstra avec un terme supplémentaire. Là où Dijkstra développe toujours le sommet au plus petit coût confirmé g, A* développe celui au plus petit f = g + h, où h estime le coût restant. Mettez h à zéro partout et le pseudocode ci-dessous devient exactement Dijkstra.

A*(graphe, depart, arrivee, h):
    pour chaque sommet v: g[v] = infini
    g[depart] = 0
    f[depart] = h(depart)
    ouverts = file de priorité contenant (f[depart], depart)
    fermes = ensemble vide

    tant que ouverts est non vide:
        u = ouverts.extraireMin()      // plus petit f
        si u == arrivee: retourner reconstruire(u)
        ajouter u à fermes

        pour chaque arête (u, v, w):
            si v dans fermes: continuer
            tentative = g[u] + w
            si tentative < g[v]:
                precedent[v] = u
                g[v] = tentative
                f[v] = tentative + h(v)
                ouverts.inserer(f[v], v)

    retourner aucun chemin

Ignorer les sommets fermés à la ligne 15 n'est sûr que si h est cohérente, c'est-à-dire h(u) <= w(u, v) + h(v) pour toute arête. Avec une heuristique seulement admissible, il faut autoriser les sommets à quitter l'ensemble fermé et à être rouverts, sinon A* peut renvoyer un chemin non optimal. Le visualiseur ci-dessus multiplie la distance à vol d'oiseau par le coût par unité le plus bas qu'offre une arête, ce qui rend h cohérente par l'inégalité triangulaire, et aucune réouverture n'est alors nécessaire.

Exemple détaillé, étape par étape

Cinq sommets, S à l'origine et l'arrivée G cinq unités à sa droite. L'intérêt de la trace, c'est le sommet que A* ne touche jamais.

Graphe d'exemple: S(0,0), A(2,1), B(2,-1), C(1,4), G(5,0). Arêtes S-A = 3, S-B = 2, S-C = 4, A-B = 2, A-G = 4, B-G = 6, C-G = 7. En multipliant la distance à vol d'oiseau par le coût par unité le plus bas d'une arête (0,894), on obtient h(S) = 4,47, h(A) = 2,83, h(B) = 2,83, h(C) = 5,06, h(G) = 0.

1. 1. Développer S, le seul sommet ouvert, à f = 4,47. Le relâchement de ses trois arêtes place A à g = 3, f = 5,83 ; B à g = 2, f = 4,83 ; et C à g = 4, f = 9,06. C paraît déjà coûteux : proche de S, mais orienté à l'opposé de l'arrivée.
2. 2. Développer B, désormais le plus petit f à 4,83. Il atteint l'arrivée à g = 8, f = 8,00. Notez que A* ne s'arrête pas là. Trouver l'arrivée n'est pas la développer, et rien ne dit encore que 8 soit le meilleur coût.
3. 3. Développer A à f = 5,83. Son arête vers G donne g = 7, ce qui bat le 8 trouvé via B, donc G s'améliore à f = 7,00.
4. 4. Développer G à f = 7,00, le plus petit f de l'ensemble ouvert. L'arrivée ayant été développée, son coût est définitif et la recherche s'arrête, C restant intact dans l'ensemble ouvert à f = 9,06.

A* renvoie S vers A vers G pour un coût de 7, après avoir développé 4 sommets. Dijkstra sur le même graphe renvoie le même chemin au même coût, mais en développe 5 : il traite C avant d'accepter de fixer l'arrivée. C ne méritait pas la visite, et c'est h qui a permis à A* de le savoir sans vérifier.

Complexité et son origine

Temps: O((V + E) log V) au pire avec un tas binaire · Espace: O(V)

Le pire cas est celui de Dijkstra, et pour la même raison : chaque sommet peut entrer une fois dans la file de priorité et chaque arête peut déclencher une diminution de clé, soit V extractions et E mises à jour en O(log V) chacune. L'heuristique ne change rien à cette borne. Elle change la constante : les sommets dont le f dépasse le coût final de l'arrivée ne sont jamais développés. Avec h = 0, A* dégénère exactement en Dijkstra ; avec un h parfait, il suit directement le chemin optimal. Sur 4000 graphes pondérés générés aléatoirement, l'implémentation ci-dessus a développé 4,58 sommets en moyenne contre 5,52 pour Dijkstra, et a renvoyé le coût optimal à chaque fois.

Quand utiliser Algorithme A*, et quand l'éviter

A* ne vaut sa mécanique supplémentaire que si vous avez une arrivée et une estimation utilisable de la distance qui vous en sépare. À défaut de l'une ou l'autre, l'un de ces algorithmes est le meilleur outil.

Pièges fréquents

• Une heuristique qui surestime casse l'optimalité. Si h peut dépasser le coût restant réel, A* risque de fixer l'arrivée par une route qui n'est pas la moins chère, et il le fera silencieusement. La distance à vol d'oiseau n'est admissible que si elle est dans la même unité que les poids des arêtes. Une distance en pixels face à des poids de 1 à 10 surestime énormément.
• Admissible n'est pas cohérente. L'ensemble fermé suppose la cohérence, h(u) <= w(u, v) + h(v) sur toute arête. Une heuristique admissible mais incohérente exige que les sommets soient rouverts quand une route moins chère apparaît, sinon le chemin renvoyé peut être non optimal.
• S'arrêter dès que l'arrivée est découverte. Atteindre l'arrivée pendant un relâchement ne prouve rien. Dans la trace ci-dessus, B trouve G à 8 une étape avant que A ne la trouve à 7. Il faut attendre que l'arrivée soit le sommet développé.
• Recalculer h à chaque comparaison. L'heuristique s'appelle une fois par sommet, pas une fois par comparaison dans la file de priorité. Mettre h en cache à côté de g fait la différence entre une heuristique rentable et une qui coûte plus qu'elle ne rapporte.
• Supposer que A* bat toujours Dijkstra. Avec une heuristique faible, A* développe les mêmes sommets que Dijkstra, plus le coût de calcul de h. Sur des graphes sans géométrie, h = 0 est le choix honnête et Dijkstra est l'implémentation la plus simple.

Questions fréquentes

Que signifie vraiment f = g + h ?

g est ce qu'un chemin jusqu'à ce sommet a coûté jusqu'ici, et c'est un fait. h est une estimation de ce que coûtera le trajet d'ici à l'arrivée. Leur somme f est le coût estimé de la meilleure route complète passant par ce sommet, et A* travaille toujours sur le sommet à la plus petite estimation.

Qu'est-ce qui rend une heuristique admissible ?

Elle ne surestime jamais le coût restant réel. La distance à vol d'oiseau convient pour un déplacement dans le plan, car aucune route ne peut être plus courte qu'une ligne droite. C'est l'admissibilité qui garantit que A* renvoie un chemin optimal.

A* est-il toujours plus rapide que Dijkstra ?

Il ne développe jamais plus de sommets que Dijkstra à graphe égal et heuristique cohérente, et en développe généralement moins. Mais il n'est pas asymptotiquement plus rapide : les deux sont en O((V + E) log V). Le gain est un facteur constant, et il se réduit à néant à mesure que l'heuristique s'affaiblit vers zéro.

A* gère-t-il les poids négatifs ?

Non. Il hérite de l'hypothèse qui fait fonctionner Dijkstra : prolonger un chemin ne le rend jamais moins cher. Utilisez Bellman-Ford quand les poids peuvent être négatifs.

Qui a inventé A* ?

Peter Hart, Nils Nilsson et Bertram Raphael, au Stanford Research Institute, dans un article de 1968 intitulé "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". Une note de 1972 des mêmes auteurs a corrigé leur affirmation initiale sur l'optimalité, en distinguant admissibilité et cohérence.

Pourquoi A* a-t-il ignoré le sommet C dans le parcours ?

C est à f = 9,06 alors que l'arrivée a été fixée à f = 7,00. Comme l'heuristique ne surestime jamais, un f de 9,06 est la promesse qu'aucune route passant par C ne peut coûter moins de 9,06, ce qui est déjà pire qu'une réponse terminée à 7. A* peut l'écarter sans regarder.