Laby : pour visualiser trois stratégies de recherche en
informatique
Ce programme dessine des labyrinthes aléatoires formés de cases
rectangulaires : on peut librement passer sur les cases jaunes, tandis que
les cases noires représentent des murs. Le but est d'aller automatiquement
de la case de départ (en bleu) à la case d'arrivée (en rouge).
L'utilisateur peut ajouter ou enlever des murs (au moyens de clics sur les
cases), et peut aussi déplacer les points de départ et d'arrivée (par des
glisser-déposer).
Trois stratégies de résolution systématique sont utilisées par le
programme.
- La résolution en profondeur, qui explore systématiquement l'arbre
des possibles branche par branche.
- La résolution heuristique, qui est une forme de résolution en
profondeur où les choix possibles sont guidés : on essaie en premier
les cases qui sont dans la direction de la case d'arrivée.
- La résolution en largeur, qui explore d'abord toutes les cases à une
certaine distance de la case de départ avant de passer aux cases
suivantes. Cette démarche est plus longue, mais nous assure de
découvrir une solution de longueur minimale (quand elle existe).
Veuillez noter que les cases visitées mais ne faisant pas partie de la
solution sont colorées en gris.
Pour télécharger le programme
Laby, cliquez sur l'image ci-dessus.
Mode d'emploi
Les glissières du haut permettent de spécifier les dimensions (horizontale
et verticale) du labyrinthe, le pourcentage de murs et le délai lors des
tentatives de solution. Notez que les changements des glissières (ainsi
que le redimensionnement de la fenêtre) sont répercutées immédiatement sur
le labyrinthe, sauf si on a cliqué sur le bouton "Non interactif", qui ne
s'avère vraiment utile que si votre ordinateur manque de rapidité. Dans
tous les cas, un clic sur le bouton "Créer labyrinthe" force la création
d'un nouveau labyrinthe.
Un clic sur un des boutons "Résolution..." provoque une recherche de
solution selon l'algorithme correspondant, recherche qui se termine par le
message approprié ("réussi" ou "impossible"). Pendant la recherche, seule
la glissière "Délai" reste active. À la fin, un clic sur le bouton "Remise
à zéro" permet d'effacer le chemin final (si obtenu) et les cases
visitées, sans pour autant changer de labyrinthe.
