TP5 : Déplacements dans un univers virtuel (partie 2)

Objectifs

Utiliser des structures de données d'une bibliothèque normalisée (les conteneurs de la Bibliothèque standard de C++).
Implémenter un type abstrait de données basé sur une représentation de graphe.
Implémenter un algorithme de recherche de plus court chemin dans un graphe.
Adapter cet algorithme pour trouver tous les plus courts chemins.

Contexte

Dans ce travail pratique, on reprend le contexte du TP2, où un agent explore un univers constitué de salles liées par des portails, avec quelques ajouts :

certaines cellules contiennent un diagonaliseur, qui une fois ramassé permet d'avancer en diagonale;
ramasser un diagonaliseur prend du temps, tout comme emprunter un portail.

Problématique

On voudrait cette fois trouver le chemin le plus rapide (le plus court en temps) pour se rendre d'une cellule à une autre. Comme nous l'avons vu, le nombre de chemins possibles peut être très grand, même dans un univers assez petit, donc calculer les longueurs de tous les chemins n'est pas une bonne option en terme d'efficacité. Par conséquent, plutôt que de tous les explorer, on peut représenter l'univers sous forme d'un graphe et utiliser un algorithme de calcul de plus court chemin.
En outre, comme il existe souvent plusieurs plus courts chemins entre deux cellules, on aimerait connaître le nombre de plus courts chemins. Pour le trouver, on peut adapter l'algorithme proposé au TP2.

Temps de déplacements

Par défaut, les déplacements unitaires possibles sont les mêmes que dans le TP2, donc à l'horizontale, à la verticale, et via les portails. Au départ, l'agent n'a pas de diagonaliseur sur lui. Quand il passe sur une cellule qui en contient un, il peut le ramasser et le garder avec lui jusqu'à destination. Avoir un diagonaliseur permet de se déplacer en diagonale, en plus des autres déplacements possibles. Par exemple, si l'agent a un diagonaliseur, à partir de la position (1,2) il peut se rendre directement (en un déplacement unitaire) aux positions suivantes : (0,1), (0,2), (0,3), (1,1), (1,3), (2,1), (2,2) et (2,3), sous réserve bien sûr que ces positions soient valides dans la salle courante. Chaque déplacement prend un certain temps :

se déplacer d'une cellule à une cellule adjacente dans la même salle prend 1 unité de temps, que ce soit à l'horizontale, à la verticale ou en diagonale;
ramasser un diagonaliseur prend 2 unités de temps;
emprunter un portail prend 3 unités de temps.

Même si ramasser un diagonaliseur prend du temps et peut nécessiter un détour, cela peut être avantageux. On peut l'illustrer par un exemple. La figure 1 montre un plus court chemin de la position (3,0) dans la salle 0 (cellule S) à la position (2,3) dans la salle 2 (cellule E), en l'absence de diagonaliseur. Le déplacement total se fait en 13 unités de temps (7 flèches à 1 unité + 2 portails à 3 unités chacun).

Supposons maintenant que l'univers contienne un diagonaliseur en position (2,1) dans la salle 0. Alors un plus court chemin de S à E, comme celui de la Figure 2, ne coûte que 12 unités de temps (7 flèches à 1 unité + diagonaliseur à 2 unités + 1 portail à 3 unités).

Certains univers contiennent des diagonaliseurs et d'autres non (comme pour les portails).

Graphe d'états

Comme les voisins d'une cellule ne sont pas les mêmes selon que l'agent possède un diagonaliseur ou non, une astuce consiste à "dédoubler" l'univers : on a deux sommets pour chaque cellule. En d'autres termes, un état de l'agent est caractérisé par sa position ainsi que le fait de posséder ou non un diagonaliseur. Le lien entre les deux copies de l'univers se fait comme suit

Au départ, on est dans la partie sans diagonaliseur.
Tant qu'on n'a pas de diagonaliseur, on ne peut pas accéder aux états qui en ont un, donc on se déplace de cellule en cellule sans diagonaliseur.
Quand on ramasse un diagonaliseur, on passe dans la copie de l'univers où tous les états ont un diagonaliseur ; c'est le seul moyen d'accéder à ces états.
Deux états correspondent à la cellule d'arrivée : avec ou sans diagonaliseur.

Calcul de tous les plus courts chemins

