Défis C & C++ #4 Balade dans le métro parisien

Le programme principal se décompose en plusieurs parties :

• évaluer la requête formulée par l'utilisateur (station de départ et d'arrivée, temps moyen…) ;
• effectuer la lecture du fichier des stations ;
• chercher un itinéraire répondant à la requête formulée ;
• afficher le résultat.

Choix de modélisation : il s'agit ici de représenter les liens qui existent entre des stations de métro d'une ville, afin de rechercher des itinéraires entre elles. Une représentation simple est celle sous forme de graphe. Chaque sommet est une station, chaque « portion » de ligne entre deux stations forme un arc. Il existe plusieurs moyens efficaces de représenter un graphe, ici on a choisi la modélisation sous forme de listes d'adjacence (pour chaque sommet du graphe, on stocke dans une liste chaînée, l'ensemble de ses successeurs). Les valuations des arcs, c'est-à-dire les distances entre les stations, ont toutes été supposées égales. En réalité, pour passer d'une station à une autre, il y a un cout qui varie selon le fait qu'il soit nécessaire de changer ou non de ligne. Pour passer d'une station à l'autre, on stockera simplement via quelle ligne cela peut se faire (dans les maillons des listes chaînées).

Algorithmes utilisés

• Pour calculer le plus court chemin d'une station à une autre, l'algorithme de Dijkstra a été utilisé, car c'est un algorithme simple et efficace, qui permet de connaître (en un temps polynomial), tous les plus courts chemins à partir d'une station, ainsi que le temps nécessaire mis pour y parvenir. Grâce à cet algorithme, on peut déjà répondre à une requête simple de l'utilisateur, à savoir quel est le plus court chemin d'une station à une autre du métro.
• Pour calculer un itinéraire multiple, mais dont l'ordre des étapes est imposé, cela revient a calculer plusieurs itinéraires simples, et de les mettre chacun bout à bout, afin de créer l'itinéraire final.
• Dans le cas ou l'ordre des étapes n'est pas défini, on se trouve alors face à un problème beaucoup plus complexe, qui ne peut être résolu en un temps normal, pour un nombre suffisamment important de stations intermédiaires (en effet, le nombre de chemins à explorer est de l'ordre de la factorielle du nombre de stations intermédiaires).

Deux approches ont été utilisées pour proposer une solution.

La première consiste à construire un arbre, pour lequel chaque nœud correspond à une station. La racine est la station de départ, et chacun de ses successeurs est les stations vers lesquelles il est possible de se rendre. Puis, à partir de chacune de ses stations, on stocke de nouveau les stations vers lesquelles il est possible de se rendre (moins la première), etc. Il va de soi que seul le chemin le plus court est utilisé (calculé à l'aide de Dijkstra). On progresse ainsi dans l'arbre, jusqu'à parvenir à la station d'arrivée (nécessairement la dernière du trajet). À ce moment, on recherche alors la feuille de l'arbre qui a la distance la plus courte ; c'est celle qui contient l'itinéraire optimal. On peut alors, en remontant à partir de cette feuille jusque la racine, déterminer cet itinéraire. Cette méthode, complète, assure de trouver le meilleur itinéraire. Cependant, comme expliqué plus haut, il n'est pas possible dans la pratique de l'utiliser, si le nombre de stations intermédiaires est trop élevé. Expérimentalement et avec les performances de la machine sur laquelle ont été faits les tests, ce seuil a été fixé à 8.

Au-delà de ce seuil, on applique donc une autre méthode, moins coûteuse, mais qui ne garantit pas la totale optimalité du trajet. On va en fait choisir l'ordre des stations en commençant par celle qui se trouve la plus proche de celle de départ, puis par celle qui est de nouveau la plus proche, jusqu'à parvenir à la station d'arrivée. Dans la pratique, cette heuristique de choix n'est pas des plus mauvaises, et l'itinéraire trouvé peut être considéré satisfaisant, pour un simple parisien désireux de visiter un grand nombre de stations de métro…

Algorithme : L'idée est de se baser sur l'utilisation des graphes. Il faut donc modéliser le plan du métro sous forme de graphe. Le graphe utilisé sera non orienté, car nous pouvons parcourir les lignes dans un sens comme dans l'autre.

Modélisation d'une ligne : Soit S1…Sn les différentes stations d'une ligne de métro, et d le delai entre 2 stations d'une même ligne. La modélisation choisie est la suivante :

Modélisation d'une correspondance. Une correspondance est l'endroit ou 2 lignes se rejoignent. Soit c le délai pour parcourir la correspondance. La modélisation choisie est la suivante :

ou la 2de station de la ligne 2 correspond avec le 3e station de la ligne 1 (les 2 stations ont le même nom).

Modélisation du départ et de l'arrivée : Pour implémenter le départ et l'arrivée, je crée 2 stations virtuelles (D et A). Je connecte ces stations au graphe via l'ensemble de leurs correspondances.

Modélisation d'une étape : Pour implémenter une étape, je crée une station virtuelle (E sur l'image), connectée au graphe représentant le plan du métro.

Pour la suite, j'appellerai G le graph représentant un plan de métro sans étape, et En l'étape n. Tous les graph G sont identiques.Ce qui donne le graphe simplifié suivant pour une étape :

Modélisation du trajet non optimisé : Dans le cas du trajet non optimisé, on doit parcourir l'ensemble des étapes dans l'ordre. Le graphe devient le suivant.

Modélisation du trajet optimisé : Dans le cas du trajet optimisé, on doit parcourir l'ensemble des étapes dans un ordre quelconque afin de trouver le chemin le plus court. Le graphe devient le suivant pour 3 étapes.

Comment l'Unicode a-t-il été géré ?

• Pour la lecture du fichier. Pour lire le fichier Unicode j'ai créé un codecvt_facet : utf16_codecvt_facet qui se charge de la conversion utf16 -> wchar_t. L'UTF-8 est géré par la facette utf8_codecvt_facet de boost.
• Pour la ligne de commande. Pour windows, la difficulté est de convertir son sharset OEM en Unicode. La seule solution simple que j'ai trouvée, c'est d'utiliser son CommandLineToArgvW. Ce n'est pas standard, mais comme ce n'est utile que sous windows, ça devrait aller. Pour les systèmes en UTF_8, c'est boost::program_options qui s'en occupe.
• Pour wcin, et wcout. Pour windows et Linux, c'est setlocale qui a résolu mon problème. Hélas il semble que les chaînes des locales ne soient pas standard. Donc je ne suis pas sur de la portabilité.
• Conclusion. La lecture d'un fichier Unicode ou UTF-8 peut se faire avec un effort raisonnable : en créant un codecvt_facet. Mais récupérer les entrées utilisateur s'avère être un véritable casse-tête. On n'a apparemment pas de moyen de savoir quels sont l'encodage et le charset en entrée. De plus, ils peuvent être différents sous un même système. Par exemple avec CodeBlock, si je lance mon projet de la console, je suis en OEM, si je le lance d'un .bat je suis en ANSI, et si je le lance de CodeBlocks la ligne de commande est en UTF-8. De plus les chaînes à passer aux locales ne sont pas standardisées, et le sujet ne semble pas très documenté (codecvt pour changer l'encodage, mais pour le charset ??) alors je serais curieux de connaître la solution simple, claire, portable, sans abus de ifdef, pour pouvoir lire une ligne de commande avec des caractères accentués.

