Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





BulgaraCeha slovacaCroataEnglezaEstonaFinlandezaFranceza
GermanaItalianaLetonaLituanianaMaghiaraOlandezaPoloneza
SarbaSlovenaSpaniolaSuedezaTurcaUcraineana

AdministrationAnimauxArtComptabilitéDiversesDroitéducationélectronique
FilmsL'économieL'histoireL'informatiqueLa biologieLa géographieLa grammaireLa littérature
La médecineLa musiqueLa politiqueLa psychologieLa sociologieLe tourismeLes mathématiquesManagement
PersonnalitésPhysiqueRecettesSportTechnique

Recherche d’une route dans un réseau

l'informatique

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger

TP n° 10

Recherche d’une route dans un réseau(2)

But : 



        Utiliser des structures chainées, des pointeurs sur ces structures,

        Faire de l’allocation dynamique de mémoire,

        Coder un algorithme de parcours de graphe

        Utiliser la documentation générée à partir du code (Doxygen)

On désire écrire une petite application pour permettre de trouver le chemin à utiliser pour aller d’une station à une autre dans le métro de Paris (pour celui de Rennes c’est trop facile).

On réalisera cette application en deux phases :

·          Construction d’une représentation en mémoire du réseau (le TP précédent),

·          Recherche d’un chemin dans ce réseau (ce TP).

On appellera station multiple une station qui se trouve sur plusieurs lignes de métro et permet donc de faire l’interconnexion de ces lignes.

Modification des fichiers

On a rajouté dans le répertoire /home-info/commun/3info/LangageC/TP10 :

·          Le fichier Chemin.h,

·          Le squelette de Chemin.c,

·          La mise à jour du répertoire DOC, consultable au moyen de votre navigateur qui donne les informations sur chacun des modules composant cette application. Pour cela afficher la page : /home-info/commun/3info/LangageC/TP10/DOC/files.html

Modification des fichiers

Modifier votre makefile pour qu’il intègre le nouveau module Chemin.c. Vous pouvez maintenant utiliser make dep, car makedepend a été installé dans votre environnement.

Retirer également le commentaire dans le main et dans la fonction Res_router.

Par la suite vous pourrez être conduit à définir et à insérer de nouvelles fonctions dans les modules réalisés lors de la première partie.

Phase 2 : Trouver les chemins issus d'un sommet :

La recherche des plus courts chemins issus d’un sommet peut se faire par l’algorithme de Djikstra. La description ci-dessous provient du site Interstice. Sur ce site il y a également une animation qui permet de comprendre le fonctionnement cet algorithme. Pour trouver ce site le plus simple est de faire une recherche sur Google avec 'Interstices court chemin'.

Objectif 1 : comprendre l’algorithme

Pour chaque sommet x, on veut calculer la valeur minimum m(x) des chemins allant du sommet de départ A vers x. Pour le routage, on veut déterminer le prédécesseur de x, noté p(x), sur un chemin de valeur m(x). Ceci permet de tracer, en le remontant, le meilleur chemin du sommet de départ A vers n'importe quel sommet x.

L'algorithme de Dijkstra repose sur le principe d'exploration à partir du meilleur, c'est à dire du meilleur prédécesseur visité.

Un sommet x est dit visité si au moins un chemin de A vers x a été évalué ; un sommet visité possède des valeurs m(x), p(x) provisoires : m(x) est la valeur minimum des chemins de A vers x déjà évalués, et p(x) le prédécesseur correspondant.

Un sommet est dit calculé s'il est visité et si l'on sait que ses valeurs m(x), p(x) sont définitives (et correctes).

Initialement, bien sûr, le sommet A est calculé (avec m(A) = 0, p(A) non défini puisque A est le point de départ des chemins), et chaque successeur x de A est visité, avec m(x) = v(A, x), p(x) = A.

Le principe d'exploration à partir du meilleur consiste à chercher, parmi les sommets visités non encore calculés, un sommet dont la valeur m(x) est minimum. On peut alors démontrer que, pour un tel sommet, les valeurs provisoires m(x), p(x) sont définitives (et correctes). Cette démonstration utilise explicitement le fait que les valeurs sont non négatives.



On marque donc x comme calculé et on prolonge l'exploration en examinant chacun des successeurs de x : chaque successeur y non encore visité devient visité, avec m(y) = m(x) + v(y, x), p(y) = x tandis que, pour chaque successeur y déjà visité, on effectue la mise à jour m(y) = min(m(y), m(x) + v(x, y)) (et p(y) = p(x) si m(y) est mis à jour). L'exploration s'arrête lorsque tous les sommets visités sont calculés (les sommets non visités sont inaccessibles, on peut considérer qu'ils ont une valeur m(x) = +∞).

Par rapport à cette description et au texte donné sur le site, on remarque qu’on peut simplifier l’initialisation en mettant le sommet A dans provisoires et non dans calculés.

L'algorithme modifié peut s'écrire de cette façon :

