INF 411 - TD 9
Finding Nemo


Votre opinion sur le cours de cette semaine : Votre opinion sur le TD précédent (TD8) :

 Login :  Mot de passe :

AVANT DE COMMENCER : Pour voir les animations, ouvrez une nouvelle page dans votre navigateur internet (Mozilla), tapez about:config dans la barre d'adresse, cherchez image.animation_mode dans la barre de recherche, double-cliquez sur le dernier once, changez-le par repeat, et redémarrez votre navigateur internet.

Préambule

En ce jour le monde aquatique est en émoi : le petit Nemo a été enlevé ! Marin, son pauvre papa, doit partir à sa recherche. Mais attention : l'océan est un vrai labyrinthe, peuplé de requins affamés ! Sauras-tu aider Marin à retrouver Nemo le plus rapidement possible, et en évitant les requins tant que faire se peut ?

Comme tout le monde le sait, l'océan se présente sous la forme d'un labyrinthe carré, comme dans l'image ci-dessus. Marin occupe initialement la case rouge, Nemo la case orange, et les requins les cases noires. Les cases gris foncé sont des falaises infranchissables.

En machine, l'océan est modélisé par une matrice pleine dont chaque cellule correspond à une case du labyrinthe. Les relations d'adjacence sont implicites, chaque cellule ayant par convention 4 voisines : une à gauche (ouest), une en dessous (sud), une à droite (est), une au dessus (nord). La classe Cell du fichier Cell.java implémente ce modèle. Notez que cette classe fournit les méthodes suivantes :

La structure et l'affichage de l'océan sont codés dans la classe Ocean, fournie dans le fichier Ocean.java. Vous pouvez l'exécuter si vous le désirez : cela affichera simplement l'image ci-dessus dans une fenêtre. Cette classe contient des constantes final Cell nemo, marlin qui codent les positions respectives de Nemo et de Marin (Marlin en anglais) au début du programme. La classe Ocean fournit par ailleurs les méthodes suivantes :

