# Travelling salesman

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], path[i])
- complex(path[i + 1], path[i + 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,)
lenght = path_lenght(total_path)
lenghts.append((total_path, lenght))

# Get minimum
lenghts.sort(key=operator.itemgetter(1))
return lenghts

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, city)
- complex(next_city, next_city))))
# Get closest neibor
min_lenght.sort(key=operator.itemgetter(1))

actual_city = min_lenght
lenght += min_lenght
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

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%