DM 1 : Visite touristique de Paris en Métro
Philippe Chassignet et Dominique Rossin
Dans ce devoir à la maison, nous continuons à travailler sur le plan
du métro parisien. Nous voulons trouver un plus court chemin
entre deux stations données. Ce plus court chemin peut être vu de
différentes manières:
-
Plus petit nombre de stations intermédiaires
- Prise en compte des temps de trajet
- Prise en compte des temps de trajet et des temps de correspondance
La partie 1 bien traitée suffira pour obtenir la note A.
Ce devoir doit être rendu au plus tard le 24 mars 2004.
La remise des travaux se fera par la commande:
/users/profs/info/Depot/INF_431/deposer programmes DM_1
groupe
où programmes doit être remplacé par la liste des noms des
fichiers contenant les sources de vos programmes (terminaison en .java)
et groupe doit être remplacé par votre numéro de groupe (de 1 à 10).
Pour faciliter la correction, il est demandé que l'exécution se fasse
comme il est précisé dans l'énoncé de chaque question.
1 Plus petit nombre de stations
On part du TD 1 avec les mêmes classes et structures de données. On
cherche le plus court chemin entre deux stations en minimisant le
nombre de stations intermédiaires.
À l'aide d'un parcours en largeur du graphe représentant le métro, on
écrit la classe Situ1 qui, à partir de deux stations de départ
et d'arrivée, calcule un plus court chemin:
java Situ1 lignes.data depart arrivee
où lignes.data est le nom du fichier
contenant le plan du métro, depart le numéro de la station
de départ et arrivee le numéro de la stations d'arrivée.
La sortie de votre programme devra être de la forme:
De la station depart a la station arrivée
-
Prendre la ligne nomLigne direction terminusLigne
- Changer à la station nomStation
- Prendre la ligne nomLigne direction terminusLigne
- ...
2 Prise en compte de la distance euclidienne
À présent, nous tenons compte du temps de parcours d'une station à une
autre. Une première approximation du temps de parcours est
proportionnelle à la distance parcourue entre ces stations.
À cette fin, on rajoute dans la classe Station située dans
le fichier MetroUtil.java la fonction suivante:
static final int COUT_ARRET = 10;
static final double COEFF_DISTANCE = 1.5;
static int tempsParcours(int ori, int dst) {
int xOri = Station.stations[ori].x, yOri = Station.stations[ori].y;
int xDst = Station.stations[dst].x, yDst = Station.stations[dst].y;
int dX = xDst - xOri;
int dY = yDst - yOri;
double dist = Math.sqrt( dX*dX + dY*dY );
return COUT_ARRET+(int)(COEFF_DISTANCE*dist);
}
Ainsi, un appel à Station.tempsParcours(3,5) renvoie le temps mis par
le métro pour aller directement de la station 3 à la station 5. Attention,
cette fonction ne vérifie pas si les stations sont reliées entre elles. Elle
renvoie un temps qui est la somme du temps de parcours effectif du
métro (dépendant de la distance euclidienne entre les stations) et
d'un temps d'arrêt à la station.
Ainsi, le plus court chemin entre deux stations ne sera plus cette
fois un chemin qui minimise le nombre de stations, mais qui minimise le
temps de parcours. Les correspondances ne sont toujours pas prises en
compte (temps de correpondance nul).
Le calcul du plus court chemin sera fait par l'algorithme de Dijkstra
simplifié, c'est-à-dire que l'on utilisera un tableau au lieu de faire
une file de priorité (cf. cours 3). On écrit la classe Situ2
qui, à partir de deux stations de départ et d'arrivée, calcule un plus
court chemin:
java Situ2 lignes.data depart arrivee
où lignes.data est le nom du fichier
contenant le plan du métro, depart le numéro de la station
de départ et arrivee le numéro de la stations d'arrivée.
La sortie de votre programme devra être comme dans la section précédente.
3 Première extension -- Mise en oeuvre d'une file de priorité
Les deux extensions proposées sont indépendantes et peuvent être
traitées dans un ordre quelconque. La première extension consiste à
mettre en oeuvre une file de priorité pour l'algorithme de
Dijkstra.
Dans notre cas, un élément de la file de priorité est une paire qui
associe un numéro de station à sa priorité, c'est-à-dire le temps de
parcours pour cette station. L'élément en tête de la file, le plus
prioritaire donc, est celui ayant le plus petit temps de parcours
à partir de la station de départ.
Une file de priorité supporte deux opérations:
-
ajouter un élément dans la file, il sera traité en fonction de sa
priorité, c'est-à-dire une procédure
static void ajouter(int numero, int priorite, FileP q)
- sortir l'élément en tête de file, soit une fonction
static int sortir(FileP q)
qui retourne le numéro de cet élément.
La structure de tas (heap en anglais) permet de réaliser chacune de ces
deux opérations en temps O(logn), n étant le nombre
d'éléments dans la file, majoré ici par le nombre de sommets du graphe.
Rappelons qu'un tas de n éléments est un arbre binaire complet rangé
dans un tableau t dont on utilise alors les indices de 0 à
n-1.
La racine est t[0].
Pour un élément t[i], les fils gauche et droit,
s'ils existent, sont respectivement t[2*i+1] et t[2*i+2].
Pour un élément t[i] (i > 0), le père est t[(i-1)/2].
De plus, un tas maintient une relation d'ordre partiel entre père et
fils.
Dans notre cas, le père aura toujours un temps de parcours inférieur ou
égal à ceux de ses fils.
L'élément le plus prioritaire de tous se trouve donc à la racine.
Pour ajouter un élément dans un tas, de capacité actuelle n, on
commence par le placer en t[n], puis on procède à des échanges en
le remontant vers la racine, jusqu'à satisfaire de nouveau la relation
d'ordre.
Pour sortir l'élément de tête d'un tas, de capacité actuelle n,
on récupère t[0], on place t[n-1] en t[0], puis on
procède à des échanges avec le plus prioritaire des deux fils, en
redescendant dans l'arbre jusqu'à satisfaire de nouveau la relation d'ordre.
Remarquons que ces deux opérations reviennent à se déplacer
seulement le long d'une branche, d'où leur coût en O(logn).
La difficulté de l'algorithme de Dijkstra vient de ce qu'il nécessite
une troisième opération sur la file de priorité :
-
modifier la priorité d'un élément donné par son numéro, c'est-à-dire
une procédure static void modifier(int numero, int priorite, FileP q)
La file doit mémoriser la position de chaque élément dans le tas.
Pour localiser un élément dans le tas, à partir de son numéro (de sommet),
il faut mémoriser son indice dans le tableau t à l'aide d'un
tableau annexe. Une modification
revient à améliorer la priorité (ie. réduire le temps de parcours), on
procéde alors à des échanges en remontant vers la racine, comme pour
un ajout, sauf que l'on part de la position donnée par l'indice
mémorisé. Il faut bien sûr que les opérations d'échange entre père et
fils mettent à jour les indices mémorisés pour assurer la cohérence de
la structure.
Pour ne pas avoir à se préocupper si l'élément est présent ou non, on
commencera par remplir la file avec tous les éléments, initialisés à
une priorité ad-hoc. Ensuite, l'algorithme de Dijkstra nous assure
qu'on ne cherchera à modifier que des éléments encore présents dans la
file.
On écrit la classe Situ3 qui, à partir de deux stations de
départ et d'arrivée, calcule un plus court chemin:
java Situ3 lignes.data depart arrivee
avec le même format de sortie que dans les deux
premières sections.
4 Deuxième extension -- Prise en compte des temps de correspondance
Par exemple, le plus court chemin (le plus rapide) de Bastille à
République consiste à prendre la ligne 8 et le plus court chemin de
République à Jacques Bonsergent consiste à prendre la ligne 5.
Pourtant, le plus court chemin de Bastille à Jacques Bonsergent consiste
à prendre uniquement ligne 5 pour éviter le changement de ligne.
Cet exemple nous montre qu'il faut repenser la structure du
graphe. On éclate chaque sommet en plusieurs sommets pour distinguer :
-
un sommet coeur de station, supposé être le point de concentration
de tous les couloirs,
- un sommet pour chaque quai, ie. chaque ligne et chaque sens desservant
la station.
Quand le graphe initial avait un arc de la station A vers la station B,
on aura maintenant 3 arcs :
-
du coeur de A jusqu'au bon quai, son temps de parcours sera très long,
disons 300 (secondes), pour prendre en compte aussi le temps d'attente
de la prochaine rame,
- du quai de la station A pour la ligne considérée vers le quai
pour cette même ligne à la station B, son temps de parcours sera
celui utilisé dans la section 2,
- du quai de la station B, vers le coeur de B, avec un temps de parcours
de 60.
Les itinéraires suivront naturellement les lignes en passant d'un sommet
quai au suivant. On ne passe par un coeur de station qu'au départ,
à l'arrivée et lors d'un changement de ligne.
Une petite difficulté technique est d'assurer l'indexation de tous ces
sommets.
Là où un numéro de station suffisait, il faut maintenant un triplet
numéro de station, numéro de ligne et code de direction.
Ces deux derniers doivent être extraits de la chaîne de caractère
qui désigne la ligne.
On utilisera pour cela les fonctions suivantes :
static final int MAX_LIGNE = 27;
static final int MAX_DIRECTION = 6;
static int numeroLigne(String ligne) {
if ( ligne == null || ligne.length() == 0 )
return 0;
if ( ligne.charAt(0) == '1' )
if ( ligne.charAt(1) >= '0' && ligne.charAt(1) <= '3' )
return 10 + ligne.charAt(1) - '0';
else
return 1;
else if ( ligne.charAt(0) >= '1' && ligne.charAt(0) <= '9' )
return ligne.charAt(0) - '0';
else if ( ligne.charAt(0) >= 'A' && ligne.charAt(0) <= 'D' )
return 14 + ligne.charAt(0) - 'A';
else if ( ligne.charAt(0) == 'P' )
return 18 + ligne.charAt(1) - '1';
else
throw new Error ("désignation de ligne incorrecte : "+ ligne);
}
static int codeDirection(String ligne) {
if ( ligne == null || ligne.length() == 0 )
return 0;
int i = 0;
while ( i < ligne.length() && ligne.charAt(i) != '-' )
++i;
++i;
if ( i < ligne.length() )
return ligne.charAt(i) - 'a';
else
throw new Error ("désignation de ligne incorrecte : "+ ligne);
}
static int codeSommet(int num, String ligne) {
return ( num*MAX_LIGNE + numeroLigne(ligne) )*MAX_DIRECTION + codeDirection(ligne);
}
La fonction numeroLigne retourne une valeur comprise entre 1 et 26,
bornes incluses. La valeur 0 est réservée pour désigner un coeur de
station.
La fonction codeDirection retourne une valeur comprise entre 0 et 5,
bornes incluses, 0 codant la direction a, etc.
Ainsi, le coeur de la station 19 est représenté par le triplet
(19,0,0), son quai pour la ligne 1, direction a est représenté
par le triplet (19,1,0), etc.
La fonction codeSommet permet de recomposer le tout en un seul entier
pour l'indexation.
On écrit la classe Situ4 qui, à partir de deux stations de
départ et d'arrivée, calcule un plus court chemin:
java Situ4 lignes.data depart arrivee
avec le même format de sortie que dans les premières sections.
This document was translated from LATEX by
HEVEA.