#Algorithme A* (A-star)Copier le lien

Prérequis : chapitre Dijkstra (relaxation, file de priorité) ; distances de Manhattan et euclidienne.

Objectifs d'apprentissage : distinguer g, h et f ; prouver l'optimalité sous admissibilité ; choisir une heuristique cohérente avec la métrique de déplacement ; comprendre quand A* surpasse Dijkstra et à quel prix en mémoire.

#1. PrincipeCopier le lien

A* évalue chaque nœud n par trois quantités :

• g(n) : coût exact du chemin déjà parcouru du départ à n ;
• h(n) : estimation du coût restant de n à la cible ;
• f(n) = g(n) + h(n) : estimation du coût total d'un chemin optimal passant par n.

À chaque itération, A* développe le nœud de plus petit f (file de priorité). Avec h = 0 partout, f = g et A* retombe exactement sur Dijkstra : A* est une généralisation guidée. Plus h approche la vraie distance restante (sans la dépasser), moins A* développe de nœuds inutiles.

#Animation interactiveCopier le lien

Entrées : une grille (murs, départ, arrivée) et l'heuristique au choix. Sorties : le chemin trouvé et l'ensemble des nœuds explorés. Lecture recommandée : comparez le nombre de nœuds développés entre h = 0 (équivalent Dijkstra) et la distance de Manhattan ; la zone explorée se resserre autour du corridor optimal.

#2. Implémentation en PythonCopier le lien

1import heapq2 3def astar(grille, depart, arrivee):4    """Chemin le plus court dans une grille 4-directionnelle.5    grille : 0 = libre, 1 = mur ; depart/arrivee : (ligne, colonne).6    Renvoie la liste des cellules du chemin, ou [] si aucun chemin."""7    lignes, colonnes = len(grille), len(grille[0])8 9    def heuristique(a, b):10        (l1, c1), (l2, c2) = a, b11        return abs(l1 - l2) + abs(c1 - c2)      # Manhattan : exacte à 4 directions12 13    def voisins(pos):14        l, c = pos

Deux choix d'implémentation hérités de Dijkstra : l'ensemble fermes filtre les entrées périmées de la file ; et le test d'arrivée se fait à l'extraction (la distance de la cible n'est définitive qu'une fois extraite), pas à sa première découverte.

#3. Propriétés : admissible et consistanteCopier le lien

Admissibilité : h(n) ≤ coût réel restant de n à la cible, pour tout n. Sous cette seule hypothèse, A* trouve un chemin optimal.

Consistance (monotonie) : pour toute arête (n, n') de coût c, h(n) ≤ c + h(n'). Une heuristique consistante est toujours admissible ; l'inverse est faux. Avec une heuristique consistante, la première extraction d'un nœud correspond à sa distance définitive : l'ensemble fermes ne rouvre jamais, et le code ci-dessus est correct sans réouvertures. Avec une heuristique admissible mais non consistante, un nœud déjà fermé doit pouvoir être rouvert ; la structure fermes du listing force alors h à être consistante, ce qui est le cas de Manhattan en déplacement 4-directionnel à coût unitaire.

#4. Heuristiques courantesCopier le lien

Le choix suit la métrique de déplacement de l'espace :

Critère : l'heuristique doit être la distance minimale dans la version sans obstacle du monde ; elle sous-estime alors toujours la vraie distance restante, quels que soient les murs.

#5. ComplexitéCopier le lien

Le pire cas reste celui d'une recherche exhaustive : O(b^d) en temps et en mémoire, où b est le facteur de branchement et d la profondeur de la solution optimale ; A* garde en mémoire tous les nœuds développés. En pratique, une heuristique informative resserre drastiquement la zone explorée : c'est le gain réel, visible dans l'animation ci-dessus. Si la mémoire devient le goulot, des variantes (IDA*, mémoire bornée) échangent du temps contre de l'espace.

#6. Exercice : grille pondéréeCopier le lien

Modifiez A* pour des cellules à coût variable : entrer dans la cellule v coûte son terrain (1 = normal, 2 = difficile, 0 = mur).

L'essentiel change en trois points : le coût d'un pas vers v devient terrain(v) ; l'heuristique doit rester admissible, donc bornée par le plus petit terrain non nul : Manhattan × 1 convient si aucun terrain n'est inférieur à 1 ; le reste (file, fermes, reconstruction) est inchangé.

1def astar_pondere(grille, depart, arrivee):2    """grille : 0 = mur, sinon coût d'entrée dans la cellule."""3    lignes, colonnes = len(grille), len(grille[0])4 5    def heuristique(a, b):6        return abs(a[0] - b[0]) + abs(a[1] - b[1])    # ≤ reste réel : terrains ≥ 17 8    g_score = {depart: 0}9    f_score = {depart: heuristique(depart, arrivee)}10    came_from = {}11    file = [(f_score[depart], depart)]12    fermes = set()13 14    while file:

Vérification : le chemin ne traverse la zone de terrain 2 que si le détour par du terrain 1 coûte davantage ; si vous mettez tous les terrains à 1, le résultat coïncide avec la version non pondérée.

#7. ApplicationsCopier le lien

1. Jeux vidéo : planification de trajectoire des personnages non joueurs, hiérarchisée (grille grossière puis fine).
2. Robotique : planification en espace continu discrétisé, heuristique issue d'une carte de coûts.
3. Calcul d'itinéraires : heuristique = distance à vol d'oiseau, très efficace sur réseaux routiers.
4. Résolution de puzzles : taquin et Rubik's cube, heuristiques admissibles classiques (distance de Manhattan des tuiles, conflits de lignes).
5. Réseaux : routage avec estimation de latence.