.. _2020tsprst: ======================================= Algo - TSP - Traveling Salesman Problem ======================================= .. only:: html **Links:** :download:`notebook <2020_tsp.ipynb>`, :downloadlink:`html <2020_tsp2html.html>`, :download:`python <2020_tsp.py>`, :downloadlink:`slides <2020_tsp.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_home/2020_tsp.ipynb|*` `TSP `__, Traveling Salesman Problem ou Problème du Voyageur de Commerce est un problème classique. Il s’agit de trouver le plus court chemin passant par des villes en supposant qu’il existe une route entre chaque paire de villes. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: .. code:: ipython3 %matplotlib inline Enoncé ------ On part d’un ensemble de villes aléatoires. .. code:: ipython3 import numpy import matplotlib.pyplot as plt villes = numpy.random.rand(20, 2) plt.plot(villes[:, 0], villes[:, 1], 'b-o') plt.plot([villes[0, 0], villes[-1, 0]], [villes[0, 1], villes[-1, 1]], 'b-o'); .. image:: 2020_tsp_4_0.png Q1 : choisir une permutation aléatoire des villes et calculer la distance du chemin qui les relie dans cet ordre ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Q2 : tirer deux villes aléatoirement, les inverser, garder la permutation si elle améliore la distance ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Q3 : choisir deux villes aléatoirement, permuter une des deux moitiés… ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Q4 : tester toutes les permutations possibles… je plaisante… ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Choisir les deux villes les plus proches, les relier, recommencer, puis… vous trouverez bien quelque chose pour finir. Réponses -------- Q1 ~~ On redessine le parcours entre les villes. .. code:: ipython3 plt.plot(villes[:, 0], villes[:, 1], 'b-o') plt.plot([villes[0, 0], villes[-1, 0]], [villes[0, 1], villes[-1, 1]], 'b-o'); .. image:: 2020_tsp_15_0.png La première étape consiste à calculer la distance d’un chemin passant par toutes les villes. .. code:: ipython3 def distance_ville(v1, v2): return numpy.sum((v1 - v2) ** 2) ** 0.5 def distance_tour(villes, permutation): tour = distance_ville(villes[permutation[0]], villes[permutation[-1]]) for i in range(0, len(permutation) - 1): tour += distance_ville(villes[permutation[i]], villes[permutation[i + 1]]) return tour distance_tour(villes, list(range(villes.shape[0]))) .. parsed-literal:: 9.978361909201357 Ensuite, pour voir la solution, on insère le code qui permet de dessiner le chemin dans une fonction. .. code:: ipython3 def dessine_tour(villes, perm): fig, ax = plt.subplots(1, 1, figsize=(4, 4)) ax.plot(villes[perm, 0], villes[perm, 1], 'b-o') ax.plot([villes[perm[0], 0], villes[perm[-1], 0]], [villes[perm[0], 1], villes[perm[-1], 1]], 'b-o') ax.set_title("dist=%f" % distance_tour(villes, perm)) return ax perm = list(range(villes.shape[0])) dessine_tour(villes, perm); .. image:: 2020_tsp_19_0.png Q2 ~~ On rédige l’algorithme. .. code:: ipython3 def ameliore_tour(villes, perm=None): # On copie la permutation perm pour éviter de modifier celle # transmise à la fonction. Si la permutation est vide, # on lui affecte la permutation identique. perm = (perm.copy() if perm is not None else list(range(villes.shape[0]))) # On calcule la distance actuelle. dist_min = distance_tour(villes, perm) # Initialisation. cont = True nb_perm, nb_iter = 0, 0 # Tant que la distance n'est pas améliorée dans les dernières # len(perm) itérations. while cont or nb_iter < len(perm): nb_iter += 1 # On tire deux villes au hasard. a = numpy.random.randint(0, len(perm) - 2) b = numpy.random.randint(a + 1, len(perm) - 1) # On permute les villes. perm[a], perm[b] = perm[b], perm[a] # On calcule la nouvelle distance. dist = distance_tour(villes, perm) # Si elle est meilleure... if dist < dist_min: # On la garde. dist_min = dist cont = True nb_perm += 1 nb_iter = 0 else: # Sinon, on annule la modification. perm[a], perm[b] = perm[b], perm[a] cont = False return dist_min, nb_perm, perm dist, nb_perm, perm = ameliore_tour(villes) print("nb perm", nb_perm) dessine_tour(villes, perm); .. parsed-literal:: nb perm 10 .. image:: 2020_tsp_21_1.png C’est pas extraordinaire. Q3 ~~ Lorsque deux segments du chemin se croisent, il est possible de construire un autre chemin plus court en *retournant* une partie du chemin. .. code:: ipython3 def ameliore_tour_renversement(villes, perm=None): perm = (perm.copy() if perm is not None else list(range(villes.shape[0]))) dist_min = distance_tour(villes, perm) cont = True nb_perm, nb_iter = 0, 0 while cont or nb_iter < len(perm) ** 2: nb_iter += 1 # Une partie qui change. On fait une copie de la permutation. p0 = perm.copy() a = numpy.random.randint(0, len(perm) - 2) b = numpy.random.randint(a + 1, len(perm) - 1) # On retourne une partie de cette permutation. if a == 0: perm[0:b] = perm[b:0:-1] perm[b] = p0[0] else: perm[a:b+1] = perm[b:a-1:-1] # La suite est quasi-identique. dist = distance_tour(villes, perm) if dist < dist_min: dist_min = dist cont = True nb_perm += 1 nb_iter = 0 else: # On reprend la copie. C'est plus simple # que de faire le retournement inverse. perm = p0 cont = False return dist_min, nb_perm, perm dist, nb_perm, perm = ameliore_tour_renversement(villes) print("nb perm", nb_perm) dessine_tour(villes, perm); .. parsed-literal:: nb perm 25 .. image:: 2020_tsp_24_1.png Il n’y a plus de croisements, ce qui est l’effet recherché. Q4 ~~ On pourrait combiner ces deux fonctions pour améliorer l’algorithme qui resterait sans doute très long pour un grand nombre de villes. On pourrait initialiser l’algorithme avec une permutation moins aléatoire pour accélérer la convergence. Pour ce faire, on regroupe les deux villes les plus proches, puis de proche en proche… .. code:: ipython3 from scipy.spatial.distance import cdist def build_permutation(villes): pairs = cdist(villes, villes) max_dist = pairs.ravel().max() for i in range(villes.shape[0]): pairs[i, i] = max_dist arg = numpy.argmin(pairs, axis=1) arg_dist = [(pairs[i, arg[i]], i, arg[i]) for i in range(villes.shape[0])] mn = min(arg_dist) perm = list(mn[1:]) pairs[perm[0], :] = max_dist pairs[:, perm[0]] = max_dist while len(perm) < villes.shape[0]: last = perm[-1] arg = numpy.argmin(pairs[last:last+1]) perm.append(arg) pairs[perm[-2], :] = max_dist pairs[:, perm[-2]] = max_dist return perm perm = build_permutation(villes) dessine_tour(villes, perm); .. image:: 2020_tsp_27_0.png Pas si mal… Il reste un croisement. On applique la fonction de la question précédente. .. code:: ipython3 dist, nb_perm, perm = ameliore_tour_renversement(villes, perm) print("nb perm", nb_perm) dessine_tour(villes, perm); .. parsed-literal:: nb perm 3 .. image:: 2020_tsp_29_1.png Ce n’est pas nécessairement le meilleur chemin mais ça va plus vite.