One classic computation problem, the travelling salesman. Even if it’s quite simple to describe, it’s one of those hideous NP complete problems, the ones that are quite difficult to resolve, as the computation time needed grows greatly with the length of the data. On Programming Praxis they have proposed to resolve the problem using brute force, and using the closest neighbor (a simplification of the problem).

I’ve created this program, in Python.

import random import itertools import operator import datetime MAX_X = 100 MAX_Y = 100 def random_cities(number): ''' Generate a number of cities located on random places ''' cities = [ (random.randrange(0, MAX_X), random.randrange(0, MAX_Y)) for i in range(number) ] return cities def path_lenght(path): ''' Get the lenght of a path ''' lenght = 0 for i in xrange(len(path) - 1): # Add the distance between two cities lenght += abs(complex(path[i][0], path[i][1]) - complex(path[i + 1][0], path[i + 1][1])) return lenght def find_path_bruteforce(cities): ''' Find the smallest path using brute force ''' lenghts = [] for path in itertools.permutations(cities, len(cities)): # Get the length of the path, adding the returning point total_path = path + (path[0],) lenght = path_lenght(total_path) lenghts.append((total_path, lenght)) # Get minimum lenghts.sort(key=operator.itemgetter(1)) return lenghts[0] def find_path_nearest(cities): ''' Find the closest neibour ''' lenghts = [] for city in cities: lenght = 0 actual_cities = cities[:] actual_city = actual_cities.pop(actual_cities.index(city)) path = [actual_city, ] # Find nearest neibour while actual_cities: min_lenght = [] for next_city in actual_cities: min_lenght.append((next_city, abs(complex(city[0], city[1]) - complex(next_city[0], next_city[1])))) # Get closest neibor min_lenght.sort(key=operator.itemgetter(1)) actual_city = min_lenght[0][0] lenght += min_lenght[0][1] actual_cities.pop(actual_cities.index(actual_city)) path.append(actual_city) # Complete the trip with the first city path.append(city) lenghts.append((tuple(path), path_lenght(path))) # Get minimum lenghts.sort(key=operator.itemgetter(1)) return lenghts[0] if __name__ == '__main__': for i in range(3, 10): print 'Number of cities: ', i cities = random_cities(i) time1 = datetime.datetime.now() path2, lenght_neighbor = find_path_nearest(cities) time2 = datetime.datetime.now() print path2, lenght_neighbor time_neighbor = time2 - time1 print 'Time neighbor: ', time_neighbor time1 = datetime.datetime.now() path1, lenght_brute = find_path_bruteforce(cities) time2 = datetime.datetime.now() print path1, lenght_brute time_brute = time2 - time1 print 'Time brute force: ', time_brute print 'Diff: ', float(lenght_neighbor - lenght_brute) / lenght_brute * 100, '%'

The time spend on each is brutally different, specially as the number of cities grow. With more than 9 cities, the time grows at some point when my computer has to take more than minutes to compute the brute force approach, while the neighbor approach will still be below the 1/100 of a second. The error also grows, being the same on small number of cities, but getting afar fast when the number of cities grow. At 9 cities, the error is about a 20-30%