Traveling Salesman: Nearest Neighbor

March 16, 2010

We represent a point as a three-slot vector with the point number (on the range 0 to n-1) in slot 0, x-coordinate in slot 1, and y-coordinate in slot 2. Here are convenience functions:

(define (n p) (vector-ref p 0))
(define (x p) (vector-ref p 1))
(define (y p) (vector-ref p 2))

A traveling salesman problem is a list of points. We make a problem with make-tsp:

(define (make-tsp n)
  (define n10 (* n 10))
  (let loop ((n (- n 1)) (ps '()))
    (if (negative? n) ps
      (let ((p (vector n (randint n10) (randint n10))))
        (if (member p ps) (loop n ps)
          (loop (- n 1) (cons p ps)))))))

We compute distances as they are used, caching them in a global variable dists, which is a two-dimensional matrix initialized in the main solving program. We store the distance twice, in both directions, because the space cost is very little (we allocate the entire matrix), and it saves us the trouble of figuring out a canonical direction:

(define dists #f)

(define (dist a b)
  (define (square x) (* x x))
  (when (negative? (matrix-ref dists (n a) (n b)))
    (let ((d (sqrt (+ (square (- (x a) (x b)))
                      (square (- (y a) (y b)))))))
      (matrix-set! dists (n a) (n b) d)
      (matrix-set! dists (n b) (n a) d)))
  (matrix-ref dists (n a) (n b)))

Given a point p and a list of unvisited points ps, function nearest finds the nearest unvisited point:

(define (nearest p ps)
  (let loop ((ps ps) (min-p #f) (min-d #f))
    (cond ((null? ps) min-p)
          ((or (not min-d) (< (dist p (car ps)) min-d))
            (loop (cdr ps) (car ps) (dist p (car ps))))
          (else (loop (cdr ps) min-p min-d)))))

We are ready for the solver. Tsp initializes the dists matrix, then enters a loop in which it tracks both the current tour and the list of unvisited points; at each step of the loop, it calculates the nearest neighbor, adds that point to the current tour and removes it from the list of unvisited points, and loops, stopping when the tour is complete. The initial point is always the first point in the input:

(define (tsp ps)
  (let ((len (length ps)))
    (set! dists (make-matrix len len -1)))
  (let loop ((tour (list (car ps))) (unvisited (cdr ps)))
    (if (null? unvisited) tour
      (let ((next (nearest (car tour) unvisited)))
        (loop (cons next tour) (remove next unvisited))))))

Here we compute the cost of the tour:

(define (cost tour)
  (if (or (null? tour) (null? (cdr tour))) 0
    (let ((start (car tour)))
      (let loop ((tour tour) (sum 0))
        (if (null? (cdr tour))
            (+ sum (dist (car tour) start))
            (loop (cdr tour) (+ sum (dist (car tour) (cadr tour)))))))))

We use remove, make-matrix, matrix-set!, matrix-ref, rand and randint from the Standard Prelude. You can run the program, complete with an example, at

About these ads

Pages: 1 2

6 Responses to “Traveling Salesman: Nearest Neighbor”

  1. Remco Niemeijer said

    My Haskell solution (see for a version with comments):

    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

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

    actual_city = min_lenght[0][0]
    lenght += min_lenght[0][1]

    # Complete the trip with the first city

    lenghts.append((tuple(path), path_lenght(path)))

    # Get minimum
    return lenghts[0]

    if __name__ == ‘__main__’:
    for i in range(3, 10):
    print ‘Number of cities: ‘, i
    cities = random_cities(i)

    time1 =
    path2, lenght_neighbor = find_path_nearest(cities)
    time2 =
    print path2, lenght_neighbor
    time_neighbor = time2 – time1
    print ‘Time neighbor: ‘, time_neighbor

    time1 =
    path1, lenght_brute = find_path_bruteforce(cities)
    time2 =
    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):
        '''total cost to travel the path and return to starting city.'''
        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))
        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[0]=brute_force({0})".format(cities),
                      setup=setup, number=1)
        c_bf = path_cost(out[0])
        t_nn = timeit(stmt="out[0]=nearest_neighbor({0})".format(cities),
                      setup=setup, number=1)
        c_nn = path_cost(out[0])
        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}%
  6. mary said


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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: