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: 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
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


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
  1. Prendre la ligne nomLigne direction terminusLigne
  2. Changer à la station nomStation
  3. Prendre la ligne nomLigne direction terminusLigne
  4. ...

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


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: 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é : 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 : 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 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.