Aller au contenu principal

Algorithme A*

Progression

#Algorithme A* (A-star)

À quoi ça sert ?

À quoi ça sert: trouver rapidement un chemin optimal en guidant Dijkstra avec une heuristique. Comment: f(n)=g(n)+h(n) avec h admissible (≤ vraie distance) et idéalement consistante pour garantir l’optimalité sans réinsertions.

#Principe

A* évalue les nœuds en combinant :

  • g(n) : le coût réel du chemin du nœud initial à n
  • h(n) : le coût heuristique estimé du chemin de n au nœud cible
  • f(n) = g(n) + h(n) : l'évaluation totale du coût du chemin passant par n

L'algorithme choisit toujours le nœud avec le plus petit f(n) pour l'exploration.

#Animation interactive

Voici une animation qui illustre le fonctionnement de l'algorithme A* :

Chargement...

#Implémentation en Python

pythonpython
1import heapq2from typing import List, Tuple, Dict, Set3 4def astar(grille: List[List[int]], depart: Tuple[int, int], arrivee: Tuple[int, int]) -> List[Tuple[int, int]]:5    """6    Implémentation de l'algorithme A* pour trouver le chemin le plus court dans une grille7    8    Args:9        grille: 2D liste où 0 = libre, 1 = mur10        depart: tuple (row, col) du point de départ11        arrivee: tuple (row, col) du point d'arrivée12    13    Returns:14        Liste de tuples représentant le chemin, ou [] si aucun chemin trouvé

#Propriétés

#Admissibilité

A* est admissible (trouve toujours la solution optimale) si l'heuristique h(n) est admissible, c'est-à-dire qu'elle ne surestime jamais le coût réel pour atteindre la cible :

  • h(n) ≤ coût_réel(n, cible)

#Consistance

A* est consistant (ou monotone) si pour chaque nœud n et chaque successeur n' de n :

  • h(n) ≤ coût(n, n') + h(n')

Une heuristique consistante est toujours admissible.

Sur/sous‑estimation

Une h trop faible → A* ≈ Dijkstra (correct mais plus lent). Une h qui surestime peut accélérer mais perd l’optimalité.

#Heuristiques courantes

  1. Distance de Manhattan :

    • h = |x1 - x2| + |y1 - y2|
    • Pour les mouvements en 4 directions (haut, bas, gauche, droite)

  2. Distance euclidienne :

    • h = √[(x1 - x2)² + (y1 - y2)²]
    • Pour les mouvements en 8 directions

  3. Distance de Chebyshev :

    • h = max(|x1 - x2|, |y1 - y2|)
    • Pour les mouvements en 8 directions avec coût uniforme

#Complexité

  • Temps : O(b^d) où b est le facteur de branchement et d la profondeur de la solution
  • Espace : O(b^d) - garde tous les nœuds en mémoire

#Exercice : Implémentation avec pondérations

Modifiez l'algorithme A* pour gérer des grilles avec des cellules pondérées (coûts différents pour se déplacer dans chaque cellule).

#Instructions

  1. Modifiez la représentation de la grille pour inclure des poids
  2. Adaptez le calcul de g_score pour utiliser les poids
  3. Testez avec différentes heuristiques

#Exemple de code

pythonpython
1import heapq2from typing import List, Tuple, Dict, Set3 4def astar_pondere(grille: List[List[float]], depart: Tuple[int, int], arrivee: Tuple[int, int]) -> List[Tuple[int, int]]:5    """6    A* pour une grille avec des poids (coûts de déplacement)7    8    Args:9        grille: 2D liste de poids (0 = mur, >0 = coût de déplacement)10        depart: tuple (row, col) du point de départ11        arrivee: tuple (row, col) du point d'arrivée12    """13    14    def heuristique(a: Tuple[int, int], b: Tuple[int, int]) -> float:

#Applications

  1. Jeux vidéo : Pathfinding pour les personnages non-joueurs (NPC)
  2. Robotique : Planification de trajectoire pour les robots mobiles
  3. GPS : Calcul d'itinéraires optimaux
  4. IA : Résolution de puzzles et problèmes de recherche
  5. Réseaux : Routage dans les réseaux de communication

A* est l'un des algorithmes de recherche de chemin les plus utilisés grâce à son efficacité et son optimalité lorsqu'une heuristique admissible est utilisée.