All in a Single Night :

Optimisations testées

Temps de référence: 68 millisecondes sans optimisation.

1. Parcours que dans un sens (avec tri, méthode appliquée dans code.py)

   Ne pas parcourir tous les circuits dans les deux sens, puisque la longueur sera la même au retour.
   Pour cela, ne garder que les parcours qui finissent dans une ville qui vient après la ville de départ dans l'ordre alphabétique.
   

       for parcours in perm(villes):
           # parcourir les A -> ... -> B et pas les B -> ... -> A symétriques
           if parcours[0] < parcours[-1]:
               continue
                   

   
   Temps: 38 ms au lieu de 68 ms.
   Divise à peu près par deux le temps, car ce n'est pas la génération des parcours qui prend du temps, mais plus le calcul
   de la durée d'un parcours (tant qu'on utilise itertools.permutations, qui renvoie un générateur et non une liste !).

   ---

2. Parcours que dans un sens (avec génération des bons parcours uniquement)

   Ne pas parcourir tous les circuits dans les deux sens, puisque la longueur sera la même au retour.
   Pour cela, ne générer que les bons circuits, en parcourant intelligemment les paires de villes de départ/arrivée
   
   Remplacer l'appel de itertools.permutations(villes) par un appel à cette nouvelle fonction :
   

   def perm(t):
       for (start, end) in itertools.combinations(range(len(t)), 2):
           middle = t[:]
           endItem = middle.pop(end)
           startItem = middle.pop(start)
           for subperm in itertools.permutations(middle):
               yield (startItem,) + subperm + (endItem,)
                   

   
   
   Ou alternativement en faisant tout un peu plus à la main avec des for et sans les pop :
   

   def perm(t):
       for start in range(len(t) - 1):
           for end in range(start + 1, len(t)):
               middle = t[0:start] + t[start+1:end] + t[end+1:]
               for subperm in itertools.permutations(middle):
                   yield t[start:start+1] + list(subperm) + t[end:end+1]
                   

   
   Temps: 36 ms au lieu de 68 ms.
   Divise de nouveau à peu près par deux le temps.
   À peine meilleur que de tout générer les circuits et filtrer ensuite. Ce petit gain ne justifie pas qu'on se complique à faire ça.

   ---

3. Utiliser un tableau à deux dimensions plutôt qu'un dictionnaire

   Convertir les distances stockées dans le dictionnaire en un tableau à deux dimensions, chaque ville étant remplacée par un nombre de 0 à n :
   

       distancesVilles, villes = parse('input.txt')
       distances = []
       for villeFrom in villes:
           distancesVilles[villeFrom][villeFrom] = 0
           distances.append([distancesVilles[villeFrom][villeTo] for villeTo in villes])
                   

   
   Ou directement créer le tableau au lieu du dictionnaire :
   

   def parse(filename):                                            def parse(filename):
       f = open(filename, 'r')                                       f = open(filename, 'r')
       linesOrig = list(map(str.strip, f.readlines()))               linesOrig = list(map(str.strip, f.readlines()))
   
       distances = {}                                            |     distances = []
       villes = []                                                     villes = []
   
       for line in linesOrig:                                          for line in linesOrig:
           tokens = line.split(' ')                                        tokens = line.split(' ')
           cityFrom = tokens[0]                                            cityFrom = tokens[0]
           cityTo = tokens[2]                                              cityTo = tokens[2]
           dist = int(tokens[4])                                           dist = int(tokens[4])
           if not cityFrom in villes:                                      if not cityFrom in villes:
               villes.append(cityFrom)                                         villes.append(cityFrom)
               distances[cityFrom] = {}                          |             for distVille in distances:
                                                                 >                      distVille.append(0)
                                                                 >                  distances.append(len(villes) * [0])
           if not cityTo in villes:                                        if not cityTo in villes:
               villes.append(cityTo)                                           villes.append(cityTo)
               distances[cityTo] = {}                            |             for distVille in distances:
                                                                 >                      distVille.append(0)
                                                                 >                  distances.append(len(villes) * [0])
   
                                                                 |         iFrom = villes.index(cityFrom)
                                                                 |         iTo = villes.index(cityTo)
           distances[cityFrom][cityTo] = dist                    |         distances[iFrom][iTo] = dist
           distances[cityTo][cityFrom] = dist                    |         distances[iTo][iFrom] = dist
       return distances, villes                                        return distances, villes
   

   
   
   Dans les deux cas, on parcourt ensuite les indices plutôt que les villes :
   

   for parcours in perm(villes):                                 | for parcours in perm(range(len(villes))):
       d = calcDist(parcours, distances)                               d = calcDist(parcours, distances)
   

   
   
   Temps: 66 ms au lieu de 68 ms.
   Pas de gain de temps significatif.