# ###################################################################
#
#       Program: tsp_recherche_locale.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 Local Search algorithm
#    used to find a solution to the travelling salesman problem. 
#    
#
#
# Objectif :
#
#    Ce programme repose sur l'implantation d'un algorithme de
#    Recherche Locale afin de résoudre le problème du voyageur 
#    de commerce.
#
# ###################################################################
#
# 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 random
import numpy as np
import matplotlib.pyplot as plt

# ===================================================================
# 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 un chemin (configuration) comme la liste des villes 
#	parcourues et le coût qui lui 	est associé
# ===================================================================
class Path(object):
	"""
	a Path is the list of cities visited and the distance travelled
	"""
	def __init__(self, chemin, distance):
		"""
    	Constructor
    	
    	Parameters
    	----------
    	chemin: list of int
    	  list of cities visited identified by their number
    	distance: int
    	  distance travelled (given by the 'f_objectif'
    	  function of class TSP)
		"""
		self.chemin = chemin
		self.distance = distance


	def __str__(self):
		return str(self.chemin) + ", " + str(self.distance)

    
	def copy(self):
		return type(self)(self.chemin.copy(), self.distance)
        
# ===================================================================
#	On définit une class TSP pour stocker et manipuler les données
#	et résoudre le problème
#	
# ===================================================================
class TSP(object):
	"""
	Class used to solve the problem that implements a Local Search
	algorithm
	"""
	
	# -----------------------------------------------------
	# 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
		self.graphics = False

	
	# -----------------------------------------------------
	# Définition de la fonction objectif
	# -----------------------------------------------------
	def f_objectif( self, chemin ):
		"""
		Compute the total distance of a path
		"""	
		
		distance_parcourue = 0
		@@@...@@@
		@@@...@@@
		@@@...@@@
		return distance_parcourue  
    
    
	# -----------------------------------------------------
	# Trouve les voisins améliorants à partir d'une
	# configuration
	# -----------------------------------------------------	
	def voisinage( self, configuration ):
		"""
		Neighborhood function that generates paths in the
		neighborhood of the current path
		
		Parameters
		----------
		configuration : path
		   current path
		"""
		
		# liste des voisins améliorants
		l = [ ]
		
		distance_a_ameliorer = configuration.distance 
		
		for i in range( 1, self.nbr_villes-2):
		    for k in range( i+1, self.nbr_villes):
		        if i > self.nbr_villes or k > self.nbr_villes:
		            continue
		        
		       @@@...@@@
		        
		        if nouvelle_configuration.distance < distance_a_ameliorer:
		            l.append( nouvelle_configuration )
		        
		# trier les configuration par ordre croissant de la distance        
		@@@...@@@
     
		return l
    
	# -----------------------------------------------------
	# Méthode de résolution basée sur la recherche locale
	# -----------------------------------------------------
	def resolution_recherche_locale(self):
		"""
		Local search
		"""	
		
		# enregistre l'évolution de la distance au cours du temps
		# en fonction du nombre d'itérations
		self.liste_evolution_courante = []
		
		#
		# Génération de la configuration initiale
		#
		
		villes_dans_le_desordre = [ x for x in range(1, self.nbr_villes+1 ) ]
		random.shuffle( villes_dans_le_desordre )
		configuration_courante = Path( villes_dans_le_desordre, self. f_objectif( villes_dans_le_desordre ) )

		# création de la configuration courante
		self.liste_evolution_courante.append( configuration_courante.distance )
		
		print("Configuration initiale=", configuration_courante)
		
		iteration = 1
		
		while True:
			
			liste_voisins_ameliorants = self.voisinage( configuration_courante )
			
			# pas de voisin améliorant, on arrête la recherche
			if len(liste_voisins_ameliorants) == 0:
				break
			
			# choix du meilleur voisin améliorant
			configuration_courante = liste_voisins_ameliorants[ 0 ]
			
			if self.verbose:
				print("=> ", iteration, ": voisins améliorants=", len(liste_voisins_ameliorants), "configuration=",configuration_courante)
				
			iteration += 1
			
			self.liste_evolution_courante.append( configuration_courante.distance )
				
		return configuration_courante
	
	# -----------------------------------------------------
	# Affichage du chemin ainsi que des distances 
	# parcourues et de la distance totale
	# -----------------------------------------------------			
	def print(self, chemin):
		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()

	# -----------------------------------------------------
	# Affiche un graphique de l'évolution du score 
	# (distance) de la configuration courante
	# -----------------------------------------------------
	def graphique(self):
		if not self.verbose:
			return 
			
		x = range( len( self.liste_evolution_courante ) )
		plt.plot( x, self.liste_evolution_courante, label='configuration courante' )
		plt.xlabel('itérations')
		plt.title('Evolution de la recherche locale')
		plt.legend()
		plt.show()

			
# ===================================================================
# 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
	
"""

# creer 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)
		
# start local search
configuration_finale = tsp.resolution_recherche_locale()

tsp.print(configuration_finale.chemin)
tsp.graphique()

#
# Trace de l'obtention de l'optimum
#
#Configuration initiale= [4, 12, 10, 9, 8, 3, 11, 13, 2, 1, 5, 6, 7], 18386
#=>  1 : voisins améliorants= 43 configuration= [4, 12, 10, 1, 8, 3, 11, 13, 2, 9, 5, 6, 7], 12301
#=>  2 : voisins améliorants= 19 configuration= [4, 6, 10, 1, 8, 3, 11, 13, 2, 9, 5, 12, 7], 10514
#=>  3 : voisins améliorants= 14 configuration= [4, 6, 10, 1, 8, 3, 11, 12, 2, 9, 5, 13, 7], 9481
#=>  4 : voisins améliorants= 5 configuration= [4, 6, 10, 1, 8, 3, 11, 12, 2, 9, 7, 13, 5], 8515
#=>  5 : voisins améliorants= 3 configuration= [4, 3, 10, 1, 8, 6, 11, 12, 2, 9, 7, 13, 5], 7708
#=>  6 : voisins améliorants= 4 configuration= [4, 3, 8, 1, 10, 6, 11, 12, 2, 9, 7, 13, 5], 7293