ipi rapport 1
Contents
1. 2 1 colonnes declarer entier d 0 longueurChainel 0 longueurChaine2 i et j it rent sur chainel et chaine declarer entier i j co t pour i de 0 longueurChainel S O Ss ak pour j de 0 longueurChaine2 OPEN pour i de 1 longueurChainel pour j de 1 longueurChaine2 si chainel i chaine2 j alors co t 0 sinon co t 1 En 9 minimum ellacd jj 5 Il effacement bilal agm s8 ik M iaee d i 1 j 1 co t RS UDS CNEUEN retourner d longueurChainel longueurChaine2 La cha ne chaine1 est de longueur longueurChainel et chaine2 de longueur longueurChaine2 Cet algorithme renvoie un entier positif ou nul Il renvoie 0 si les cha nes 1 et 2 sont gales Si les cha nes 1 et 2 sont tr s diff rentes la fonction renverra au maximum la plus grande longueur des deux cha nes 3 Appartenance des stations de d part et d arriv e aux lignes Les deux stations tant donn es on fait les combinaisons de tous les chemins possibles On commence par faire un produit cart sien des diff rentes correspondances des deux stations Chaque combinaison de deux lignes n cessite un passage par une correspondance on doit avoir un maximum de deux correspondances La proc dure pour trouver le chemin le plus court est expliqu e dans l exemple suivant Exemple D part Arriv e 1 3 2 6 Dans la station de d part on trouve les lignes 1 et 2 et dans la station d arriv e les lignes 3 et2. 6 Les deux stations n ayant pas de ligne en commun on passera forc ment par au moins une correspondance Pour cela on fait le produit cart sien des 5 diff rentes lignes On obtient sur cet exemple les combinaisons suivantes Ensuite pour chacune des deux lignes on va r cup rer les correspondances possibles et on rejette les solutions plus de deux correspondances Sur le premier cas de l exemple pr c dent on trouve 1 23 13 5733 127373 Trois chemins sont donc possibles pour aller de la ligne 1 a la ligne 3 Pour le premier cas les lignes 1 et 3 se croisent a une station donc une seule correspondance et pour les deux autres chemins possibles il faut passer par une autre ligne soit deux correspondance On r it re cette operation pour les 3 autres cas de l exemple 4 Choix du chemin le plus court On a comme donn es la distance de chaque station par rapport au terminus On commence donc par faire une fonction qui retourne la distance entre deux stations qui sont sur une m me ligne Ensuite on fait la m me chose pour les stations interm diaires puis on additionne le tout pour avoir la distance totale d un chemin Pour avoir la distance en terme de correspondances il suffit de rajouter un compteur sur les stations dans la base de donn es Ainsi pour avoir le chemin le plus court en terme de distance il suffit de prendre le minimum des distances obtenues pr c demment Quant au chemin le plus court au nive
3. Transport Urbain Projet IPI Pierre CABEZA Hanga DIDI Lundi 10 Mars 2008 Adrien DONG Omar HARBI Paul IYABI Wilson JOUET Groupe 2 1 1 Nabil MHENNI M Tarhini Sommaire SONI NA NE Sauna ER MAA anne 2 I Ce que doit faire le syst me 3 II Ses grandes fonctionnalit s 4 1 Initialisation et remplissage de la base de donn es 4 2 Correction des fautes de frappe 4 a Id e g n rales a Basak kaha TAE RE AR MAR SR RS dia 4 b La distance de Levenstein 1 1 ss 4 3 Appartenance des stations de d part et d arriv e aux lignes 5 4 Choix du chemin le plus court 6 III Manuel d utilisation pr liminaire ss 7 1 Presentation de l application et fonctionnement 7 2 D pannage Assistance nee 7 ING ANNEX aNG NAGANAP en ennui 8 I Ce que doit faire le syst me On est amen r aliser un logiciel permettant un utilisateur donn de consulter un itin raire entre deux stations d un r seau de transport d fini pr alablement Cet itin raire doit tre le plus court possible en terme de correspondances et ou de distance selon le choix de l utilisateur On se limitera deux changements de ligne au maximum pour un itin raire Il faut galement noter que l interconnexion entre le point de d part A et celui d arriv e B peut tre interrompue Les distances au terminus ne sont que des approximations On peut aussi ajou
4. au des correspondances on prend tout simplement le minimum des diff rents compteurs obtenus pour chaque chemin III Manuel d utilisation pr liminaire 1 Pr sentation de l application et fonctionnement Le logiciel que l on est amen r aliser a pour but d aider les voyageurs utilisant les moyens de transport obtenir un itin raire qui soit le plus court en terme de nombre de correspondances et ou de temps de parcourt On tudie la possibilit de d velopper une interface graphique r alis e travers un langage objet comme C Java ou GTK pour une utilisation sous Unix Etape 1 L utilisateur est amen saisir la station de d part et celle d arriv e Ces deux cha nes de caract res doivent tre saisies dans l ordre d part puis arriv e Si on opte pour une interface graphique on prendra soin de cr er deux champs une fen tre de saisie assez classique avec un champ pour la station de d part et une autre pour l arriv e ainsi qu un bouton submit pour valider notre choix Etape 2 Avant d effectuer la recherche du chemin le logiciel devra v rifier si les deux stations saisies par l utilisateur sont correctes et existent bien dans la base de donn es compos e des stations du r seau de transport m tro et bus Si au moins une des deux cha nes de caract re n est pas valide le logiciel devra proposer une correction et donner un nom de station se rapprochant le plus possible de la station saisie par
5. l utilisateur qui par la suite devra valider cette correction si elle lui convient Le logiciel peut galement proposer une liste de correction Dans ce cas il devra choisir l une d entre elles Etape 3 Si l tape 2 est valid e le logiciel proposera un chemin servant d itin raire reliant la station de d part et la station d arriv e Le chemin donnera les diff rentes correspondances qu on devra emprunter pour atteindre la destination ainsi que le num ro de la ligne utilis e Pour la solution graphique on pourra s inspirer du site www ratp fr ou www transilien fr 2 D pannage Assistance Pour tout probl me veuillez contacter les responsables du projet l adresse mail suivante transport urbain gmail com IV Annexe Voici l ensemble des stations de m tro utilis es dans ce projet Elles sont ici pr sent es sous la forme d un fichier texte qu il faudra envoyer vers une base de donn es On proc dera de la m me mani re pour les lignes de bus Nom de la station n de la ligne Distance au terminus en m Saint Lazare 14 0 Madeleine 14 500 Pyramides 14 1500 Chatelet 14 2000 Gare de Lyon 14 2500 Cour St Emilion 14 3000 Biblioth que Fran ois Mitterand 14 3500 Olympiades 14 4000 Chatelet 11 0 Hotel de Ville 11 500 Rambuteau 11 1000 Arts et M tiers 11 1500 R publique 11 2000 Goncourt 11 2500 Belleville 11 3000 Pyr n es 11 3500 Jourdain 11 4000 Places des F tes 11 4500 T l graphe 11 5000 Po
6. rte des Lilas 11 5500 Mairie des Lilas 11 6000 Place d Italie 5 0 Campo Formio 5 500 Saint Marcel 5 1000 Quai de la Rapee 5 1500 Bastille 5 2000 Breguet Sabin 5 2500 Richard Lenoir 5 3000 Oberkampf 5 3500 Republique 5 4000 Jacques Bonsergent 5 4500 Gare de l Est 5 5000 Gare du Nord 5 5500 Stalingrad 5 6000 Jaur s 5 6500 Laumi re 5 7000 Ourcq 5 7500 Porte de Pantin 5 8000 Hoche 5 8500 Eglise de Pantin 5 9000
7. t l utilisation de la fonction scanf sur celui ci nous oblige avoir un texte bien format car la moindre erreur peut entra ner le non fonctionnement du programme si l on change les lignes par exemple 2 Correction des fautes de frappe a Id e g n rale L id e est de mettre en place une correction intuitive qui va proposer le nom de station le plus proche de celui entr e par l utilisateur lorsque celui ci se trompe S il y en a plusieurs on en fait une liste qu on affiche Pour cela il suffit de comparer le nombre d op rations faire pour passer du mot tape par l utilisateur l ensemble des mots qui se trouvent dans la base de donn es ce nombre s appelle le co t Il se calcule gr ce la distance de Levenstein On considerera que la marge d erreur du co t pour un nom erron est de 4 mais cette valeur peut tre amen e changer b La distance de Levenstein La distance de Levenshtein mesure la similarit entre deux cha nes de caract res Elle est gale au nombre minimal de caract res qu il faut supprimer ins rer ou remplacer pour passer d une cha ne l autre Cette distance est donc d autant plus grande que le nombre de diff rences entre les deux cha nes est grand Son algorithme g n ral peut se r sumer ainsi entier DistanceDeLevenshtein caractere chainel 1 longueurChainel caractere chaine2 1 longueurChaine2 d est un tableau de longueurChainel 1 rang es et longueurChaine
8. ter comme option d utilisation de choisir uniquement les correspondances entre m tros ou entre bus L utilisateur pouvant se trompant lors de la saisie des stations il est indispensable de pr voir un module permettant d identifier et de corriger les fautes de frappes Entre autre il doit pouvoir proposer une ou plusieurs corrections lorsqu on oublie ou rajoute des lettres au maximum 2 ou bien qu on en inverse Exemple Saint Micel 3 Saint michel Luxembourgh 3 Luxembourg Gare de Loyn gt Gare de Lyon Donner la station de depart Gare de Lyon Donner la station d arriv e Saint Michel Chemin non direct le plus court Gare de Lyon gt Ch telet Metro 14 Ch telet 3 Saint Michel Metro 4 II Ses grandes fonctionnalit s 1 Initialisation et remplissage de la base de donn es En premier lieu on a d choisir 3 lignes de m tro et 2 lignes de bus dans le plan des transports en commun parisiens savoir les lignes 5 11 et 14 pour le m tro et les lignes 26 et 65 pour les bus Deux solutions s offrent nous pour stocker les informations concernant les diff rentes stations nom num ro s de ligne distance au terminus soit utiliser un fichier texte soit utiliser une base de donn es SQL La deuxi me solution nous appara t plus appropri e pour la mise en place du projet En effet l initialisation par un fichier texte peut poser des probl mes de m moire lorsque le nombre de stations augmente e
Download Pdf Manuals
Related Search