Robot et labyrinthe - Lycée Marguerite de Navarre (Bourges) Lycée Alain Fournier (Bourges)

Titre du sujet
Robot et labyrinthe
Établissement
Lycée Marguerite de Navarre (Bourges)
Année
2017-2018
Etablissement(s) jumelé(s)
Lycée Alain Fournier (Bourges)
Résumé
On considère un robot pouvant se déplacer dans 4 directions (N, S, E,O) et un labyrinthe quelconque composé de cases vides et de murs (un mur a la même dimension qu’une case vide).
1-Pouvez-vous proposer un algorithme permettant au robot de sortir de n’importe quel labyrinthe ?
2-Pouvez-vous quantifier le temps moyen qu’il va falloir au robot pour sortir ?
3-Imaginez maintenant que le robot dispose de la possibilité de voir le bout d’un couloir, et également se rappelle de la partie du
labyrinthe qu’il a déjà parcouru. Pouvez-vous améliorer votre
algorithme ?