## Traveling Salesman: Nearest Neighbor

### March 16, 2010

We saw in the previous exercise that finding an exact solution for the traveling salesman problem is extremely time consuming, taking time *O*(*n*!). The alternative is a heuristic that delivers a reasonably good solution quickly. One such heuristic is the “nearest neighbor:” pick a starting point, then at each step pick the nearest unvisited point, add it to the current tour and mark it visited, repeating until there are no unvisited points.

Your task is to write a program that solves the traveling salesman problem using the nearest neighbor heuristic. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/16/programming-praxis-traveling-salesman-nearest-neighbor/ for a version with comments):

[...] Praxis – Traveling Salesman: Nearest Neighbor By Remco Niemeijer In today’s Programming Praxis exercise we have to implement a significantly faster algorithm for the traveling [...]

[...] data. On Programming Praxis they have proposed to resolve the problem using brute force, and using the closest neighbor (a simplification of the [...]

A solution in Python, including comparison with brute force. Comments on my blog on http://wrongsideofmemphis.wordpress.com/2010/03/16/travelling-salesman/

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, ‘%’

Another brute force and nearest neighbor implementation in python.

hello

The algorithm I would like the C languagei

Can you help me?