Comment les comparaisons de chaînes ont été gérées ? En créant un collate (héritant de std::collate), nommé DVPCollate. Il s'occupe de faire les comparaisons ou les conversions en chaîne sans accent ni majuscule.

Comment trouver le chemin le plus court entre deux stations ?

• Idée de départ. Au premier abord, on aurait tendance à se dire: déplaçons-nous de station en station, à partir de la première. Testons toutes les possibilités de chemin et gardons la meilleure. Ça marche à condition de ne pas boucler. Pour ça il faut s'interdire de reprendre un tronçon déjà utilisé, dans le même sens.
• Principale amélioration. Ça marche, mais une première grosse optimisation me vient à l'esprit : quand on parcourt une ligne, pourquoi perdre du temps à faire toutes les stations, alors qu'on sait qu'on va aller : ou à une intersection ou à la station finale (à condition d'être sur une ligne qui y va). J'appellerai croisement une station desservie par plusieurs lignes. Dans la première méthode, on avait besoin d'un tableau associatif qui pour une station nous donne toute les stations contiguës et la ligne qui y va. En revanche, pour cette deuxième méthode il faut avoir deux tableaux associatifs : un qui pour une station nous donne toutes les lignes accessibles ou un autre qui pour une ligne nous donne tous les croisements accessibles. (Remarquez qu'on ne s'intéresse pas aux autres stations)
• Optimisations classiques. Les optimisations qui suivent sont assez classiques. Il s'agit de couper la recherche le plus tôt possible. C'est-à-dire de détecter le plus tôt possible qu'un chemin ne sera pas intéressant. La première méthode est la plus évidente : si la durée du chemin en cours de test est déjà plus longue que la meilleure durée déjà trouvée inutile de continuer. L'idée suivante est inspirée de l'algorithme de Dijkstra. L'idée de départ c'est que si on est déjà venu à une station en moins de temps, il est inutile de poursuivre ce chemin, alors qu'on sait qu'il lui existe une alternative plus courte. Cependant ce n'est pas si simple dans notre cas à cause temps perdu aux changements de ligne. En effet, si on est déjà venu à une station en moins de temps, ce n'était pas forcement par la même ligne. Donc la solution actuelle a encore une chance d'être meilleure, en évitant un changement de ligne. Mais cette idée est quand même utilisable, à condition de l'adapter. Puisqu’on peut connaître le meilleur temps fait pour une station, pour chaque ligne qui y mène.
• Comment trouver le meilleur chemin, avec des étapes (sans optimisation de l'ordre) ? Dans ce cas, aucune difficulté. Il suffit de demander les chemins de stations à stations, dans l'ordre demandé. Une toute petite optimisation aurait été possible, il s'agit de ne pas recalculer le même chemin si la même paire de stations apparaît deux fois. Je ne l'ai pas fait.
• Comment trouver le meilleur chemin, avec des étapes (avec optimisation de l'ordre) ? Pour se simplifier la vie, on va commencer pas une petite optimisation toute bête : Supprimer les doublons. En effet, si l'utilisateur se fiche de l'ordre des étapes, on peut supposer que le chemin le plus court pour aller trois fois à une même station… c'est d'y rester.