/* Initialisations */

calculés= ;

m(A)=0 ;

provisoires=;

/* Itérations */

tant que provisoires

   soit x Є provisoires tel que m(x) est minimum sur provisoires ;

   calculés=calculés + ; provisoires=provisoires- ;

   pour tout sommet y successeur de x   

      cas

         y Є calculés -> rien

         y Є provisoires ->

            si m(x)+v(x,y)< m(y)

               m(y)=m(x)+v(x,y) ;

               p(y)=x ;

            fsi

         autrement ->

            provisoires=provisoires + ;

            m(y)=m(x)+v(x,y) ;

            p(y)=x ;

      fcas

   fpour

ftantque

/* les sommets n'appartenant pas à calculés sont inaccessibles */

La complexité de l'algorithme est de l’ordre de n².

Objectif 2 : réaliser des fonctions de service

Pour s’adapter à cet algorithme, on représente un sommet x par la structure Etape contenant :

·          un pointeur vers une station,

·          un index dans l’ensemble des sommets calculés pour retrouver le prédécesseur p(x),

·          la distance m(x).

Pour représenter un ensemble tel que calculés ou provisoires on utilise la structure Chemin qui contient le nombre d’éléments et un pointeur vers un tableau d’Etape.

Commencer par écrire les fonctions de service : Chem_existe, Chem_meilleur, Chem_ajouter, Chem_retirer, Chem_print.

Objectif 3 : réaliser le cœur de l’algorithme

Comment, en fonction du nombre de stations d’un réseau, faut-il dimensionner la taille du tableau des étapes associé à une structure Chemin ?

Si vous avez bien retiré les commentaires dans le main et dans Res_router, vous pouvez facilement tester la génération de tous les chemins qui partent de la première station par ordre alphabétique.

·          Dans Chem_construire créer les structures pour la gestion des ensembles calculés et provisoires.

·          Initialiser provisoires avec la station depart passée en paramètre.




Ce début doit vous permettre de tester un bon nombre des fonctions de service.

·          Ecrire la fonction Chem_candidat qui réalise le cas à l’intérieur de la boucle pour tout sommet y successeur de x

·          Réfléchir à la manière de générer l’ensemble des successeurs d’une station au moyen des fonctions Sta_nextLigne et Sta_nextNom.

·          Faire la boucle générale tant que provisoire non vide. En sortie de boucle, ne pas oublier de libérer les allocations de  mémoire.

·          Pour tester on pourra mettre des impressions intermédiaires grace à Chem_print.

·          Faire un premier test avec une seule ligne.

./metro RES/14.lig

·          On pourra ensuite tester avec 2 lignes, et puis supprimer les impressions intermédiaires et tester sur tout le réseau.

·          Prévoir une extension rudimentaire de Res_router qui se limite à lire au clavier 2 numéros pour choisir les stations.

·          Ceux qui sont à l’aise, pourront montrer que l’on peut utiliser 2 fois moins de mémoire en faisant partager un même tableau d’Etape par les ensembles calculés et provisoires. Ceci nécessite toutefois de reprendre la programmation de  Chem_retirer.

Objectif 4 : s’adapter aux besoins

·          Sachant que pour désigner une station, un utilisateur ne précisera pas la ligne mais se servira uniquement du nom, modifier l’algorithme (initialisation et test de fin).

·          Réaliser la fonction Chem_trajet, qui affiche dans le bon ordre les stations traversées. On pourra en faire une version simple, toutes les stations ; une version plus facile à lire, sans les stations intermédiaires entre deux stations multiples ; ou finalement complète en indiquant la ligne à prendre et le nom de la direction (nom du terminus).

  0 Alma – Marceau           : 09 => Mairie de Montreuil

  1 Franklin D. Roosevelt    : 09

  6 Franklin D. Roosevelt    : 01 => Chateau de Vincennes

 17 Reuilly Diderot          : 01

Objectif 5 : définir l’interface utilisateur

L’interface pour sélectionner un élément dans un grand nombre (ici 346 stations) n’est pas très simple à concevoir. La solution rudimentaire avec saisie d’un numéro est à exclure, la frappe du nom en entier est trop sensible aux erreurs de frappe.

Imaginer une solution s’inspirant vaguement des expressions régulières dans laquelle on pourrait s’appuyer sur les lettres en majuscule et réaliser des impressions partielles des noms ainsi sélectionnés. Vous pouvez également proposer une autre approche.

Objectif 5 : générer la documentation

·          Appeler doxygen –s metro.doxy pour créer le fichier de configuration par défaut.

·          Dans metro.doxy mettre à jour les lignes PROJECT_NAME, OUTPUT_LANGUAGE,  OPTIMIZE_OUTPUT_FOR_C, FILE_PATTERNS, HTML_OUTPUT = DOC, GENERATE_LATEX = NO, HAVE_DOT=YES

·          Rappeler doxygen metro.doxy et utiliser votre navigateur pour voir la documentation.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 637
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site