Aller au contenu principal

Algorithme A*

#Algorithme A* (A-star)

L'algorithme A* (A-star) est un algorithme de recherche de chemin très populaire en intelligence artificielle et en robotique. Il combine les avantages de l'algorithme de Dijkstra (optimalité) et de l'algorithme glouton (rapidité) en utilisant une heuristique pour guider la recherche.

#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.

#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.