## 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

### 6 Responses to “Traveling Salesman: Nearest Neighbor”

1. Remco Niemeijer said

```import Control.Monad
import Data.List
import qualified Data.List.Key as K
import System.Random

dist :: (Int, Int) -> (Int, Int) -> Float
dist (x1, y1) (x2, y2) = sqrt (f (x1 - x2) ** 2 + f (y1 - y2) ** 2)
where f = fromIntegral

cost :: [(Int, Int)] -> Float
cost xs = sum \$ zipWith dist xs (tail xs ++ xs)

randomPoints :: Int -> IO [(Int, Int)]
randomPoints n = f [] where
f ps = if length ps == n then return ps else
do p <- liftM2 (,) rnd rnd
if elem p ps then f ps else f (p:ps)
rnd = randomRIO (0, 10 * n)

nearTour :: [(Int, Int)] -> [(Integer, (Int, Int))]
nearTour = f . zip [0..] where
f [] = []
f [x] = [x]
f ((i,p):ps) = (i,p) : f (nxt : delete nxt ps) where
nxt = K.minimum (dist p . snd) ps
```
2. […] 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 […]

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

4. khelben said

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

5. Mike said

Another brute force and nearest neighbor implementation in python.

```from itertools import permutations
from random import randint
from timeit import timeit

#  complex numbers are used to represent cities because python has them built-in.
#  could easily be changed to 2-tuples by changing random_cities and leg_cost

def random_cities(n,max_x=100,max_y=100):
'''return set of n cities randomly placed on a max_x by max_y grid.'''

cities = set()
while len(cities) < n:

return cities

def leg_cost(city1,city2):
'''returns cost of travel from city1 to city2.'''

return abs(city1 - city2)

def path_cost(path):

return sum(leg_cost(path[n-1],path[n]) for n in range(len(path)))

def brute_force(cities):
'''finds shortest path by exhaustively checking all paths.'''

return min(permutations(cities), key=path_cost)

def nearest_neighbor(cities):
'''finds a path through the cities using a nearest neighbor heuristic.'''

unvisited = cities.copy()
visited = [unvisited.pop()]

while unvisited:
city = min(unvisited, key=lambda c: leg_cost(visited[-1],c))
visited.append(city)
unvisited.remove(city)

return visited

setup = "from __main__ import brute_force, nearest_neighbor, out"
out = [ None ]

for ncities in range(3,7):
cities = random_cities(ncities)

t_bf = timeit(stmt="out=brute_force({0})".format(cities),
setup=setup, number=1)
c_bf = path_cost(out)

t_nn = timeit(stmt="out=nearest_neighbor({0})".format(cities),
setup=setup, number=1)
c_nn = path_cost(out)

tdelta = 100*(t_nn - t_bf) / t_bf
cdelta = 100*(c_nn - c_bf) / c_bf

print """Number of cities: {ncities}
time       cost
brute_force     : {t_bf:8.1e}  {c_bf:8.2}
nearest_neighbor: {t_nn:8.1e}  {c_nn:8.2}
difference      : {tdelta:8.1f}% {cdelta:8.1f}%
""".format(**locals())

```
6. mary said

hello

The algorithm I would like the C languagei
Can you help me?