Ballade américaine

Fichiers annexes

Création du graphe

Nous allons utiliser le graphe dont les sommets sont les états américains, deux états étant reliés par une arête si et seulement si ils sont limitrophes.

Le fichier etats.csv contient la liste des états des États-Unis classés par ordre alphabétique. Pour illustrer cela, exécutez les instructions suivantes :

import csv

with open('etats.csv', 'r') as csvfile:
    csvfile = csv.reader(csvfile, delimiter=';')
    for line in csvfile:
        print(line)

Question 1 Modifier cela pour obtenir une fonction liste_etats() qui retourne la liste remplie en listant le fichier etats.csv. On doit avoir, par exemple :

>>> etats = liste_etats()
>>> etats[49]
['WY', 'Wyoming', 'Cheyenne', '41.1456', '-104.802']

Comme les sommets du graphe vont correspondre aux états américain, on en déduit que notre graphe comporte 50 sommets, numérotés de 0 à 49.

On a donc une liste d'adjacence des états, numérotés de 0 à 49. Pour obtenir les arêtes, nous allons utiliser

from usa_adjacence import etats_adjacents

On a alors :

>>> etats_adjacents
[ [23, 41, 9, 8],
  [],
  [4, 27, 43, 30],
  [24, 41, 23, 17, 42, 35],
  ...
]

Ainsi, les états adjacents à l'état numéro 0 sont les états numéro 23, 41, 9 et 8.

Question 2 Quels sont les noms des états limitrophes du Minnesota ?

Question 3 Écrire une fonction matrice_adjacence() qui construit et retourne la matrice d'adjacence associée à etats_adjacents.

Création d'un graphe pondéré

Avec la liste etats que vous avez dû obtenir à partir du fichier etats.csv, on a par exemple :

>>> etats[0]
['AL', 'Alabama', 'Montgomery', '32.3617', '-86.2792']

En particulier, les composantes d'indice 3 et 4 (en comptant à partir de 0) correspondent à la latitude et la longitude de la capitale de chaque état. Ici, Montgomery, capitale de l'Alabama, a pour coordonnées ${`32.3617^\\circ`}$ Nord et ${`86.2792^\\circ`}$ Ouest.

Pour calculer la distance entre deux points du globe repérés par leurs latitudes ${`\\varphi_i`}$ et leurs longitudes ${`\\psi_i`}$ , on utilise la formule suivante, dite de distance orthodromique :

&#123;`d = R \\arccos\\bigl(\\sin(\\varphi_1) \\sin(\\varphi_2) + \\cos(\\varphi_1) \\cos(\\varphi_2) \\cos(\\psi_2 - \\psi_1)\\bigr)`&#125;

où ${`R`}$ désigne le rayon de la Terre. Pour simplifier, on suppose que la Terre est une sphère parfaite de rayon ${`6370,7`}$ kilomètres. On pourra remarquer que les latitudes et longitudes sont exprimés en degrés.

Question 4 Écrire une fonction distance(lat1, lng1, lat2, lng2) qui calcule la distance à la surface de la Terre entre deux points repérés par leurs latitudes et longitudes.

À titre indicatif, Austin (capitale du Texas) et Denver (capitale du Colorado) sont distantes d'environ 1240 kilomètres.

Question 5 Écrire une fonction matrice_ponderee() qui construit et retourne la représentation sous forme de matrice d'adjacence du graphe des états limitrophes pondéré par les distances entre capitales.

Distance minimale entre deux capitales d'états

Questin 6 Compléter l'algorithme de Dijkstra (voir à la fin).

On pourra tester l'algorithme, en vérifiant par exemple que dans le graphe, la distance minimale entre Altanta et Sacramento est approximativement de 3455 kilomètres.

def dijkstra(graphe, source):
    # initialisation
    taille = len(graphe)
    front = ...
    d = ...
    while len(front) > 0:
        # tant qu'il y a des sommets à visiter
        # 1. on détermine, dans le front,
        #    le sommet le plus proche de la source
        ...
        # 2. on retire sommet du front
        ...
        # 3. on visite les voisins de sommet
        for s in range(taille):
            if graphe[sommet][s] != inf:
                # si s est un voisin de sommet
                if ...:
                    # on découvre s
                    ...
                else:
                    ...
    # on a fini quand le front est vide
    return d

Notes d'implémentation

Le graphe pondéré est représenté par une matrice d'adjacence graphe. En particulier, deux sommets i et j sont voisins si la distance entre les deux est finie, c'est-à-dire si graphe[i][j] != inf.
Les distances d'un sommet à la source sont stockés dans une liste d. À l'initialisation, toutes ces distances sont à inf sauf la source qui est à une distance 0 d'elle-même.
La liste front contient les sommets à traîter. À l'initialisation, seule la source est à traîter.
Les sommets non encore découverts sont ceux pour lesquels on ne connaît pas de chemin jusqu'à la source. Autrement dit, ce sont ceux dont la distance à la source est infinie.

Chemins minimisant les distances

On souhaite modifier la fonction implémentant l'algorithme de Dijkstra en ajoutant un tableau e (pour étape) qui indique dans quelle direction partir pour rejoindre la source.

Ainsi, lors de la détermination des plus courts chemins vers la capitale de l'Alabama, si à la fin de l'algorithme, on obtient

>>> e[15]
24

Cela signifier que pour rejoindre la capitale de l'Alabama, en partant de Topeka (capitale du Kansas, numéro 15), il faut d'abord rejoindre Jefferson City (capitale du Missouri, numéro 24).

Question 7 Et une fois à Jefferson City, où faut-il aller ensuite ?

On pourra initialiser le tableau e de telle sorte que pour tout i, e[i] soit égal à i.

Question 8 Lors de l'exécution de l'algorithme, à chaque diminution de la distance jusqu'à la source (à partir, éventuellement, d'une distance infinie si l'on découvre un sommet), comment modifier e ?

Question 9 Modifier la fonction dijkstra pour prendre en compte le tableau e. Elle devra en particulier retourner deux tableaux : celui d des distances et celui e des étapes.

Question 10

À partir du tableau e obtenu à l'aide de la fonction dijkstra modifiée, écrire une fonction itineraire(e, depart) qui, étant donné le tableau e et le numéro de l'état de départ, retourne la liste des numéros états à traverser pour rejoindre la source. Si c'est impossible, on renverra la liste vide.
On peut modifier cet fonction pour renvoyer une liste de chaînes de caractères indiquant la capitale d'état et l'état correspondant.

Avec Sacramento (CA) comme source, on veut par exemple :

>>> itineraire(e, 9)
[ 'Atlanta (GA)',
  'Nashville (TN)',
  'Jefferson City (MO)',
  'Topeka (KS)',
  'Denver (CO)',
  'Salt Lake City (UT)',
  'Carson City (NV)',
  'Sacramento (CA)'
]

Question 11 (Bonus) Une fois la gestion des itinaires implémentée, on pourra visualiser l'évolution du graphe en construction en ajoutant l'instruction

affiche_etapes(e)

dans la boucle de la fonction dijkstra, après avoir importé la fonction du module usa_affichage.