L'algorithme de Dijkstra permet de calculer un seul plus court chemin entre deux sommets donnés, alors qu'une requête nbPlusCourts doit trouver tous les plus courts chemins et retourner leur nombre. L'algorithme du TP2 explore toutes les possibilités de chemins possibles, et incrémente un compteur chaque fois qu'on trouve un chemin. Pour trouver tous les plus courts chemins, on peut exploiter l'algorithme de Dijkstra et adapter l'algorithme du TP2 en utilisant la stratégie suivante (de "séparation et évaluation progressive", ou branch and bound) :

Si le temps nécessaire pour se rendre à un état (via le chemin courant) dépasse le temps d'un plus court chemin, alors on abandonne cette piste (ça ne sert à rien de continuer).
Sinon, on poursuit l'exploration récursivement. Bien sûr, on ne compte que les chemins qui ont la bonne longueur.

Structure du programme

Pour bien amorcer ce travail, il est fortement recommandé de commencer avec le squelette de départ fourni dans tp5.zip. Vous pouvez modifier ces fichiers autant que vous le désirez. Toutefois, pour la correction automatique, vous devez préserver la syntaxe d'appel du programme et ses formats d'entrée et de sortie.

Syntaxe d'appel du programme tp5

Le programme tp5 doit pouvoir être lancé en ligne de commande avec la syntaxe suivante.

./tp5 -c univers.txt [graphe.txt]
./tp5 graphe.txt [requetes.txt]

où :

l'option -c indique que l'on veut convertir un univers en graphe;
le fichier univers.txt décrit un univers comme dans le TP2, avec ajout des diagonaliseurs;
le fichier graphe.txt contient une liste de sommets suivie d'une liste d'arcs, le tout formant un graphe;
le fichier requetes.txt spécifie les requêtes à traiter.

Le programme tp5 doit lire depuis un flux d'entrée (std::istream). Selon le mode d'exécution, les résultats produits par votre programme doivent être écrits :

sur le flux de sortie qui est déjà en paramètre de la fonction pour la conversion en graphe;
dans la sortie standard (stdout) à l'aide du flux de sortie C++ std::cout pour le traitement de requêtes.

À noter que le squelette fourni implémente déjà cela dans le cas où on traite des requêtes. Dans le mode conversion, l'écriture se fera dans graphe.txt s'il est donné comme argument, sinon dans le terminal (sortie standard). Cet aspect est déjà implémenté.

Format d'un fichier d'univers

Un fichier d'univers contient une liste de salles, suivie d'une liste de portails, puis d'une liste de diagonaliseurs. Chaque cellule suit la même syntaxe qu'au TP2. Par exemple, le fichier figure2-univers.txt ci-bas décrit l'univers de l'exemple de la Figure 2.

carre 4
diamant 5
triangle 7
-----
0 (1,0) <--> 1 (0,2)
0 (0,3) <--> 2 (0,6)
1 (3,3) <--> 2 (3,3)
-----
0 (2,1)

Les contraintes sur les numéros de salles restent les mêmes qu'au TP2.

Format d'un fichier de graphe

Un fichier de graphe contient une liste de sommets, suivie d'une liste d'arcs :

0 : 0 (0,0) -
1 : 0 (0,1) -
...
n : 0 (0,0) D
n+1 : 0 (0,1) D
...
-----
0 1 : 1
0 2 : 1
...

