Quand A* garantit-il un chemin optimal ?

Quand l’heuristique ne surestime jamais le vrai coût restant (elle est admissible) et, pour les implémentations efficaces avec h consistante, que les égalités sont bien tranchées. Manhattan est admissible sur une grille uniforme 4-connexe ; l’octile convient aux pas diagonaux 8-connexes.

En quoi la recherche gloutonne au meilleur d’abord diffère-t-elle de A* ?

Le glouton ouvre les nœuds seulement selon h et ignore g, donc il peut foncer vers le but à travers un terrain cher. A* équilibre le coût déjà dépensé g et l’estimation du reste h via f = g + h.

Pourquoi regarder l’ensemble ouvert et l’ensemble fermé ?

L’ensemble ouvert est la frontière des candidats ; le fermé a déjà été développé. Leur croissance montre quelle part de la carte chaque algorithme explore avant de figer le chemin.

A* et Dijkstra (grille)

Grille 40×28 : A*, Dijkstra ou recherche gloutonne ; heuristiques, 4- et 8-connexité, murs et cellules coûteuses ; coloration des ensembles ouvert et fermé.

À propos du modèle

A* et Dijkstra cherchent un chemin de faible coût du départ au but sur une grille 40×28. On compare l’algorithme de Dijkstra (coût uniforme), A* avec f = g + h et la recherche gloutonne au meilleur d’abord, avec les heuristiques de Manhattan / octile / euclidienne et la 4- ou 8-connexité. Murs et cellules coûteuses se dessinent à la main ; on voit croître l’ensemble ouvert et l’ensemble fermé. A* est le plus efficace parmi les algorithmes optimaux si h est admissible ; Dijkstra est le cas h = 0 ; le glouton ne suit que h et peut être rapide, mais sous-optimal. Recherche discrète sur grille, sans réparation itérée du chemin, sans points de saut ni graphes de visibilité continus. On fait varier l’algorithme, l’heuristique et la connexité : le dessin de l’expansion et le coût du chemin.

Public : Algorithmes et planification de chemins : A*, Dijkstra, heuristiques sur grille.

Notions clés

recherche A*
algorithme de Dijkstra
heuristique
ensemble ouvert
recherche de chemin sur grille
heuristique admissible

Comment ça marche

Sur une grille 40×28, on cherche un chemin du départ au but. Dijkstra développe selon le coût g, A* selon f = g + h, le glouton seulement selon h. Heuristiques de Manhattan, octile et euclidienne ; 4- ou 8-connexité. À l’écran : ensembles ouvert et fermé, et le chemin trouvé.

Formules

A*: f(n) = g(n) + h(n), open := min-heap by f

Manhattan h = |Δr| + |Δc|; Octile h = max + (√2−1)·min

Questions fréquentes

Quand A* garantit-il un chemin optimal ?: Quand l’heuristique ne surestime jamais le vrai coût restant (elle est admissible) et, pour les implémentations efficaces avec h consistante, que les égalités sont bien tranchées. Manhattan est admissible sur une grille uniforme 4-connexe ; l’octile convient aux pas diagonaux 8-connexes.
En quoi la recherche gloutonne au meilleur d’abord diffère-t-elle de A* ?: Le glouton ouvre les nœuds seulement selon h et ignore g, donc il peut foncer vers le but à travers un terrain cher. A* équilibre le coût déjà dépensé g et l’estimation du reste h via f = g + h.
Pourquoi regarder l’ensemble ouvert et l’ensemble fermé ?: L’ensemble ouvert est la frontière des candidats ; le fermé a déjà été développé. Leur croissance montre quelle part de la carte chaque algorithme explore avant de figer le chemin.

Poursuivez avec des thèmes proches de cette catégorie — ou les 48 de «Ingénierie».

Toute la catégorie →

NouveauCollège–lycée

Labyrinthes et A*

Lancer la simulation

Labyrinthes parfaits sur une grille 40×28 : parcours récursif, Wilson, Eller ou Prim aléatoire ; résolution par A* (Manhattan, 4-voisinage). On peut dessiner des murs et déplacer le départ et le but.

NouveauCollège–lycée

Arbre couvrant de poids minimal (Prim et Kruskal)

Lancer la simulation

Points aléatoires dans le plan, graphe complet à poids euclidiens : Prim pas à pas depuis une racine, ou Kruskal avec ensembles disjoints ; on compare le poids total.

NouveauCollège–lycée

Planificateur RRT (grille)

Lancer la simulation

La même carte de murs 40×28 : échantillons aléatoires, nœud le plus proche, pas avec test de collision, biais d’échantillonnage vers le but ; bouton pour comparer à A*.

NouveauCollège–lycée

Flèche d’une poutre : méthode de la force unité

Lancer la simulation

Poutre d’Euler–Bernoulli sur appuis simples, force P et charge w : flèche analytique contre l’intégrale des travaux virtuels ∫Mm/EI dx.

NouveauCollège–lycée

Réservoir à paroi mince sous pression

Lancer la simulation

Contraintes de membrane dans un cylindre et une sphère : circonférentielle σθ, longitudinale σz, équivalent de von Mises, contrôle r/t et coefficient de sécurité à l’écoulement.

NouveauCollège–lycée

Train planétaire

Lancer la simulation

Solaire, satellites, couronne intérieure : formule de Willis ; on bloque la couronne, le solaire ou le porte-satellites et l’on compare les rapports.

A* et Dijkstra (grille)

À propos du modèle

Comment ça marche

Formules

Questions fréquentes

Simulations voisines

Labyrinthes et A*

Arbre couvrant de poids minimal (Prim et Kruskal)

Planificateur RRT (grille)

Flèche d’une poutre : méthode de la force unité

Réservoir à paroi mince sous pression

Train planétaire

A* et Dijkstra (grille)

À propos du modèle

Comment ça marche

Formules

Questions fréquentes