# ################################################################### # # Program: tsp_glouton.py # Author: Jean-Michel Richer # Organisation: Computer Science Department, # University of Angers, # France # Email: jean-michel.richer@univ-angers.fr # Creation date: April, 2021 #  Modification: April, 2021 # # ################################################################### # # Aim: # # This program is an implementation of a greedy search algorithm # used to find a solution to the travelling salesman problem. # At each step we choose the nearest city. # # # Objectif : # # Ce programme repose sur l'utilisation d'un algorithme glouton # afin de résoudre le problème du voyageur de commerce. # A chaque étape nous choisissons la ville la plus proche de # la ville actuelle. # # ################################################################### # # License # # This program is a free software you can modifiy it and # redistribute it for non profitable use. # # ################################################################### """ Les données de ce problème sont issues du site suivant : https://developers.google.com/optimization/routing/tsp#c++ """ import sys import numpy as np # =================================================================== # Les données en entrée sont les suivantes : # - une liste des villes sous forme de liste de chaines de caractères # - les distances entre les villes sous forme d'une matrice d'entiers # (en l'occurrence il s'agit d'une liste de liste d'entiers) # =================================================================== villes = [ "1. New York, NY", "2. Los Angeles, CA", "3. Chicago, IL", "4. Minneapolis, MN", "5. Denver, CO", "6. Dallas, TX", "7. Seattle, WA", "8. Boston, MA", "9. San Francisco, CA", "10. St. Louis, MI", "11. Houston, TX", "12. Phoenix, AZ", "13. Salt Lake City, UT" ] distances = [ [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972], [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579], [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260], [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987], [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371], [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999], [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701], [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099], [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600], [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162], [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200], [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504], [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0] ] # =================================================================== # On définit une class TSP pour stocker et manipuler les données # et résoudre le problème # =================================================================== class TSP(object): """ This is the main class used to solve the problem """ # ----------------------------------------------------- # Le constructeur modifie les données de manière à # utiliser des indices qui commencent à 1 et non à 0 # # On modifie la matrice des distances en ajoutant une # ligne et une colonne de zéros, puis on convertit tous # les 0 en une distance égale à la valeur maximum trouvée # dans la matrice + 1, ce qui permettra de rechercher une # distance minimum sans obtenir de zéro # ----------------------------------------------------- def __init__( self, villes, distances ): """ Constructor Parameters ---------- villes : list of string list of cities names distances : list of list of int matrix of distances between cities """ self.nbr_villes = len(villes) self.villes = villes.copy() self.villes.insert(0, "-------") self.distances = np.array( distances ) # add column of 0 @@@...@@@ @@@...@@@ # add line of 0 @@@...@@@ @@@...@@@ # find maximum distance maximum = @@@...@@@ # replace all 0 distances by maximum + 1 @@@...@@@ print("---- Matrice des distances modifiée ----") print(self.distances) self.verbose = True # ----------------------------------------------------- # Méthode de résolution gloutonne qui consiste à partir # de la première ville (New York) et à se diriger à # chaque étape vers la ville pour laquelle la distance # est minimale # On retourne le chemine sous forme d'une liste et la # distance totale parcourue # ----------------------------------------------------- def resolution_gloutonne(self): """ Greedy search method: we start from the first city and at each step we choose the nearest city """ print("=" * 30) print("Recherche gloutonne") print("=" * 30) # on commence par la première ville ville_actuelle = 1 chemin = [ 1 ] # on crée une liste des villes non encore visitées villes_a_visiter = [ ville for ville in range(2, self.nbr_villes+1) ] # distance parcourue distance_parcourue = 0 etape = 1 # tant qu'on a pas visité toutes les villes while len(villes_a_visiter) != 0: if self.verbose: print("---- etape ", etape, "----") print("villes_a_visiter=", villes_a_visiter) # trouver la ville dont la distance à la ville actuelle # est minimale. Initialement il s'agit de la ville 0 # inexistante et de distance égale à la distance maximum # plus un distance_minimale = self.distances[0][0] ville_la_plus_proche = 0 @@@...@@@ @@@...@@@ @@@...@@@ # supprimer la ville la plus proche des villes à visiter villes_a_visiter.remove( ville_la_plus_proche ) # ajouter la ville la plus proche au chemin chemin.append( ville_la_plus_proche ) # mettre à jour la distance distance_parcourue += distance_minimale # la ville actuelle devient la ville la plus proche ville_actuelle = ville_la_plus_proche if self.verbose: print("ville la plus proche=", self.villes[ ville_la_plus_proche ]) print("distance minimale =", distance_minimale) print("distance totale =", distance_parcourue) etape += 1 # ne pas oublier d'ajouter la distance de la dernière ville # à la première ville pour revenir sur la première ville distance_parcourue += self.distances[ ville_actuelle ][ 1 ] if self.verbose: print("---- etape ", etape, "----") print("retour ville départ =", self.villes[ 1 ]) print("distance minimale =", self.distances[ ville_actuelle ][ 1 ]) print("distance totale =", distance_parcourue) return chemin, distance_parcourue # ----------------------------------------------------- # Affichage du chemin et des distances parcourues # ----------------------------------------------------- def print(self, chemin): """ Display path and distances """ print() print("chemin=",chemin) print() print("------------------------------------------") print(" ville | dist. | totale") print("------------------------------------------") distance_totale = 0 print( "{0:25s} | {1:5d} | {2:5d}".format(self.villes[ chemin[0] ], 0, 0)) for ville in range(1, len(chemin)): distance = self.distances[ chemin[ville-1] ][ chemin[ville] ] distance_totale += distance print( "{0:25s} | {1:5d} | {2:5d}".format(self.villes[ chemin[ville] ], distance, distance_totale)) distance = self.distances[ chemin[ville] ][ chemin[0] ] distance_totale += distance print( "{0:25s} | {1:5d} | {2:5d}".format(self.villes[ chemin[0] ], distance, distance_totale)) print() # =================================================================== # Programme principal # =================================================================== HELP_MESSAGE = """ Program arguments are: -h or --help to get this message -q or --quiet to remove verbose mode and avoid to display graphics """ # créer une instance du problème tsp = TSP( villes, distances ) # gestion des arguments du programme if len(sys.argv) >= 1: try: for i in range(1, len(sys.argv)): arg = sys.argv[i] if arg == "-h" or arg == "--help": print( HELP_MESSAGE ) elif arg == "-q" or arg == "--quiet": tsp.verbose = False else: raise ValueError("Unexpected argument") except: print("="*40) print(sys.exc_info()[1]) print("="*40) print( HELP_MESSAGE ) sys.exit(1) # obtenir le résultat après résolution gloutonne chemin, distance = tsp.resolution_gloutonne() # affichage de la solution print("=" * 40) print("Solution") print("=" * 40) tsp.print(chemin)