import pylab import math dico_villes={'A' : ( 0 , 0 ), 'B' : ( 7 , 3 ), 'C' : ( 3 , 1 ), 'D' : ( 2 , 4 ), 'E' : ( 4 , 6 ), 'F' : ( 3 , 2 ), 'G' : ( 5 , 0 )} def distance(Villes, i,j) : """ Cette fonction calcule la distance entre les villes i et j qui sont deux clefs du dictionnaire Villes """ dx = Villes[i][0] - Villes[j][0] dy = Villes[i][1] - Villes[j][1] return (dx**2 + dy**2) ** 0.5 ''' Vous allez vérifier le tableau voyageur de commerce Par exemple pour vérifier le racine de 26 présent à la ligne B colonne D on demande à Python : >>> distance (dico_villes, 'B','D') >>> math.sqrt(26) ''' def VilleLaPlusProche(v, dico_villes): ''' L'objectif de cette fonction est de renvoyer la ville la plus proche de v parmi les villes présentes dans dico_villes ainsi que la distance. Voici le pseudo-code de cette fonction : (A vous de le traduire en Python) mini est une liste à deux élements : le premier élément est égale à v l'autre à 1000000000000 Pour chaque ville (VILLE) du dictionniaire dico_villes faire : ----si VILLE n'est pas v et si la distance entre VILLE et v est inférieur au deuxième élément de mini ---------Alors le premier element de mini devient VILLE et le deuxième element de mini devient la distance entre ville et v ----Fin du si Fin du pour renvoyer la variable min ''' mini=[v,1000000000000] #C'est à vous def SupprimerVille(ville,dico_villes): ''' L'objectif de cette fonction est de supprmier ville du dictionnaire dico_villes. par exemple on souhaite avoir dico_villes sans la ville 'B'. Voici le pseudo-code de cette fonction. A vous de le traduire en Python : dico est un dictionnaire vide Pour toutes les clefs (CLEF) de dico_villes : ----si CLEF est différente de ville --------alors ajouter CLEF au dictionnaire dico Fin du pour renvoyer dico ''' #C'est à vous ''' Tester: >>>SupprimerVille('B',dico_villes) ''' def parcours(dico_villes,depart): ''' L'objectif de cette fonction est de renvoyer l'itinéraire fournit par l'algorithme glouton du voyageur de commerce en partant de la ville depart Voici le pseudo-code de cette fonction. A vous de le traduire en Python : villes_a_visiter est une variable égale à dico_villes dist est une variable égale à 0 (# distance totale de l'itinéraire glouton) ville_visited est une liste contenant depart v est une variable égale à depart Tant que le nb de ville de villes_a_visiter est supérieur à 1. ----tmp est une variable égale à VilleLaPlusProche(v,villes_a_visiter) c'est à dire la ville la plus proche de v ----parmi les villes présentes dans villes_a_visiter ----ajouter à dist la valeur de tmp[1] ----ajouter tmp[0] à la liste ville_visited (rmq: tmp[0] est la ville la plus proche de v) ----Supprimer v du dictionnaire villes_a_visiter (utiliser la fonction SupprimerVille ci-dessus) ----la variable v est égal à tmp[0] Fin du tant que ajouter à dist la distance de v à la ville de depart renvoyer une liste dont le premier element est dist et le deuxième est ville_visited ''' #C'est à vous return [dist,ville_visited] ''' A l'aide cette fonction vérifier vos résultats de la page 2 du pdf voyageur de commerce : Par exemple pour l'itinéraire glouton en partant de A : >>>parcours(dico_villes,'A') [22.07496472499763, ['A', 'C', 'F', 'D', 'E', 'B', 'G']] Tester tous les itinéraire gloutons : # Noter les commandes et les résultats ci-dessous : ''' def voyage(dico_villes): ''' L'objectif de cette fonction est de renvoyer l'itinaire fournit par l'algorithme glouton du voyageur de commerce Voici le pseudo-code de cette fonction. A vous de le traduire en Python : Min est une liste à 2 elements. Le premier element est égal à 1000000000000000 et le deuxième est une liste vide. Pour toutes les villes de dico_villes ----tmp est une variable égale à parcours(dico_villes,v) ----Remarque : tmp est une liste -> [dictance,itinéraire partant de v] ----Si le 1er element de la liste tmp est inférieur au 1er element de la liste Min --------Alors : ------------affecter au 1er element de Min la valeur du 1er element de la liste tmp ------------affecter au 2eme element de Min la valeur du 2eme element de la liste tmp Afficher la distance totale renvoyer la variable Min ''' Min=[1000000000000000,[]] #C'est à vous return Min def trace(dico_ville,tour) : """ Ne rien modifier dans cette fonction Cette fonction prend en parametre un dictionnaire de villes et un itinéraire (une liste de villes présentes dans le dictionnaire) Cette fonction permet alors de tracer sur un graphique l'itinéraire """ x = [ dico_ville[t][0] for t in tour ] y = [ dico_ville[t][1] for t in tour ] x += [ x [0] ] # on ajoute la dernière ville pour boucler y += [ y [0] ] # pylab.plot (x,y, linewidth=5) i=0 for ville in tour : pylab.text (x[i],y[i],ville) i=i+1 pylab.title("Ville de départ :" + tour[0]) pylab.show () ''' Par exemple pour de vérifier vos graphiques tracé à la page 3 du pdf sur le voyageur de commerce >>> itineraire = parcours(dico_villes,'A')[1] >>> print(itineraire) >>>trace(dico_villes,itineraire) Vérifier l'ensemble de vos graphiques de la page 3 ''' ####################################################################################### '''Voici les coordonnées de 23 villes de France. dico={'Annecy': (6.13, 45.90), 'Auxerre': (3.57, 47.79), 'Bastia': (9.45, 42.71), 'Bordeaux': (-0.58, 44.84), 'Boulogne': (1.61, 50.726), 'Brest': (-4.486, 48.39), 'Caen': (-0.37, 49.18), 'Grenoble': (5.736, 45.18), 'Le Havre': (0.108, 49.49), 'Lens': (2.83, 50.43), 'Lille': (3.06, 50.6365), 'Lyon': (4.83, 45.757), 'Paris': (2.35, 48.86), 'Marseille': (5.37, 43.296), 'Metz': (6.176, 49.12), 'Nantes': (-1.55, 47.218), 'Nancy': (6.18, 48.69), 'Nice': (7.27, 43.7), 'Rennes': (-1.68, 48.05683136), 'Strasbourg': (7.687339783, 48.11), 'Saint-Etienne': (4.287, 45.44), 'Sedan': (4.94, 49.7), 'Toulouse': (1.44, 43.6)} Sans modifier les fonctions définies ci-dessus, répondre aux questions en indiquant la (ou les commandes) python à utiliser): 1- Quel itinéraire conseiller au voyageur de commerce qui souhaite passer par ces 23 villes (et revenir au point de départ)? 2- On donnera la ville de départ et l'ordre des villes à visiter sous la forme d'une liste 3- On sauvegardera également l'itinaire sous la forme d'un carte. Remarque : La distance totale affichée peut vous paraitre bizarre car les coordonnées des villes correspondent à la latitude et à la longitude (qui sont exprimée en degré) . Si vous voulez une valeur approchée en kilometre, il faut multiplier le résultat par 111. '''