Par la suite on va associer une marque à chaque cellule de l'Ocean. Ces marques sont gérées de la manière suivante. Initialement, elles valent toutes -1, et on dit alors que les cellules ne sont pas marquées. Durant le déroulement du programme, certaines cellules seront marquées, c'est-à-dire que leurs marques prendront des valeurs ≥ 0 (la valeur exacte dépendra de l'algorithme). Après tout changement de marque, la fenêtre est mise à jour.

Pour aider Marin à retrouver Nemo, nous allons implémenter plusieurs parcours de graphe. Encore une fois, les sommets du graphe sont les cellules du labyrinthe, et les arêtes sont représentées implicitement par les relations d'adjacence ouest, sud, est, nord. Tout le code sera à écrire dans la classe Traversal.java. De plus les tests se font en exécutant cette classe et en commentant/décommentant les lignes écrites dans la méthode main.

1. Parcours en profondeur

Note : dans cette partie du TD, on ne se préoccupe pas des requins.

De tempérament obtus et inquiet, Marin a tendance à foncer droit devant sans trop réfléchir. Ce comportement typique de poisson clown sera modélisé par un parcours en profondeur, que vous implémenterez dans la méthode depthFirst de la classe Traversal. Pour cela vous pourrez introduire une méthode auxiliaire récursive static boolean depthFirstFrom(Cell c) qui renvoie true s'il existe un chemin de c à Nemo en ne passant que par des cases du labyrinthe non encore marquées.

Pour pouvoir suivre Marin à la trace, nous adopterons le code de couleurs suivant :

Cela nous conduit à l'algorithme récursif suivant :

Le comportement de l'algorithme est illustré dans l'animation ci-dessous. Vous voyez la couleur rouge apparaître quand la pile d'appels se remplit et les couleurs bleu et violet quand elle se vide. Pour obtenir une animation ralentie de votre algorithme, utilisez la méthode slow fournie dans le squelette de la classe Traversal dans votre méthode depthFirstFrom.

NB : l'ensemble des cellules déjà visitées est encodé dans les marques. Il n'est donc pas nécessaire de les stocker explicitement dans un HashMap.

Déposez ici le fichier Transversal.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2. Parcours en largeur

Note : dans cette partie du TD, on ne se préoccupe toujours pas des requins.

Bonne nouvelle ! Grâce à l'intervention de Dory, Marin va recevoir l'aide du banc de poissons argentés. Il va donc pouvoir les lancer dans toutes les directions à la fois, et le premier d'entre eux qui trouvera Nemo le signalera immédiatement. Ce processus sera modélisé par un parcours en largeur.

2.1 Parcours simple

Complétez la méthode breadthFirst de la classe Traversal. Cette méthode implémente (itérativement) un parcours en largeur et s'arrête dès que Nemo a été atteint. Plus précisément, on va marquer chaque case en parcourant le graphe en largeur et, pour cela, on stocke les cases qui sont en cours de traitement dans une file d'attente qui sera représentée par une LinkedList. On ne demande pas de reconstituer le chemin de Marin à Nemo pour l'instant. Le comportement de l'algorithme est illustré dans l'animation ci-dessous :

Déposez ici le fichier Transversal.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.2 Distances au point de départ

Complétez la méthode breadthFirstWithDistance de la classe Traversal. Cette méthode implémente le même parcours en largeur, mais augmente la valeur des marques au fur et à mesure du parcours. Plus précisément, la marque affectée à une cellule donnée doit correspondre à la distance (c'est-à-dire la longueur du plus court chemin) de cette cellule à la cellule initiale de Marin dans le labyrinthe. Pour ce faire, lorsque l'on marque une cellule avec une couleur n, les cellules voisines qui seront marquées à l'étape suivante seront marquées avec la couleur n+1 Attention : on demande un algorithme de complexité linéaire ! Son comportement est illustré dans l'animation ci-dessous (les couleurs changent au fur et à mesure que la distance à la cellule initiale augmente).

À la fin du parcours, affichez la distance entre Marin et Nemo dans la console. Vous devez obtenir la sortie suivante :


    Distance : 104

Déposez ici le fichier Transversal.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.3 Chemin le plus court

Complétez la méthode breadthFirstWithShortestPath de la classe Traversal. Cette méthode implémente le même parcours en largeur, mais affecte une marque à chaque cellule en fonction de la cellule qui la précède dans le parcours. Plus précisément, si on accède à une cellule par la gauche, on lui affecte la valeur 1. Par le bas, la valeur 2. Par la droite, la valeur 3. Par le haut, la valeur 4. Pour plus de lisibilité, ces valeurs sont stockées respectivement dans les constantes WEST, SOUTH, EAST, NORTH de la classe Traversal.

Complétez maintenant la méthode backTrack, qui part de la cellule de Nemo et suit les marques en sens inverse jusqu'à retrouver la cellule initiale de Marin. Chaque cellule traversée durant le backtracking sera coloriée en bleu, c'est-à-dire que sa marque sera ré-affectée à la valeur stockée dans le champ pathColor. La condition d'arrêt pourra faire appel à la méthode isMarlin de la classe Ocean. On pourra également s'aider des méthodes dynamiques west(), south(), east() et north() de la classe Cell qui renvoient respectivement la cellule de gauche, du bas, de droite et du haut.

La méthode backTrack sera appelée à la fin de la méthode breadthFirstWithShortestPath afin de marquer le chemin trouvé.

Le comportement de l'algorithme est illustré dans l'animation ci-dessous :

Déposez ici le fichier Transversal.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3. Éviter les requins

Note : ça y est, cette fois on se préoccupe des requins !

Changeons maintenant de labyrinthe. Pour cela, au début de la classe Traversal, modifiez la ligne

static final Ocean ocean = new Ocean(0);
en
static final Ocean ocean = new Ocean(1);
Le nouveau labyrinthe est identique à l'ancien, sauf qu'un morceau de mur a été remplacé par un requin. Si vous exécutez à nouveau la méthode breadthFirstWithShortestPath, vous constaterez qu'elle calcule un chemin passant par ce requin, tandis que d'autres chemins certes plus longs l'évitent. On désire maintenant modifier le parcours afin qu'il calcule un chemin rencontrant un minimum de requins.

Pour cela on va simplement remplacer la file utilisée dans le parcours par une file à double entrée (double-ended queue ou simplement dequeue en anglais). Le principe de cette file est d'avoir deux entrées, l'une par l'avant, l'autre par l'arrière, et une seule sortie par l'avant. Pour l'implémentation on utilisera encore une LinkedList.

Complétez la méthode avoidSharks de la classe Traversal. Le parcours en largeur est modifié comme suit : lorsqu'on se trouve à une cellule donnée et qu'on inspecte ses voisines accessibles, on insère celles qui ont des requins par l'arrière dans la file, et celles qui n'en ont pas par l'avant. Ainsi, les cellules du labyrinthe accessibles sans passer par aucun requin sont visitées en premier, puis c'est au tour des cellules accessibles en passant par un seul requin, puis en passant par 2 requins, et ainsi de suite. Ce comportement est illustré dans l'animation ci-dessous. La preuve est très similaire à celle de l'invariant de distance pour le parcours en largeur.

Vous pouvez maintenant tester votre code sur d'autres labyrinthes. Prenez par exemple celui obtenu en remplaçant new Ocean(1) par new Ocean(2) au début de la classe Traversal. Voici ci-dessous les comportements des divers parcours implémentés durant le TD sur ce labyrinthe (de haut en bas : parcours en profondeur, parcours en largeur classique, parcours en largeur modifié) :

Déposez ici le fichier Transversal.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4. Question complémentaire

Vous avez dû vous apercevoir que le parcours ainsi réalisé n'est ni un parcours en largeur, ni un parcours en profondeur, mais un mix des deux. Cela se voit bien sur les labyrinthes de la partie 3. La raison de ce comportement est qu'une dequeue est la concaténation d'une pile et d'une file. Lors du parcours, on vide d'abord la pile, puis, lorsque celle-ci est vide, on commence à vider la file qui elle-même se transforme alors en pile, et ainsi de suite. La conséquence de ce comportement est que le chemin obtenu en sortie n'est pas toujours le plus court parmi ceux qui rencontrent le moins de requins. C'est ennuyeux car le pauvre Marin risque de se fatiguer inutilement ! Comment remédier à ce défaut ? Plus précisément, comment modifier le parcours pour qu'il calcule un chemin de longueur optimale parmi ceux qui rencontrent le moins de requins, tout en restant de complexité linéaire ?

Déposez ici le fichier Transversal.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer


Voici une solution. Évidemment ce n'est pas la seule !