Simulic
Français

Recherche de chemin dans un labyrinthe – BFS, DFS et A*

InformatiqueAlgorithmique et résolution de problèmes17–18 ans

Chargement…

Partager Signaler un problème

Une grille avec des murs, une case de départ et une case d’arrivée. Les élèves choisissent le parcours en largeur (BFS, avec une file), le parcours en profondeur (DFS, avec une pile) ou A*, puis suivent chaque étape : les cases en attente sont numérotées dans l’ordre où elles seront retirées, les cases explorées sont colorées selon la distance, puis le chemin trouvé apparaît. Dessinez ou effacez des murs, déplacez le départ et l’arrivée, créez de nouveaux labyrinthes et comparez les cases explorées et la longueur du chemin de chaque algorithme.

Leçon : Algorithmes de recherche de chemin sur une grille : parcours en largeur (BFS), en profondeur (DFS) et A*

Ce qu’elle montre

Un labyrinthe est modélisé par une grille de cases ; chaque déplacement mène à une case voisine (haut, bas, gauche, droite), et tous coûtent autant. Le parcours en largeur range les cases en attente dans une file : il explore d’abord toutes les cases à un pas, puis à deux pas, et la première fois qu’il atteint l’arrivée, il tient un plus court chemin. Le parcours en profondeur utilise une pile et suit une direction jusqu’à être bloqué, si bien que son chemin est souvent plus long. A* classe les cases selon f = g + h, où h est la distance de Manhattan jusqu’à l’arrivée.

Mode d’emploi

Choisissez BFS, DFS ou A* et appuyez sur Pas à pas pour suivre les cases numérotées en attente, ou sur Lancer pour une animation. Comparez le tableau des résultats après chaque essai. Utilisez Dessiner des murs, Effacer des murs, Placer le départ et Placer l’arrivée pour modifier la grille, ou choisissez un Type de grille puis Nouvelle grille.

Paramètres modifiables

  • Algorithme BFS – parcours en largeur, DFS – parcours en profondeur, A* – guidé par une estimation de distance
  • Type de grille Labyrinthe à boucles, Obstacles aléatoires, Grille vide
  • Nombre de colonnes 11–41 cases
  • Murs supplémentaires retirés (labyrinthe) 0–60 %
  • Densité d’obstacles 0–45 %
  • Vitesse 1–100 pas/s

Questions à explorer

  1. Pourquoi le chemin trouvé par BFS est-il toujours un plus court chemin, alors que celui de DFS souvent pas ?
  2. Sur une grille vide, quel algorithme explore le moins de cases, et pourquoi ?
  3. Pouvez-vous construire un labyrinthe où DFS atteint l’arrivée en explorant moins de cases que BFS ?

Simulations associées