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:
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.
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
À 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.
Les deux extensions proposées sont indépendantes et peuvent être traitées dans un ordre quelconque. La première extension consiste à mettre en uvre 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:
Rappelons qu'un tas de éléments est un arbre binaire complet rangé dans un tableau t dont on utilise alors les indices de 0 à . 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 , 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 , 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 .
La difficulté de l'algorithme de Dijkstra vient de ce qu'il nécessite une troisième opération sur la file de priorité:
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.
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:
Quand le graphe initial avait un arc de la station A vers la station B, on aura maintenant 3 arcs:
Les itinéraires suivront naturellement les lignes en passant d'un sommet quai au suivant. On ne passe par un cur 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(3) <= '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 cur de
station.
La fonction codeDirection retourne une valeur comprise entre 0 et 5,
bornes incluses, 0 codant la direction a, etc.
Ainsi, le cur 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.