Le problème du voyageur de commerce, et une résolution par recuit simulé

Dans ce sujet, on étudie le problème du voyageur de commerce qui doit visiter toutes les capitales des états des États-Unis.

Il est difficile d'envisager une méthode exhaustive pour déterminer quel est le circuit le plus court, et on utilise une méthode approchée mais efficace : le recuit simulé.

Fichiers

• recuit.py
• capitales_etats.csv

Le problème du voyageur de commerce

Le début du fichier recuit.py commence en gros par les lignes suivantes, qui chargent un fichier csv et en affiche les lignes:

import csv

with open('capitales_etats.csv', 'r') as csvfile:
    csvfile = csv.reader(csvfile, delimiter='\t')
    for line in csvfile:
        print(line)

Question 1 Modifier cette partie du code pour remplir une liste capitales dont le contenu est le suivant (attention aux types des données obtenues) :

>>> capitales
[['Alabama', 'Montgomery', 32.3617, -86.2792],
 ['Arizona', 'Phoenix', 33.45, -112.067],
 ['Arkansas', 'Little Rock', 34.7361, -92.3311],
 ['California', 'Sacramento', 38.5556, -121.469],
 ...
 ['Wisconsin', 'Madison', 43.0667, -89.4],
 ['Wyoming', 'Cheyenne', 41.1456, -104.802]]

On retirera les capitales de l'Alaska et d'Hawaii pour se concentrer sur le « mainland. »

La distance de deux points à la surface d'une sphère de rayon ${`R`}$ et repérés par leurs latitudes ${`\\varphi_i`}$ et longitudes ${`\\psi_i`}$ est donnée par la formule suivante :

Question 2 Écrire une fonction dist(lat1, lng1, lat2, lng2) qui calcule la distance entre deux points à la surface de la Terre, repérés par leurs latitutes et longitudes. On considérera que la Terre est assimilée à une sphère parfaite de rayon 6370,7 kilomètres.

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

Question Écrire une fonction distance_circuit(l) qui prends en entrée une liste du même format que capitales et qui renvoie la distance totale parcourue en visitant les villes dans l'ordre spécifié par la liste, et en revenant au point de départ.

La distance du circuit correspondant au parcours des capitales dans l'ordre donné par le fichier est de 80257 kilomètres.

Le problème du voyageur de commerce est de déterminer le circuit qui permet de visiter toutes les villes d'une liste (ici, celle de la liste capitales) en revenant au point de départ, tout en minimisant la distance parcourue.

Nous allons tenter de résoudre ce problème pour visiter toutes les capitales du mainland des États-Unis d'Amérique.

Question — Un problème d'ordre de grandeur

1. Justifier qu'il y a ${`47!`}$ circuits possibles.
2. À l'aide d'un petit programme python, donner une estimation de ce nombre.
3. Si un ordinateur teste un milliard de circuits par seconde, combien de milliards d'années faudra-t-il pour tester tous les circuits ?

La question précédente montre qu'il est inenvisageable de tester tous les circuits possibles. Nous allons donc, plutôt que de trouver l'itinéraire optimal (que l'on n'aura pas tout de suite), tenter de déterminer raisonnablement rapidement un circuit raisonnablement court.

Optimisation locale

Une méthode pour obtenir un circuit raisonnable est la suivante : on tire au sort deux villes de la liste, et on regarde si en échangeant leurs places dans la liste, la longueur totale du circuit diminue. Si c'est le cas, on en conserve l'échange des deux villes.

Question Compléter la fonction echange(L, i, j) afin que :

• la fonction détermine si la longueur du circuit diminue en échangeant les villes numéro i et j ;
• si c'est le cas, l'échange est effectif et la fonction renvoie True ;
• sinon, le circuit n'est pas modifié et la fonction renvoie False.

Une fois cela fait, et après avoir rechargé le fichier, exécutez la commande simulation().

Cette méthode est assez facile à programmer, mais ne permet pas d'optimiser le circuit de façon totalement satisfaisante. La raison est qu'elle ne permet d'atteindre que le minimum local en « suivant la pente », même si on trouve un meilleur minimum local un peu plus loin.

Recuit simulé

Une manière d'améliorer cela est d'utiliser la méthode de « recuit simulé. » Le principe est le suivant : on suppose que l'on a une température ${`T`}$, et pour chaque étape, comme précédemment, on tire au sort deux villes de la liste, et on regarde si l'échange des deux villes réduit la longueur totale du circuit. Cette fois,

• si la distance diminue, on effectue l'échange ;
• sinon, la distance totale du circuit augmente. Si l'on note ${`\\Delta L`}$ cette augmentation, alors on effectue l'échange avec une probabilité

Question Modifier la fonction echange pour implémenter la méthode du recuit simulé. La température T sera une variable globale, le début du code de la fonction devra donc commencer par l'instruction global T.

Question Pour contrôler la température, repérer et « décommenter » les parties du code correspondant à l'indicateur textuel text_temp, ainsi que les boutons bt100 et bt1000.