villes=['Annecy', 'Auxerre', 'Bastia', 'Bordeaux', 'Boulogne', 'Brest', 'Caen', 'Grenoble', 
'Le Havre', 'Lens', 'Lille', 'Lyon', 'Paris', 'Marseille', 'Metz', 'Nantes', 'Nancy', 'Nice',
 'Rennes', 'Strasbourg', 'Saint-Etienne', 'Sedan', 'Toulouse']

1. Combien y a t-il de villes à visiter ?
2. Combien y a t-il d'itinéraires possibles ?

 distancier[villeA][villeB]

1. Quelle est la distance entre Lille et Lens ?
2. Quelle est la distance entre Boulogne et Bastia ?

Voici une proposition (non pertinente) d'un itinéraire.

itineraire=['Annecy', 'Auxerre', 'Bastia', 'Bordeaux', 'Boulogne', 'Brest', 'Caen', 'Grenoble',
 'Le Havre', 'Lens', 'Lille', 'Lyon', 'Paris', 'Marseille', 'Metz', 'Nantes', 'Nancy', 'Nice', 
 'Rennes', 'Strasbourg', 'Saint-Etienne', 'Sedan', 'Toulouse']

1. Compléter la fonction ci-dessous, qui permet de calculer la distance de cet itinéraire. (N'oubliez pas de revenir au point de départ !)

def calcul_distance(itineraire):
    res=0
    for ...
    		...
    		...
    return res

...

tracer(itineraire)

itineraire=['Annecy', 'Auxerre', 'Bastia', 'Bordeaux', 'Boulogne', 'Brest', 'Caen', 'Grenoble', 'Le Havre', 'Lens', 'Lille', 'Lyon', 'Paris', 'Marseille', 'Metz', 'Nantes', 'Nancy', 'Nice', 'Rennes', 'Strasbourg', 'Saint-Etienne', 'Sedan', 'Toulouse']
Tracer l'itinéraire ci-dessous :

1. Combien de temps a mis votre ordinateur pour calculer l'itinéraire précédent ? (en seconde)
2. Combien de temps mettra votre ordinateur pour calculer les distances de l'ensemble des itinéraires possibles (Manip'1) ?
   (Donner une réponse en secondes puis en années)

...

 itineraire=["Lens"]

Tant que vous n'en avez pas marre : 
	compléter le paragraphe ci-dessous en remplaçant V1 , V2 , V3 , ... par le nom de la bonne ville.
		itineraire=["Lens"]
		A l'aide de la variable  distancier  déterminer  la ville la plus proche de Lens qui n'est pas dans itineraire ? On note V1 cette ville.
		itineraire=["Lens",V1]
		A l'aide de la variable  distancier  déterminer  la ville la plus proche de V1 qui n'est pas dans itineraire ? On note V2 cette ville.
		itineraire=["Lens",V1,V2]
		A l'aide de la variable  distancier  déterminer  la ville la plus proche de V2 qui n'est pas dans itineraire ? On note V3 cette ville.
		itineraire=["Lens",V1,V2,V3]
		A l'aide de la variable  distancier  déterminer  la ville la plus proche de V3 qui n'est pas dans itineraire ? On note V4 cette ville.
		itineraire=["Lens",V1,V2,V3,V4]
		A l'aide de la variable  distancier  déterminer  la ville la plus proche de V4 qui n'est pas dans itineraire ? On note V5 cette ville.
		...
		...
		itineraire=["Lens",V1,V2,V3,...V20]
		A l'aide de la variable  distancier  déterminer  la ville la plus proche de V20 qui n'est pas dans itineraire ? On note V21 cette ville.
		itineraire=["Lens",V1,V2,V3,...V20,V21]
		print(calcul_distance(itineraire))
		print(itineraire)
Passer  à la suite...

1. Compléter la fonction ci-dessous qui permet d'avoir la ville la plus proche d'une ville donnée en paramètre.
2. Quelle est la ville la plus proche de Paris ?

def ville_la_plus_proche(ville,L):
    global distancier
    """
    : param numero_ville: (str)  nom de la ville
    : param L : (list) liste des villes
    : return: (str)  la ville la plus proche de la ville "ville".
    """

	 ...

    for v in L :
		...
		...
		...
    return ville_la_plus_proche
    

...

Que fait la fonction ci-dessous?

   
def supprimer(v,L):
    '''
    v est un element d'une liste L
    '''
    L1=[]
    for elt in L:
        if elt !=v :
            L1.append(elt)
    return L1

1. Compléter la fonction ci-dessous qui permet d'avoir un itinéraire "glouton" partant de la ville depart
2. Tester votre fonction en partant de Nice et afficher l’itinéraire

def parcoursV1(depart):
	 global liste_villes    
    nb_ville=len(liste_villes)
    villes_visited=[depart]
    liste_villes=supprimerV1(depart,liste_villes)
    while 
    
    
    
    return villes_visited
 

...

Appliquer l'algorithme "glouton" en prenant pour ville de départ chacune des villes de liste_villes et sélectionner le parcours le plus optimal.

...

Afficher ci-dessous l’itinéraire obtenu, l'ordre de visite des villes et la distance totale.

Montrer que cette méthode gloutone ne donne pas une solution globalement optimale.