Avant tout, récupérez le fichier graphestp3.tar.gz et décompressez-le :
gunzip graphestp3.tar.gz
tar xvf graphestp3.tar
rm graphestp3.tar
cd GraphesTp3; ls
Cette archive contient des programmes C pour manipuler des graphes,
la documentation de ces programmes
se trouve ici :
Rappel du premier TP : description des structures de données utilisée pour représenter un graphe sous la forme Γ (application successeurs). Pensez également à vous référer à la documentation du code source, en particulier :
|
La RATP propose à ses usagers un service interactif qui trouve le plus court trajet entre deux stations du métro au choix de l'utilisateur. Notre but dans ce TP sera de réaliser une version simplifiée d'un tel logiciel, et de réfléchir aux stratégies les plus efficaces pour résoudre des problèmes du mêeme type.
0. Les données
Vous trouverez dans le fichier metro_complet.graph un graphe valué construit de la façon suivante :
make graphe2ps.exe
graphe2ps.exe metro_complet.graph
display metro_complet.graph.eps
1. Dijkstra dans le métro
Implémentez l'algorithme de Dijkstra étudié en cours. Voici une courte description de la fonction demandée :
/* ====================================================================== */
/*! \fn void Dijkstra(graphe * g, int i)
\param g (entrée) : un graphe pondéré. La pondération de chaque arc doit
se trouver dans le champ v_arc de la structure cell .
\param i (entrée) : un sommet de g.
\brief calcule, pour chaque sommet x de g, la longueur d'un plus court
chemin de i vers x. Cette longueur est stockée dans le champ
v_sommets de g .
*/
/* ====================================================================== */
Testez votre programme sur un graphe de taille réduite de votre choix (celui-ci par exemple), puis sur le graphe du métro.
Fonctions et données utiles :
2. Plus court chemin
Implémentez un algorithme de recherche de plus court chemin d'un sommet d vers un sommet a, qui se base sur les valeurs calculées par Dijkstra. Voici une courte description de la fonction demandée :
/* ====================================================================== */
/*! \fn graphe * PCC(graphe * g, int d, int a)
\param g (entrée) : un graphe pondéré. La pondération de chaque arc doit
se trouver dans le champ v_arc de la structure cell .
\param d (entrée) : un sommet (départ).
\param a (entrée) : un sommet (arrivée).
\return un plus court chemin de d vers a dans g , représenté par un graphe.
\brief retourne un plus court chemin de d vers a dans g .
*/
/* ====================================================================== */
On pourra améliorer le temps de calcul en stoppant l'algorithme de Dijkstra dès que le sommet a est atteint.
Testez votre programme sur un graphe de taille réduite de votre choix, puis sur le graphe du métro. Visualisez (voir EPSGraphe) le plus court chemin obtenu ainsi que l'ensemble des sommets explorés, pour quelques exemples de trajets dans le métro.
Fonctions et données utiles :
3. Amélioration de Dijkstra
Dans l'algorithme de Dijkstra, les sommets n'appartenant pas à S peuvent se diviser en deux sous-ensembles :
Implémentez cette amélioration et testez-la.
Fonctions et données utiles :
4. Amélioration de l'estimation du temps de trajet
Dans ce qui précède, nous ne prenons pas en compte les temps arrêts du métro à chaque station. On désire rajouter à l'estimation du temps total de trajet une attente moyenne de 20s par arrêt. Pour ce faire il existe deux types de solutions :
5. Approche A*
5.1 On désire maintenant résoudre le même problème par une approche A*. Définissez un graphe de résolution de problème et proposez une ou plusieurs heuristiques A*, sans tenir compte des temps d'arrêt aux stations.
5.2 Il suffit maintenant de modifier légèrement l'algorithme de Dijkstra (variante de la question 3) pour implémenter la stratégie A* pour ce problème. Réalisez cette implémentation, et visualisez (voir EPSGraphe) l'ensemble des sommets explorés pour quelques exemples de trajets. Comparez le nombre de ces sommets avec le nombre de sommets explorés par Dijkstra.
Fonctions et données utiles :
5.3 Proposez une heuristique A*, tenant compte des temps d'arrêt aux stations.
Remerciements
Nous tenons à remercier la RATP pour les données mises à disposition sur son site Web, ainsi que L. Granboulan et L. Mauborgne de l'ENS, auteurs d'un TP sur la recherche de plus courts chemins dans le métro dont nous nous sommes librement inspirés.