L’algorithme A* permet de trouver un plus court chemin en orientant la recherche vers un objectif. Il combine le coût déjà parcouru et une estimation du coût restant. Cette estimation s’appelle une heuristique.
En Python, A* s’implémente souvent avec heapq, car on doit toujours explorer en premier la position dont le score estimé est le plus prometteur.
La réponse courte
A* choisit le prochain sommet avec ce score :
f(n) = g(n) + h(n)
où :
g(n)est le coût réel depuis le départ ;h(n)est l’estimation du coût restant jusqu’à l’arrivée ;f(n)est le score utilisé dans la file de priorité.
Si l’heuristique ne surestime jamais le coût restant, A* peut trouver un plus court chemin optimal.
Dijkstra ou A*
Dijkstra explore selon le coût déjà connu. A* ajoute une direction grâce à l’heuristique.
| Algorithme | Score de priorité | Usage |
|---|---|---|
| Dijkstra | coût depuis le départ | plus court chemin sans objectif spatial clair |
| A* | coût depuis le départ + estimation restante | chemin vers une cible avec bonne heuristique |
Sur une grille, une heuristique classique est la distance de Manhattan.
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
Elle fonctionne bien quand on se déplace seulement horizontalement ou verticalement.
Exemple complet sur une grille
Voici une implémentation simple de A* sur une grille. Les cases avec 1 sont des obstacles, les cases avec 0 sont libres.
import heapq
def voisins(position, grille):
ligne, colonne = position
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dl, dc in directions:
nl = ligne + dl
nc = colonne + dc
if 0 <= nl < len(grille) and 0 <= nc < len(grille[0]):
if grille[nl][nc] == 0:
yield (nl, nc)
def reconstruire_chemin(parents, arrivee):
chemin = []
courant = arrivee
while courant is not None:
chemin.append(courant)
courant = parents[courant]
return chemin[::-1]
def a_star(grille, depart, arrivee):
file = [(0, depart)]
parents = {depart: None}
couts = {depart: 0}
while file:
_, position = heapq.heappop(file)
if position == arrivee:
return reconstruire_chemin(parents, arrivee)
for voisin in voisins(position, grille):
nouveau_cout = couts[position] + 1
if nouveau_cout < couts.get(voisin, float("inf")):
couts[voisin] = nouveau_cout
priorite = nouveau_cout + manhattan(voisin, arrivee)
parents[voisin] = position
heapq.heappush(file, (priorite, voisin))
return None
grille = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 0],
]
print(a_star(grille, (0, 0), (3, 3)))
Le résultat est une liste de coordonnées formant le chemin.
Le rôle de l’heuristique
L’heuristique est le cœur de A*. Elle doit être rapide à calculer et donner une estimation utile.
| Contexte | Heuristique possible |
|---|---|
| Grille 4 directions | distance de Manhattan |
| Grille 8 directions | distance diagonale ou euclidienne |
| Carte routière | distance à vol d’oiseau |
| Graphe abstrait | parfois aucune bonne heuristique |
Si h(n) = 0 pour tous les sommets, A* se comporte comme Dijkstra. Si l’heuristique surestime trop, l’algorithme peut perdre la garantie d’optimalité.
Complexité
Dans le pire cas, A* peut explorer beaucoup de sommets. Sa complexité dépend fortement de la qualité de l’heuristique.
Avec une file de priorité basée sur heapq, chaque insertion ou extraction coûte O(log n).
En pratique, A* est intéressant quand l’heuristique réduit clairement la zone explorée. Sinon, Dijkstra reste plus simple à raisonner.
Pour replacer cette notion, voir la complexité algorithmique en Python.
Erreurs fréquentes
La première erreur est d’utiliser une heuristique qui surestime le coût restant sans comprendre les conséquences. Le chemin peut devenir rapide à trouver, mais pas forcément optimal.
La deuxième erreur est d’oublier de mettre à jour le parent quand un meilleur coût est trouvé.
La troisième erreur est de confondre obstacle et coût. Une case bloquée ne doit pas être générée comme voisin. Une case coûteuse peut être autorisée, mais avec un coût supérieur.
La quatrième erreur est de croire que A* remplace toujours Dijkstra. Si vous n’avez pas d’objectif unique ou pas d’heuristique pertinente, Dijkstra est souvent plus direct.
Où continuer
A* vient naturellement après BFS, Dijkstra et heapq.
- Algorithmes Python : tous les guides pour apprendre pas à pas
- BFS et DFS en Python
- File de priorité avec heapq
- Dijkstra en Python
La règle à retenir : A* est Dijkstra guidé par une estimation. Plus l’heuristique est pertinente, moins l’algorithme explore inutilement.
Références
- Documentation Python – heapq
- Documentation Python – structures de données
- Documentation Python – math.dist