Pour chaque sommet, son identifiant est suivi de ":" puis de l'état correspondant, c'est-à-dire la cellule et un caractère 'D' ou '-' selon que l'on possède un diagonaliseur ou non. Les identifiants des sommets sont les entiers successifs de 0 à 2n-1, où n est le nombre de cellules dans l'univers. Pour chaque arête, on a les deux identifiants de noeuds séparés par un espace (départ puis arrivée de l'arête), puis ":" et le temps du déplacement unitaire correspondant. Les fichiers mini-univers.txt et mini-graphe.txt montrent un exemple d'univers avec le graphe à générer.

Important : pour des fins de correction, il faut

avoir en premier tous les états sans diagonaliseur, puis tous ceux avec diagonaliseur, dans le même ordre, de sorte que les identifiants d'une même cellule sont k et n+k (respectivement sans et avec diagonaliseur);
respecter l'ordre lexicographique pour les coordonnées;
respecter l'ordre lexicographique pour les arcs.

Format d'un fichier de requêtes

Il y a deux types de requêtes, avec la même syntaxe : nom_requete ":" S ">" E, où S et E sont les cellules de départ et d'arrivée (comme dans les figures ci-dessus). Exemple :

  plusCourt    : 0 (3,0) > 2 (2,3)
  nbPlusCourts : 0 (3,0) > 2 (2,3)

Format de sortie

Une requête "plusCourt" doit trouver un plus court chemin de S à E, et afficher le temps total suivi de ":" puis la liste des états constituant le chemin, séparés par "->"
Une requête "nbPlusCourts" doit afficher le nombre de plus courts chemins de S à E

Par exemple, pour l'univers de la Figure 1 (sans diagonaliseur), les deux requêtes ci-dessus affichent :

13 : 0 (3,0) - -> 0 (2,0) - -> 0 (1,0) - -> 1 (0,2) - -> 1 (1,2) - -> 1 (2,2) - -> 1 (2,3) - -> 1 (3,3) - -> 2 (3,3) - -> 2 (2,3) -
3

Et pour l'univers de la Figure 2 (avec diagonaliseur) on obtient :

12 : 0 (3,0) - -> 0 (2,0) - -> 0 (2,1) - -> 0 (2,1) D -> 0 (1,2) D -> 0 (0,3) D -> 2 (0,6) D -> 2 (1,5) D -> 2 (2,4) D -> 2 (2,3) D
6

S'il n'y a pas de chemin, on affiche -1 : S , où S est la cellule de départ.

Contraintes

Bibliothèque standard C++ obligatoire

Contrairement aux précédents TPs, vous devez maintenant utiliser les conteneurs de la Bibliothèque standard de C++ (Standard Template Library): stack, list, vector, priority_queue, set, map, etc. Cette contrainte vise à mettre en pratique l'utilisation d'une bibliothèque normalisée.

Évidemment, vous pouvez créer vos propres structures lorsque cela est justifié. Par exemple, si vous avez besoin d'un monceau de base, vous devriez normalement utiliser std::priority_queue. Par contre, si vous avez besoin d'une fonctionnalité non offerte dans std::priority_queue, comme l'opération «réduire clé», vous pouvez créer et utiliser votre propre classe Monceau. Ces cas doivent être brièvement justifiés dans le code source.

Environnement de développement

Relisez les Politiques et les directives sur les outils informatiques dans le cours INF3105. Votre TP5 doit pouvoir être compilé avec g++ version 11 ou 13 (versions installées sur le serveur java.labunix.uqam.ca).

Tests

Des tests sont disponibles dans tests.zip.

Pour lancer les tests, lancez le script evaluer.py sur une machine Linux. Vous pouvez par exemple vous connecter sur le serveur java :

ssh codeMS@java.labunix.uqam.ca

Que vous soyez sur java ou votre propre machine Linux, suivez les instructions suivantes :

cd tp5
wget http://cria2.uqam.ca/INF3105/tp5/tests.zip  // si vous n'avez pas encore récupéré le fichier zip
make
unzip tests.zip
cd tests
g++ -O3 -o valideur valideur.cpp
cd ..
./tests/evaluer.py

Voici un exemple de résultat d'exécution (sur java) :

Évaluation du programme tp5 d'INF3105
Mode: Mode.etudiant
Système d'exploitation: Linux
CPU:  Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz
Nom_test	CPU	Mém	PCC	TempsOK	ChemOK	nbPCC	nbPCCOK
C1a-req10  	0.01	4316	10	10	10	10	10
C1a-req100 	0.05	4392	100	100	100	100	100
C1a-req1000	0.51	4232	1000	1000	1000	1000	1000
C1b-req10  	0.01	4196	10	10	10	10	10
C1b-req100 	0.04	4252	100	100	100	100	100
C1b-req1000	0.43	4316	1000	1000	1000	1000	1000
C1c-req10  	0.01	4364	10	10	10	10	10
C1c-req100 	0.07	4468	100	100	100	100	100
C1c-req1000	0.66	4396	1000	1000	1000	1000	1000
C1d-req10  	0.00	4132	10	10	10	10	10
C1d-req100 	0.03	4268	100	100	100	100	100
C1d-req1000	0.32	4120	1000	1000	1000	1000	1000
C1e-req10  	0.05	8544	10	10	10	10	10
C1e-req100 	0.29	8476	100	100	100	100	100
C1e-req1000	2.66	8372	1000	1000	1000	1000	1000
C2a-req10  	0.01	4400	10	10	10	10	10
C2a-req100 	0.08	4532	100	100	100	100	100
C2a-req1000	0.71	4484	1000	1000	1000	1000	1000
C2b-req10  	0.01	4584	10	10	10	10	10
C2b-req100 	0.09	4588	100	100	100	100	100
C2b-req1000	0.92	4632	1000	1000	1000	1000	1000
C2c-req10  	0.00	4268	10	10	10	10	10
C2c-req100 	0.06	4308	100	100	100	100	100
C2c-req1000	0.65	4208	1000	1000	1000	1000	1000
C2d-req10  	0.01	4072	10	10	10	10	10
C2d-req100 	0.05	4152	100	100	100	100	100
C2d-req1000	0.56	4168	1000	1000	1000	1000	1000
C2e-req10  	0.06	7360	10	10	10	10	10
C2e-req100 	0.43	7732	100	100	100	100	100
C2e-req1000	4.47	7684	1000	1000	1000	1000	1000
E1b-req10  	0.56	64300	10	10	10	0	0
E1b-req100 	2.70	64228	100	100	100	0	0
E1b-req1000	24.01	64668	1000	1000	1000	0	0
E2a-req10  	0.75	53692	10	10	10	0	0
E2a-req100 	4.88	53940	100	100	100	0	0
E2a-req1000	48.03	54104	1000	1000	1000	0	0
G1a-req10  	0.25	10044	0	0	0	10	10
G1a-req100 	1.61	10328	0	0	0	100	100
G1a-req1000	19.30	10264	0	0	0	1000	1000
G1b-req10  	0.36	40588	0	0	0	10	10
G1b-req100 	30.65	40852	0	0	0	100	100
G1b-req1000	384.36	40940	0	0	0	1000	1000
G2a-req10  	15.87	46604	0	0	0	10	10
G2a-req100 	524.07	46944	0	0	0	100	100

Notez que ces temps ont été obtenus à partir d'une implémentation non optimisée. La meilleure solution (parmi les vôtres) servira de référence.

Signification des colonnes:

CPU : Temps CPU (mode utilisateur) en secondes.
Mém : Taille de la mémoire résidente reportée par time.
PCC : Nombre de requêtes plusCourt dans le fichier.
TempsOK : Nombre de requêtes plusCourt pour lesquelles le temps du plus court chemin est correct.
ChemOK : Nombre de requêtes plusCourt qui affichent correctement un plus court chemin.
nbPCC : Nombre de requêtes nbPlusCourts dans le fichier.
nbPCCOK : Nombre de requêtes nbPlusCourts qui comptent correctement le nombre de plus courts chemins.

Remise

Vous devez remettre votre travail au plus tard le 13 août 2024 à 23h59m EST (heure de Montréal) via le formulaire de remise du TP5.

Vous pouvez soumettre votre TP autant de fois que vous voulez. Seule la dernière soumission sera considérée.

Évaluation

Ce travail pratique compte pour 10% de la note finale.

Grille de correction

Critère	Description	Points
A.	Respect des directives pour la remise. Fichiers sources seulement (ex.: .h, .cpp, Makefile). Aucun fichier source manquant (les fichiers fournis doivent être soumis, même si non modifiés). Aucun fichier binaire (ex.: .o, .obj, .gch, exécutable, etc.). Aucun fichier test. Aucun fichier caché. Aucun sous-dossier: tous les fichiers doivent être à la racine du fichier ZIP. Remise par le formulaire Web. Pas de remise par courriel. Compilable avec `make` sans modification. Exécutable sans modification. Auto-évaluation: la valeur choisie (Correctement / Partiellement / Aucunement) est correcte.	10
B.	Conversion en graphe Le programme produit le bon fichier graphe.txt quand on lui donne en entrée un fichier univers.txt à convertir.	20
C.	Fonctionnement correct du calcul de chemins Le programme retourne les bons résultats avec la requête `plusCourt` quand on lui donne en entrée un fichier de graphe correct C1 : pour un univers sans diagonaliseur. (30 points) C2 : pour un univers avec diagonaliseur(s). (15 points)	45
D.	Fonctionnement correct du calcul du nombre de plus courts chemins Le programme retourne les bons résultats avec la requête `nbPlusCourts`.	15
E.	Efficacité Temps raisonnables pour calculer des requêtes `plusCourt` et `nbPlusCourts`.	10
	Total	100

Pénalités

Pour les cas problématiques, jusqu'à 2 points peuvent être retranchés pour la qualité de la langue et de la présentation.
Retard: 5% de la note maximale par heure de retard.

Crédits et licences

Le contenu de ce TP a été initialement écrit en collaboration avec Carole Porrier.