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.

Nous utiliserons le fichier communes-departement-region.csv contenant des communes françaises.

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

# 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()

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

# 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))

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.

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

# 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()