Question transversaleMathsNSIGraphes et réseaux

Comment un programme trouve-t-il le chemin le plus court pour sortir d'un labyrinthe ?

Q: Combien de passages dans une grille de n × n cases ?

$n(n-1)$ horizontaux et $n(n-1)$ verticaux : $2n(n-1)$.

Le parcours en largeur explore les cases par couches : toutes celles à distance 1, puis 2, etc. La première fois qu'il atteint la sortie, il a trouvé un plus court chemin. Pour un labyrinthe de 20 × 20 cases, il visite au plus 400 cases et examine au plus 760 passages.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Enfant, je résolvais les labyrinthes des magazines en suivant le mur avec mon doigt. En NSI, nous avons programmé un robot qui sort d'un labyrinthe, et le professeur nous a demandé de trouver le chemin le plus court, pas seulement un chemin. J'ai découvert que deux parcours de graphes donnent des résultats très différents, et j'ai voulu comprendre pourquoi.

L'enjeu et les notions du programme

Modéliser un labyrinthe par un graphe et justifier par récurrence que le parcours en largeur donne les distances minimales.

Mathématiques

Raisonnement par récurrence (terminale)
Dénombrement des cases et des passages d'une grille (terminale)
Distance dans un quadrillage (seconde)

Numérique et sciences informatiques

Parcours en largeur et en profondeur d'un graphe (terminale)
Structures de file et de pile (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Un labyrinthe est un graphe : chaque case est un sommet, chaque passage ouvert entre deux cases voisines est une arête. Problématique : quel parcours de ce graphe garantit le chemin le plus court vers la sortie ?
2. NSI : largeur contre profondeur
3,5 min
Le parcours en profondeur avance le plus loin possible, puis revient en arrière (une pile). Il trouve la sortie, mais souvent par un long détour : comme suivre un mur.
Le parcours en largeur utilise une file : on y place l'entrée ; tant que la file n'est pas vide, on retire la première case et on ajoute à la fin ses voisines non encore visitées, en notant leur distance (distance de la case + 1) et leur prédécesseur. Les cases sortent de la file par distance croissante, couche par couche, comme une onde qui se propage. Quand la sortie est atteinte, on remonte les prédécesseurs pour obtenir le chemin.
3. Mathématiques : correction et coût
3,5 min
Propriété $P (k)$ P(k) : toutes les cases à distance $k$ k de l'entrée reçoivent la distance $k$ k, et avant toute case plus lointaine. Initialisation : l'entrée a la distance 0. Hérédité : une case à distance $k + 1$ k+1 a un voisin à distance $k$ k, traité avant toutes les cases plus lointaines (hypothèse de récurrence) ; elle est donc découverte depuis ce voisin avec la distance $k + 1$ k+1, et pas avant, car aucune case à distance $k - 1$ k-1 ou moins n'est sa voisine.
Coût pour une grille de $20 \times 20$ 20×20 : 400 cases. Chaque case a au plus 4 voisines ; le nombre de passages possibles est $2 \times 20 \times 19 = 760$ 2×20×19=760 (horizontaux et verticaux). Chaque case entre une fois dans la file, chaque passage est examiné au plus deux fois : de l'ordre de $400 + 2 \times 760$ 400+2×760 opérations, instantané.
4. Conclusion
1,5 min
Le parcours en largeur trouve le plus court chemin parce qu'il explore les cases par distance croissante, ce qu'une récurrence démontre. Son coût est proportionnel au nombre de cases et de passages. J'ouvre sur l'algorithme de Dijkstra, qui généralise cette idée quand les passages ont des longueurs différentes.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

file : entr \overset{e}{ˊ} e (0) \to couche 1 \to couche 2 \to \dots \to sortie (d) file : entrée (0)\to couche 1\to couche 2\to\dots\to sortie (d) 20 \times 20 = 400 cases 2 \times 20 \times 19 = 760 passages co \overset{u}{ˆ} t \approx n + 2 m 20\times20=400 cases 2\times20\times19=760 passages coût \approx n+2m

Conclusion : la réponse à la question

Pour sortir au plus court, il faut explorer en largeur : la file impose l'ordre des distances croissantes. Le parcours en profondeur trouve une sortie, le parcours en largeur trouve la meilleure.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Pourquoi une file et pas une pile ?

La file fait sortir les cases dans l'ordre où elles ont été découvertes, donc par distance croissante.

Combien de passages dans une grille de n × n cases ?

$n (n - 1)$ n(n-1) horizontaux et $n (n - 1)$ n(n-1) verticaux : $2 n (n - 1)$ 2n(n-1).

La méthode de la main sur le mur marche-t-elle toujours ?

Elle sort d'un labyrinthe dont les murs sont tous reliés au bord, mais ne donne pas le plus court chemin.

Que faire si les passages ont des longueurs différentes ?

Utiliser l'algorithme de Dijkstra, qui remplace la file par une file de priorité.

Pourquoi marquer les cases visitées ?

Pour ne pas les traiter plusieurs fois et ne pas tourner en rond.

Les pièges qui coûtent des points

Croire que tout parcours donne le plus court chemin.
Oublier de marquer les cases visitées.
Confondre nombre de cases et nombre de passages.

Revoir les notions

Autres questions : graphes et réseaux

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →