Computation in Python

• Implement
  
  • traveling_salesman
    

    import sys
    
    import numpy as np
    import scipy as sp
    

    None
    

  • traveling_salesman.read_instance
    

    def read_instance(file_name):
    
        # Count the cities.
        count = None
        with open(file_name) as file:
            count = int(file.readline())
    
        # Load the city identifiers and coordinates.
        instance = np.loadtxt(
            file_name, dtype=int, comments=None, skiprows=1, max_rows=count
        )
    
        # TODO Validate the result.
    
        return instance
    

    None
    

  • traveling_salesman.distances
    

    def distances(instance):
    
        coordinates = instance[:, 1:]
    
        # Measure the Euclidean distances between all cities.
        distances = sp.spatial.distance_matrix(coordinates, coordinates)
    
        # Round the distances and convert them to integers.
        integral_distances = np.rint(distances).astype(int)
    
        return integral_distances
    

  • traveling_salesman.distance
    

    def distance(tour, distances):
    
        destinations = np.roll(tour, 1)
        distances_ = distances[tour, destinations]
        distance = np.sum(distances_)
    
        return distance
    

  • traveling_salesman.tour_random
    

    def tour_random(instance, distances, random):
        """Return indices for a random tour, and its distance"""
    
        tour = np.arange(len(instance))
    
        random.shuffle(tour)
    
        distance1 = distance(tour, distances)
    
        return tour, distance1
    

  • traveling_salesman.solution
    

    def solution(tour, instance):
        """Convert tour indices to city identifiers."""
    
        cities = instance[:, 0]
        solution = cities[tour]
    
        return solution
    

  • traveling_salesman.tour
    

    def tour(solution, instance):
        """Convert a solution into a tour."""
    
        cities = instance[:, 0]
    
        a = np.array([10,20,30])
    
        # solution = cities[tour]
    
        return solution
    

• Use traveling_salesman.tour_random
  

  import numpy as np
  import traveling_salesman as ts
  
  instance = ts.read_instance('pr76.tsp')
  distances = ts.distances(instance)
  random = np.random.default_rng(0)
  tour, distance = ts.tour_random(instance, distances, random)
  solution = ts.solution(tour, instance)
  
  return f"Solution: \n {solution}" "\n\n" f"Distance: {distance:.2E}"
  

  Solution:
   [ 6 65 62 17 59 40 36 72 46  9 48 31 73 63  5 71 44 20 21 51 28 43 24 35
   11 54  3 75 61 76 14 12 18 53 29 37 19 45  4  2 67 25 22  1  7 23 27 38
   74 66 56 41 13 16 50 33 26 47 15 10 39 68 58 52 32 69 49  8 64 70 60 55
   30 42 57 34]
  
  Distance: 5.43E+05
  

• Use traveling_salesman.tour_nearest_neighbor
  

  import traveling_salesman as ts
  
  instance = ts.read_instance('pr76.tsp')
  distances = ts.distances(instance)
  tour, distance = ts.tour_nearest_neighbor(instance, distances)
  solution = ts.solution(tour, instance)
  
  return f"Solution: \n {solution}" "\n\n" f"Distance: {distance:.2E}"
  

  Solution:
   [65 66 51 52 53 54 42 43 28 29 30 31 19 20  5  6  7  8  9 10 11 12 13 14
   15 16 17 18 37 36 35 34 40 41 60 59 58 57 63 64 62 61 55 56 50 49 48 44
   45 46 24 25 21 22 23  1  2  3  4 26 27 33 32 38 39 72 73 71 67 68 69 47
   70 76 75 74]
  
  Distance: 1.57E+05