Algorithme A* sur Grille
Recherche guidée par une heuristique
Enonce
Implémenter a_etoile(grille, depart, arrivee) sur une grille $n \times m$ où 0 est passable et 1 est un mur. Renvoyer la longueur du plus court chemin (ou -1 si inaccessible).
Utiliser la distance de Manhattan comme heuristique.
⚠ Bonus : Comparer le nombre de cases explorées par A* vs un BFS standard sur le même labyrinthe.
Signature attendue
def a_etoile(grille: list, depart: tuple, arrivee: tuple) -> int:Exemple
a_etoile([[0, 0, 1], [1, 0, 0], [0, 0, 0]], (0, 0), (2, 2))→4
📖 Rappel de cours
L'algorithme A* (« A star ») est une amélioration de Dijkstra qui exploite une heuristique $h(n)$ pour guider la recherche vers l'objectif. Pour chaque sommet $n$, il maintient :
- $g(n)$ : coût réel connu depuis le départ
- $h(n)$ : estimation heuristique du coût restant jusqu'à l'arrivée
- $f(n) = g(n) + h(n)$ : estimation totale du coût d'un chemin passant par $n$
A* explore en priorité les sommets de plus petite valeur $f(n)$ (tas binaire).
Heuristique admissible :
$h(n) \leq d^*(n, \text{arrivée})$ pour tout $n$ (l'estimation ne surestime jamais le coût réel restant). Si $h$ est admissible, A* trouve un plus court chemin optimal.
Distance de Manhattan :
Pour une grille avec déplacements à 4 directions, $h(i, j) = |i - i_{\text{cible}}| + |j - j_{\text{cible}}|$ est admissible et même consistante.
Si $h(n) = 0$ pour tout $n$, A* dégénère en Dijkstra. Plus $h$ est précise, moins de sommets sont explorés.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Diamètre d'un Arbre
- Algorithme de Floyd-Warshall
- Composantes Fortement Connexes (Kosaraju)
- Flot Maximal — Edmonds-Karp
- Critère de Delaunay (in-circle)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.