GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Plus court chemin en France ======

On se donne une liste de villes françaises et on cherche un chemin passant par toutes les villes, exactement une fois, le plus court possible.

===== Liste des villes =====

Nous utiliserons le fichier {{ :nsi:datasets:communes-departement-region.csv |}} contenant des communes françaises.

Pour extraire les données, je propose ce module court :

<code python>
# data.py
import csv

def format(city):
    return {
        "insee":city['code_commune_INSEE'],
        "nom":city['nom_commune_complet'],
        "lat":float(city['latitude']),
        "lng":float(city['longitude'])
    }

def load_cities():
    with open("communes-departement-region.csv", "r", encoding="utf8") as f:
        reader = csv.DictReader(f, delimiter=',')
        cities = []
        for city in reader:
            try:
                cities.append(format(city))
            except:
                pass
    return cities

cities = load_cities()
</code>

===== Distance =====

Pour la géométrie, je vous propose le module suivant :

<code python>
# distance.py
from math import radians, cos, sin, acos

def cosd(angle_deg:float) -> float:
    '''
    renvoie le cosinus de angle_deg, exprimé en degrés
    '''
    return cos(radians(angle_deg))

def sind(angle_deg:float) -> float:
    '''
    renvoie le sinus de angle_deg, exprimé en degrés
    '''
    return sin(radians(angle_deg))

def distance(lat1:float, lng1:float, lat2:float, lng2:float) -> float:
    '''
    renvoie la distance en km, entre deux points positionnés selon les coordonnées gps
    '''
    R = 6378
    return R*acos(sind(lat1)*sind(lat2) + cosd(lng1-lng2)*cosd(lat1)*cosd(lat2))
</code>

===== module glouton =====

Dans un module ''glouton.py'', écrivez une fonction ''shortest_path(cities)'' qui reçoit la liste des ville sélectionnées et renvoie une copie de cette liste mais dans un ordre différent.

Le nouvel ordre correspond au plus court chemin, commençant par la première ville et en passant par toutes les autres exactement une fois.

On sait que l'algorithme glouton ne renvoie pas forcément le meilleur chemin. On se contente toutefois du meilleur trouvé par l'algorithme glouton.

===== démonstration =====

Pour illustrer le résultat, je vous propose le script de démonstration :

<code python>
# demo.py
from glouton import shortest_path
import matplotlib.pyplot as plt
import random
from data import cities

random.seed(452)
N = 100
selected_cities = [random.choice(cities) for i in range(N)]
path = shortest_path(selected_cities)

# la France est en gros à 45° de latitude, c'est pourquoi on doit
# multiplier les longitudes par cos(45°) = 0.71

x_cities = [city["lng"]*.71 for city in selected_cities]
y_cities = [city["lat"]     for city in selected_cities]
plt.scatter(x_cities, y_cities)

x_values = [city["lng"]*.71 for city in path ]
y_values = [city["lat"] for city in path ]
plt.plot(x_values, y_values)
plt.show()
</code>

<WRAP tip>
''random.choice'' permet de sélectionner des villes au hasard. Mais si on se contente de cela, à chaque test, la liste de villes sélectionnées sera différente à chaque exécution ce qui n'est pas pratique. Avec ''random.seed(452)'', on « cale » le générateur aléatoire dans un certain état et les nombres aléatoires produits seront toujours les mêmes. On aurait pu mettre n'importe quoi d'autre que ''452'', j'ai seulement constaté que cela donnait  une bonne liste.
</WRAP>