#! /usr/bin/env python3 # def tsp_greedy ( filename ): #*****************************************************************************80 # ## tsp_greedy() seeks an optimal traveling salesperson path by the greedy method. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 06 March 2022 # # Author: # # John Burkardt # # Input: # # string FILENAME, the name of the file containing the distance # matrix information. This is an optional input. If it is not provided, # the program will prompt for it. # import numpy as np import platform print ( '' ) print ( 'tsp_greedy():' ) print ( ' Python version: %s' % ( platform.python_version ( ) ) ) print ( ' For the traveling salesperson problem, find a "greedy"' ) print ( ' solution by choosing a starting city, and then constructing' ) print ( ' the tour by always moving to the nearest unvisited city.' ) # # Get the distance table. # distance = np.loadtxt ( filename ) # # Approve the distance table. # dims = distance.shape m = dims[0] n = dims[1] if ( m != n ): print ( '' ) print ( 'tsp_greedy(): Fatal error!' ) print ( ' The MxN distance matrix must be square.' ) print ( ' Your matrix has M = %d, N = %d', m, n ) raise Exception ( 'tsp_greedy(): Fatal error!' ) v = np.diagonal ( distance ) test = np.linalg.norm ( v ) if ( 0.0 < test ): print ( '' ) print ( 'tsp_greedy(): Fatal error!' ) print ( ' The distance matrix must have zero diagonal.' ) print ( ' Your matrix has ||diag(D)|| = %g', test ) raise Exception ( 'tsp_brute - Fatal error!' ) test = np.linalg.norm ( distance - distance.transpose ( ) ) if ( 0.0 < test ): print ( '' ) print ( 'tsp_greedy(): Fatal error!' ) print ( ' The distance matrix must be symmetric.' ) print ( ' Your matrix has ||D-D''|| = %g' % ( test ) ) raise Exception ( 'tsp_brute - Fatal error!' ) # # Print the distance matrix. # print ( '' ) print ( ' The city-to-city distance matrix:' ) print ( '' ) for i in range ( 0, n ): for j in range ( 0, n ): print ( ' %4g' % ( distance[i,j] ), end = '' ) print ( '' ) # # Initialize the best cost and tour. # cost_best = np.inf p_best = np.arange ( n ) # # Let each city be the starting point. # for start in range ( 0, n ): p = path_greedy ( n, distance, start ) cost = path_cost ( n, distance, p ) if ( cost < cost_best ): p_best = p.copy() cost_best = cost print ( ' Greedy tour starting at city', start, ' costs ', cost ) # # Report. # print ( '' ) print ( ' The best itinerary found:' ) print ( '' ) print ( ' Step From To Distance' ) print ( '' ) for i1 in range ( 0, n ): i2 = ( ( i1 + 1 ) % n ) print ( ' %4d %2d %2d %14.6g' \ % ( i2, p_best[i1], p_best[i2], distance[p_best[i1],p_best[i2]] ) ) print ( ' ---- -- -- --------------' ) print ( ' Total: %14.6g' % ( cost_best ) ) # # Terminate. # print ( '' ) print ( 'tsp_greedy():' ) print ( ' Normal end of execution.' ) return def path_cost ( n, distance, p ): #*****************************************************************************80 # ## path_cost() evaluates the cost of a round trip. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 06 March 2022 # # Author: # # John Burkardt # # Input: # # integer N, the number of cities. # # real DISTANCE(N,N), the city to city distance table. # # integer P(N), a permutation of 1:N, the route. # # Output: # # real COST, the cost of the route. # cost = 0.0 i1 = n - 1 for i2 in range ( 0, n ): cost = cost + distance[p[i1],p[i2]] i1 = i2 return cost def path_greedy ( n, distance, start ): #*****************************************************************************80 # ## path_greedy() finds a greedy route for a given start. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 06 March 2022 # # Author: # # John Burkardt # # Input: # # integer N, the number of cities. # # real DISTANCE(N,N), the city to city distance table. # # integer START, the starting city. # # Output: # # integer P(N), a greedy route that starts at START. # import numpy as np p = np.zeros ( n, dtype = np.int ) p[0] = start d = distance.copy ( ) d[:,start] = np.inf for i in range ( 0, n ): d[i,i] = np.inf c1 = start for j in range ( 1, n ): c2 = np.argmin ( d[c1,:] ) p[j] = c2 d[:,c2] = np.inf c1 = c2 return p def timestamp ( ): #*****************************************************************************80 # ## timestamp() prints the date as a timestamp. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 21 August 2019 # # Author: # # John Burkardt # import time t = time.time ( ) print ( time.ctime ( t ) ) return if ( __name__ == '__main__' ): timestamp ( ) tsp_greedy ( 'five.txt' ) tsp_greedy ( 'fifteen.txt' ) tsp_greedy ( 'seventeen.txt' ) tsp_greedy ( 'fortyeight.txt' ) timestamp ( )