Université Paris-Diderot calculer un itinéraire (sous-)optimal entre deux villes Rédiger Pour trouver le "meilleur" itinéraire d'une ville de départ D à une ville
| Previous PDF | Next PDF |
Itinéraire Express, Véhicule - Commune de Saint-Nicolas-de-la-Taille
5 jui 2008 · 19°C Départ: Paris, Ile-de-France (75, France) 1 Sortir de Paris et continuer sur l'Avenue de la Grande Armée 5 13km Avenue de la Grande
[PDF] ITINÉRAIRES DE SUBSTITUTION AU DÉPART DE LA - Blog RER E
Relations Clientèle SNCF Transilien ITINÉRAIRES DE SUBSTITUTION AU DÉPART DE LA GARE DES BOULLEREAUX CHAMPIGNY Janvier 2015 Paris
[PDF] Séance 9: Calculer des itinéraires routiers - IRIF
Université Paris-Diderot calculer un itinéraire (sous-)optimal entre deux villes Rédiger Pour trouver le "meilleur" itinéraire d'une ville de départ D à une ville
[PDF] Projet de Programmation Logique n 1 ITINERAIRE Calcul d - LIPN
Université Paris 13 - Licence d'informatique L'objectif du projet Itinéraire est de développer un programme en ProLog capable d'aider un se rendre d'une station `a une autre, en respectant certain conditions (horaire de départ, horaire
[PDF] MODULE 5 ITINÉRAIRES - CFMWS
proche et de l'impératif présent - phrases complexes avec « quand » - expliquer et comprendre un itinéraire : a points de départ et d'arrivée b points de repère
[PDF] Fiches SE REPERER DANS LE TEMPS ET LESPACE - Programme
Laisser un message expliquant un itinéraire Connaitre la France, Paris : identifier les arrondissements de Paris ainsi que quelques ainsi l'heure de départ
[PDF] VOTRE TRAJET
15 mar 2020 · Itinéraire détaillé pour le trajet entre GARE DE PARIS NORD et MONTSOULT MAFFLIERS Horaires de départ et d'arrivée Moyens de
[PDF] Plan daccès - Banque de France
Entrée du public : 31 rue Croix des Petits Champs, 75001 Paris Paris Départ pour Paris tous les jours entre 6h30 et 20h Comptez de 30 minutes à 1h30
[PDF] ITINERAIRE AUTOCAR - Anciens Et Réunions
[PDF] Itinéraire Balade Rue Jacquemont - Gestion De Projet
[PDF] Itinéraire Bali 2016 - La Famille Et La Parentalité
[PDF] ITINERAIRE BEZIERS – MAS DE LONDRES Prendre Autoroute A75 - Anciens Et Réunions
[PDF] ITINERAIRE BIS 7 rue la Charbonnière
[PDF] Itinéraire camping-car Italie printemps 2012 (PDF, 3.3 Mo) - Anciens Et Réunions
[PDF] Itinéraire Centre de documents d`identité d`Interlaken
[PDF] ITINERAIRE CHATEAU MONTAGNE - Anciens Et Réunions
[PDF] Itinéraire commenté de la visite du site, des monuments, etc.
[PDF] itinéraire complet ici - Pacifique Lagon Voyages - Voyager
[PDF] Itinéraire conseillé pour 7 à 10 jours en Thailande - Anciens Et Réunions
[PDF] Itineraire Croatie du nord au sud sur le littoral - France
[PDF] Itinéraire culturels de Constanta, Roumanie I.1. La
[PDF] Itinéraire cyclotouristique 3 - Hauts d`Esserts-Blay
Introduction à la Programmation 1 - Travaux Pratiques
Séance 9:Calculer des itinéraires routiers
Université Paris-Diderot
Objectifs:-T ravailleravec des listes de différents t ypesetdes listes de listes-Utili serles b ouclesforetwhileDans ce TP nous allons travailler avec des listes de listes qui représentent une carte routière (simplifiée) de
la France. À l"aide des bouclewhileetfornous allons implémenter un simple algorithme permettant de
calculer un itinéraire (sous-)optimal entre deux villes.Rédiger les réponses aux questions et les tests pour chaque réponse dans le fichierItineraire.pyqui vous
est fourni.1 Chargement de la carte routière
Des données décrivant une carte routière sont disponibles dans les fichierscities.csvetroutes.csv. La procédure
loadData()qui vous est fournie dansItineraire.py, s"occupe de charger ces données dans les listes cityName,cityCoord,adjCities,routeetnRoutes. Ces variables sont accessibles par toutes les fonctions que vous aller écrire dansItineraire.py. Voici ce que ces listes contiennent après l"exécution deloadData():-cityNamedécrit les codes et les noms des villes. Chaque ville a un code entier unique compris entre
1 et 232 (inclus). Pour une ville de codei,cityName[i]est le nom de la villei.
-cityCoordcontient les coordonnées des villes dans le plan (en km). Pour une ville de codei, cityCoord[i][0]etcityCoord[i][1]représentent les coordonnées X et Y de la villei, respecti- vement.-adjCitiesest une liste de listes qui décrit les routes entre villes. S"il existe une route entre deux
villes, on dit qu"elles sontvoisines. Chaque ville a au plus 10 villes voisines. Pour une ville de codei,
adjCities[i]est une liste contenant les villes voisines dei(l"ordre des voisines dans cette liste ne sera pas important pour nous). DoncadjCities[i][j]c"est le code duj-eme ville voisine dei.-routeest une liste de listes qui décrit les longueurs des routes. Plus précisément,route[i][j]est
la longueur (en km) de la route qui lie la ville de codeià saj-eme ville voisine (remarquez que cette
voisine est la ville de codeadjCities[i][j]).Chaque route peut être parcourue dans les deux sens donc, dans les listes ci-dessus, si la villekest parmi les
voisines dei, alors la villeiest parmi les voisines dek. 12 Trouver les itinéraires
Pour trouver le "meilleur" itinéraire d"une ville de départ D à une ville d"arrivée A, on va utiliser la stratégie
suivante. 1.Se placer dans la ville de dépa rtD ;
2.Depuis la ville courante se déplacer dans sa ville voisine la plus "p roche"de A, si une ville voisine
existe; 3.Rép éterl"étap ep récédentejusqu"à se placer sur A (ou jusqu"à ce qu "ilne soit plus p ossiblede se
déplacer).Ici pour mesurer combien une ville V est "proche" de A on va utiliser les coordonnées de V et A pour calculer
leur distance (à vol d"oiseau) sur le plan à deux dimensions. Attention à ne pas confondre cette distance avec
la longueur d"une route. En effet V et A ne sont pas forcement connectées par une route.De plus on va chercher uniquement des itinéraires simples (c"est à dire qui ne passent jamais deux fois
par la même ville). On restreindra donc la recherche de l"étape 2 aux villes qui ne font pas déjà partie de
l"itinéraire.La stratégie plus haut ne garantit pas de trouver l"itinéraire le plus court (ni de trouver un itinéraire!),
mais peut trouver des itinéraires la plupart du temps "satisfaisants" sur des réseaux routiers suffisamment
connectés.Suivre les étapes suivantes.
Exercice 1 (Calculer la distance à vol d"oiseau,?)Écrire une fonctiondistCoordqui attend en paramètre le code d"une ville de départ et le code d"une ville
d"arrivée et renvoie leur distance (entière) calculée à partir des coordonnées des deux villes. Pour calculer la
partie entière de la racine carrée, utilisez la fonctionsqrtcomme exemplifiée en bas :1fromm athi mports qrt2int(sqrt(x))# partie entiere de la racine carree de x Exercice 2 (Calculer une étape de l"itinéraire,??)
Écrire une fonctionfindClosestpour la recherche de la ville la plus proche d"une ville d"arrivée. Cette
fonction reçoit le code d"une ville de départ V, le code d"une ville d"arrivée A, et une liste de booléensexcept.
Pour une ville de codei,except[i]estTruesiidoit être exclue de la recherche, etFalsesinon.La fonctionfindClosestrenvoie l"indice de la ville voisine de V la plus proche de A (selondistCoord),
parmi les voisines de V marquéesFalsedans la listeexcept. La fonction renvoie -1 si une telle voisine n"existe
pas.Remarquer que la valeur de retour n"est pas le code de la ville voisine trouvée, mais l"indice de cette ville dans
la liste des voisines de V. Par exemple si V à 3 voisines[V1, V2, V3], sidistCoord(V, V1) == 34,distCoord(V, V2) == 45, distCoord(V, V3) == 40,except[V1] == True,except[V2] ==except [V3] == False, alors la fonc- tionfindClosestrenvoie l"indice deV3, c"est-à-dire 2.Exercice 3 (Calculer un itinéraire,? ? ?)Écrire une fonctionfindRoutequi reçoit le code d"une ville de départ, le code d"une ville d"arrivée et renvoie
la longueur d"un itinéraire trouvé selon la stratégie décrite au début de la section 2 . La longueur d"un itinéraire est la somme des longueurs des routes dont il est composé.Suggestion. Pendant le calcul de l"itinéraire, maintenir une liste de booléensvisited, tel quevisited[i]
== Truesi la villeia déjà été ajoutée à l"itinéraire. Consulter cette information à chaque étape de la stratégie
pour éviter de se déplacer dans une ville déjà rencontrée. 2 Prévoir de renvoyer -1 dans le cas où la stratégie ne trouve aucun itinéraire. Tester la fonction, après avoir initialisé les listes avecloadData.Contrat:
Entrée: ville de départ : 5 (Paris), ville d"arrivée : 59 (Bordeaux)Sortie: 631
Entrée: ville de départ : 230 (Arles), ville d"arrivée : 154 (Auch) Sortie: 453Exercice 4 (Afficher l"itinéraire,?)Modifier la fonction de l"exercice
3 p ourqu"elle affiche sur la console les noms de toutes les villes de l"itinéraire calculé, y compris la ville de départ et d"arrivée. Tester la fonction, après avoir initialisé les listes avecloadData.Contrat:
Entrée: ville de départ : 5 (Paris), ville d"arrivée : 59 (Bordeaux)Sortie:
Paris Chartres Le Mans Angers Chôlet Parthenay Niort Saintes Bordeaux 631Entrée: ville de départ : 230 (Arles), ville d"arrivée : 154 (Auch)
Sortie:
Arles Montpellier Millau Albi Toulouse Auch
453Exercice 5 (Itinéraire par nom,?)
Écrire une fonctionfindRouteByNamequi est identique àfindRoutemais reçoit les noms des deux villes
au lieu de leur code. Tester cette fonction comme à l"exercice 4 , sur des couples de villes françaises de votre choix. Sur une carte de la France, vérifier la plausibilité de l"itinéraire calculé.Vous pouvez aussi vérifier la "qualité" de l"itinéraire en comparant sa longueur à celle d"un itinéraire trouvé
sur le Web.3quotesdbs_dbs11.pdfusesText_17